A PARTHENO-GENETIC ALGORITHM FOR DYNAMIC 0-1 MULTIDIMENSIONAL KNAPSACK PROBLEM

被引：7
|
作者：
Unal, Ali Nadi [1 ]
Kayakutlu, Gulgun [2 ]
机构：
[1] Turkish Air Force Acad, Aeronaut & Space Technol Inst, Dept Ind Engn, TR-34149 Istanbul, Turkey
[2] Istanbul Tech Univ, Dept Ind Engn, TR-34367 Istanbul, Turkey
来源：
RAIRO-OPERATIONS RESEARCH | 2016年 / 50卷 / 01期
关键词：
Combinatorial optimization; dynamic environments; multidimensional knapsack problem; partheno-genetic algorithm; OPTIMIZATION; METAHEURISTICS;
D O I：
10.1051/ro/2015011
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
Multidimensional Knapsack problem (MKP) is a well/known, NP-hard combinatorial optimization problem. Several metaheuristics or exact algorithms have been proposed to solve stationary MKP. This study aims to solve this difficult problem with dynamic conditions, testing a new evolutionary algorithm. In the present study, the Partheno-genetic algorithm (PGA) is tested by evolving parameters in time. Originality of the study is based on comparing the performances in static and dynamic conditions. First the effectiveness of the PGA is tested on both the stationary, and the dynamic MKP. Then, the improvements with different random restarting schemes are observed. The PGA achievements are shown in statistical and graphical analysis.
引用
收藏
页码：47 / 66
页数：20
相关论文
共 50 条
  • [1] An partheno-genetic algorithm for multidimensional knapsack problem
    Bai, JC
    Chang, HY
    Yi, Y
    PROCEEDINGS OF 2005 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-9, 2005, : 2962 - 2965
  • [2] Knowledge-Based Genetic Algorithm for the 0-1 Multidimensional Knapsack Problem
    Rezoug, Abdellah
    Bader-El-Den, Mohamed
    Boughaci, Dalila
    2017 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2017, : 2030 - 2037
  • [3] 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
  • [4] Memetic Algorithm for Solving the 0-1 Multidimensional Knapsack Problem
    Rezoug, Abdellah
    Boughaci, Dalila
    Badr-El-Den, Mohamed
    PROGRESS IN ARTIFICIAL INTELLIGENCE-BK, 2015, 9273 : 298 - 304
  • [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