The performance of a genetic algorithm is dependent on the genetic operators, in general, and on the type of crossover operator, in particular. The population diversity is usually used as the performance measure for the premature convergence. In this paper, a fuzzy genetic algorithm is proposed for solving binary encoded combinatorial optimization problems. A new crossover operator and probability selection technique is proposed based on the population diversity using a fuzzy logic controller. The measurement of the population diversity is based on the genotype and phenotype properties. In this fuzzy inference system, the selection of the crossover operator and its probability are controlled by a set of fuzzy rules derived from the fuzzy logic controller. Extensive computational experiments are conducted on the proposed algorithm, and the results are compared with some crossover operators commonly used for solving multidimensional 0/1 knapsack problems published in the literature. The results indicate that the proposed algorithm is effective in finding better quality solutions. 1. Introduction Premature convergence is a common problem in finding the optimal solution in Genetic Algorithm (GA) and it is strongly related to the loss of the population diversity. When population diversity is low, a GA will converge very quickly. On the other hand, if the diversity of the population is too high, it is very time consuming for a GA to converge and this may cause wastage in computational resources. The performance of a GA is dependent on the genetic operators in general and on the type of crossover operator, in particular. During the evolution process by a GA, if the selected chromosomes are identical, some of the crossover operators have failed to create offspring that are different from their parents. Effective crossover in a GA is achieved through establishing the optimum relationship between the crossover and the search problem itself. In this paper, a fuzzy genetic algorithm (FGA) is proposed for solving binary encoded combinatorial optimization problems like the Multidimensional 0/1 Knapsack Problem (MKP). The aim is to design a crossover operator and probability selection technique based on the population diversity using Fuzzy Logic Controller (FLC). The diversity of the population is measured on the basis of the genotype and phenotype characteristics of the chromosomes. In addition, a new technique based on Hamming Distance (HD), Fitness Value (FV), and Active Genes (AG) of the mate chromosomes is proposed during the sexual selection. In recent years,
References
[1]
F. Djannaty and S. Doostdar, “A hybrid genetic algorithm for the multidimensional knapsack problem,” International Journal of Contemporary Mathematical Sciences, vol. 3, no. 9, pp. 443–456, 2008.
[2]
M. Tomassini, L. Vanneschi, F. Fernández, and G. Galeano, “A Study of Diversity in Multipopulation Genetic Programming,” in Proceedings of the Artificial Evolution, vol. 2936 of Lecture Notes in Computer Science, pp. 243–255, 2004.
[3]
R. W. Morrison and K. A. De Jong, “Measurement of population diversity,” in Proceedings of the Artificial Evolution, vol. 2310 of Lecture Notes in Computer Science, pp. 1047–1074, 2002.
[4]
M. Wineberg and F. Oppacher, “Distance between populations,” in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), vol. 2724 of Lecture Notes in Computer Science, pp. 1481–1492, 2003.
[5]
G. Sywerda, “Uniform crossover in genetic algorithms,” in Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 2–9, Morgan Kaufmann, 1989.
[6]
K. A. De Jong and W. M. Spears, “A formal analysis of the role of multi-point crossover in genetic algorithms,” Annals of Mathematics and Artificial Intelligence, vol. 5, no. 1, pp. 1–26, 1992.
[7]
K. A. De Jong and W. M. Spears, “An analysis of the interacting roles of population size and crossover in genetic algorithms,” in Proceedings of the Parallel Problem Solving from Nature, vol. 496 of Lecture Notes in Computer Science, pp. 38–47, 1991.
[8]
L. J. Eshelman, R. A. Caruana, and J. D. Schaffer, “Biases in the crossover landscape,” in Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 10–19, Morgan Kauffman, 1989.
[9]
D. E. Goldberg and K. Sastry, “A practical schema theorem for genetic algorithm design and tuning,” in Proceedings of the Genetic and Evolutionary Computation Conference, pp. 328–335, 2001.
[10]
L. Davis, “Adapting operator probabilities in genetic algorithms,” in Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 61–69, Morgan Kaufmann, 1989.
[11]
C. Fernandes, R. Tavares, and A. C. Rosa, “niGAVaPS—outbreeding in genetic algorithms,” in Proceedings of the Symposium on Applied Computing, (ACM '00), pp. 477–482, 2000.
[12]
M. Annunziato and S. Pizzuti, “Adaptive parameterization of evolutionary algorithms driven by reproduction and competition,” in Proceedings of the European Symposium on Intelligent Techniques, (ESIT '00), pp. 246–256, 2000.
[13]
M. Srinivas and L. M. Patnaik, “Adaptive probabilities of crossover and mutation in genetic algorithms,” IEEE Transactions on Systems, Man and Cybernetics, vol. 24, no. 4, pp. 656–667, 1994.
[14]
Y. J. Cao and Q. H. Wu, “Optimization of control parameters in genetic algorithms: a stochastic approach,” International Journal of Systems Science, vol. 30, no. 5, pp. 551–559, 1999.
[15]
T.-P. Hong, H-S. Wang, W-Y. Lin, and W-Y. Lee, “Evolution of appropriate crossover and mutation operators in a genetic process,” Applied Intelligence, vol. 16, no. 1, pp. 7–17, 2002.
[16]
Y. H. Song, G. S. Wang, P. Y. Wang, and A. T. Johns, “Environmental/economic dispatch using fuzzy logic controlled genetic algorithms,” in Proceedings of the Generation, Transmission and Distribution, vol. 144, no. 4, pp. 377–382, 1997.
[17]
Y. Yun and M. Gen, “Performance analysis of adaptive genetic algorithms with fuzzy logic and heuristics,” Fuzzy Optimization and Decision Making, vol. 2, no. 2, pp. 161–175, 2003.
[18]
Q. Li, D. Zheng, Y. Tang, and Z. Chen, “A new kind of fuzzy genetic algorithm,” Journal of University of Science and Technology Beijing, vol. 23, no. 1, pp. 85–89, 2001.
[19]
C.-H. Wang, T-P. Hong, and S-S. Tseng, “Integrating membership functions and fuzzy rule sets from multiple knowledge sources,” Fuzzy Sets and Systems, vol. 112, no. 1, pp. 141–154, 2000.
[20]
H. Liu, Z. Xu, and A. Abraham, “Hybrid fuzzy-genetic algorithm approach for crew grouping,” in Proceedings of the 5th International Conference on Intelligent Systems Design and Applications, (ISDA '05), pp. 332–337, September 2005.
[21]
M. A. Lee and H. Takagi, “Dynamic control of genetic algorithms using fuzzy logic techniques,” in Proceedings of the 5th International Conference on Genetic Algorithms, pp. 76–83, 1993.
[22]
M. A. Lee and H. Takagi, “Integrating design stages of fuzzy systems using genetic algorithms,” in Proceedings of the 2nd IEEE International Conference on Fuzzy System, pp. 612–617, April 1993.
[23]
S.-M. Im and J-J. Lee, “Adaptive crossover, mutation and selection using fuzzy system for genetic algorithms,” Artificial Life and Robotics, vol. 13, no. 1, pp. 129–133, 2008.
[24]
J. Botzheim, L. Gál, and L.T. Kóczy, “Fuzzy rule base model identification by bacterial memetic algoritms,” Recent Advances in Decision Making, vol. 222, pp. 21–43, 2009.
[25]
K. Q. Zhu and Z. Liu, “Population diversity in permutation-based genetic algorithm,” in Proceedings of the 15th European Conference on Machine Learning, (ECML '04), vol. 3201 of Lecture Notes in Computer Science, pp. 537–547, September 2004.
[26]
C. Jassadapakorn and P. Chongstitvatana, “Diversity control to improve convergence rate in genetic algorithms,” in Proceedings of the 4th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL 2003), vol. 2690 of Lecture Notes in Computer Science, pp. 421–425, 2003.
[27]
P. C. Chu and J. E. Beasley, “A genetic algorithm for the multidimensional knapsack problem,” Journal of Heuristics, vol. 4, no. 1, pp. 63–86, 1998.
[28]
M. J. Varnamkhasti and L. S. Lee, “A genetic algorithm based on sexual selection for the multidimensional 0/1 knapsack problems,” 10 pages, International Journal of Modern Physics: Conference Series . In press.
