Memetic Algorithm for Solving the 0-1 Multidimensional Knapsack Problem

被引：6

作者：

Rezoug, Abdellah ^{[1
]}

Boughaci, Dalila ^{[2
]}

Badr-El-Den, Mohamed ^{[3
]}

机构：

[1] Univ Mhamed Bougarra Boumerdes, Dept Comp Sci, Boumerdes, Algeria

[2] USTHB, Dept Comp Sci Beb Ezzouar, FEI, Algiers, Algeria

[3] Univ Portsmouth, Fac Technol, Sch Comp, Portsmouth, Hants, England

来源：

PROGRESS IN ARTIFICIAL INTELLIGENCE-BK | 2015年 / 9273卷

关键词：

Multidimensional knapsack problem; Stochastic local search; Genetic algorithm; Simulated annealing; Local search; Memetic algorithm; OPTIMIZATION;

D O I：

10.1007/978-3-319-23485-4_31

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper, we propose a memetic algorithm for the Multidimensional Knapsack Problem (MKP). First, we propose to combine a genetic algorithm with a stochastic local search (GA-SLS), then with a simulated annealing (GA-SA). The two proposed versions of our approach (GA-SLS and GA-SA) are implemented and evaluated on benchmarks to measure their performance. The experiments show that both GA-SLS and GA-SA are able to find competitive results compared to other well-known hybrid GA based approaches.

引用

页码：298 / 304

页数：7

共 50 条

[21] A flipping local search genetic algorithm for the multidimensional 0-1 knapsack problem
Alonso, Cesar L.
Caro, Fernando
Montana, Jose Luis
CURRENT TOPICS IN ARTIFICIAL INTELLIGENCE, 2006, 4177 : 21 - 30
[22] Hybrid binary Wolf pack algorithm for the 0-1 multidimensional knapsack problem
Li H.
Bai P.
Wu H.-S.
International Journal of Wireless and Mobile Computing, 2017, 12 (03) : 291 - 304
[23] A PARTHENO-GENETIC ALGORITHM FOR DYNAMIC 0-1 MULTIDIMENSIONAL KNAPSACK PROBLEM
Unal, Ali Nadi
Kayakutlu, Gulgun
RAIRO-OPERATIONS RESEARCH, 2016, 50 (01) : 47 - 66
[24] An improved method for solving the large-scale multidimensional 0-1 knapsack problem
Liu, Xu
Xiang, Fenghong
Mao, Jianlin
2014 INTERNATIONAL CONFERENCE ON ELECTRONICS AND COMMUNICATION SYSTEMS (ICECS), 2014,
[25] Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes
Pan, LQ
Martín-Vide, C
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2005, 65 (12) : 1578 - 1584
[26] Solving Multidimensional 0-1 Knapsack Problem by Tissue P Systems with Cell Division
He, Juanjuan
Miao, Zhengke
Zhang, Zheng
Shi, Xiaolong
2009 FOURTH INTERNATIONAL CONFERENCE ON BIO-INSPIRED COMPUTING: THEORIES AND APPLICATIONS, PROCEEDINGS, 2009, : 249 - +
[27] A HYBRID OF ROUGH SETS AND GENETIC ALGORITHMS FOR SOLVING THE 0-1 MULTIDIMENSIONAL KNAPSACK PROBLEM
Yang, Hsu-Hao
Wang, Ming-Tsung
Yang, Chung-Han
INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL, 2013, 9 (09): : 3537 - 3548
[28] EFFICIENT ALGORITHM FOR 0-1 KNAPSACK PROBLEM
NAUSS, RM
MANAGEMENT SCIENCE, 1976, 23 (01) : 27 - 31
[29] A minimal algorithm for the 0-1 Knapsack Problem
Pisinger, D
OPERATIONS RESEARCH, 1997, 45 (05) : 758 - 767
[30] EFFICIENT ALGORITHM FOR 0-1 KNAPSACK PROBLEM
FAYARD, D
PLATEAU, G
MANAGEMENT SCIENCE, 1978, 24 (09) : 918 - 919

← 1 2 3 4 5 →