Abstract
This paper examines the effect of mating restriction on the search ability of EMO algorithms. First we propose a simple but flexible mating restriction scheme where a pair of similar (or dissimilar) individuals is selected as parents. In the proposed scheme, one parent is selected from the current population by the standard binary tournament selection. Candidates for a mate of the selected parent are winners of multiple standard binary tournaments. The selection of the mate among multiple candidates is based on the similarity (or dissimilarity) to the first parent. The strength of mating restriction is controlled by the number of candidates (i.e., the number of tournaments used for choosing candidates from the current population). Next we examine the effect of mating restriction on the search ability of EMO algorithms to find all Pareto-optimal solutions through computational experiments on small test problems using the SPEA and the NSGA-II. It is shown that the choice of dissimilar parents improves the search ability of the NSGA-II on small test problems. Then we further examine the effect of mating restriction using large test problems. It is shown that the choice of similar parents improves the search ability of the SPEA and the NSGA-II to efficiently find near Pareto-optimal solutions of large test problems. Empirical results reported in this paper suggest that the proposed mating restriction scheme can improve the performance of EMO algorithms for many test problems while its effect is problem-dependent and algorithm-dependent.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Coello Coello, C. A., Van Veldhuizen, D. A., and Lamont, G. B.: Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic Publishers, Boston (2002).
Czyzak, P., and Jaszkiewicz, A.: Pareto-Simulated Annealing — A Metaheuristic Technique for Multi-Objective Combinatorial Optimization, Journal of Multi-Criteria Decision Analysis 7 (1998) 34–47.
Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Chichester (2001).
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T.: A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II, IEEE Trans. on Evolutionary Computation 6 (2002) 182–197.
Fonseca, C. M., and Fleming, P. J.: Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization, Proc. of 5th International Conference on Genetic Algorithms (1993) 416–423.
Fonseca, C. M., and Fleming, P. J.: An Overview of Evolutionary Algorithms in Multiobjective Optimization, Evolutionary Computation 3 (1995) 1–16.
Goldberg, D. E.: Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading (1989).
Hajela, P., and Lin, C. Y.: Genetic Search Strategies in Multicriterion Optimal Design, Structural Optimization 4 (1992) 99–107.
Horn, J., Nafpliotis, N., and Goldberg, D. E.: A Niched Pareto Genetic Algorithm for Multi-Objective Optimization, Proc. of 1st IEEE International Conference on Evolutionary Computation (1994) 82–87.
Ishibuchi, H., and Murata, T.: A Multi-Objective Genetic Local Search Algorithm and Its Application to Flowshop Scheduling, IEEE Trans. on Systems, Man, and Cybernetics — Part C: Applications and Reviews 28 (1998) 392–403.
Jaszkiewicz, A.: Genetic Local Search for Multi-Objective Combinatorial Optimization, European Journal of Operational Research 137 (2002) 50–71.
Knowles, J. D., and Corne, D. W.: On Metrics for Comparing Non-Dominated Sets, Proc. of 2002 Congress on Evolutionary Computation (2002) 711–716.
Schaffer, J. D.: Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, Proc. of 1st International Conference on Genetic Algorithms and Their Applications (1985) 93–100.
Van Veldhuizen, D. A., and Lamont, G. B.: Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art, Evolutionary Computation 8 (2000) 125–147.
Watanabe, S., Hiroyasu, T., and Miki, M.: LCGA: Local Cultivation Genetic Algorithm for Multi-Objective Optimization Problem, Proc. of 2002 Genetic and Evolutionary Computation Conference (2002) 702.
Zitzler, E., Deb, K., Thiele, L.: Comparison of Multiobjective Evolutionary Algorithms: Empirical Results, Evolutionary Computation 8 (2000) 173–195.
Zitzler, E., Thiele, L.: Multiobjective Optimization using Evolutionary Algorithms — A Comparative Case Study, Proc. of 5th International Conference on Parallel Problem Solving from Nature (1998) 292–301.
Zitzler, E., Thiele, L.: Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach, IEEE Transactions on Evolutionary Computation 3 (1999) 257–271.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ishibuchi, H., Shibata, Y. (2003). An Empirical Study on the Effect of Mating Restriction on the Search Ability of EMO Algorithms. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Thiele, L., Deb, K. (eds) Evolutionary Multi-Criterion Optimization. EMO 2003. Lecture Notes in Computer Science, vol 2632. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36970-8_31
Download citation
DOI: https://doi.org/10.1007/3-540-36970-8_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-01869-8
Online ISBN: 978-3-540-36970-7
eBook Packages: Springer Book Archive