Date of Publication :16th August 2017
Abstract: Genetic Algorithms (GA) provide a simple method to solve complex optimization problems. The performance of a Genetic Algorithm mainly depends on the genetic parameters, operators and the fitness function used. This paper proposed an improved Genetic Algorithm to solve a NP-hard problem i.e. Knapsack problem. The Improved GA is implemented using C programming language. It gives better results when compared against an existing GA to solve the Knapsack Problem. This paper also proposes an optimal parameter setting for Knapsack Problem using GA.
Reference :
-
- Anabela Simoes, Ernesto Costa, “An Evolutionary Approach to the Zer/one Knapsak Problem: Testing Ideas from Biology”, Proceeding of fifth International Conference on Artificial Neural Networks and Genetic Algorithms Prague, Czech Republic, pp.22-25 April 2001.
- Christine L.Mumford, “Comparing Representations and Recombination operators for the multi-objective 0/1 Knapsack Problem”, 2003, pp.854-861, IEEE.
- Colin Reeves, “Genetic Algorithms”, chapter 3, pp. 55 82.
- David E.Goldberg, “Genetic Algorithms in Search, Optimization and Machine learning”, Addition Wesley, Reading, MA,1989.
- David E. Goldberg and Kalyanmoy Deb, “A comparative Anaysis of selection schemes used in Genetic Algorithms”, Foundations of Genetic Algorithms Edited by Gregory J.E. Rawlins, 1991, pp.69-92.
- Hristaheva, Maya and Shrestha Dipti, “Solving the 0-1 Knapsack Problem with Genetic Algorithms”.
- Khoa Duc Tran, “A survey of genetic algorithm parameters and their setting”,
- M. Srinivas, L.M. Patnaik,”Adaptive probabilities of Crossover and Mutation in genetic algorithms”, IEEE transactions on systems, man and cybernetics, vol.24, no. 4,April 1994, pp. 656-667.
- Onur Boyabatli, Ihsan Sabuncuoglu, “parameter selection in genetic algorithms”, Systematics, Cybernetics and Informatics, Vol. 2, No.4 , pp.78-83.
- Scott H. Doughlas,” Variations on a simple genetic algorithm”, Rochester Institute of technology, Rochester, NY.
- Siamak Sarmady,” An investigation on genetic algorithm parameters”.
- Stanley Gotshall, Bart Rylander,”Optimal population size and the genetic algorithm”, IEEE.
- Yu-an Zhang, Makoto Sakamoto, Hiroshi Furutani,” Effects of population size and Mutation rate on results of genetic algorithm”, Fourth international conference on Natural Computation, IEEE,2008.
- Yi Yang, Qian-sheng Fang,”The improved genetic algorithm for solving Knapsack Problem Based on HandelC”, IEEE.
- Grefenstette, John J., “Optimization of Control parameters for Genetic Algorithms”, IEEE Transactions on Systems, Man and Cybernetics, Vol. smc, No.1 pp.222-228, IEEE Lop number 5406073, 1986.