Paper:
Basic Study on Assembling of Objective Functions in Many-Objective Optimization Problems
Shun Otake, Tomohiro Yoshikawa, and Takeshi Furuhashi
Nagoya University, Furo-cho, Chikusa-ku, Nagoya 464-8603, Japan
Genetic Algorithms (GAs) have been widely applied to Multiobjective Optimization Problems (MOPs), called MOGA. A set of Pareto solutions in MOPs having plural fitness functions are searched, then GA is applied in a multipoint search. MOGA performance decreases with the increasing number of objective functions because solution space spreads exponentially. An effective MOGA search is an important issue in many objective optimization problems. One effective approach is assembling objective functions and reducing their number, but appropriate assembly and the number of objective functions to be assembled has not been studied sufficiently. Our purpose here is to determine the effects of assembling objective functions by studying assembly effects when MOGA is applied to a simplified Nurse Scheduling Problem (sNSP) in two types of assembly based on objective function meaning and correlation coefficients.
- [1] J. H. Holland, “Adaptation in Natural and Artificial Systems,” The Univ. Michigan Press, 1975.
- [2] H. Ishibuchi, H. Ohyanagi, and Y. Nojima, “Evolution of Cooperative Behavior in a Spatial Iterated Prisoner’s Dilemma Game with Different Representation Schemes of Game Strategies,” Proc. of IEEE Int. Conf. on Fuzzy Systems, pp. 1568-1573, 2009.
- [3] K. Deb, “Multi-Objective Optimization using Evolutionary Algorithms,” Chichester, UK, Wiley, 2001.
- [4] K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan, “A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization, NSGA-II,” In KanGAL report 200001, Indian Institute of Technology, Kanpur, India, 2000.
- [5] T. Wagner, N. Beume, and B. Naujoks, “Pareto-, Aggregation-, and Indicator-based Methods in Many-objective Optimization,” Lecture Notes in Computer Science 4403, Evolutionary Multi-Criterion Optimization-EMO, pp. 742-756, Springer, Berlin, March, 2007.
- [6] E. J. Hughes, “Evolutionary Many-Objective Optimization: Many Once or One Many?,” Proc. IEEE Congress on Evolutionary Computation (CEC 2005), pp. 222-227, Sep. 2005.
- [7] H. Aguirre and K. Tanaka, “Working Principles, Behavior, and Performance of MOEAs on MNK Landscapes,” European J. of Operational Research, Vol.181, Issue 3, pp. 1670-1690, 2007.
- [8] E. Cantú-Paz, “A Survey of Parallel Genetic Algorithms,” Calculateurs Paralleles, Vol.10, No.2, 1998.
- [9] L. Nang and K. Matsuo, “A survey on the parallel genetic algorithms,” J. of the Society of Instrument and Control Engineers, Vol.33, No.6, pp. 500-509, 1994.
- [10] J. Tang, M. H. Lim, Y. S. Ong, and M. J. Er, “Study of Migration Topology in Island Model Parallel Hybrid-GA for Large Scale Quadratic Assignment Problems,” Proc. of the Eighth Int. Conf. on Control Automation and System, Vol.3, pp. 2286-2291, 2004.
- [11] H. Ishiguro, T. Yoshikawa, and T. Furuhashi, “Visualization of Relationships between Genes and Evaluation Values in GA and Feedback into Genetic Operations,” J. of Japan Society for Fuzzy Theory and Intelligent Informatics, Vol.21, No.3, pp. 327-337, 2009. (in Japanese)
- [12] K. Deb, “A Fast and Elitist Multi-Objective Genetic Algorithm, NSGA-II,” IEEE Trans. on Evolutionary Computation, Indian Institute of Technology, Vol.6, No.2, pp. 182-197, 2002.
- [13] N. Ueno and T. Furuhashi, “A Nurse Scheduling Support System with Nurse-in-Chief’s Know-How,” Fuzzy, Artificial Intelligence, Neural Networks and Computational Intelligence (FAN Symposium ’04), Vol.14, pp. 174-177, 2004. (in Japanese)
- [14] H. Ishiguro, T. Yoshikawa, and T. Furuhashi, “Study on Visualization of Relationships between Genes and Evaluation Values in Evolution Process of MOGA for NSP,” Proc. of Symposium on Evolutionary Computation, pp. 149-155, 2008. (in Japanese)
- [15] J. W. Sammon, Jr, “A Nonlinear Mapping for Data Structure Analysis,” IEEE Trans. on Computers, Vol.C-18, No.5, pp. 401-409, 1969.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.