抑制孤立簇的软件模块化优化算法

doi:10.11772/j.issn.1001-9081.2017081940

计算机应用 ›› 2018, Vol. 38 ›› Issue (3): 791-798.DOI: 10.11772/j.issn.1001-9081.2017081940

抑制孤立簇的软件模块化优化算法

牟立峰, 王方媛

上海大学悉尼工商学院, 上海 201899

收稿日期:2017-08-07 修回日期:2017-09-05 出版日期:2018-03-10 发布日期:2018-03-07
通讯作者: 王方媛
作者简介:牟立峰(1978-),男,黑龙江牡丹江人,讲师,博士,主要研究方向:基于搜索的软件工程、进化算法设计;王方媛(1994-),女,山东即墨人,硕士研究生,主要研究方向:基于搜索的软件工程、进化算法设计。
基金资助:
国家自然科学基金资助项目（71302051）。

Software modularization optimization algorithm with eliminating isolated clusters

MU Lifeng, WANG Fangyuan

SHU-UTS SILC Business School, Shanghai University, Shanghai 201899, China

Received:2017-08-07 Revised:2017-09-05 Online:2018-03-10 Published:2018-03-07
Supported by:
This work is partially supported by the National Natural Science Foundation of China (71302051).

摘要/Abstract

摘要： 针对传统软件模块化指标在解决软件模块化问题时容易导致孤立簇的问题，提出改进型软件模块化指标IMQ作为进化算法的适应函数以有效抑制孤立簇现象，并以IMQ最大化为目标建立软件模块化的数学规划模型，设计符合问题特点的基于相似度竞争和选择机制的改进遗传算法（IGA）求解该模型。首先，运用边收缩方法的启发式策略生成高质量的初始解，并将其作为种子植入到初始种群中；然后，利用IGA对模型进行求解，在提升搜索效率的同时进一步提高解的质量；最后，运用真实数据和仿真数据进行对比实验。实验结果表明IMQ指标能有效减少孤立簇的数目，而IGA比传统的多点爬山算法（IHC）和基于分组编码（GNE）的遗传算法具有更强的寻优能力和鲁棒性。

关键词: 软件模块化, 软件聚类问题, 遗传算法, 启发式策略, 产品设计

Abstract: Considering the isolated cluster problem caused by traditional software modularization methods, a new metric named Improved Modularization Quality (IMQ) was proposed and used as the fitness function of an evolutionary algorithm to eliminate isolated clusters effectively. A mathematical programming model with the goal of maximizing IMQ was developed to represent software modularization problem. In addition, an Improved Genetic Algorithm (IGA) with competition and selection mechanism similarity was designed to solve this model. Firstly, a heuristic strategy based on edge contraction was used to generate high-quality solutions. Then the solutions were implanted as seeds into the initial population. At last, the proposed IGA was employed to further improve solution quality. Comparison experimental results prove that IMQ can effectively reduce the number of isolated clusters, and IGA has stronger robustness and ability of finding better solutions than Improved Hill Climbing Algorithm (IHC) and GA based on Group Number Encoding (GNE).

Key words: software modularization, software clustering problem, Genetic Algorithm (GA), heuristic strategy, product design

中图分类号:

TP311.5

牟立峰, 王方媛. 抑制孤立簇的软件模块化优化算法[J]. 计算机应用, 2018, 38(3): 791-798.

MU Lifeng, WANG Fangyuan. Software modularization optimization algorithm with eliminating isolated clusters[J]. Journal of Computer Applications, 2018, 38(3): 791-798.

参考文献

