×

zbMATH — the first resource for mathematics

Working principles, behavior, and performance of MOEAs on MNK-landscapes. (English) Zbl 1123.90063
Summary: This work studies the working principles, behavior, and performance of multiobjective evolutionary algorithms (MOEAs) on multiobjective epistatic fitness functions with discrete binary search spaces by using MNK-landscapes. First, we analyze the structure and some of the properties of MNK-landscapes under a multiobjective perspective by using enumeration on small landscapes. Then, we focus on the performance and behavior of MOEAs on large landscapes. We organize our study around selection, drift, mutation, and recombination, the four major and intertwined processes that drive adaptive evolution over fitness landscapes. This work clearly shows pros and cons of the main features of MOEAs, gives a valuable guide for the practitioner on how to set up his/her algorithm, enhance MOEAs, and presents useful insights on how to design more robust and efficient MOEAs.

MSC:
90C29 Multi-objective and goal programming
90C27 Combinatorial optimization
Software:
SPEA2
PDF BibTeX Cite
Full Text: DOI
References:
[1] Altenberg, L., Evolving better representations through selective genome growth, (), 182-187
[2] Altenberg, L., Fitness landscapes: NK landscapes, shape handbook of evolutionary computation, (1997), Institute of Physics Publishing and Oxford University Press, pp. B2.7:5-10
[3] Aguirre, H.; Tanaka, K., Genetic algorithms on NK-landscapes: effects of selection, drift, mutation, and recombination, (), 131-142 · Zbl 1033.68708
[4] Aguirre, H.; Tanaka, K., Insights on properties of multiobjective MNK-landscapes, (), 196-203
[5] Aguirre, H.; Tanaka, K., Effects of elitism and population climbing on multiobjective MNK-landscapes, (), 449-456
[6] Aguirre, H.; Tanaka, K., Selection, drift, recombination, and mutation in multiobjective evolutionary algorithms on scalable MNK-landscapes, (), 355-369 · Zbl 1109.68582
[7] Bosman, P.; Thierens, D., The balance between proximity and diversity in multiobjective evolutionary algorithms, IEEE transactions on evolutionary computation, 7, 2, 174-188, (2003)
[8] Coello, C.; Van Veldhuizen, D.; Lamont, G., Evolutionary algorithms for solving multi-objective problems, (2002), Kluwer Academic Publishers Boston · Zbl 1130.90002
[9] Davidor, Y., Epistasis variance: A viewpoint of GA-hardness, Foundations of genetic algorithms, 5, (1991), Morgan Kaufman, pp. 23-35
[10] Day, R.; Kleeman, M.; Lamont, G., Multi-objective fast messy genetic algorithm solving deception problems, 2004 IEEE congress on evolutionary computation (CEC’2004), 2, (2004), IEEE Service Center
[11] Day, R.; Lamont, G., Extended multiobjective fast messy genetic algorithm solving deception problems, (), 296-310 · Zbl 1109.68590
[12] De Jong, K.A.; Potter, M.A.; Spears, W.M., Using problem generators to explore the effects of epistasis, (), 338-345
[13] Deb, K., Agrawal, S., Pratap, A., Meyarivan, T. 2000. A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. KanGAL report 200001.
[14] Deb, K., Multi-objective optimization using evolutionary algorithms, (2001), John Wiley & Sons Chichester, West Sussex, England · Zbl 0970.90091
[15] Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable multi-objective optimization test problems, (), 825-830
[16] Fleischer, M., The measure of Pareto optima: applications to multi-objective metaheuristics, (), 519-533 · Zbl 1036.90530
[17] Fonseca, C.M., Fleming, P.J., 1993. Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. In: Proceedings of 5th International Conference on Genetic Algorithms, pp. 416-423.
[18] Heckendorn, R.; Rana, S.; Whitley, D., Test function generators as embedded landscapes, Foundations of genetic algorithms, 5, (1999), Morgan Kaufman, pp. 183-198
[19] Holland, J., Adaptation in natural and artificial systems, (1975), University of Michigan Press
[20] Hajela, P.; Lin, C.Y., Genetic search strategies in multicriterion optimal design, Structural optimization, 4, 99-107, (1992)
[21] Ishibuchi, H.; Shibata, Y., An empirical study on the effect of mating restriction on the search ability of EMO algorithms, (), 433-447 · Zbl 1036.90539
[22] Ishibuchi, H.; Shibata, Y., A similarity-based mating scheme for evolutionary multiobjective optimization, (), 1065-1076 · Zbl 1028.68787
[23] Ishibuchi, H.; Shibata, Y., Mating scheme for controlling the diversity-convergence balance for multiobjective optimization, (), 1259-1271
[24] Kauffman, S.A., The origins of order: self-organization and selection in evolution, (1993), Oxford University Press
[25] Knowles, J.; Corne, D., On metrics for comparing non-dominated sets, (), 711-716
[26] Khan, N., Goldberg, D., Pelikan, M., 2002. Multi-Objective Bayesian Optimization Algorithm. ILLiGAL Report 2002009. University of Illinois at Urbana-Champaign.
[27] Khan, N., 2003. Bayesian Optimization Algorithms for Multiobjective and Hierarchically Difficult Problems. Master thesis, University of Illinois at Urbana-Champaign.
[28] Kim, M.; Hiroyasu, T.; Miki, M.; Watanabe, S., SPEA2+: improving the performance of the strength Pareto evolutionary algorithm 2, (), 742-751
[29] Manderick, B.; de Weger, M.; Spiessens, P., The genetic algorithm and the structure of the fitness landscape, (), 143-150
[30] Merz, P.; Freisleben, B., On the effectiveness of evolutionary search in high-dimensional NK-landscapes, (), 741-745
[31] Mathias, K.E.; Eshelman, L.J.; Schaffer, D., Niches in NK-landscapes, Foundations of genetic algorithms, 6, (2001), Morgan Kaufman, pp. 27-46 · Zbl 0992.68058
[32] Smith, R.; Smith, J., An examination of tunable, random search landscapes, Foundations of genetic algorithms, 5, (1999), Morgan Kaufman, pp. 165-182
[33] Thierens, D.; Goldberg, D.; Pereira, A., Domino convergence, drift and the temporal salience structure of problems, (), 535-540
[34] Watanabe, S., Hiroyasu, T., Miki, M., 2002. Neighborhood cultivation genetic algorithm for multiobjective optimization problems. In: Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning (SEAL 2002), pp. 198-202.
[35] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C.; Grunert da Fonseca, V., Performance assessment of multiobjective optimizers: an analysis and review, IEEE transactions on evolutionary computation, 7, 2, 117-132, (2003)
[36] Zitzler, E., Laumanns, M., Thiele, 2001. L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, TIK-Report.
[37] Zitzler, E., 1999. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. PhD thesis, Swiss Federal Institute of Technology, Zurich.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.