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 条
  • [1] A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem
    Yoon, Yourim
    Kim, Yong-Hyuk
    DISCRETE DYNAMICS IN NATURE AND SOCIETY, 2013, 2013
  • [2] Solving Multidimensional 0-1 Knapsack Problem with an Artificial Fish Swarm Algorithm
    Azad, Md. Abul Kalam
    Rocha, Ana Maria A. C.
    Fernandes, Edite M. G. P.
    COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2012, PT III, 2012, 7335 : 72 - 86
  • [3] An new algorithm of solving 0-1 knapsack problem
    Tuo Shou-Heng
    2011 INTERNATIONAL CONFERENCE ON FUTURE COMPUTER SCIENCE AND APPLICATION (FCSA 2011), VOL 1, 2011, : 543 - 546
  • [4] A Novel Bat algorithm of solving 0-1 Knapsack Problem
    Chen, Yanfeng
    PROCEEDINGS OF THE 2016 4TH INTERNATIONAL CONFERENCE ON MACHINERY, MATERIALS AND COMPUTING TECHNOLOGY, 2016, 60 : 1598 - 1601
  • [5] Heuristics for the 0-1 multidimensional knapsack problem
    Boyer, V.
    Elkihel, M.
    El Baz, D.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 199 (03) : 658 - 664
  • [6] The multidimensional 0-1 knapsack problem:: An overview
    Fréville, A
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 155 (01) : 1 - 21
  • [7] A parallel Tabu Search algorithm for the 0-1 Multidimensional Knapsack Problem
    Niar, S
    Freville, A
    11TH INTERNATIONAL PARALLEL PROCESSING SYMPOSIUM, PROCEEDINGS, 1997, : 512 - 516
  • [8] An Artificial Bee Colony Algorithm for the 0-1 Multidimensional Knapsack Problem
    Sundar, Shyam
    Singh, Alok
    Rossi, Andre
    CONTEMPORARY COMPUTING, PT 1, 2010, 94 : 141 - +
  • [9] A Binary differential search algorithm for the 0-1 multidimensional knapsack problem
    Liu, Jianjun
    Wu, Changzhi
    Cao, Jiang
    Wang, Xiangyu
    Teo, Kok Lay
    APPLIED MATHEMATICAL MODELLING, 2016, 40 (23-24) : 9788 - 9805
  • [10] ALGORITHM FOR 0-1 KNAPSACK PROBLEM
    LAURIERE, M
    MATHEMATICAL PROGRAMMING, 1978, 14 (01) : 1 - 10
12345