Communications - Scientific Letters of the University of Zilina 2021, 23(1):E1-E10 | DOI: 10.26552/com.C.2021.1.E1-E10

Improving Initial Population for Genetic Algorithm using the Multi Linear Regression Based Technique (MLRBT)

Esra'a Alkafaween ORCID...1, Ahmad B. A. Hassanat ORCID...2, Sakher Tarawneh ORCID...3
1 IT Department, Mutah University, Karak, Jordan
2 IT Department, Mutah University, Karak, Jordan and Computer Science Department, Community College, University of Tabuk, Tabuk, Saudi Arabia and Industrial Innovation and Robotics Center, University of Tabuk, Tabuk, Saudi Arabia
3 Industrial Innovation and Robotics Center, University of Tabuk, Tabuk, Saudi Arabia

Genetic algorithms (GAs) are powerful heuristic search techniques that are used successfully to solve problems for many different applications. Seeding the initial population is considered as the first step of the GAs.

In this work, a new method is proposed, for the initial population seeding called the Multi Linear Regression Based Technique (MLRBT). That method divides a given large scale TSP problem into smaller sub-problems and the technique works frequently until the sub-problem size is very small, four cities or less. Experiments were carried out using the well-known Travelling Salesman Problem (TSP) instances and they showed promising results in improving the GAs' performance to solve the TSP.

Keywords: genetic algorithm; population seeding; TSP; multi linear regression

