Constrained Optimization with Genetic Algorithms: Channel Routing Case

• RAHMANI Adel Torkaman

  Faculty of Engineering, University of Tokushima

• ONO Norihiko

  Faculty of Engineering, University of Tokushima

抄録

This paper reports on the application of Genetic Algorithms (GAs) to constrained optimization problems. Genetic algorithms are general search methods inspired by the theory of evolution, i.e. natural selection and survival of fittest. They have successfully been applied to a variety of optimization problems, including numerical as well as combinatorial ones. Our main focus in this paper is to study the application of GAs to constrained combinatorial optimization. We review previous approaches to constrained optimization using genetic algorithms. We argue that none of these approaches are applicable to highly constrained optimization problems and suggest a more general approach which is incorporating domain - specific knowledge into general framework of genetic algorithm. By applying GA to a highly constrained design problem, we show how domain knowledge in the form of constraints could be effectively used to direct genetic search toward promising search states from which good solutions can be easily found. In particular, the Channel Routing Problem is considered. Channel Routing is one of the phases in physical design of VLSI chips. It is a highly constrained NP-complete problem. We propose a modified mutation operator, which incorporates problem specific information, that enables genetic algorithm to perform sustained search for the optimal solution in the most promising parts of the search space. Experimental results over a set of six test problems are presented and a comparison is made with another approach to the same problem.

収録刊行物

• 人工知能学会誌

  人工知能学会誌 11 (3), 461-469, 1996-05-01

  社団法人人工知能学会

キーワード

• constrained optimization
• genetic algorithms
• channel routing
• knowledge-based operators

詳細情報

• CRID: 1571980077101637760
• NII論文ID: 110002807949
• NII書誌ID: AN10067140
• ISSN: 09128085
• 本文言語コード: en
• データソース種別:
  • CiNii Articles