[1] HARMAN M. The current state and future of search based software engineering[C]//FOSE'07:Proceedings of the 2007 Future of Software Engineering. Washington, DC:IEEE Computer Society, 2007:342-357.
[2] KUMARI A C, SRINIVAS K. Hyper-heuristic approach for multi-objective software module clustering[J]. Journal of Systems and Software, 2016, 117:384-401.
[3] STEVENS W P, MYERS G J, CONSTANTINE L L. Structured design[J]. IBM Systems Journal, 1974, 13(2):115-139.
[4] HARRISON R, COUNSELL S J, NITHI R V, et al. An evaluation of the MOOD set of object-oriented software metrics[J]. IEEE Transactions on Software Engineering, 1998, 24(6):491-496.
[5] TUCKER A, SWIFT S, LIU X, et al. Variable grouping in multivariate time series via correlation[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2001, 31(2):235-245.
[6] MANCORIDIS S, MITCHELL B S, CHEN Y, et al. Bunch:a clustering tool for the recovery and maintenance of software system structures[C]//ICSM'99:Proceedings of the 1999 IEEE International Conference on Software Maintenance. Washington, DC:IEEE Computer Society, 1999:50-59.
[7] PRADITWONG K, HARMAN M, YAO X, et al. Software module clustering as a multi-objective search problem[J]. IEEE Transactions on Software Engineering, 2011, 37(2):264-282.
[8] MacQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley:University of California Press, 1967:281-297.
[9] HADI A S. Finding groups in data:an introduction to chster analysis[J]. Technometrics, 1992, 34(1):111-112.
[10] BANDYOPADHYAY S, MAULIK U. Genetic clustering for automatic evolution of clusters and application to image classification[J]. Pattern Recognition, 2002, 35(6):1197-1208.
[11] OMRAN M G H, SALMAN A, ENGELBRECHT A P. Dynamic clustering using particle swarm optimization with application in image segmentation[J]. Pattern Analysis & Applications, 2006, 8(4):332.
[12] MAQBOOL O, BABRI H. Hierarchical clustering for software architecture recovery[J]. IEEE Transactions on Software Engineering, 2007, 33(11):759-780.
[13] HARMAN M, HIERONS R M, PROCTOR M. A new representation and crossover operator for search-based optimization of software modularization[C]//GECCO'02:Proceedings of the Genetic and Evolutionary Computation Conference. San Francisco, CA:Morgan Kaufmann Publishers, 2002:1351-1358.
[14] MITCHELL B S, MANCORIDIS S. On the evaluation of the Bunch search-based software modularization algorithm[J]. Soft Computing, 2008, 12(1):77-93.
[15] MKAOUER W, KESSENTINI M, SHAOUT A, et al. Many-objective software remodularization using NSGA-Ⅲ[J]. ACM Transactions on Software Engineering & Methodology, 2015, 24(3):Article No. 17.
[16] AKBALIK A, HADJ-ALOUANE A B, SAUER N, et al. NP-hard and polynomial cases for the single-item lot sizing problem with batch ordering under capacity reservation contract[J]. European Journal of Operational Research, 2017, 257(2):483-493.
[17] 杨劼,高红,刘涛,等.基于改进遗传算法的泊位岸桥协调调度优化[J].计算机应用,2016,36(11):3136-3140. (YANG J, GAO H, LIU T, et al. Integrated berth and quay-crane scheduling based on improved genetic algorithm[J]. Journal of Computer Applications, 2016, 36(11):3136-3140.)
[18] 范青武,王普,高学金.一种基于有向交叉的遗传算法[J].控制与决策,2009,24(4):542-546. (FAN Q W, WANG P, GAO X J, et al. Improved genetic algorithm based on oriented crossover[J]. Control and Decision, 2009, 24(4):542-546.)
[19] ARCURI A. A practical guide for using statistical tests to assess randomized algorithms in software engineering[C]//ICSE'11:Proceedings of the 33rd International Conference on Software Engineering. New York:ACM, 2011:1-10.
[20] PRADITWONG K. Solving software module clustering problem by evolutionary algorithms[C]//JCSSE 2011:Proceedings of the Eighth International Joint Conference on Computer Science and Software Engineering. Piscataway, NJ:IEEE, 2011:154-159.

抑制孤立簇的软件模块化优化算法

Software modularization optimization algorithm with eliminating isolated clusters

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[4]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[5]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[6]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[7]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[8]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[9]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[10]	张阳, 王小宁. 基于Word2Vec词嵌入和高维生物基因选择遗传算法的文本特征选择方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3151-3155.
[11]	黄晓祥, 胡咏梅, 吴丹, 任力杰. 基于变分自编码器的异常颈动脉早期识别和预测[J]. 计算机应用, 2021, 41(10): 3082-3088.
[12]	杨华龙, 王美玉, 辛禹辰. 横向整合战略下异质车辆库存路径优化模型[J]. 计算机应用, 2021, 41(10): 3040-3048.
[13]	陈桢, 钟一文, 林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94.
[14]	王永航, 张天宇, 郑红星. 考虑恶劣天气的班轮多阶段重调度方法[J]. 计算机应用, 2021, 41(1): 286-294.
[15]	李华峰, 黄樟灿, 张蔷, 湛航, 谈庆. 求解需求可拆分车辆路径问题的改进的金字塔演化策略[J]. 计算机应用, 2021, 41(1): 300-306.