Received: March 9, 2020; Accepted: May 11, 2020; Prepublished online: October 20, 2020; Published: January 4, 2021  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Alkafaween, E., Hassanat, A.B.A., & Tarawneh, S. (2021). Improving Initial Population for Genetic Algorithm using the Multi Linear Regression Based Technique (MLRBT). Communications - Scientific Letters of the University of Zilina, 23(1), E1-10. doi: 10.26552/com.C.2021.1.E1-E10
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. HENDRICKS, D., GEBBIE, T., WILCOX, D. High-speed detection of emergent market clustering via an unsupervised parallel genetic algorithm. South African Journal of Science [online]. 2016, 112(1/2), p. 1-9. eISSN 1996-7489. Available from: https://doi.org/10.17159/sajs.2016/20140340 Go to original source...
    2. GOLBERG, D. E. Genetic algorithms in search, optimization, and machine learning. Boston: Addion - Wesley Longman Publishing Co., 1989. ISBN 978-0-201-15767-3.
    3. MOHAMMED, A. A., NAGIB, G. Optimal routing in Ad-Hoc network using genetic algorithm. International Journal of Advanced Networking and Applications. 2012, 3(5), p. 1323-1328. ISSN 0975-0290, eISSN 0975-0282.
    4. AYALA, H. V. H., DOS SANTOS COELHO, L. Tuning of PID controller based on a multiobjective genetic algorithm applied to a robotic manipulator. Expert Systems with Applications [online]. 2012, 39(10), p. 8968-8974. ISSN 0957-4174. Available from: https://doi.org/10.1016/j.eswa.2012.02.027 Go to original source...
    5. HOLLAND, J. H. Genetic algorithms. Scientific American [online]. 1992, 267(1), p. 66-72. ISSN 0036-8733. Available from: http://dx.doi.org/10.1038/scientificamerican0792-66 Go to original source...
    6. EIBEN, A. E., SMITH, J. E. Introduction to evolutionary computing [online]. Berlin Heidelberg: Springer Science & Business Media, 2003. ISBN 978-3-642-07285-7, eISBN 978-3-662-05094-1. Available from: https://doi.org/10.1007/978-3-662-05094-1 Go to original source...
    7. GENDREAU, M., POTVIN, J.-Y. Handbook of metaheuristics. Vol. 2. Springer International Publishing, 2010. ISBN 978-1-4419-1663-1. Go to original source...
    8. HASSANAT, A., ALMOHAMMADI, K., ALKAFAWEEN, E., ABUNAWAS, E., HAMMOURI, A., PRASATH, V. B. Choosing mutation and crossover ratios for genetic algorithms - a review with a new dynamic approach. Information [online]. 2019, 10(12), 390. ISSN ‫‏‬2078-2489. Available from: https://doi.org/10.3390/info10120390 Go to original source...
    9. HASSANAT, A. B., ALKAFAWEEN, E. A., AL-NAWAISEH, N. A., ABBADI, M. A., ALKASASSBEH, M., ALHASANAT, M. B. Enhancing genetic algorithms using multi mutations: experimental results on the travelling salesman problem. International Journal of Computer Science and Information Security. 2016, 14(7), p. 785-801. ISSN 1947-5500. Go to original source...
    10. HUSSAIN, A., MUHAMMAD, Y. S., SAJID, M. N. A simulated study of genetic algorithm with a new crossover operator using traveling salesman problem. Journal of Mathematics. 2019, 51(5), p. 61-77. ISSN 1016-2526.
    11. ZHONG, J., HU, X., GU, M., ZHANG, J. Comparison of performance between different selection strategies on simple genetic algorithms. In: International Conference on Computational Intelligence for Modelling, Control and Automation CIMCA '05 and International Conference on Intelligent Agents, Web Technologies and Internet Commerce CIMCA-IAWTIC'06: proceedings. Vol. 2. 2005. p. 1115-1121.
    12. ALKAFAWEEN, E., HASSANAT, A. Improving TSP solutions using GA with a new hybrid mutation based on knowledge and randomness. arXiv preprint arXiv:1801.07233. 2018.
    13. HASSANAT, A., ALKAFAWEEN, E. On enhancing genetic algorithms using new crossovers. International Journal of Computer Applications in Technology [online]. 2017, 55(3), p. 202-212. ISSN 0952-8091. Available from: https://doi.org/10.1504/IJCAT.2017.10005868 Go to original source...
    14. ALKAFAWEEN, E. O. Novel methods for enhancing the performance of genetic algorithms. Master's degree thesis. Karak: Mutah University, 2018.
    15. VEDAT, T., DALOGLU, A. T. An improved genetic algorithm with initial population strategy and self-adaptive member grouping. Computers and Structures [online]. 2008, 86(11-12), p. 1204-1218. ISSN 0045-7949. Available from: https://doi.org/10.1016/j.compstruc.2007.11.006 Go to original source...
    16. YUGAY, O., KIM, I., KIM, B., KO, F. I. Hybrid genetic algorithm for solving traveling salesman problem with sorted population. In: 3rd International Conference on Convergence and Hybrid Information Technology: proceedings [online]. IEEE, 2008. ISBN 978-0-7695-3407-7. Available from: https://doi.org/10.1109/ICCIT.2008.373 Go to original source...
    17. WAGSTAFF, K., CARDIE, C., ROGERS, S., SCHRODL, S. Constrained K-means clustering with background knowledge. In: 8th International Conference on Machine Learning ICML'01: proceedings. 2001. p. 577-584.
    18. WEI, Y., HU, Y., GU, K. Parallel search strategies for TSPs using a greedy genetic algorithm. In: 3rd International Conference on Natural Computation ICNC 2007: proceedings [online]. Vol. 3. IEEE, 2007. Available from: https://doi.org/10.1109/ICNC.2007.537 Go to original source...
    19. RAY, S. S., BANDYOPADHYAY, S., PAL, S. K. Genetic operators for combinatorial optimization in TSP and microarray gene ordering. Applied Intelligence [online]. 2007, 26(3), p. 183-195. ISSN 0924-669X, eISSN 1573-7497. Available from: https://doi.org/10.1007/s10489-006-0018-y Go to original source...
    20. PAUL, P. V., RAMALINGAM, A., BASKARAN, R., DHAVACHELVAN, P., VIVEKANANDAN, K., SUBRAMANIAN, R., VENKATACHALAPATHY, V. Performance analyses on population seeding techniques for genetic algorithms. IJET International Journal of Engineering and Technology. 2013, 5(3), p. 2993-3000. ISSN 2319-8613, eISSN 0975-4024.
    21. CHANG, D.-X., ZHANG, X.-D., ZHENG, C.-W. A genetic algorithm with gene rearrangement for K-means clustering, Pattern Recognition. 2009, 42(7), p. 1210-1222. ISSN 0031-3203. Available from: https://doi.org/10.1016/j.patcog.2008.11.006. Go to original source...
    22. SALLABI, O. M., EL-HADDAD, Y. An improved genetic algorithm to solve the traveling salesman problem. World Academy of Science, Engineering and Technology. 2009, 52(3), p. 471-474. ISSN 2010-376X, eISSN 2010-3778.
    23. HASSANAT, A., PRASATH, V., ABBADI, M., ABU-QDARI, S., FARIS, H. An improved genetic algorithm with a new initialization mechanism based on regression techniques. Information [online]. 2018, 9(7), 167. ISSN ‫‏‬2078-2489. Available from: https://doi.org/10.3390/info9070167 Go to original source...
    24. REINELT, G. TSPLIB [online] [accessed 2018]. University of Heidelberg 1996. Available from: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95
    25. DENG, Y., LIU, Y., ZHOU, D. An improved genetic algorithm with initial population strategy for symmetric TSP. Mathematical Problems in Engineering [online]. 2015, 2015, 212794. ISSN 1024-123X, eISSN 1563-5147. Available from: https://doi.org/10.1155/2015/212794 Go to original source...

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content