A mixture experiments multi-objective hyper-heuristic

Abstract

This paper proposes a hyper-heuristic that combines genetic algorithm with mixture experiments to solve multi-objective optimisation problems. At every iteration, the proposed algorithm combines the selection criterion (rank indicator) of a number of well-established evolutionary algorithms including NSGA-II, SPEA2 and two versions of IBEA. Each indicator is called according to an associated probability calculated and updated during the search by means of mixture experiments. Mixture experiments are a particular type of experimental design suitable for the calibration of parameters that represent probabilities. Their main output is an explanatory model of algorithm performance as a function of its parameters. By finding the maximum (probability distribution) of the surface represented by this model, we also find a good algorithm parameterisation. The design of mixture experiments approach allowed the authors to identify and exploit synergies between the different rank indicators at the different stages of the search. This is demonstrated by our experimental results in which the proposed algorithm compared favourably against other well-established algorithms.

Keywords:

• hyperheuristics
• multi-objective optimisation
• mixture experiments
• design of experiments
• evolutionary algorithms
• response surface methodology