×

Improving convergence of evolutionary multi-objective optimization with local search: a concurrent-hybrid algorithm. (English) Zbl 1251.90358

Summary: A local search method is often introduced in an evolutionary optimization algorithm to enhance its speed and accuracy of convergence to optimal solutions. In multi-objective optimization problems, the implementation of local search is a non-trivial task, as determining a goal for local search in presence of multiple conflicting objectives becomes a difficult task. In this paper, we borrow a multiple criteria decision making concept of employing a reference point based approach of minimizing an achievement scalarizing function and integrate it as a search operator with a concurrent approach in an evolutionary multi-objective algorithm. Simulation results of the new concurrent-hybrid algorithm on several two to four-objective problems compared to a serial approach, clearly show the importance of local search in aiding a computationally faster and accurate convergence to the Pareto optimal front.

MSC:

90C29 Multi-objective and goal programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C59 Approximation methods and heuristics in mathematical programming

Software:

SPEA2; KNITRO
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Beyer HG, Schwefel HP (2002) Evolution strategies–a comprehensive introduction. Nat Comput 1(1):3–52 · Zbl 1014.68134 · doi:10.1023/A:1015059928466
[2] Byrd RH, Nocedal J, Waltz RA (2006) KNITRO: an integrated package for nonlinear optimization. In: Pillo G, Roma M (eds) Large-scale nonlinear optimization. Springer, Berlin, pp 35–39 · Zbl 1108.90004
[3] Chankong V, Haimes YY (1983) Multiobjective decision making theory and methodology. Elsevier, New York · Zbl 0622.90002
[4] Coello, CAC, Lamont, GB (eds) (2004) Applications of multi-objective evolutionary algorithms. World Scientific, Singapore · Zbl 1087.68121
[5] Coello CAC, Lamont GB, Veldhuizen DAV (2007) Evolutionary algorithms for solving multi-objective problems. 2nd edn. Springer, New York · Zbl 1142.90029
[6] Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, Chichester · Zbl 0970.90091
[7] Deb K (2008) A robust evolutionary framework for multi-objective optimization. In: Keijzer M et al (eds) Proceedings of the 10th annual conference on Genetic and evolutionary computation (GECCO 2008). ACM, New York, pp 633–640
[8] Deb K, Sindhya K (2008) Deciphering innovative principles for optimal electric brushless D.C. permanent magnet motor design. In: Proceedings of the world congress on Evolutionary computation (CEC 2008). IEEE Press, Piscataway, pp 2283–2290
[9] Deb K, Agarwal S, Pratap A, Meyarivan T (2002a) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197 · Zbl 05451853 · doi:10.1109/4235.996017
[10] Deb K, Thiele L, Laumanns M, Zitzler E (2002b) Scalable multi-objective optimization test problems. In: Proceedings of the congress on Evolutionary computation (CEC 2002), vol 1. IEEE Press, Piscataway, pp 825–830
[11] Deb K, Mohan M, Mishra S (2003) Towards a quick computation of wellspread Pareto-optimal solutions. In: Fonseca CM et al (eds) Proceedings of the evolutionary multi-criterion optimization (EMO 2003). Springer, Berlin, pp 222–236 · Zbl 1036.90525
[12] Deb K, Srinivasan A (2008) Innovization: discovery of innovative design principles through multiobjective evolutionary optimization. In: Knowles J (eds) multiobjective problem solving from nature. Springer, Berlin, pp 243–262
[13] Emmerich M, Deutz A, Beume N (2007) Gradient-based/evolutionary relay hybrid for computing Pareto front approximations maximizing the S-metric. In: Bartz-Beielstein T et al (eds) Proceedings of the 4th international workshop on Hybrid metaheuristics (HM 2007). Springer, Berlin, pp 140–156
[14] Galperin EA, Wiecek MM (1999) Retrieval and use of the balance set in multiobjective global optimization. Comput Math Appl 37:111–123 · Zbl 0931.90045 · doi:10.1016/S0898-1221(99)00063-2
[15] Glover F (1989) Tabu search-part I. ORSA J Comput 1(3):190–206 · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[16] Goel T, Deb K (2002) Hybrid methods for multi-objective evolutionary algorithms. In: Wang L, Tan KC, Furuhashi T, Kim JH, Yao X (eds) Proceedings of the 4th Asia-Pacific conference on Simulated evolution and learning (SEAL 2002), vol 1. Nanyang Technical University, Singapore, pp 188–192
[17] Hansen MP (2000) Use of substitute scalarizing functions to guide a local search based heuristic: the case of moTSP. J Heuristics 6(3):419–431 · Zbl 1071.90577 · doi:10.1023/A:1009690717521
[18] Harada K, Sakuma J, Kobayashi S (2006) Local search for multiobjective function optimization: Pareto descent method. In: Keijzer M et al (eds) Proceedings of the 6th annual conference on Genetic and evolutionary computation (GECCO 2006). ACM, New York, pp 659–666
[19] Ishibuchi H, Murata T (1998) A multi-objective genetic local search algorithm and its applications to flowshop scheduling. IEEE Trans Syst Man Cybernet C 28(3):392–403 · doi:10.1109/5326.704576
[20] Ishibuchi H, Narukawa K (2004) Some issues on the implementation of local search in evolutionary multiobjective optimization. In: Deb K et al (eds) Proceedings of the genetic and evolutionary computation (GECCO 2004). Springer, Berlin, pp 1246–1258
[21] Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7(2):204–223 · Zbl 05452017 · doi:10.1109/TEVC.2003.810752
[22] Ishibuchi H, Doi T, Nojima Y (2006) Incorporating of scalarization fitness functions into evolutionary multiobjective optimization algorithms. In: Runarsson TP et al (eds) Proceedings of the parallel problem solving from nature (PPSN IX 2006). Springer, Berlin, pp 493–502
[23] Jaszkiewicz A (2002) Genetic local search for multiple objective combinatorial optimization. Eur J Oper Res 137(1):50–71 · Zbl 1002.90051 · doi:10.1016/S0377-2217(01)00104-7
[24] Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680 · Zbl 1225.90162
[25] Knowles JD, Corne DW (2000a) Approximating the non-dominated front using the Pareto archived evolutionary strategy. Evol Comput 8(2):149–172 · Zbl 05412708 · doi:10.1162/106365600568167
[26] Knowles JD, Corne DW (2000b) M-PAES: a memetic algorithm for multiobjective optimization. In: Proceedings of the congress on Evolutionary computation (CEC 2000), vol 1. IEEE Press, Piscataway, pp 325–332
[27] Kuhn HW, Tucker AW (1951) Nonlinear programming. In: Neyman J (ed) Proceedings of the second Berkeley symposium on Mathematical statistics and probability. University of California Press, Berkeley, pp 481–492
[28] Kukkonen S, Deb K (2006) Improved pruning of non-dominated solutions based on crowding distance for bi-objective optimization problems. In: Proceedings of the congress on Evolutionary computation (CEC 2006). IEEE Press, Piscataway, pp 1179–1186
[29] Laumanns M, Thiele L, Deb K, Zitzler E (2002) Combining convergence and diversity in evolutionary multi-objective optimization. Evol Comput 10(3):263–282 · Zbl 05412728 · doi:10.1162/106365602760234108
[30] Levia HA, Esquivel SC, Gallard RH (2000) Multiplicity and local search in evolutionary algorithms to build the Pareto front. In: Proceedings of the XXth international conference of the Chilean Computer Science Society, pp 7–13
[31] Luque M, Miettinen K, Eskelinen P, Ruiz F (2009) Incorporating preference information in interactive reference point methods for multiobjective optimization. Omega 37(2):450–462 · Zbl 1176.90549 · doi:10.1016/j.omega.2007.06.001
[32] Miettinen K (1999) Nonlinear multiobjective optimization. Kluwer, Boston · Zbl 0949.90082
[33] Miettinen K, Mäkelä MM, Kaario K (2006) Experiments with classification based scalarizing functions in interactive multiobjective optimization. Eur J Oper Res 175(2):931–947 · Zbl 1142.90482 · doi:10.1016/j.ejor.2005.06.019
[34] Miettinen K, Ruiz F, Wierzbicki AP (2008) Introduction to multiobjective optimization: interactive approaches. In: Branke J (eds) Multiobjective optimization: interactive and evolutionary approaches. Springer, Berlin
[35] Osyczka A (1984) Multicriterion optimization in engineering with Fortran programs. Ellis Horwood Limited, Chichester
[36] Sawaragi Y, Nakayama H, Tanino T (1985) Theory of multiobjective optimization. Academic Press, Orlando · Zbl 0566.90053
[37] Shaw KJ, Nortcliffe AL, Thomson M, Love J, Fleming PJ, Fonseca CM (1999) Assessing the performance of multiobjective genetic algorithms for optimization of a batch process scheduling problem. In: Proceedings of the congress on Evolutionary computation (CEC 1999). IEEE Press, Piscataway, pp 37–45
[38] Sindhya K, Deb K, Miettinen K (2008) A local search based evolutionary multi-objective approach for fast and accurate convergence. In: Rudolph G et al (eds) Proceedings of the Parallel Problem Solving from Nature (PPSN X 2008), Springer, Berlin/Heidelberg, pp 815–824
[39] Talbi EG, Rahoual M, Mabed MH, Dhaenens C (2001) A hybrid evolutionary approach for multicriteria optimization problems: Application to the flow shop. In: Zitzler E et al (eds) Proceedings of the evolutionary multi-criterion optimization (EMO 2001), Springer, Berlin, pp 416–428
[40] Tapia C, Coello CAC (2007) Applications of multi-objective evolutionary algorithms in economics and finance: a survey. In: Proceedings of the congress on Evolutionary computation (CEC 2007), IEEE Press, pp 532–539
[41] Wierzbicki AP (1980) The use of reference objectives in multiobjective optimization. In: Fandel G, Gal T (eds) MCDM theory and application. Springer, Hagen, pp 468–486
[42] Wierzbicki AP (1986) On the completeness and constructiveness of parametric characterizations to vector optimization problems. OR Spektrum 8:73–87 · Zbl 0592.90084 · doi:10.1007/BF01719738
[43] Zitzler E, Thiele L (1998a) An evolutionary algorithm for multiobjective optimization: the strength Pareto approach. Technical Report 43, Computer Engineering and Networks Laboratory, ETH
[44] Zitzler E, Thiele L (1998b) Multi-objective optimization using evolutionary algorithms–a comparative case study. In: Eiben AE et al (eds) Proceedings of the parallel problem solving from nature (PPSN V 1998). Springer, Berlin, pp 292–301
[45] Zitzler E, Laumanns M, Thiele L (2001) SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou KC et al (eds) Proceedings of the evolutionary methods for design optimization and control with applications to industrial problems (EUROGEN 2001). International Center for Numerical Methods in Engineering (CIMNE), pp 95–100
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.