A multi-objective evolutionary algorithm based on Pareto prediction for automatic test task scheduling problems

Hui Lu, Rongrong Zhou, Zongming Fei, Jinhua Shi

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

The test task scheduling problem (TTSP) is a combinatorial optimization problem still under investigation. A multi-objective evolutionary algorithm based on Pareto prediction (PP-MOEA) is proposed fully considering the characteristics of TTSP. In a multi-objective TTSP, multiple solutions in the decision space correspond to a point in the objective space and the number of true Pareto front in the objective space is relatively small. Moreover, there are less solutions distributing in either high or low objective values while most solutions distribute in average. Based on these characteristics, a pure elitism strategy and a novel scale-down non-dominated sorting (SDNS) method are combined to improve the efficiency and convergence of the algorithm. Additionally, an extended encoding range approach and a Pareto prediction strategy are proposed to help exploring new solutions and increase the diversity of population. The Pareto prediction strategy is implemented by following the historical evolutionary information of the current Pareto set and then predicting the next generation of several individuals. The makespan (maximal test completion time) and the mean workload of the instruments are considered in this research. Based on the general framework of MOEAs, the proposed algorithm is more effective and efficient in tackling multi-objective TTSPs. PP-MOEA has the better performance of convergence and diversity compared with other algorithms based on the statistical analysis of experiments results.

Original languageEnglish
Pages (from-to)394-412
Number of pages19
JournalApplied Soft Computing Journal
Volume66
DOIs
StatePublished - May 2018

Bibliographical note

Funding Information:
This research is supported by the National Natural Science Foundation of China under Grant No. 61671041 and No. 61101153 . Hui Lu received a Ph.D. degree in navigation, guidance and control from Harbin Engineering University, Harbin, China, in 2004. She is a professor at the Beihang University, Beijing, China. Her research interests include information and communication systems, intelligent optimization. Rongrong Zhou received a B.Sc degree in School of Electronic and Information Engineering from Nanjing University of Aeronautics and Astronautics, Nanjing, China, in 2016. She is currently a master candidate at the Beihang University. Her main research areas include optimization algorithm design and application in automatic test system. Zongming Fei received a Ph.D. degree in computer science from Georgia Institute of Technology, Atlanta, GA, United States, in 2000. He is a professor at the University of Kentucky, Lexington, Kentucky, United States. His research interests include networking protocols and architecture, multimedia networking, and Smart Grid communications. Jinhua Shi received a B.Sc degree in School of Information Engineering from Dalian Maritime University, Daliang, China, in 2015. She is currently a master candidate at the Beihang University. Her main research areas include automatic test system and optimization.

Publisher Copyright:
© 2018 Elsevier B.V.

Keywords

  • Encoding mechanism
  • Multi-objective evolutionary algorithms
  • Pareto prediction strategy
  • Scale-down non-dominated sorting method
  • Scheduling theory

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'A multi-objective evolutionary algorithm based on Pareto prediction for automatic test task scheduling problems'. Together they form a unique fingerprint.

Cite this