多目标群体进化软件模块聚类方法

摘要

本发明针对软件系统重构中的软件模块聚类问题，公开了多目标群体进化软件模块聚类方法。本方法首先对从软件系统的源程序中提取出方法依赖图，软件系统模块聚类方案用二维矩阵编码，使用模块质量和逆向边数作为软件模块聚类目标，进行群体进化操作迭代，更新帕累托非支配解集，最后输出聚类结果。本方法提供了一种有效的软件模块聚类方法，用于软件系统重构，提高软件系统的可理解性。

说明书

技术领域

本发明属于软件系统重构技术领域，主要涉及软件系统重构中的软件模块聚类问题，本发明提供了多目标群体进化软件模块聚类方法，主要用于解决软件系统代码重构时优化系统代码的结构，消除系统代码冗余，提高系统代码的可理解性，减少软件系统维护成本。

背景技术

软件作为信息产业的核心，软件服务于各行各业，时刻影响着国家的科技和国民经济的发展，随着软件所属行业业务的变化，为之服务的软件功能与系统结构也会发生相应的变化。因此，需要软件维护人员根据业务的变化对软件系统的功能和结构进行相应的调整。随着对软件结构的不断更改，软件系统结构愈加复杂，同时软件的规模会逐渐扩大，会导致软件系统结构的逐渐恶化，最终软件系统难以维护甚至废弃。当软件系统的结构发生退化时，软件的可维护性会受到严重影响。如何使软件系统变得易于理解、维护和管理是一个亟待解决的问题。

软件模块聚类是软件系统重构、恢复软件系统结构的有效手段，对软件模块进行聚类，能够很大程度提高软件系统的可理解性，降低软件的维护成本。目前常用的软件模块聚类方法主要是基于搜索的方法，传统方法没有考虑软件系统本身的特性或者只考虑某一单一规则，在解空间中盲目搜索，聚类效果一般，结果的多样性不足，不利于复杂软件系统进行软件模块聚类。

本发明将软件模块聚类描述为多目标搜索问题，基于多目标进化优化方法进行聚类，结合软件模块聚类问题的特殊性，以软件模块质量和逆向边数为依据，采用双目标概率更新聚类方案，从根本上保证了产生的聚类结果具有合理性和聚类结果的有效性。

发明内容

本方法解决的问题：软件模块聚类问题是一个经典的组合优化问题，直接使用传统基于搜索的优化方法无法有效的针对软件模块聚类问题自身的特点进行设计，容易使得搜索的结果不全面，缺少多样性，无法为软件维护人员提供多种决策选择。本发明基于群体搜索的思路，使用双目标概率更新聚类方案，克服现有的大多数方法仅仅考虑软件模块质量这个单一目标而导致的聚类结果缺少多样性，提出多目标群体进化软件模块聚类方法，为大规模软件模块聚类问题提供了一种较为简单且有效的方法，得到模块聚类帕累托非支配解集，可根据实际情况由决策者选取符合特定情况的最优解。

本发明的技术方案如图1所示包括以下的步骤：

