Skip to main content
SpringerLink
Log in

A mixture experiments multi-objective hyper-heuristic

  • General Paper
  • Published:
Journal of the Operational Research Society

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3

Similar content being viewed by others

References

  • Aickelin U and Li J (2007). An estimation of distribution algorithm for nurse scheduling. Annals of Operations Research 155 (1): 289–309.

    Article  Google Scholar 

  • Bader-El-Den M and Poli R (2008). Generating SAT local-search heuristics using a GP hyperheuristic framework. Lecture Notes in Computer Science 4926: 37–49.

    Article  Google Scholar 

  • Bai R and Kendall G (2005). An investigation of automated planograms using a simulated annealing based hyper-heuristic. In: Ibaraki T, Nonobe K and Yagiura M (eds) Metaheuristics: Progress as Real Problem Solvers. Operations Research/Computer Science Interfaces Series, Vol. 32 Springer: Berlin, Heidelberg, New York, pp 87–108.

    Chapter  Google Scholar 

  • Bai R, Burke EK and Kendall G (2008). Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation. Journal of the Operational Research Society 59 (10): 1387–1397.

    Article  Google Scholar 

  • Burke E, Hart E, Kendall G, Newall J, Ross P and Schulenburg S (2003a). Hyper-heuristics: An emerging direction in modern search technology. In: Glover F and Kochenberger G (eds) Handbook of Metaheuristics. Springer: Berlin, pp 457–474.

    Chapter  Google Scholar 

  • Burke ED, Silva JDL and Soubeiga E (2003b). Hyperheuristic approaches for multiobjective optimisation. In: Proceedings of the Fifth Metaheuristics International Conference (MIC 2003). Kyoto, Japan, pp 11.1–11.6.

    Google Scholar 

  • Burke EK, Kendall G and Soubeiga E (2003c). A tabu-search hyper-heuristic for timetabling and rostering. Journal of Heuristics 9 (6): 451–470.

    Article  Google Scholar 

  • Burke EK, Hyde M and Kendall G (2006a). Evolving bin packing heuristics with genetic programming. Lecture Notes in Computer Science 4193: 860–869.

    Article  Google Scholar 

  • Burke EK, MacCarthy BL, Petrovic S and Qu R (2006b). Multiple-retrieval case based reasoning for course timetabling problems. Journal of the Operational Research Society 57 (2): 148–162.

    Article  Google Scholar 

  • Burke EK, Petrovic S and Qu R (2006c). Case-based heuristic selection for timetabling problems. Journal of Scheduling 9 (2): 115–132.

    Article  Google Scholar 

  • Burke EK, Hyde MR, Kendall G and Woodward J (2007). Automatic heuristic generation with genetic programming: Evolving a jack-of-all-trades or a master of one. In: Proceedings of the 9th annual conference on Genetic and evolutionary computation (GECCO 20077). ACM: London, UK, pp 1559–1565.

    Chapter  Google Scholar 

  • Burke EK, Hyde M, Kendall G, Ochoa G, Ozcan E and Woodward J (2009). A classification of hyper-heuristic approaches. In: Gendreau M and Potvin J-Y (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science. Springer: New York.

    Google Scholar 

  • Chasalow S and Brand R (1995). Algorithm AS 299: Generation of simplex lattice points. Applied Statistics 44 (4): 534–545.

    Article  Google Scholar 

  • Conover WJ (1999). Practical Nonparametric Statistics. 3rd edn, Wiley Series in Probability and Statistics Wiley: New York.

    Google Scholar 

  • Cornell J (2002). Experiments with Mixtures: Design, Models and the Analysis of Mixture Data. 3rd edn, Wiley Series in Probability and Statistics. Wiley: New York.

    Book  Google Scholar 

  • Cowling P, Kendall G and Soubeiga E (2000). A hyperheuristic approach to scheduling a sales summit. In: Burke EK and Erben W (eds) LNCS 2079, Practice and Theory of Automated Timetabling III: Third International Conference, PATAT 2000. Springer-Verlag: Berlin, pp 176–190.

    Google Scholar 

  • Cowling P, Kendall G and Han L (2002). An investigation of a hyperheuristic genetic algorithm applied to a trainer scheduling problem. In: Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002), Honolulu, HI, pp 1185–1190, 12–17 May.

    Google Scholar 

  • Deb K and Agrawal RB (1995). Real-coded genetic algorithms with simulated binary crossover: Studies on multi-modal and multi-objective problems. Complex Systems 9 (6): 431–454.

    Google Scholar 

  • Deb K, Pratap A, Agarwal S and Meyarivan T (2002a). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6 (2): 182–197.

    Article  Google Scholar 

  • Deb K, Thiele L, Laumanns M and Zitzler E (2002b). Scalable multi-objective optimization test problems. In: Congress on Evolutionary Computation (CEC 2002), IEEE: Honolulu, HI, USA, Vol. 1, pp 825–830.

    Google Scholar 

  • Denzinger J, Fuchs M and Fuchs M (1997). High performance ATP systems by combining several AI methods. In: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI 97), Massachusetts, USA, pp 102–107.

    Google Scholar 

  • Dimopoulos C and Zalzala AMS (2001). Investigating the use of genetic programming for a classic one-machine scheduling problem. Advances in Engineering Software 32 (6): 489–498.

    Article  Google Scholar 

  • Fisher H and Thompson GL (1961). Probabilistic learning combinations of local job-shop scheduling rules. In: Factory Scheduling Conference. Carnegie Institute of Technology, Pittsburgh, PA, USA, pp 225–251.

    Google Scholar 

  • Fukunaga AS (2008). Automated discovery of local search heuristics for satisfiability testing. Evolutionary Computation 16 (1): 31–61.

    Article  Google Scholar 

  • Geiger CD, Uzsoy R and Aytŭg H (2006). Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. Journal of Scheduling 9 (1): 7–34.

    Article  Google Scholar 

  • Keller RE and Poli R (2007a). Cost-benefit investigation of a genetic-programming hyperheuristic. Lecture Notes in Computer Science 4926: 13–24.

    Article  Google Scholar 

  • Keller RE and Poli R (2007b). Linear genetic programming of parsimonious metaheuristics. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC 2007), Singapore, pp 4508–4515.

    Chapter  Google Scholar 

  • Kendall G and Mohamad M (2004). Channel assignment in cellular communication using a great deluge hyper-heuristic. In: Proceedings of the 12th IEEE International Conference on Networks (ICON 2004). IEEE: Singapore, pp 790–795.

    Google Scholar 

  • Kibria RH and Li Y (2006). Optimizing the initialization of dynamic decision heuristics in DPLL SAT solvers using genetic programming. Lecture Notes in Computer Science 3905: 331–340.

    Article  Google Scholar 

  • Knowles J, Thiele L and Zitzler E (2006). A Tutorial on the Performance Assessment of Stochastic Multiobjective Optimizers. Computer Engineering and Networks Laboratory (TIK): ETH Zurich, Switzerland, revised version, p 214.

    Google Scholar 

  • Li H and Zhang Q (2009). Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Transactions on Evolutionary Computation 12 (2): 284–302.

    Article  Google Scholar 

  • Petrovic S, Fayad C, Petrovic D, Burke E and Kendall G (2008). Fuzzy job shop scheduling with lot-sizing. Annals of Operations Research 159 (1): 275–292.

    Article  Google Scholar 

  • Ross P (2005). Hyper-heuristics. In: Burke EK and Kendall G (eds) Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Springer: New York, Ch. 17, pp 529–556.

    Chapter  Google Scholar 

  • Ross P, Schulenburg S, Marín-Blázquez JG and Hart E (2002). Hyper-heuristics: Learning to combine simple heuristics in bin-packing problems. In: Genetic and Evolutionary Computation Conference (GECCO 2002), New York, July 9–13, pp 942–948.

    Google Scholar 

  • Tay JC and Ho NB (2008). Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computers & Industrial Engineering 54 (3): 453–473.

    Article  Google Scholar 

  • Terashima-Marín H, Zárate CJF, Ross P and Valenzuela-Rendón M (2006). A GA-based method to produce generalized hyper-heuristics for the 2d-regular cutting stock problem. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO 2006), ACM: Seattle, Washington, USA, July 8–12, pp 591–598.

    Chapter  Google Scholar 

  • Vázquez-Rodríguez JA and Petrovic S (2010a). Calibrating continuous multi-objective heuristics using mixture experiments. Journal of Heuristics 18 (5): 699–726.

    Article  Google Scholar 

  • Vázquez-Rodríguez JA and Petrovic S (2010b). A new dispatching rule based genetic algorithm for the multi-objective job shop problem. Journal of Heuristics 16 (6): 771–793.

    Article  Google Scholar 

  • Vázquez-Rodríguez JA, Petrovic S and Salhi A (2007). A combined meta-heuristic with hyper-heuristic approach to the scheduling of the hybrid flow shop with sequence dependent setup times and uniform machines. In: Baptiste P, Kendall G, Munier-Kordon A and Sourd F (eds) Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications. Paris, France, pp 506–513.

    Google Scholar 

  • Zitzler E and Künzli S (2004). Indicator-based selection in multiobjective search. Lecture Notes in Computer Science 3242: 832–842.

    Article  Google Scholar 

  • Zitzler E, Deb K and Thiele L (2000). Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation 8 (2): 173–195.

    Article  Google Scholar 

  • Zitzler E, Laumanns M and Thiele L (2002). SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou K, Tsahalis D, Periaux J et al (eds) Evolutionary Methods for Design, Optimisation and Control. pp 95–100.

Download references

Author information

Authors and Affiliations

  1. University of Nottingham, Nottinghamshire, UK

    J A Vázquez-Rodríguez & S Petrovic

Authors
  1. J A Vázquez-Rodríguez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S Petrovic
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vázquez-Rodríguez, J., Petrovic, S. A mixture experiments multi-objective hyper-heuristic. J Oper Res Soc 64, 1664–1675 (2013). https://doi.org/10.1057/jors.2012.125

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2012.125

Keywords

Search

Navigation