Abstract
This work proposes a method to search effectively on many-objective problems by instantaneously partitioning the objective space into subspaces and performing one generation of the evolutionary search in each subspace. The proposed method uses a partition strategy to define a schedule of subspace sampling, so that different regions of objective space could be emphasized at different generations. In addition, it uses an adaptive ε-ranking procedure to re-rank solutions in each subspace, giving selective advantage to some of the solutions initially ranked highest in the whole objective space. Adaptation works to keep the actual number of highest ranked solutions in each subspace close to a desired number. The performance of the proposed method is verified on MNK-Landscapes. Experimental results show that convergence and diversity of the solutions found can improve remarkably on 4 ≤ M ≤ 10 objectives.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Multiobjective Optimization
- Epistatic Interaction
- Objective Space
- Extreme Solution
- Nondominated Solution
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, Chichester (2001)
Coello, C., Van Veldhuizen, D., Lamont, G.: Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic Publishers, Boston (2002)
Aguirre, H., Tanaka, K.: Insights on Properties of Multiobjective MNK-Landscapes. In: Proc. 2004 IEEE Congress on Evolutionary Computation, pp. 196–203. IEEE Service Center, Los Alamitos (2004)
Aguirre, H., Tanaka, K.: Working Principles, Behavior, and Performance of MOEAs on MNK-Landscapes. European Journal of Operational Research 181(3), 1670–1690 (2007)
Purshouse, R., Fleming, P.: Conflict, harmony, and independence: Relationships in evolutionary multi-criterion optimisation. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.) EMO 2003. LNCS, vol. 2632, pp. 16–30. Springer, Heidelberg (2003)
Aguirre, H., Tanaka, K.: Selection, drift, recombination, and mutation in multiobjective evolutionary algorithms on scalable MNK-landscapes. In: Coello Coello, C.A., Hernández Aguirre, A., Zitzler, E. (eds.) EMO 2005. LNCS, vol. 3410, pp. 355–369. Springer, Heidelberg (2005)
Hughes, E.J.: Evolutionary Many-Objective Optimization: Many Once or One Many? In: Proc. 2005 IEEE Congress on Evolutionary Computation, vol. 1, pp. 222–227. IEEE Service Center, Los Alamitos (2005)
Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II, KanGAL report 200001 (2000)
Yu, P.L.: Cone Convexity, Cone Extreme Points, and Nondominated Solutions in Decision Problems with Multiobjectives. Journal of Optimization Theory and Applications 14(3), 319–377 (1974)
Laumanns, M., Thiele, L., Deb, K., Zitzler, E.: Combining Convergence and Diversity in Evolutionary Multi-objective Optimization. Evolutionary Computation 10(3), 263–282 (2002)
Kauffman, S.A.: The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, Oxford (1993)
Aguirre, H., Tanaka, K.: Adaptive ε-Ranking on MNK-Landscapes. In: Proc. 2009 IEEE Symposium on Computational Intelligence in Multicriteria Decision Making (2009)
Aguirre, H., Tanaka, K.: Robust Optimization by ε-Ranking On High Dimensional Objective Spaces. In: Li, X., Kirley, M., Zhang, M., Green, D., Ciesielski, V., Abass, H.A., Michalewicz, Z., Hendtlass, T., Deb, K., Tan, K.C., Branke, J., Shi, Y. (eds.) SEAL 2008. LNCS, vol. 5361, pp. 421–431. Springer, Heidelberg (2008)
Zitzler, E.: Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications, PhD thesis, Swiss Federal Institute of Technology, Zurich (1999)
Fonseca, C., Paquete, L., López-Ibáñez, M.: An Improved Dimension-sweep Algorithm for the Hypervolume Indicator. In: Proc. 2006 IEEE Congress on Evolutionary Computation, pp. 1157–1163. IEEE Service Center, Los Alamitos (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aguirre, H., Tanaka, K. (2009). Many-Objective Optimization by Space Partitioning and Adaptive ε-Ranking on MNK-Landscapes. In: Ehrgott, M., Fonseca, C.M., Gandibleux, X., Hao, JK., Sevaux, M. (eds) Evolutionary Multi-Criterion Optimization. EMO 2009. Lecture Notes in Computer Science, vol 5467. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01020-0_33
Download citation
DOI: https://doi.org/10.1007/978-3-642-01020-0_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01019-4
Online ISBN: 978-3-642-01020-0
eBook Packages: Computer ScienceComputer Science (R0)