A Genetic Algorithm for Solving Knapsack Problems Based on Adaptive Evolution in Dual Population

Abstract:

In order to solve knapsack problems efficiently, an improved genetic algorithm based on adaptive evolution in dual population (called DPAGA) is proposed. In DPAGA, the new population produced by selecting operation is regarded as main population. The population composed by the individuals washed out by selecting operation is regarded as subordinate population. The individual evolution strategy of main population is different from that of subordinate population. The crossover operators and mutation operators are all adjusted non-linearly and adaptively. DPAGA is used to solve knapsack problems. The experimental results show that its convergence speed and solution quality are all better then that of simple genetic algorithm. It is also suited to solve other optimization problems.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 2799-2802
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.2799
• Online since: September 2013
• Authors: Tai Shan Yan, Guan Qi Guo, Hong Min Li, Wei He
• Keywords: Adaptive Evalution, Dual Population, Genetic Algorithm (GA), Knapsack Problem

References

[1] Lee Hae Sang, Lie Chang Hoon. A computation method for evaluating importance-measures of Gates in a fault tree. I EEE Trans. on Reliability , 1997 , 46 (3) : 360 – 365.

DOI: 10.1109/24.664007

[2] WANG Li, SHAO Ding-hong, LU Jin-gui. The Genetic Algorithm of Solving 0/1knapsack Problem. Computer Simulation, 1998, 23(3): 154～156.

[3] LI Kenli, LI Qinghua. An Adaptive algorithm for knapsack problem. Computer research and development, 2004, 7(41): 1292-1297.

[4] ZHU Xiaorong, ZHANG Xinghua. A quantum genetic algorithm with repair function and its application in knapsack question. Computer pplications, 2007, 22(5): 1187-1190.

[5] HUANG Xiyue, ZHANG Zhuhong. Morden intelligent algorithm - theory and application. Beijing: Science Publishing Company, (2005).