A new physarum-based hybrid optimization algorithm for solving 0/1 knapsack problem
Contribuinte(s) |
Hutchinson, David Kanade, Takeo Kittler, Josef Kleinberg, Jon M. Mattern, Friedemann Mitchell, John C. Naor, Moni Rangan, C. Pandu Steffen, Bernhard Terozopoulos, Demetri Tygar, Doug Weikum, Gerhard |
---|---|
Data(s) |
01/01/2015
|
Resumo |
As a typical NP-complete problem, 0/1 Knapsack Problem (KP), has been widely applied in many domains for solving practical problems. Although ant colony optimization (ACO) algorithms can obtain approximate solutions to 0/1 KP, there exist some shortcomings such as the low convergence rate, premature convergence and weak robustness. In order to get rid of the above-mentioned shortcomings, this paper proposes a new kind of Physarum-based hybrid optimization algorithm, denoted as PM-ACO, based on the critical paths reserved by Physarum-inspired mathematical (PM) model. By releasing additional pheromone to items that are on the important pipelines of PM model, PM-ACO algorithms can enhance item pheromone matrix and realize a positive feedback process of updating item pheromone. The experimental results in two different datasets show that PM-ACO algorithms have a stronger robustness and a higher convergence rate compared with traditional ACO algorithms. |
Identificador | |
Idioma(s) |
eng |
Publicador |
Springer |
Relação |
http://dro.deakin.edu.au/eserv/DU:30082178/zhang-anewphysarum-2015.pdf http://dro.deakin.edu.au/eserv/DU:30082178/zhang-anewphysarum-evid-2015.pdf http://www.dx.doi.org/10.1007/978-3-319-20472-7_26 |
Direitos |
2015, Springer |
Palavras-Chave | #0/1 Knapsack #Physarum-inspired model #ACO |
Tipo |
Book Chapter |