Optimization of performance of genetic algorithm for 0-1 knapsack problems using Taguchi method

Anagun A., Sarac T.

COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2006, PT 3, cilt.3982, ss.678-687, 2006 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 3982
  • Basım Tarihi: 2006
  • Dergi Adı: COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2006, PT 3
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Compendex, EMBASE, MathSciNet, Philosopher's Index, zbMATH
  • Sayfa Sayıları: ss.678-687
  • Eskişehir Osmangazi Üniversitesi Adresli: Evet

Özet

In this paper, a genetic algorithm (GA) is developed for solving 0-1 knapsack problems (KPs) and performance of the GA is optimized using Taguchi method (TM). In addition to population size, crossover rate, and mutation rate, three types of crossover operators and three types of reproduction operators are taken into account for solving different 0-1 KPs, each has differently configured in terms of size of the problem and the correlation among weights and profits of items. Three sizes and three types of instances are generated for 0-1 KPs and optimal values of the genetic operators for different types of instances are investigated by using TM. We discussed not only how to determine the significantly effective parameters for GA developed for 0-1 KPs using TM, but also trace how the optimum values of the parameters vary regarding to the structure of the problem.