TY - GEN
T1 - Improvements to penalty-based evolutionary algorithms for the multi-dimensional knapsack problem using a gene-based adaptive mutation approach
AU - Uyar, Şima
AU - Eryiǧit, Gülşen
PY - 2005
Y1 - 2005
N2 - Knapsack problems are among the most common problems in literature tackled with evolutionary algorithms (EA). Their major advantage lies in the fact that they are relatively simple to implement while they allow generalizations for a wide range of real world problems. The multi-dimensional knapsack problem (MKP), which belongs to the class of NP-complete combinatorial optimization problems, is one of the variations of the knapsack problem. The MKP has a wide range of real world applications such as cargo loading, selecting projects to fund, budget management, cutting stock, etc. The MKP has been studied quite extensively in the EA community. Due to the constrained nature of the problem, constraint handling techniques gain great importance in the performance of the proposed EA approaches. In this study, the applicability of a generational EA that uses a penalty-based constraint handling technique and a gene locus based, asymmetric, adaptive mutation scheme is explored for the MKP. The effects of the parameters of the explored approach is determined through tests. Further experiments, using large MKP instances from commonly used benchmarks available through the Internet are performed. Comparison tables are given for the performance of the explored approach and other good performing EAs found in literature for the MKP. Results show that performance improves greatly when compared with other penalty-based techniques, but the explored approach is still not the best performer among all. However, unlike the explored technique, the EAs using the other constraint handling techniques require a great amount of extra computational effort and need heuristic information specific to the optimization problem. Based on these observations, and the fact that the performance difference between the explored scheme and the better performers is not too high, research on improving the explored approach is still in progress.
AB - Knapsack problems are among the most common problems in literature tackled with evolutionary algorithms (EA). Their major advantage lies in the fact that they are relatively simple to implement while they allow generalizations for a wide range of real world problems. The multi-dimensional knapsack problem (MKP), which belongs to the class of NP-complete combinatorial optimization problems, is one of the variations of the knapsack problem. The MKP has a wide range of real world applications such as cargo loading, selecting projects to fund, budget management, cutting stock, etc. The MKP has been studied quite extensively in the EA community. Due to the constrained nature of the problem, constraint handling techniques gain great importance in the performance of the proposed EA approaches. In this study, the applicability of a generational EA that uses a penalty-based constraint handling technique and a gene locus based, asymmetric, adaptive mutation scheme is explored for the MKP. The effects of the parameters of the explored approach is determined through tests. Further experiments, using large MKP instances from commonly used benchmarks available through the Internet are performed. Comparison tables are given for the performance of the explored approach and other good performing EAs found in literature for the MKP. Results show that performance improves greatly when compared with other penalty-based techniques, but the explored approach is still not the best performer among all. However, unlike the explored technique, the EAs using the other constraint handling techniques require a great amount of extra computational effort and need heuristic information specific to the optimization problem. Based on these observations, and the fact that the performance difference between the explored scheme and the better performers is not too high, research on improving the explored approach is still in progress.
KW - Adaptive mutation
KW - Genetic algorithms
KW - Multi-dimensional knapsack problem
KW - Penalty-based constraint handling
UR - http://www.scopus.com/inward/record.url?scp=32444444616&partnerID=8YFLogxK
U2 - 10.1145/1068009.1068214
DO - 10.1145/1068009.1068214
M3 - Conference contribution
AN - SCOPUS:32444444616
SN - 1595930108
T3 - GECCO 2005 - Genetic and Evolutionary Computation Conference
SP - 1257
EP - 1264
BT - GECCO 2005 - Genetic and Evolutionary Computation Conference
A2 - Beyer, H.G.
A2 - O'Reilly, U.M.
A2 - Arnold, D.
A2 - Banzhaf, W.
A2 - Blum, C.
A2 - Bonabeau, E.W.
A2 - Cantu-Paz, E.
A2 - Dasgupta, D.
A2 - Deb, K.
A2 - et al, al
T2 - GECCO 2005 - Genetic and Evolutionary Computation Conference
Y2 - 25 June 2005 through 29 June 2005
ER -