Open Access0/1 Knapsack Problem using Diversity based Dual Population Genetic Algorithm
Author(s) -
A. J. Umbarkar,
Madhuri S. Joshi
Publication year - 2014
Publication title -
international journal of intelligent systems and applications
Language(s) - English
Resource type - Journals
eISSN - 2074-9058
pISSN - 2074-904X
DOI - 10.5815/ijisa.2014.10.05
Subject(s) - knapsack problem , continuous knapsack problem , polynomial time approximation scheme , computer science , genetic algorithm , mathematical optimization , population , convergence (economics) , dual (grammatical number) , algorithm , mathematics , art , demography , literature , sociology , economics , economic growth
The 0/1 Knapsack Problem is an optimization problem solved using various soft computing methods. The solution to the 0/1 Knapsack Problem (KP) can be viewed as the result of a sequence of decisions. Simple Genetic Algorithm (SGA) effectively solves knapsack problem for large data set. But it has problems like premature convergence and population diversity. Dual Population Genetic Algorithm (DPGA) is an improved version of Genetic Algorithm (GA) with the solution to above problems. This paper proposes Dual Population GA for solving 0/1 knapsack Problem. Experimental results of knapsack on SGA and DPGA are compared on standard as well as random data sets. The experimental result shows DPGA performs better than knapsack on SGA.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom