Acceso abierto

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


Cite

[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.10.1007/3-540-44503-X_27 Search in Google Scholar

[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.10.1016/j.cor.2009.02.027 Search in Google Scholar

[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.10.1080/00207540310001626319 Search in Google Scholar

[4] Bandyopadhyay S., Maulik U., An evolutionary technique based on K-Means algorithm for optimal clustering in RN, Information Sciences, 146, 2002, 221-237.10.1016/S0020-0255(02)00208-6 Search in Google Scholar

[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.10.3390/a10040123 Search in Google Scholar

[6] Chu P. C., Beasley J. E., A Genetic Algorithm for The Multidimensional Knapsack Problem, Journal of Heuristics, 4, 1998, 63-86.10.1023/A:1009642405419 Search in Google Scholar

[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.10.5962/bhl.title.82303 Search in Google Scholar

[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.10.1109/4235.850651 Search in Google Scholar

[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.1016/j.patrec.2011.07.011 Search in Google Scholar

[10] Friedman M., Comparison of Alternative Tests of Significance for the Problem of m Rankings, Annals of Mathematical Statistics, 11, 1940, 86-92.10.1214/aoms/1177731944 Search in Google Scholar

[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.10.1007/s10489-017-0972-6 Search in Google Scholar

[12] Goh K. S., Lim A., Rodrigues B., Sexual Selection for Genetic Algorithms, Artificial Intelligence Review, 19, 2003, 123-152.10.1023/A:1022692631328 Search in Google Scholar

[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. Search in Google Scholar

[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.10.1007/978-3-642-32584-7_3 Search in Google Scholar

[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.10.1016/j.knosys.2019.07.011 Search in Google Scholar

[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.10.1109/ICCCNT.2017.8204118 Search in Google Scholar

[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.10.11591/ijeecs.v13.i2.pp521-526 Search in Google Scholar

[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.10.1109/TSMCB.2003.81855715376846 Search in Google Scholar

[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.10.1007/978-1-4684-2001-2_9 Search in Google Scholar

[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. Search in Google Scholar

[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. Search in Google Scholar

[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.10.1007/s12652-020-02300-8 Search in Google Scholar

[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. Search in Google Scholar

[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.10.4236/ajor.2018.85023 Search in Google Scholar

[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.10.1108/EC-01-2019-0021 Search in Google Scholar

[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.10.1016/j.asoc.2006.10.012 Search in Google Scholar

[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. Search in Google Scholar

[28] Maulik U., Bandyopadhyay S., Genetic algorithm-based clustering technique, Pattern Recognition, 33, 2000, 1455-1465.10.1016/S0031-3203(99)00137-5 Search in Google Scholar

[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.10.1049/cp:19951076 Search in Google Scholar

[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.10.1016/j.procs.2015.03.185 Search in Google Scholar

[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.10.1109/TCYB.2020.298386032324588 Search in Google Scholar

[32] Torrente A., Romo J., Initializing k-means Clustering by Bootstrap and Data Depth, Journal of Classification, 38, 2021, 232–256.10.1007/s00357-020-09372-3 Search in Google Scholar

[33] Umbarkar A. J., Sheth P. D., Crossover Operators in Genetic Algorithms: A Review, ICTACT Journal on Soft Computing, 6, 2015, 1083-1092.10.21917/ijsc.2015.0150 Search in Google Scholar

[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.10.1142/S2010194512005508 Search in Google Scholar

[35] Wang L., Pan C., Robust level set image segmentation via a local correntropy-based K-means clustering, Pattern Recognition, 47, 2014, 1917-1925.10.1016/j.patcog.2013.11.014 Search in Google Scholar

[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.10.1007/978-3-540-92910-9_21 Search in Google Scholar

[37] Wilcoxon F., Individual Comparisons by Ranking Methods. Biometrics Bulletin, 1, 1945, 80-83.10.2307/3001968 Search in Google Scholar

[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. Search in Google Scholar

[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.10.1007/s00500-015-1681-x Search in Google Scholar

eISSN:
2300-3405
Idioma:
Inglés
Calendario de la edición:
4 veces al año
Temas de la revista:
Computer Sciences, Artificial Intelligence, Software Development