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 条
  • [31] A modified hybrid rice optimization algorithm for solving 0-1 knapsack problem
    Zhe Shu
    Zhiwei Ye
    Xinlu Zong
    Shiqin Liu
    Daode Zhang
    Chunzhi Wang
    Mingwei Wang
    Applied Intelligence, 2022, 52 : 5751 - 5769
  • [32] Cognitive discrete gravitational search algorithm for solving 0-1 knapsack problem
    Razavi, Seyedeh Fatemeh
    Sajedi, Hedieh
    JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, 2015, 29 (05) : 2247 - 2258
  • [33] Solving the 0-1 Knapsack Problem with Polynomial-Time Quantum Algorithm
    Liu, Hongying
    Nie, Shuzhi
    COMMUNICATIONS AND INFORMATION PROCESSING, PT 2, 2012, 289 : 377 - +
  • [34] Solving 0-1 knapsack problem by a novel global harmony search algorithm
    Zou, Dexuan
    Gao, Liqun
    Li, Steven
    Wu, Jianhua
    APPLIED SOFT COMPUTING, 2011, 11 (02) : 1556 - 1564
  • [35] An improved particle swarm optimization algorithm for solving 0-1 knapsack problem
    Zhang, Guo-Li
    Wei, Yi
    PROCEEDINGS OF 2008 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-7, 2008, : 915 - +
  • [36] The Performance of the Modified Subgradient Algorithm on Solving the 0-1 Quadratic Knapsack Problem
    Sipahioglu, Aydin
    Sarac, Tugba
    INFORMATICA, 2009, 20 (02) : 293 - 304
  • [37] A novel quantum swarm evolutionary algorithm for solving 0-1 knapsack problem
    Wang, Y
    Feng, XY
    Huang, YX
    Zhou, WG
    Liang, YC
    Zhou, CG
    ADVANCES IN NATURAL COMPUTATION, PT 2, PROCEEDINGS, 2005, 3611 : 698 - 704
  • [38] Application of differential evolution algorithm for solving discounted {0-1} knapsack problem
    Zhang Guang-Tao
    Zhang Nan
    Zhang Jun
    PROCEEDINGS OF 2017 IEEE 2ND INFORMATION TECHNOLOGY, NETWORKING, ELECTRONIC AND AUTOMATION CONTROL CONFERENCE (ITNEC), 2017, : 1558 - 1561
  • [39] The performance of the modified subgradient algorithm on solving the 0-1 quadratic knapsack problem
    Sipahioglu, Aydin
    Sarac, Tugba
    20TH INTERNATIONAL CONFERENCE, EURO MINI CONFERENCE CONTINUOUS OPTIMIZATION AND KNOWLEDGE-BASED TECHNOLOGIES, EUROPT'2008, 2008, : 381 - 385
  • [40] A modified hybrid rice optimization algorithm for solving 0-1 knapsack problem
    Shu, Zhe
    Ye, Zhiwei
    Zong, Xinlu
    Liu, Shiqin
    Zhang, Daode
    Wang, Chunzhi
    Wang, Mingwei
    APPLIED INTELLIGENCE, 2022, 52 (05) : 5751 - 5769
12345