Title :
A new method for solving 0/1 knapsack problem based on evolutionary algorithm with schema replaced
Author :
Li, Kangshun ; Jia, Yuzhen ; Zhang, Wensheng ; Xie, Yang
Author_Institution :
Sch. of Inf. Eng., Jiangxi Univ. of Sci. & Technol., Ganzhou
Abstract :
Knapsack problem is a typical NP complete problem. Knapsack problem correspondent mathematical model is proposed in this paper, and the evolutionary algorithm with schema replaced is raised. In this algorithm, it leads the search direction of the population by collecting the best several individuals to a schema. Because of that, the searching efficiency is improved. At last, the simulation experiment is given and the answer of the knapsack problem which is solved by simple evolutionary algorithm and the evolutionary algorithm with schema replaced two is compared. By this comparison, the advantage which use schema replaced to solve knapsack problem is proved.
Keywords :
computational complexity; evolutionary computation; knapsack problems; search problems; NP complete problem; evolutionary algorithm; knapsack problem; schema replaced; searching efficiency; Automation; Education; Evolutionary computation; Genetic mutations; Greedy algorithms; Logistics; Mathematical model; Simulated annealing; evolutionary algorithm; knapsack problem; schema replaced;
Conference_Titel :
Automation and Logistics, 2008. ICAL 2008. IEEE International Conference on
Conference_Location :
Qingdao
Print_ISBN :
978-1-4244-2502-0
Electronic_ISBN :
978-1-4244-2503-7
DOI :
10.1109/ICAL.2008.4636603
