AMGA: an archive-based micro genetic algorithm for multi-objective optimization

ABSTRACT

In this paper, we propose a new evolutionary algorithm for multi-objective optimization. The proposed algorithm benefits from the existing literature and borrows several concepts from existing multi-objective optimization algorithms. The proposed algorithm employs a new kind of selection procedure which benefits from the search history of the algorithm and attempts to minimize the number of function evaluations required to achieve the desired convergence. The proposed algorithm works with a very small population size and maintains an archive of best and diverse solutions obtained so as to report a large number of non-dominated solutions at the end of the simulation. Improved formulation for some of the existing diversity preservation techniques is also proposed. Certain implementation aspects that facilitate better performance of the algorithm are discussed. Comprehensive benchmarking and comparison of the proposed algorithm with some of the state-of-the-art multi-objective evolutionary algorithms demonstrate the improved search capability of the proposed algorithm.

REFERENCES

• 1: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 2: R. Dawkins. The Selfish Gene. Oxford University Press, New York, 1976.
• 3: N. Eldredge. Macro-Evolutionary Dynamics: Species, Niches and Adaptive Peaks. McGraw-Hill, New York, 1989.
• 4: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 5: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 6: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 7: C. A. Coello. A comprehensive survey of evolutionary-based multiobjective optimization techniques. Knowledge Information Systems, 1(3):269--308, 1999.
• 8: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization. In Proceedings of the EUROGEN2001 Conference, pages 95--100, 2001.
• 9: David Corne , Joshua D. Knowles , Martin J. Oates, The Pareto Envelope-Based Selection Algorithm for Multi-objective Optimisation, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.839-848, September 18-20, 2000
• 10: K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182--197, 2002.
• 11: S. Watanabe, T. Hiroyasu, and M. Miki. NCGA: Neighborhood cultivation genetic algorithm for multi-objective optimization problems. In Proceedings of the Genetic and Evolutionary Computation Conference GECCO 2002, pages 458--465, 2002.
• 12: G. G. Yen and L. Haiming. Dynamic multiobjective evolutionary algorithm: adaptive cell-based rank and density estimation. IEEE Transactions on Evolutionary Computation, 7(3):253--274, June 2003.
• 13: M. Kim, T. Hiroyasu, and M. Mikiand S. Watanabe. SPEA2+: Improving the performance of the strength pareto evolutionary algorithm 2. In Parallel Problem Solving from Nature PPSN VIII, pages 742--751, 2004.
• 14: S. Y. Ho, L. S. Shu, and J. H. Chen. Intelligent evolutionary algorithms for large parameter optimization problems. IEEE Transactions on Evolutionary Computation, 8(6):522--541, 2004.
• 15: Kalyanmoy Deb , Manikanth Mohan , Shikhar Mishra, Evaluating the ε-Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions, Evolutionary Computation, v.13 n.4, p.501-525, December 2005 [doi>10.1162/106365605774666895]
• 16: K. Deb and S. Tiwari. Omni-optimizer, a generic evolutionary algorithm for single and multi-objective optimization. European Journal of Operational Research, 185(3):1062--1087, 2008.
• 17: H. Eskandari, C. D. Geiger, and G. B. Lamont. Fastpga: A dynamic population sizing approach for solving expensive multiobjective optimization problems. In Evolutionary Multiobjective Optimization Conference EMO-2007, pages 141--155. LNCS 4403 Springer-Verlag Berlin Heidelberg, 2007.
• 18: Y. Sensor. Pareto optimality in multi-objective problems. Applied Mathematics and Optimization, 4(1):41--59, March 1977.
• 19: Y. Sensor. Pareto optimality in multi-objective problems. Applied Mathematics and Optimization, 4(1):41--59, March 1977.
• 20: S. Kukkonen and K. Deb. Improved pruning of non-dominated solutions based on crowding distance for bi-objective optimization problems. Technical Report 7, Indian Institute of Technology Kanpur, India, 2006.
• 21: S. Kukkonen and K. Deb. A fast and effective method for pruning of non-dominated solutions in many-objective problems. Technical Report 4, Indian Institute of Technology Kanpur, India, 2007.
• 22: K. Deb and R. B. Agrawal. Simulated binary crossover for continuous search space. Complex Systems, 9(2):115--148, 1995.
• 23: K. Deb and M. Goyal. A combined genetic adaptive search (geneas) for engineering design. Computer Science and Informatics, 26(4):30--45, 1996.
• 24: M. T. Jenson. Reducing the run-time complexity of multiobjective eas: The nsga-ii and other algorithms. IEEE Transactions on Evolutionary Computation, 7(5):503--515, 2003.
• 25: Juan J. Durillo, Antonio J. Nebro, Francisco Luna, Bernabe Dorronsoro, and Enrique Alba. jmetal: a java framework for developing multi-objective optimization metaheuristics. Technical report, E. T. s. Ingenieria Informatica Campus de Teatinos 29071 Malaga Spain, 2006.
• 26: K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable multi-objective optimization problems. In Proceedings of IEEE Congress on Evolutionary Computation, volume 1, pages 825{830, Honolulu, HI, USA, 12--17 May 2002.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
diversity preservation, evolutionary algorithms, micro-genetic algorithm, multi-objective optimization