计算机科学 ›› 2017, Vol. 44 ›› Issue (12): 249-254.doi: 10.11896/j.issn.1002-137X.2017.12.045

• 人工智能 • 上一篇    下一篇

混合拓扑结构的粒子群算法及其在测试数据生成中的应用研究

焦重阳,周清雷,张文宁   

  1. 郑州大学信息工程学院 郑州450001,郑州大学信息工程学院 郑州450001,中国人民解放军信息工程大学 郑州450001;中原工学院 郑州450001
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金项目(61250007),河南省科技厅基础与前沿技术研究项目(152300410055)资助

MPSO and Its Application in Test Data Automatic Generation

JIAO Chong-yang, ZHOU Qing-lei and ZHANG Wen-ning   

  • Online:2018-12-01 Published:2018-12-01

摘要: 粒子群算法(PSO)的拓扑结构是影响算法性能的关键因素,为了从根源上避免粒子群算法易陷入局部极值及早熟收敛等问题,提出一种混合拓扑结构的粒子群优化算法(MPSO)并将其应用于软件结构测试数据的自动生成中。通过不同邻域拓扑结构对算法性能影响的分析,采用一种全局寻优和局部寻优相结合的混合粒子群优化算法。通过观察粒子群的多样性反馈信息,对每一代种群粒子以进化时选择全局拓扑结构模型(GPSO)或局部拓扑结构模型(LPSO)的方法进行。实验结果表明,MPSO使得种群的多样性得到保证,避免了粒子群陷入局部极值,提高了算法的收敛速度。

关键词: 粒子群算法,测试数据自动生成,拓扑结构,全局寻优,局部寻优,多样性

Abstract: To date,meta-heuristic search algorithms have been applied to automate test data generation.The topology of particle swarm optimization (PSO) is one of the key factors that affect algorithm performance.In order to overcome the phenomena of falling into local optimal and premature convergence of the standard particle swarm algorithm (PSO),a mixture neighborhood structure (MPSO) was proposed to generate software structure test data automatically.Based on the analysis of the different neighborhood topology structure effect on the performance of particle optimization,this paper presented a new particle swarm optimization with mix topological structure.MPSO is based on the combination of global optimization and local optimization.In each generation,by observing the feedback information of diversity of the population,the particle speed update method is selected by global topology model or local topology model.The experimental results show that MPSO increases the swarm diversity,avoids falling into local optimization,and improves the convergence speed of the proposed algorithm.

Key words: Particle swarm algorithm,Automatic test data generation,Topology structure,Global optimization,Local optimization,Diversity

[1] HARMAN M.Search-Based software engineering [C]∥International Conference on Computational Science.Springer Berlin Heidelberg,2006:740-747.
[2] KENNEDY J,EBERHART R.Particle swarm optimization[C]∥Proceedings of the IEEE International Conference on Neural Networks.1995:1942-1948.
[3] EBERHART R,KENNEDY J.A new optimizer using particleswarm theory[C]∥Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Nagoya,1995:39-43.
[4] KENNEDY J,MENDS R.Neighborhood topologies in fully informed and best-of-neighborhood particle swarms[J].IEEE Transaction on Systems Man and Cybernetics Part C-Applications and Reviews,2006,6(4):515-519.
[5] KENNEDY J,MENDS R.Population structure and particle swarmperformance[C]∥Proceeding of the 2002 Congress on Evolutionary computation.Honolulu,HI,USA,2002:1671-1676.
[6] WANG X F,WANG F,QIU Y H.Research on a novel particle swarm algorithm with dynamic topology[J].Computer Science,2007,4(3):205-207.(in Chinese) 王雪飞,王芳,邱玉辉.一种具有动态拓扑结构的粒子群算法研究[J].计算机科学,2007,4(3):205-207.
[7] ZHAO S Z,LIANG J J,SUGANTHAN P N,et al.Dynamicmulti-swarm particle swarm optimizer with local search for large scale global optimization[C]∥2008 IEEE Swarm Intelligence Symposium.Hong Kong,2008:3845-3852.
[8] LIU Y M,ZHAO Q Z,SUI C L,et al.Particle swarm optimizer based on dynamic neighborhood topology and mutation operator[J].Control and Decision,2010,5(7):968-974.(in Chinese) 刘衍民,赵庆祯,隋常玲,等.一种基于动态邻居和变异因子的粒子群算法[J].控制与决策,2010,25(7):968-974.
[9] SHI S,CHEN Y.Dynamic particle swarm optimization algori-thm with hierarchical ring topology[J].Computer Engineering and Applications,2013,9(8):1-5.(in Chinese) 石松,陈云.层次环形拓扑结构的动态粒子群算法[J].计算机工程与应用,2013,49(8):1-5.
[10] MOHAIS A S,MENDES R,WARD C,et al.Neighborhood re-structuring in particle swarm optimization[C]∥Australian Conference on Artificial Intelligence.2005:776-785.
[11] WEN W,HAO Z F.Improved Particle Swarm Optimizer Based on Dynamic Topology[J].Computer Engineering and Applications,2005,1(34):82-85.(in Chinese) 温雯,郝志峰.一种基于动态拓扑结构的PSO改进算法[J].计算机工程与应用,2005,41(34):82-85.
[12] CHEN Z Y,HE Z S,ZHANG C.Image multi-level thresholds based on PSO with Von Neumann neighborhood[J].Application Research of Computers,2009,6(5):1977-2000.(in Chinese) 陈自郁,何中市,张程.基于冯诺依曼邻居的粒子群多阈值分割算法[J].计算机应用研究,2009,26(5):1977-2000.
[13] KENNEDY J.Small World and mega-minds:effects of neighb-orhood topology on particle swarm performance[C]∥IEEE Congress on Evolutionary Computation.Piscataway,NJ,1999:1931-1938.
[14] RIGET J,VESTERSTROEM J S.A diversity guided particle swarm optimizer- the ARPSO[R].Denmark:University of Aaehus,2002.
[15] KOREL B.Dynamic method for software test data generation[J].Software Testing,Verification and Reliability,1992,2(4):203-213.
[16] TRACEY N,CLARK J,MANDER K,et al.An automatedframework for structural test-data generation[C]∥Proceeding of the 13th International Conference on Automated Software Engineering.Honolulu,HI,USA,1998:285-288.
[17] MCMINN P.Search-based software test data generation:A survey[J].Software Testing,Verification and Reliability,2004,14(2):105-156.
[18] HARMAN M,MCMINN P.A theoretical and empirical study of search-based testing:local,global,and hybrid search[J].IEEE Transactions on Software Engineering,2010,6(2):226-247.
[19] MA S L,YE D Y,YANG L L.A new design criteria of particle swarm topology[J].Computer Engineering,2015,1(1):200-206.(in Chinese) 马胜蓝,叶东毅,杨玲玲.一种新的粒子群拓扑结构设计准则[J].计算机工程,2015,41(1):200-206.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!