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 条
  • [21] A minimal algorithm for the 0-1 Knapsack Problem
    Pisinger, D
    OPERATIONS RESEARCH, 1997, 45 (05) : 758 - 767
  • [22] EFFICIENT ALGORITHM FOR 0-1 KNAPSACK PROBLEM
    FAYARD, D
    PLATEAU, G
    MANAGEMENT SCIENCE, 1978, 24 (09) : 918 - 919
  • [23] Genetic algorithm based on Greedy strategy in the 0-1 Knapsack Problem
    Zhao, JiangFei
    Huang, Tinglei
    Pang, Fei
    Liu, YuanJie
    THIRD INTERNATIONAL CONFERENCE ON GENETIC AND EVOLUTIONARY COMPUTING, 2009, : 105 - 107
  • [24] The Modified Hybrid Adaptive Genetic Algorithm for 0-1 Knapsack Problem
    Ma, Yanqin
    PROCEEDINGS OF THE 2012 24TH CHINESE CONTROL AND DECISION CONFERENCE (CCDC), 2012, : 326 - 329
  • [25] A Partheno-genetic Algorithm for combinatorial optimization
    Li, MJ
    Fan, SS
    Luo, A
    NEURAL INFORMATION PROCESSING, 2004, 3316 : 224 - 229
  • [26] Migrating Birds Optimization (MBO) Algorithm to Solve 0-1 Multidimensional Knapsack Problem
    Tongur, Vahit
    Ulker, Erkan
    2017 INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND ENGINEERING (UBMK), 2017, : 786 - 789
  • [27] Improved convergent heuristics for the 0-1 multidimensional knapsack problem
    Hanafi, Said
    Wilbaut, Christophe
    ANNALS OF OPERATIONS RESEARCH, 2011, 183 (01) : 125 - 142
  • [28] A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem
    Yoon, Yourim
    Kim, Yong-Hyuk
    DISCRETE DYNAMICS IN NATURE AND SOCIETY, 2013, 2013
  • [29] 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
  • [30] The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects
    Arnaud Fréville
    SaÏd Hanafi
    Annals of Operations Research, 2005, 139 : 195 - 227
12345