基于聚类的多目标遗传算法在类职责分配中的应用

计算机工程与科学

基于聚类的多目标遗传算法在类职责分配中的应用

李雅琎1，刘伟1，2，胡志刚1

（1.中南大学软件学院，湖南长沙 410075;2.湖南中医药大学管理与信息工程学院，湖南长沙 410208）

收稿日期:2015-07-31 修回日期:2015-09-14 出版日期:2016-07-25 发布日期:2016-07-25

Application of multiobjective genetic algorithms based on clustering in class responsibility assignment

LI Ya jin1,LIU Wei1，2,HU Zhi gang1

（1.School of Software,Central South University,Changsha 410075;
2.School of Management and Information Engineering,Hunan University of Chinese Medicine,Changsha 410083,China）

Received:2015-07-31 Revised:2015-09-14 Online:2016-07-25 Published:2016-07-25

摘要/Abstract

摘要：

在面向对象软件设计与实现过程中，类职责分配是其中最重要且复杂的步骤之一，它在很大程度上影响软件质量。为了实现类职责自动分配的目标，从软件内聚与耦合度量的角度出发，建立了类职责分配问题多目标优化模型。在基于快速非支配排序多目标遗传算法基础上，引入凝聚的层次聚类技术，保证群体多样性，避免陷入未成熟收敛。在实验中，通过对类职责自动分配并与一个已有的设计优良的软件系统进行对比，验证了此算法的正确性。另外，通过与单目标遗传算法、SPEA2算法对比表明，本算法在解决类职责分配问题上运行效果最好。

关键词: 类职责分配, 多目标遗传算法, 快速非支配排序, 凝聚层次聚类

Abstract:

In the process of objectoriented software design and implementation, responsibility assignment problem (CRA) is one of the most important and complicated procedures, which affects the quality of software to a large extent. In order to achieve the goal of CRA automatically, we propose a CRA multiobjective optimization model which is built from the perspective of cohesion and coupling metrics. On the basis of fast nondominated sorting genetic algorithm, we introduce the agglomerate hierarchical clustering technology to ensure population diversity and to avoid premature convergence. Experiments on automatical class responsibility assignment verify the correctness of the algorithm, whose results are also compared with an existing welldesigned software system. In addition, compared with the single objective genetic algorithm and the SPEA2 algorithm, the proposed algorithm has the best CRA operation effect.

Key words: class responsibility assignment, multi-objective genetic algorithms, fast non-dominated sorting, hierarchical agglomerative clustering

李雅琎1，刘伟1，2，胡志刚1. 基于聚类的多目标遗传算法在类职责分配中的应用[J]. 计算机工程与科学.

LI Ya jin1,LIU Wei1，2,HU Zhi gang1. Application of multiobjective genetic algorithms based on clustering in class responsibility assignment [J]. Computer Engineering & Science.

参考文献［10］

［1］	Praditwong K,Harman M,Xin Yao.Software module clustering as a multi-objective search problem［J］.IEEE Transactions on Software Engineering,2011,37(2):264282.
［2］	Masoud H,Jalili S.A clusteringbased model for class responsibility assignment problem in objectoriented analysis［J］.Journal of Systems and Software,2014,93(10):110131.
［3］	Havashi S, Yanagida T, Saeki M, et al.Class responsibility assignment as fuzzy constraint satisfaction［C］∥Proc of the 6th International Workshop on Empirical Software Engineering,2014:1924.
［4］	Glavas G,Fertalj K.Metaheuristic approach to class responsibility assignment problem［C］∥Proc of the 33rd International Conference on Information Technology Interfaces,2011:591596.
［5］	Basdavanos M, Chatzigeorgious A. Placement of entities in objectoriented systems by means of a singleobjective genetic algorithm［C］∥Proc of IEEE International Conference on Software Maintenance,2007:176182.
［6］	Bowman M,Briand L C,Labiche Y.Solving the class responsibility assignment problem in objectoriented analysis with multiobjective genetic algorithms［J］.IEEE Transactions on Software Engineering,2010,36(6):817837.
［7］	Saini D K,Sharma Y.Soft computing particle swarm optimization based approachfor class responsibility assignment problem［J］.International Journal of Computer Applications,2012,40(12):1924.
［8］	Lavinia F, Corina C. Multiobjective genetic algorithm with clusteringbased ranking and direct control of diversity［C］∥Proc of the 17th International Conference on System Theory Control and Computing,2013:213218.
［9］	Su Haifeng,Chen Li,Zhang Jianhua.Research on reactive power planning of distribution network based on the clustering crowding niche genetic algorithm［J］.Power System Protection and Control,2011,39(5):2730.(in Chinese)
［10］	Li Bo,Qiu Hongyan.Twostage fuzzy clustering genetic algorithm for multipledepot vehicle routing problem［J］.Computer Engineering and Applications,2014,50(5):261264.(in Chinese)
［11］	Deb K,Agrawal S,Pratap A,et al.A Fast elitist nondominated sorting genetic algorithm for multiobjective optimization:NSGAII［M］∥Parallel Problem Solving from Nature PPSN VI. Volume 1917 of the Series Lecture Notes in Computer Science.Berlin Heideberg:Springer,2000:849858.
［12］	Lanza M,Marinescu R.Objectoriented metrics in practice:Using software metrics to characterize,evaluate,and improve the design of objectedoriented systems［M］.Berlin Heideberg:Springer,2010.
［13］	Cobb H G, Grefenstette J J. Genetic algorithms for tracking changing environments［C］∥Proc of the 5th International Conference on Genetic Algorithms,1993:523530.
［14］	Neamtiu I,Foster J S,Hicks M.Understanding source code evolution using abstract syntax tree matching［J］.Acm Sigsoft Software Engineering Notes,2005,30(4):15.
［15］	Zitzler E, Laumanns M, Thiele L. SPEA2:Improving the strength pareto evolutionary algorithm［J］.TIK,Swiss Federal Institute of Technology,2001,10(39):103124.
	附中文参考文献：
［9］	苏海峰,陈丽,张建华.基于聚类排挤小生境遗传算法的配电网无功规划研究［J］.电力系统保护与控制,2011,39 (5):2730.
［10］	李波,邱红艳.基于双层模糊聚类的多车场车辆路径遗传算法［J］.计算机工程与应用,2014,50(5):261264.

[1]	周忠宝1,刘悦悦1,2,金倩颖1,肖和录1,程旭曼3. 基于FDH的分区域多目标遗传算法[J]. 计算机工程与科学, 2018, 40(07): 1295-1302.
[2]	赵宏伟，刘波，谢广钱，刘恒. 卫星有效载荷的多目标多学科设计优化研究[J]. J4, 2015, 37(12): 2276-2281.
[3]	陈良军郑金华龙丹. 多目标遗传算法在人脸识别中的应用[J]. J4, 2006, 28(10): 66-67.