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

• 计算机软件技术 • 上一篇    下一篇

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

牟立峰, 王方媛   

  1. 上海大学 悉尼工商学院, 上海 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   

  1. 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).

摘要: 针对传统软件模块化指标在解决软件模块化问题时容易导致孤立簇的问题,提出改进型软件模块化指标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

中图分类号: