The efficiency of indicator-based local search for multi-objective combinatorial optimisation problems

• Aarts, E., Korst, J., Michiels, W.: Simulated annealing. In: Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Springer, Berlin (2005), Chap. 7

  Google Scholar 

• Auger, A., Hansen, N.: A restart CMA evolution strategy with increasing population size. In: IEEE Congress on Evolutionary Computation (CEC 2005), vol. 2, pp. 1769–1776 (2005)

  Chapter  Google Scholar 

• Basseur, M.: Design of cooperative algorithms for multi-objective optimization: application to the flow-shop scheduling problem. PhD thesis, University of Sciences and Technology of Lille, France (2005)

• Basseur, M., Burke, E.K.: Indicator-based multiobjective local search. In: IEEE Congress on Evolutionary Computation (CEC 2007), Singapore, September 2007, pp. 3100–3107 (2007)

  Chapter  Google Scholar 

• Basseur, M., Seynhaeve, F., Talbi, E.-G.: Design of multi-objective evolutionary algorithms: application to the flow-shop scheduling problem. In: IEEE Congress on Evolutionary Computation (CEC), 2002, Honolulu, USA, vol. 2, pp. 1151–1156 (2002)

  Google Scholar 

• Basseur, M., Zitzler, E.: Handling uncertainty in indicator-based multiobjective optimization. Int. J. Comput. Intell. Res. 2(3), 255–272 (2006)

  MathSciNet  Google Scholar 

• Bentley, P.J., Wakefield, J.P.: Finding acceptable solutions in the Pareto-optimal range using multiobjective genetic algorithms. Soft Comput. Eng. Des. Manuf. 5, 231–340 (1997)

  Google Scholar 

• Bringmann, K., Friedrich, T.: Approximating the least hypervolume contributor: NP-hard in general, but fast in practice. In: 5th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2009). Lecture Notes in Computer Science, vol. 5467, pp. 6–20. Springer, Berlin (2009)

  Chapter  Google Scholar 

• Burke, E., De Causmaecker, P., Vanden Berghe, G., Van Landeghem, H.: The state of the art of nurse rostering. J. Sched. 7(6), 441–499 (2004)

  Article  MathSciNet  MATH  Google Scholar 

• Cahon, S., Melab, N., Talbi, E.-G.: ParadisEO: a framework for the reusable design of parallel and distributed metaheuristics. J. Heuristics 10(3), 357–380 (2004)

  Article  Google Scholar 

• Cheang, B., Li, H., Lim, A., Rodrigues, B.: Nurse rostering problems—a bibliographic survey. Eur. J. Oper. Res. 151, 447–460 (2003)

  Article  MathSciNet  MATH  Google Scholar 

• Deb, K.: Multi-objective optimization. In: Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Chap. 10, pp. 273–316. Springer, Berlin (2006)

  Google Scholar 

• Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 181–197 (2002)

  Article  Google Scholar 

• Du, J., Leung, J.Y.-T.: Minimizing total tardiness on one machine is NP-hard. Math. Oper. Res. 15, 483–495 (1990)

  Article  MathSciNet  MATH  Google Scholar 

• Ehrgott, M., Gandibleux, X.: Approximative solution methods for multiobjective combinatorial optimization. Trab. Investig. Oper. 12(1), 1–63 (2004)

  MathSciNet  MATH  Google Scholar 

• Emmerich, M., Beume, N., Naujoks, B.: An EMO algorithm using the hypervolume measure as selection criterion. In: 3rd International Conference on Evolutionary Multi-criterion Optimization (EMO 2005). Lecture Note in Computer Science, vol. 3410, pp. 62–76. Springer, Berlin (2005)

  Chapter  Google Scholar 

• Fonseca, C.M., Fleming, P.J.: Genetic algorithms for multiobjective optimization: formulation discussion and generalization. In: Fifth International Conference on Genetic Algorithms (ICGA’93), San Mateo, USA, pp. 416–423 (1993)

  Google Scholar 

• Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Boston (1989)

  MATH  Google Scholar 

• Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)

  Article  MathSciNet  MATH  Google Scholar 

• Grunert da Fonseca, V., Fonseca, C.M., Hall, A.O.: Inferential performance assessment of stochastic optimisers and the attainment function. In: 1st International Conference on Evolutionary Multi-criterion Optimization (EMO 2001). Lecture Note in Computer Science, vol. 1993, pp. 213–225. Springer, Berlin (2001)

  Chapter  Google Scholar 

• Ishibuchi, T.H.: A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans. Syst. Man Cybern., Part C, Appl. Rev. 28(3), 1998 (1998)

  Article  Google Scholar 

• Hansen, M.P.: Tabu search for multiobjective optimization: MOTS. In: MCDM’97 Conference, Cap town, South Africa (1997)

  Google Scholar 

• Kim, Y.-D.: Minimizing total tardiness in permutation flowshops. Eur. J. Oper. Res. 33, 541–551 (1995)

  Article  Google Scholar 

• Knowles, J.D.: Local-search and hybrid evolutionary algorithms for Pareto optimization. PhD thesis, University of Reading (2002)

• Knowles, J.D., Corne, D.W.: Approximating the nondominated front using the Pareto archived evolution strategy. Evol. Comput. 8(2), 149–172 (2000)

  Article  Google Scholar 

• Knowles, J.D., Thiele, L., Zitzler, E.: A tutorial on the performance assessment of stochastive multiobjective optimizers. Technical report TIK-Report No. 214, Computer Engineering and Networks Laboratory, ETH Zurich, July 2005

• Labbé, M., Laporte, G., Rodríguez Martín, I., Salazar González, J.J.: The ring star problem: polyhedral analysis and exact algorithm. Networks 43, 177–189 (2004)

  Article  MathSciNet  MATH  Google Scholar 

• Landa-Silva, D., Burke, E.K., Petrovic, S.: An introduction to multiobjective metaheuristics for scheduling and timetabling. In: Metaheuristics for Multiobjective Optimisation, pp. 91–129, Chap. 4. Springer, Berlin (2004)

  Chapter  Google Scholar 

• Landa-Silva, D., Le, K.N.: A simple evolutionary algorithm with self-adaptation for multi-objective nurse scheduling. In: Adaptive and Multilevel Metaheuristics, vol. 136, pp. 133–155, Chap. 7. Springer, Berlin (2008)

  Chapter  Google Scholar 

• Lenstra, J.K., Kan, A.H.G.R., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343–362 (1977)

  Article  Google Scholar 

• Liefooghe, A., Jourdan, L., Jozefowiez, N., Talbi, E.-G.: On the integration of a TSP heuristic into an EA for the bi-objective ring star problem. In: International Workshop on Hybrid Metaheuristics (HM 2008), Malaga, Spain. Lecture Notes in Computer Science, vol. 5296, pp. 117–130. Springer, Berlin (2008)

  Chapter  Google Scholar 

• Liefooghe, A., Mesmoudi, S., Humeau, J., Jourdan, L., Talbi, E.-G.: A study on dominance-based local search approaches for multiobjective combinatorial optimization. In: Second International Workshop on Engineering Stochastic Local Search Algorithms (SLS 2009), Brussels, Belgium. Lecture Notes in Computer Science, vol. 5752, pp. 120–124 (2009)

  Google Scholar 

• Murata, T., Nozawa, H., Ishibuchi, H., Gen, M.: Modification of local search directions for non-dominated solutions in cellular multiobjective genetic algorithms for pattern classification problems. In: 2nd International Conference on Evolutionary Multi-criterion Optimization (EMO 2003). Lecture Notes in Computer Science, vol. 2632, pp. 593–607. Springer, Berlin (2003)

  Chapter  Google Scholar 

• Nagar, A., Haddock, J., Heragu, S.: Multiple and bicriteria scheduling: a literature survey. Eur. J. Oper. Res. 81, 88–104 (1995)

  Article  MATH  Google Scholar 

• Oliver, I.M., Smith, D.J., Holland, J.R.C.: A study of permutation crossover operators on the traveling salesman problem. In: Proceedings of the Second International Conference on Genetic algorithms and their application, Mahwah, NJ, USA, pp. 224–230. Erlbaum, Hillsdate (1987)

  Google Scholar 

• Paquete, L., Stützle, T.: A study of local search algorithms for the biobjective QAP with correlated flow matrices. Eur. J. Oper. Res. 169(3), 943–959 (2006)

  Article  MATH  Google Scholar 

• Ross, P.: Hyper-heuristics. In: Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, pp. 527—556, Chap. 17. Springer, Berlin (2006)

  Google Scholar 

• Srinivas, N., Deb, K.: Multiobjective optimization using nondominated sorting in genetic algorithms. Evol. Comput. 2(3), 221–248 (1994)

  Article  Google Scholar 

• Taillard, E.: Benchmarks for basic scheduling problems. Cent. Eur. J. Oper. Res. 64, 278–285 (1993)

  MATH  Google Scholar 

• Talbi, E.G., Rahoual, M., Mabed, M.H., Dhaenens, C.: A hybrid evolutionary approach for multicriteria optimization problems: application to the flow shop. In: 1st International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001). Lecture Notes in Computer Science, vol. 1993, pp. 416–428 (2001)

  Chapter  Google Scholar 

• Tan, K.C., Lee, T.H., Khor, E.F.: Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization. Evol. Comput. 5(6), 565–588 (2001)

  Article  Google Scholar 

• Viana, A., Pinho de Sousa, J., Matos, M.A.: Multiobjective constraint oriented neighbourhoods. In: 6th Metaheuristics International Conference (MIC 2005), Vienna, Austria, pp. 896–903 (2005)

  Google Scholar 

• Zitzler, E., Künzli, S.: Indicator-based selection in multiobjective search. In: 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII), Birmingham, UK, pp. 832–842 (2004)

  Chapter  Google Scholar 

• Zitzler, E., Laumanns, M., Bleuler, S.: A tutorial on evolutionary multiobjective optimization. In: Gandibleux, X., et al. (eds.) Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, pp. 3–37. Springer, Berlin (2004)

  Chapter  Google Scholar 

• Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou, K. et al. (eds.) Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), pp. 95–100. International Center for Numerical Methods in Engineering (CIMNE), Barcelona (2002)

  Google Scholar 

• Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. Evol. Comput. 3, 257–271 (1999)

  Article  Google Scholar 

• Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Grunert da Fonseca, V.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117–132 (2003)

  Article  Google Scholar 

Download references