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

21 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

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