文章基本信息

标题：HYBRID GREEDY � PARTICLE SWARM OPTIMIZATION � GENETIC ALGORITHM AND ITS CONVERGENCE TO SOLVE MULTIDIMENSIONAL KNAPSACK PROBLEM 0-1
本地全文：下载
作者：FIDIA DENY TISNA A. ; SOBRI ABUSINI ; ARI ANDARI 等
期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2013
卷号：58
期号：3
出版社：Journal of Theoretical and Applied
摘要：In this research, we present a hybrid algorithm called Greedy � Particle Swarm Optimization � Genetic Algorithm (GPSOGA). This algorithm is based on greedy process, particle swarm optimization, and some genetic operators. Greedy algorithm is used as initial population, Particle Swarm Optimization (PSO) as main algorithm and Genetic Algorithm (GA) as support algorithm. Multidimensional knapsack problem 0-1 (MKP 0-1) will be used as test problem. To solve MKP 0-1, GPSOGA divided into 3 variants: GPSOGA (1), GPSOGA (2), and GPSOGA (3) based on criteria how they choose an initial solution in each algorithm. Then we will see which variant that is better to solve MKP 0-1, in term of the best solution ever known, the average of solution in each run, and the average of computational time. After running program individually, we can see that GPSOGA (3) is more suitable than GPSOGA (1) and GPSOGA (2) to solve MKP 0-1. Because it can solve the test problem more accurate, and have better average solution except in Data 2 and Data 3. We also provide convergence analysis to GPSOGA solution. So, it can be proved that GPSOGA solution is always convergent to global optimum and it can�t exceed the exact solution in solving MKP 0-1.
关键词：Genetic Algorithm; Greedy Algorithm; Multidimensional Knapsack Problem 0-1; Particle Swarm Optimization