TY - GEN
T1 - A new Physarum-based hybrid optimization algorithm for solving 0/1 knapsack problem
AU - Chen, Shi
AU - Gao, Chao
AU - Zhang, Zili
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - 0/1 Knapsack
KW - ACO
KW - Physarum-inspired model
UR - http://www.scopus.com/inward/record.url?scp=84947723536&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-20472-7_26
DO - 10.1007/978-3-319-20472-7_26
M3 - 会议稿件
AN - SCOPUS:84947723536
SN - 9783319204710
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 238
EP - 246
BT - Advances in Swarm and Computational Intelligence - 6th International Conference, ICSI 2015 held in conjunction with the 2nd BRICS Congress, CCI 2015, Proceedings
A2 - Tan, Ying
A2 - Buarque, Fernando
A2 - Engelbrecht, Andries
A2 - Gelbukh, Alexander
A2 - Das, Swagatam
A2 - Shi, Yuhui
PB - Springer Verlag
T2 - 6th International Conference on Swarm Intelligence, ICSI 2015 held in conjunction with the 2nd BRICS Congress on Computational Intelligence, CCI 2015
Y2 - 25 June 2015 through 28 June 2015
ER -