Computer Science ›› 2017, Vol. 44 ›› Issue (12): 249-254.doi: 10.11896/j.issn.1002-137X.2017.12.045

Previous Articles     Next Articles

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

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!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .