×

A fuzzy genetic algorithm based on binary encoding for solving multidimensional knapsack problems. (English) Zbl 1244.90257

Summary: The fundamental problem in genetic algorithms is premature convergence, and it is strongly related to the loss of genetic diversity of the population. This study aims at proposing some techniques to tackle the premature convergence by controlling the population diversity. Firstly, a sexual selection mechanism which utilizes the mate chromosome during selection is used. The second technique focuses on controlling the genetic parameters by applying the fuzzy logic controller. Computational experiments are conducted on the proposed techniques and the results are compared with other genetic operators, heuristics, and local search algorithms commonly used for solving multidimensional 0/1 knapsack problems published in the literature.

MSC:

90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
93C42 Fuzzy control/observation systems
90C27 Combinatorial optimization
90C09 Boolean programming

Software:

Knapsack; OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, Calif, USA, 1979. · Zbl 0411.68039
[2] J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, Ann Arbor, Mich, USA, 1975. · Zbl 0429.03045
[3] F. Herrera and M. Lozano, “Fuzzy genetic algorithms: issues and models,” Tech. Rep. DECSAI-98116, Department of Computer Science and A.I., University of Granada, 1998. · Zbl 0905.68116
[4] Y. H. Song, G. S. Wang, P. Y. Wang, and A. T. Johns, “Environmental/economic dispatch using fuzzy logic controlled genetic algorithms,” IEE Proceedings: Generation, Transmission and Distribution, vol. 144, no. 4, pp. 377-382, 1997.
[5] 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. · doi:10.1023/A:1023499201829
[6] R. Subbu, A. C. Sanderson, and P. P. Bonissone, “Fuzzy logic controlled genetic algorithms versus tuned genetic algorithms: an agile manufacturing application,” in Proceedings of the IEEE International Symposium on Intelligent Control (ISIC ’98), pp. 434-440, September 1998.
[7] Q. Li, X. Tong, S. Xie, and G. Liu, “An improved adaptive algorithm for controlling the probabilities of crossover and mutation based on a fuzzy control strategy,” in 6th International Conference on Hybrid Intelligent Systems and 4th Conference on Neuro-Computing and Evolving Intelligence (HIS-NCEI ’06), December 2006. · doi:10.1109/HIS.2006.264933
[8] 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.
[9] K. Wang, “A new fuzzy genetic algorithm based on population diversity,” in Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 108-112, 2001.
[10] H. Liu, Z. Xu, and A. Abraham, “Hybrid fuzzy-genetic algorithm approach for crew grouping,” in 5th International Conference on Intelligent Systems Design and Applications (ISDA ’05), pp. 332-337, September 2005. · doi:10.1109/ISDA.2005.51
[11] F. Herrera, E. Herrera-Viedma, M. Lozano, and J. L. Verdegay, “Fuzzy tools to improve genetic algorithms,” in Proceedings of the European Congress on Intelligent Techniques and soft Computing, pp. 1532-1539, 1994.
[12] F. Herrera and M. Lozano, “Adaptation of genetic algorithm parameters based on fuzzy logic controllers,” in Genetic Algorithms and Soft Computing, F. Herrera and J. L. Verdegay, Eds., pp. 95-125, Physica, 1996.
[13] F. Herrera and M. Lozano, “Fuzzy adaptive genetic algorithm: design, taxonomy, and future directions,” Soft Computing, vol. 7, no. 8, pp. 545-562, 2005.
[14] 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.
[15] 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. · doi:10.1007/s10015-008-0545-1
[16] M. Jalali Varnamkhasti and L. S. Lee, “Fuzzy genetic algorithm with sexual selection,” in Proceedings of the 2nd International Conference and Workshops on Basic and Applied Sciences and Regional Annual Fundamental Science Seminar, pp. 38-43, 2009.
[17] S. A. Jafari, S. Mashohor, and M. J. Varnamkhasti, “Committee neural networks with fuzzy genetic algorithm,” Journal of Petroleum Science and Engineering, vol. 76, no. 3-4, pp. 217-223, 2011. · doi:10.1016/j.petrol.2011.01.006
[18] 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. · doi:10.1109/21.286385
[19] K. Q. Zhu and Z. Liu, “Empirical study of population diversity in permutation-based genetic algorithm,” in Proceedings of the 15th European Conference on Machine Learning (ECML ’04), vol. 3103 of Lecture Notes in Computer Science, pp. 537-547, 2004. · Zbl 1132.68615
[20] M. Jalali Varnamkhasti, L. S. Lee, M. R. Abu Bakar, and W. J. Leong, “A genetic algorithm with fuzzy crossover operator and probability,” Advances in Operations Research, vol. 2012, Article ID 956498, 16 pages, 2012. · Zbl 1236.90150 · doi:10.1155/2012/956498
[21] 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 ’03), vol. 2690 of Lecture Notes in Computer Science, pp. 421-425, 2004.
[22] H. M. Voigt, J. Born, and I. Santibanez-Koref, “A multivalued evolutionary algorithm,” Tech. Rep. TR-93-022, International Computer Science Institute, Berkeley, Calif, USA, 1993.
[23] 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 International Conference on Parallel Problem Solving from Nature, vol. 496 of Lecture Notes in Comput. Sci., pp. 38-47, 1991.
[24] 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. · Zbl 1004.68538 · doi:10.1007/BF01530777
[25] G. Syswerda, “Uniform crossover in genetic algorithms,” in Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 2-9, 1989.
[26] 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, 1989. · Zbl 0709.68046
[27] S. Rajasekaran and G. A. Vijayalakshmi Pai, Neural Networks, Fuzzy Logic and Genetic Algorithms Synthesis and Application, PHL Learning Private Limited, New Dehli, India, 2008.
[28] J. J. Grefenstette, “Optimization of control parameters for genetic algorithms,” IEEE Transactions on Systems, Man and Cybernetics, vol. 16, no. 1, pp. 122-128, 1986.
[29] K. A. De Jong, Analysis of the behavior of a class of genetic adaptive systems, Ph.D. thesis, Department of Computer and Communication Sciences, University of Michigan, 1975.
[30] K. A. De Jong, “Adaptive system design: a genetic approach,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 10, no. 9, pp. 566-574, 1980. · doi:10.1109/TSMC.1980.4308561
[31] 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.
[32] J. D. Schaffer, R. A. Caruana, L. J. Eshelman, and R. Das, “A study of control parameters affecting online performance of genetic algorithms for function optimization,” in Proceedings of the 3rd International Conference Genetic Algorithms, pp. 51-60, 1989.
[33] D. Pisinger, “An expanding-core algorithm for the exact 0-1 knapsack problem,” European Journal of Operational Research, vol. 87, no. 1, pp. 175-187, 1995. · Zbl 0914.90199 · doi:10.1016/0377-2217(94)00013-3
[34] L. Davis, “Adapting operator probabilities in genetic algorithms,” in Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 91-69, 1989.
[35] C. Fernandes, R. Tavares, and A. Rosa, “niGAVaPS-outbreeding in genetic algorithms,” in Proceedings of the Symposium on Applied Computing (ACM ’00), pp. 477-482, 2000.
[36] 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.
[37] S. N. Sivanandam and S. N. Deepa, Introduction to Genetic Algorithms, Springer, Berlin, Germany, 2008. · Zbl 1129.90001
[38] M. Jalali Varnamkhasti, “A genetic algorithm based on new mutation for solving 0/1 knapsack problem,” Far East Journal of Mathematical Science, vol. 64, no. 1, pp. 23-35, 2012. · Zbl 1275.68132
[39] B. Gavish and H. Pirkul, “Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality,” Mathematical Programming, vol. 31, no. 1, pp. 78-105, 1985. · Zbl 0571.90065 · doi:10.1007/BF02591863
[40] S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Chichester, UK, 1990. · Zbl 0708.68002
[41] 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. · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[42] A. Freville and G. Plateau, “An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem,” Discrete Applied Mathematics, vol. 49, no. 1-3, pp. 189-212, 1994. · Zbl 0802.90077 · doi:10.1016/0166-218X(94)90209-7
[43] F. Djannaty and S. Doostdar, “A hybrid genetic algorithm for the multidimensional knapsack problem,” International Journal of Contemporary Mathematical Sciences, vol. 3, no. 9-12, pp. 443-456, 2008. · Zbl 1213.90178
[44] F. Qian and R. Ding, “Simulated annealing for the 0/1 multidimensional knapsack problem,” Numerical Mathematics, vol. 16, no. 4, pp. 320-327, 2007. · Zbl 1174.65420
[45] M. J. Magazine and O. Oguz, “A heuristic algorithm for the multidimensional zero-one knapsack problem,” European Journal of Operational Research, vol. 16, no. 3, pp. 319-326, 1984. · Zbl 0532.90070 · doi:10.1016/0377-2217(84)90286-8
[46] A. Volgenant and J. A. Zoon, “Improved heuristic for multidimensional 0-1 knapsack problems,” Journal of the Operational Research Society, vol. 41, no. 10, pp. 963-970, 1990. · Zbl 0724.90044 · doi:10.1057/jors.1990.148
[47] H. Pirkul, “A heuristic solution procedure for the multiconstrained zero-one knapsack problem,” Naval Research Logistics, vol. 34, no. 2, pp. 161-172, 1987. · Zbl 0609.90092 · doi:10.1002/1520-6750(198704)34:2<161::AID-NAV3220340203>3.0.CO;2-A
[48] J. E. Beasley, “OR-Library: distributing test problems by electronic mail,” Journal of the Operational Research Society, vol. 41, no. 11, pp. 1069-1072, 1990.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.