Hybrid greedy - Particle swarm optimization - Genetic algorithm and its convergence to solve multidimensional knapsack problem 0-1

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 20×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.