Basic Study on Assembling of Objective Functions in Many-Objective Optimization Problems

Shun Otake; Tomohiro Yoshikawa; Takeshi Furuhashi

doi:10.20965/jaciii.2010.p0618

single-jc.php

« previous

JACIII Vol.14 No.6 pp. 618-623

doi: 10.20965/jaciii.2010.p0618

(2010)

Paper:

Views over last 60 days: 953

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

Received:

November 26, 2009

Accepted:

May 25, 2010

Published:

September 20, 2010

Keywords:

nurse scheduling problem, many-objective optimization problem, assembling of objective functions, visualization

Abstract

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.

Cite this article as:

S. Otake, T. Yoshikawa, and T. Furuhashi, “Basic Study on Assembling of Objective Functions in Many-Objective Optimization Problems,” J. Adv. Comput. Intell. Intell. Inform., Vol.14 No.6, pp. 618-623, 2010.

Data files:

References

[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.

[1] [1] J. H. Holland, “Adaptation in Natural and Artificial Systems,” The Univ. Michigan Press, 1975.

[2] [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] [3] K. Deb, “Multi-Objective Optimization using Evolutionary Algorithms,” Chichester, UK, Wiley, 2001.

[4] [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] [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] [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] [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] [8] E. Cantú-Paz, “A Survey of Parallel Genetic Algorithms,” Calculateurs Paralleles, Vol.10, No.2, 1998.

[9] [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] [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] [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] [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] [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] [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] [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.