Optimization with constraints using a cultured differential evolution approach

ABSTRACT

In this paper we propose a cultural algorithm, where different knowledge sources modify the variation operator of a differential evolution algorithm. Differential evolution is used as a basis for the population, variation and selection processes. The experiments performed show that the cultured differential evolution is able to reduce the number of fitness function evaluations needed to obtain a good aproximation of the optimum value in constrained real-parameter optimization. Comparisons are provided with respect to three techniques that are representative of the state-of-the-art in the area.

REFERENCES

• 1: Thomas Back , David B. Fogel , Zbigniew Michalewicz, Handbook of Evolutionary Computation, IOP Publishing Ltd., Bristol, UK, 1997
• 2: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 3: C.-J. Chung and R. G. Reynolds. A Testbed for Solving Optimization Problems using Cultural Algorithms. In L. J. Fogel, P. J. Angeline, and T. Bäck, editors, Evolutionary Programming V: Proceedings of the Fifth Annual Conference on Evolutionary Programming, Cambridge, Massachusetts, 1996. MIT Press.
• 4: C.-J. Chung and R. G. Reynolds. CAEP: An Evolution-based Tool for Real-Valued Function Optimization using Cultural Algorithms. Journal on Artificial Intelligence Tools, 7(3):239--292, 1998.
• 5: Carlos A. Coello Coello , Ricardo Landa Becerra, Adding Knowledge And Efficient Data Structures To Evolutionary Programming: A Cultural Algorithm For Constrained Optimization, Proceedings of the Genetic and Evolutionary Computation Conference, p.201-209, July 09-13, 2002
• 6: C. A. Coello Coello and R. Landa Becerra. Efficient Evolutionary Optimization through the use of a Cultural Algorithm. Engineering Optimization, 36(2):219--236, April 2004.
• 7: Gary B. Lamont , David A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: S. B. Hamida and M. Schoenauer. ASCHEA: New Results Using Adaptive Segregational Constraint Handling. In Proceedings of the Congress on Evolutionary Computation 2002 (CEC'2002), volume 1, pages 884--889, Piscataway, New Jersey, May 2002. IEEE Service Center.
• 10: R. Iacoban, R. G. Reynolds, and J. Brewster. Cultural Swarms: Modeling the Impact of Culture on Social Interaction and Problem Solving. In 2003 IEEE Swarm Intelligence Symposium Proceedings, pages 205--211, Indianapolis, Indiana, USA, April 2003. IEEE Service Center.
• 11: X. Jin and R. G. Reynolds. Using Knowledge-Based Evolutionary Computation to Solve Nonlinear Constraint Optimization Problems: a Cultural Algorithm Approach. In 1999 Congress on Evolutionary Computation, pages 1672--1678, Washington, D.C., July 1999. IEEE Service Center.
• 12: James Kennedy , Russell C. Eberhart, Swarm intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 13: S. Koziel and Z. Michalewicz. Evolutionary Algorithms, Homomorphous Mappings, and Constrained Parameter Optimization. Evolutionary Computation, 7(1):19--44, 1999.
• 14: J. Lampinen. Solving Problems Subject to Multiple Nonlinear Constraints by the Differential Evolution. In R. M. . P. Osmera, editor, Proceedings of MENDEL 2001, 7th International Conference on Soft Computing, pages 50--57, June 2001.
• 15: J. Lampinen. A Constraint Handling Approach for the Diifferential Evolution Algorithm. In Proceedings of the Congress on Evolutionary Computation 2002 (CEC'2002), volume 2, pages 1468--1473, Piscataway, New Jersey, May 2002. IEEE Service Center.
• 16: Y.-C. Lin, K.-S. Hwang, and F.-S. Wang. Hybrid Differential Evolution with Multiplier Updating Method for Nonlinear Constrained Optimization. In Proceedings of the Congress on Evolutionary Computation 2002 (CEC'2002), volume 1, pages 872--877, Piscataway, New Jersey, May 2002. IEEE Service Center.
• 17: Z. Michalewicz and M. Schoenauer. Evolutionary Algorithms for Constrained Parameter Optimization Problems. Evolutionary Computation, 4(1):1--32, 1996.
• 18: Ian C. Parmee , I. C. Parmee, Evolutionary and Adaptive Computing in Engineering Design: The Integration of Adaptive Search Exploration and Optimization with Engineering Design Pro, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 19: Kenneth V. Price, An introduction to differential evolution, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 20: R. G. Reynolds. An Introduction to Cultural Algorithms. In A. V. Sebald and L. J. Fogel, editors, Proceedings of the Third Annual Conference on Evolutionary Programming, pages 131--139. World Scientific, River Edge, New Jersey, 1994.
• 21: Robert G. Reynolds, Cultural algorithms: theory and applications, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 22: R. G. Reynolds, Z. Michalewicz, and M. Cavaretta. Using cultural algorithms for constraint handling in GENOCOP. In J. R. McDonnell, R. G. Reynolds, and D. B. Fogel, editors, Proceedings of the Fourth Annual Conference on Evolutionary Programming, pages 298--305. MIT Press, Cambridge, Massachusetts, 1995.
• 23: T. P. Runarsson and X. Yao. Stochastic Ranking for Constrained Evolutionary Optimization. IEEE Transactions on Evolutionary Computation, 4(3):284--294, September 2000.
• 24: Saleh M. Saleem , Robert G. Reynolds, Knowledge-based solution to dynamic optimization problems using cultural algorithms, 2001
• 25: R. Storn. On the Usage of Differential Evolution for Function Optimization. In 1996 Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS 1996), pages 519--523, Berkeley, 1996. IEEE.
• 26: R. Storn. System Design by Constraint Adaptation and Differential Evolution. IEEE Transactions on Evolutionary Computation, 3(1):22--34, April 1999.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

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

General Terms:
Algorithms, Design

Keywords:
constraint handling, cultural algorithms, differential evolution, optimization