Geodesic
A Partheno-Genetic Algorithm for Dynamic 0-1 Multidimensional Knapsack Problem
Ünal, Ali Nadi1 ; Kayakutlu, Gülgün2 
1 Turkish Air Force Academy, Aeronautics and Space Technologies Institute, Industrial Engineering Department, 34149 Yeşilyurt, İstanbul, Türkiye.
2 İstanbul Technical University, Industrial Engineering Department, 34367 Maçka, İstanbul, Türkiye.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 47-66

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ro/2015011
Classification : 90C27, 68T20
Keywords: Combinatorial optimization, dynamic environments, multidimensional knapsack problem, partheno-genetic algorithm

Ünal, Ali Nadi 1 ; Kayakutlu, Gülgün 2

1 Turkish Air Force Academy, Aeronautics and Space Technologies Institute, Industrial Engineering Department, 34149 Yeşilyurt, İstanbul, Türkiye.
2 İstanbul Technical University, Industrial Engineering Department, 34367 Maçka, İstanbul, Türkiye. 
@article{RO_2016__50_1_47_0,
     author = {\"Unal, Ali Nadi and Kayakutlu, G\"ulg\"un},
     title = {A {Partheno-Genetic} {Algorithm} for {Dynamic} 0-1 {Multidimensional} {Knapsack} {Problem}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {47--66},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ro/2015011},
     mrnumber = {3460662},
     zbl = {1333.90112},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2015011/}
}
TY  - JOUR
AU  - Ünal, Ali Nadi
AU  - Kayakutlu, Gülgün
TI  - A Partheno-Genetic Algorithm for Dynamic 0-1 Multidimensional Knapsack Problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 47
EP  - 66
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2015011/
DO  - 10.1051/ro/2015011
LA  - en
ID  - RO_2016__50_1_47_0
ER  - 
%0 Journal Article
%A Ünal, Ali Nadi
%A Kayakutlu, Gülgün
%T A Partheno-Genetic Algorithm for Dynamic 0-1 Multidimensional Knapsack Problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 47-66
%V 50
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2015011/
%R 10.1051/ro/2015011
%G en
%F RO_2016__50_1_47_0
Ünal, Ali Nadi; Kayakutlu, Gülgün. A Partheno-Genetic Algorithm for Dynamic 0-1 Multidimensional Knapsack Problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 47-66. doi: 10.1051/ro/2015011

Cité par Sources :