Constrained Optimization with Genetic Algorithms : Channel Routing Case
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人人工知能学会の論文
- 1996-05-01
著者
-
Ono Norihiko
Faculty Of Engineering University Of Tokushima
-
Rahmani Adel
Faculty of Engineering, University of Tokushima
-
Rahmani Adel
Faculty Of Engineering University Of Tokushima
関連論文
- Constrained Optimization with Genetic Algorithms : Channel Routing Case
- Distributed Self-organizing Agents Learning How to Communicate