步骤1：面向对象语言编写的软件系统中，构造方法依赖图表示软件系统中方法之间的调用关系：顶点代表代码中的方法，边代表方法之间的调用关系；使用矩阵表示方法依赖图：若系统有n个方法，用集合F＝{f

其中i和j都为1到n之间的任意整数值；

步骤2：编码；模块聚类是软件系统方法集合的一个划分，假设模块聚类数量为m，聚类结果可以用集合C＝{c

步骤3：构造软件模块聚类目标：软件模块质量MQ和逆向边数fit_derection，软件模块质量MQ：软件模块聚类后，第x个聚类和第y个聚类之间的耦合性用ε

第x个聚类的内聚性用μ

x,y分别表示第x个聚类和第y个聚类，其中x,y为1到m之间的任意一个整数值,F

模块聚类的逆向边数fit_derection：

其中V

步骤4：群体初始化，设定最大迭代次数r，初始化帕累托非支配解集为空，对群体每个个体代表的聚类方案确定模块聚类中心：根据软件系统的方法依赖图，计算每个顶点的度d

每个顶点以prob

步骤5：群体进化操作；对于个体w，首先计算其模块质量MQ和逆向边数fit_derection这两个聚类目标值，然后计算个体w中方法f

其中1≤g≤m，MQ

步骤6：更新帕累托非支配解集；根据每个个体的聚类目标值：软件模块质量MQ和逆向边数fit_derection，由个体间非支配关系更新帕累托非支配解集：如果当前个体被帕累托非支配解集中某个解支配，则当前个体不用加入帕累托非支配解集；如果当前个体支配了帕累托非支配解集中某个解，则删除帕累托非支配解集所有被支配的解，并把当前个体加入帕累托非支配解集；如果当前个体和帕累托非支配解集中所有解都不存在支配关系，则并把当前个体加入帕累托非支配解集；

步骤7：重复迭代进行步骤5和步骤6，若达到最大迭代次数r，则结束整个步骤，帕累托非支配解集中的个体对应的聚类方案就是本软件模块聚类结果，输出聚类结果，否则重复执行步骤5到步骤6的操作，直到达到最大迭代次数。

有益效果：

当前，处理软件模块聚类问题的方法有很多，常见的应用于解决软件模块聚类问题的方法有基于图理论的方法、基于数据挖掘的聚类方法和基于搜索的群体智能方法，但在解决大规模复杂软件系统时，传统的基于搜索的方法大多考虑一个目标，提供的可选择方案少，聚类效果有待提升。

软件模块聚类问题是一个组合优化问题，本发明提出了双目标概率群体进化方法，进化操作简单有效，为大规模复杂软件模块聚类问题提供了一种较为简单有效的多目标聚类方法，使得软件模块聚类的结果在达到高内聚，低耦合的软件开发准则的同时也能很好的符合逆向边数最小的原则，提高软件模块聚类的结果有效性性，改善了软件系统的可理解性和可维护性。

对真实的软件系统ispell进行软件模块聚类，该ispell软件系统有24个方法，聚类个数设置为4，群体规模分别取10、20、50、80、100、150，迭代次数为100次，其中横坐标表示软件模块质量MQ，纵坐标表示逆向边数，每个点表示一个帕累托非支配解，如图2所示，随着群体规模的增大，解集逐渐向坐标系右下方迁移，帕累托非支配解集在逐渐整体变优，说明了本方法的有效性。

附图说明

附图1本发明的流程图

附图2群体规模对ispell软件系统模块聚类的影响

附图3某软件系统的方法依赖图

附图4某软件系统的模块聚类结果图

具体实施方式

以某个软件系统为例，如图3所示是此软件系统的方法依赖图，具体说明本发明公开的软件模块聚类方法的实施方式。

步骤1：对如图2所示的方法调用关系用二维矩阵进行编码，此软件系统含有8个模块，这些方法表示为集合F＝{f

步骤2：对群体进行初始化，初始化帕累托非支配解集为空，设定多目标群体进化软件模块聚类方法的参数：群体规模，即群体中的个体数量N＝2，软件模块聚类的聚类数量m＝3，最大迭代次数为100。

计算方法依赖图各个顶点的度和每个顶点作为聚类中心的概率值：

每个顶点以prob

同理对个体P

步骤3：计算每个个体的两个聚类目标值：软件模块质量MQ和逆向边数fit_derection，以个体P

计算聚类c

计算聚类c

软件系统模块聚类后，计算第i个聚类c

ε

ε

ε

计算第i个聚类的内聚性μ

同理计算个体P

计算逆向边数：

将最优解(0.623,0.333)作为非支配个体加入到帕累托非支配解集合中，对帕累托非支配解集进行更新。

步骤4根据个体P

比较计算出方法w分别属于3个聚类的概率P

P

对个体P

步骤5：更新帕累托非支配解集；根据每个个体的聚类目标值：软件模块质量和逆向边数，由个体间非支配关系更新帕累托非支配解集：如果当前个体被帕累托非支配解集中某个解支配，则当前个体不用加入帕累托非支配解集；如果当前个体支配了帕累托非支配解集中某个解，则删除帕累托非支配解集所有被支配的解，并把当前个体加入帕累托非支配解集；如果当前个体和帕累托非支配解集中所有解都不存在支配关系，则并把当前个体加入帕累托非支配解集。

步骤6：重复迭代进行步骤4和步骤5，若达到最大迭代次数100，则结束整个步骤，帕累托非支配解集中的个体对应的聚类方案就是本软件模块聚类结果，输出聚类结果，否则重复执行步骤4到步骤5的操作。比较种群中所有个体的目标函数适应度值，把本次迭代的帕累托非支配个体加入到外部集中不断迭代，更新外部集，判断迭代次数是否达到最大迭代次数100，若达到最大迭代次数，则结束整个步骤，得到软件模块聚类结果，否则重复执行步骤4到步骤6的操作，聚类结果如图4所示。