Article ID: | iaor19982568 |
Country: | United States |
Volume: | 8 |
Issue: | 2 |
Start Page Number: | 173 |
End Page Number: | 182 |
Publication Date: | Mar 1996 |
Journal: | INFORMS Journal On Computing |
Authors: | Tate David M., Smith Alice E., Coit David W. |
Keywords: | artificial intelligence, programming: integer |
The application of genetic algorithms (GA) to constrained optimization problems has been hindered by the inefficiencies of reproduction and mutation when feasibility of generated solutions is impossible to guarantee and feasible solutions are very difficult to find. Although several authors have suggested the use of both static and dynamic penalty functions for genetic search, this paper presents a general adaptive penalty technique which makes use of feedback obtained during the search along with a dynamic distance metric. The effectiveness of this method is illustrated on two diverse combinatorial applications: (1) the unequal-area, shape-constrained facility layout problem and (2) the series-parallel redundancy allocation problem to maximize system reliability given cost and weight constraints. The adaptive penalty function is shown to be robust with regard to random number seed, parameter settings, number and degree of constraints, and problem instance.