Summary

Proceedings of the 2012 International Symposium on Nonlinear Theory and its Applications

2012

Session Number:A4L-A

Session:

Number:219

Recycling Lethal Chromosomes Based on Immune Operation in Genetic Algorithm for Multi-Knapsack Problem

Jing Guo,  Jousuke Kuroiwa,  Hisakazu Ogura,  Izumi Suwa,  Haruhiko Shirai,  Tomohiro Odaka,  

pp.219-222

Publication Date:

Online ISSN:2188-5079

DOI:10.15248/proc.1.219

PDF download (553.6KB)

Summary:
In order to enhance GA's performance in solving constrained optimization problems, we proposed a recycling method of lethal chromosomes (LCs) in GA with a double island algorithm model based on an immune operation. The method revives LCs by applying vaccines abstracted from LCs. We apply our method into a multi-knapsack problem (MKP), which corresponds to a classic combinatorial problem. The exhaustive simulation results indicate that our method acts a superior performance of finding optimal solutions.

References:

[1] K. S. Tang, K. F. Man, S. Kwong, Q. He, “Genetic Algorithm and their Applications,” IEEE Signal Processing Magazine, vol.13, pp.22-37, 1996.

[2] I. Hitoshi, S. Nobuo, “The Influence of Lethal Gene on the Behavior of Genetic Algorithm,” Society of Instrument and Control Engineers, vol.31, pp.569-576, 1995.

[3] D. Pisinger, “An Exact Algorithm for Large Multiple Knapsack Problem,” European Journal of Operational Research, vol.114, pp.528-541, 1999.

[4] M. C. Xie, T. Yamaguchi, T. Odaka, H. Ogura, “An Analysis of Evolutionary States in the GA with Lethal Genes,” IEICE Trans. DII, vol.J79-D-II, pp.870-878, 1996.