On Solving 0/1 Multidimensional Knapsack Problem with a Genetic Algorithm Using a Selection Operator Based on K-Means Clustering Principle

• Autorzy: Laabadi Soukaina , Naimi Mohamed , Amri Hassan El , Achchab Boujemâa

Identyfikatory

DOI

10.2478/fcds-2022-0014

• Języki publikacji: EN

Abstrakty

EN

The growing need for profit maximization and cost minimization has made the optimization field very attractive to both researchers and practitioners. In fact, many authors were interested in this field and they have developed a large number of optimization algorithms to solve either academic or real-life problems. Among such algorithms, we cite a well-known metaheuristic called the genetic algorithm. This optimizer tool, as any algorithm, suffers from some drawbacks; like the problem of premature convergence. In this paper, we propose a new selection strategy hoping to avoid such a problem. The proposed selection operator is based on the principle of the k-means clustering method for the purpose of guiding the genetic algorithm to explore different regions of the search space. We have elaborated a genetic algorithm based on this new selection mechanism. We have then tested our algorithm on various data instances of the 0/1 multidimensional knapsack problem. The obtained results are encouraging when compared with those reached by other versions of genetic algorithms and those reached by an adapted version of the particle swarm optimization algorithm.

Słowa kluczowe

EN

genetic algorithm; K-Means Clustering Method; optimization; selection operators; 0/1 Multidimensional Knapsack Problem

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2022
• Tom: Vol. 47, No. 3
• Strony: 247--269
• Opis fizyczny: Bibliogr. 39 poz., rys., tab.

Twórcy

autor

Laabadi Soukaina

• Hassan II University, Teacher's Training College (ENS), Casablanca, Morocco

autor

Naimi Mohamed

• Hassan First University, National School of Applied Sciences (ENSA), Berrechid, Morocco

autor

Amri Hassan El

• Hassan II University, Teacher's Training College (ENS), Casablanca, Morocco

autor

Achchab Boujemâa

• Hassan First University, National School of Applied Sciences (ENSA), Berrechid, Morocco

Bibliografia

• [1] Aggarwal C. C., Hinneburg A., Keim D. A., On the Surprising Behavior of Distance Metrics in High Dimensional Space, in: Proceedings of the 8th International Conference on Database Theory, London, UK, Springer, 2001, 420-434.
• [2] Aghezzaf B., Naimi M., The two-stage recombination operator and its application to the multiobjective 0/1 knapsack problem: A comparative study, Computers and Operations Research, 36, 2009, 3247-3262.
• [3] Aytug H., Khouja M., Vergara F. E., Use of genetic algorithms to solve production and operations management problems: A review, International Journal of Production Research, 41, 2003, 3955-4009.
• [4] Bandyopadhyay S., Maulik U., An evolutionary technique based on K-Means algorithm for optimal clustering in RN, Information Sciences, 146, 2002, 221-237.
• [5] Chehouri A., Younes R., Khoder J., Perron J., Ilinca A., A Selection Process for Genetic Algorithm Using Clustering Analysis, Algorithms, 10, 2017, Article No. 123.
• [6] Chu P. C., Beasley J. E., A Genetic Algorithm for The Multidimensional Knapsack Problem, Journal of Heuristics, 4, 1998, 63-86.
• [7] Darwin C., On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life, John Murray Publishers, London, 1859.
• [8] Dimopoulos C., Zalzala A. M. S., Recent developments in evolutionary computation for manufacturing optimization: problems, solutions, and comparisons, IEEE Transactions on Evolutionary Computation, 4, 2000, 93-113.
• [9] Erisoglu M., Calis N., Sakallioglu S., A new algorithm for initial cluster centers in k-means algorithm, Pattern Recognition Letters, 32, 2011, 1701-1705.
• [10] Friedman M., Comparison of Alternative Tests of Significance for the Problem of m Rankings, Annals of Mathematical Statistics, 11, 1940, 86-92.
• [11] García J., Crawford B., Soto R., Castro C., Paredes F., A k-means binarization framework applied to multidimensional knapsack problem, Applied Intelligence, 48, 2018, 357-380.
• [12] Goh K. S., Lim A., Rodrigues B., Sexual Selection for Genetic Algorithms, Artificial Intelligence Review, 19, 2003, 123-152.
• [13] Goldberg D. E., Lingle R., Alleles, Loci, and the Traveling Salesman Problem, in: Proceedings of the First International Conference on Genetic Algorithms and their Applications, Los Angeles, US, Lawrence Erlbaum Associates Publishers, 1985, 154-159.
• [14] Golfarelli M., Rizzi S., Turricchia E., Sprint Planning Optimization in Agile Data Warehouse Design, in: Proceedings of the 14th International Conference on Data Warehousing and Knowledge Discovery, Vienna, Austria, Springer, 2012, 30-41.
• [15] Gong G., Deng Q., Chiong R., Gong X., Huang H., An effective memetic algorithm for multi-objective job-shop scheduling, Knowledge-Based Systems, 182, 2019, Article No. 104840.
• [16] Gupta I. K., Choubey A., Choubey S., Clustered genetic algorithm to solve multidimensional knapsack problem, in: Proceedings of the 8th International Conference on Computing, Communication and Networking Technologies, Delhi, India, IEEE, 2017, 1-6.
• [17] Hossain M. Z., Akhtar M. N., Ahmad R. B., Rahman M., A dynamic K-means clustering for data mining, Indonesian Journal of Electrical Engineering and Computer Science, 13, 2019, 521-526.
• [18] Juang C. F., A hybrid of genetic algorithm and particle swarm optimization for recurrent network design, IEEE Transactions on Systems, Man, and Cybernetics, 34, 2004, 997-1006.
• [19] Karp R. M., Reducibility among Combinatorial Problems, in: R.E. Miller, J.W. Thatcher, J.D. Bohlinger (Eds.), Complexity of Computer Computations, Springer, Boston, 1972, 85-103.
• [20] Kennedy J., Eberhart R. C., A discrete binary version of the particle swarm algorithm, in: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, 5, 1997, 4104-4108.
• [21] Khalili-Damghani K., Taghavifard M., Solving a bi-objective project capital budgeting problem using a fuzzy multi-dimensional knapsack, Journal of Industrial Engineering International, 7, 2011, 67-73.
• [22] Krishnakumar S., Manivannan K., Effective segmentation and classification of brain tumor using rough K means algorithm and multi kernel SVM in MR images, Journal of Ambient Intelligence and Humanized Computing, 12, 2021, 6751–6760.
• [23] Laabadi S., Naimi M., El Amri H., Achchab B., A hybrid genetic algorithm for solving 0/1 Knapsack Problem, in: Proceedings of the First International Conference on Learning and Optimization Algorithms: Theory and Applications, Rabat, Morocco, ACM, 2018, Article No. 51.
• [24] Laabadi S., Naimi M., El Amri H., Achchab B., The 0/1 Multidimensional Knapsack Problem and Its Variants: A Survey of Practical Models and Heuristic Approaches, American Journal of Operations Research, 8, 2018, 395-439.
• [25] Laabadi S., Naimi M., El Amri H., Achchab B., An improved sexual genetic algorithm for solving 0/1 multidimensional knapsack problem, Engineering Computations, 36, 2019, 2260-2292.
• [26] Lee Z. J., Su S. F., Chuang C. C., Liu K. H., Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment, Applied Soft Computing, 8, 2008, 55-78.
• [27] MacQueen J., Some Methods for Classification and Analysis of Multivariate Observations, in: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, San Francisco, US, University of California Press, 1967, 281-297. [28] Maulik U., Bandyopadhyay S., Genetic algorithm-based clustering technique, Pattern Recognition, 33, 2000, 1455-1465.
• [29] Rudolph G., Sprave J., A Cellular Genetic Algorithm with Self-adjusting Acceptance Threshold, in: Proceedings of the First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, Sheffield, UK, IEEE, 1995, 365–372.
• [30] Santhanam T., Padmavathi M. S., Application of K-Means and Genetic Algorithms for Dimension Reduction by Integrating SVM for Diabetes Diagnosis, Procedia Computer Science, 47, 2015, 76-83.
• [31] Sun Y., Xue B., Zhang M., Yen G. G., Lv J., Automatically Designing CNN Architectures Using the Genetic Algorithm for Image Classification, IEEE Transactions on Cybernetics, 50, 2020, 3840-3854.
• [32] Torrente A., Romo J., Initializing k-means Clustering by Bootstrap and Data Depth, Journal of Classification, 38, 2021, 232–256.
• [33] Umbarkar A. J., Sheth P. D., Crossover Operators in Genetic Algorithms: A Review, ICTACT Journal on Soft Computing, 6, 2015, 1083-1092.
• [34] Varnamkhasti M. J., Lee L. S., A Genetic Algorithm Based on Sexual Selection for The Multidimensional 0/1 Knapsack Problems, International Journal of Modern Physics: Conference Series, 9, 2012, 422-431.
• [35] Wang L., Pan C., Robust level set image segmentation via a local correntropy-based K-means clustering, Pattern Recognition, 47, 2014, 1917-1925.
• [36] Whitley D., Sutton A. M., Genetic Algorithms - A Survey of Models and Methods, in: G. Rozenberg, T. Bäck, J.N. Kok (Eds.), Handbook of Natural Computing, Springer, Berlin, 2012, 637-671.
• [37] Wilcoxon F., Individual Comparisons by Ranking Methods. Biometrics Bulletin, 1, 1945, 80-83.
• [38] Yang H. H, Wang M. T, Yang C. H., A Hybrid of Rough Sets and Genetic Algorithms for Solving the 0-1 Multidimensional Knapsack Problem, International Journal of Innovative Computing, Information and Control, 9, 2013, 3537-3548.
• [39] Zouache D., Nouioua F., Moussaoui A., Quantum-inspired firefly algorithm with particle swarm optimization for discrete optimization problems, Soft Computing, 20, 2016, 2781-2799.