Diversity metrics for direct-coded variable-length chromosome shortest path problem evolutionary algorithms | Computing Skip to main content
Springer Nature Link
Log in

Diversity metrics for direct-coded variable-length chromosome shortest path problem evolutionary algorithms

  • Special Issue Article
  • Published:
Computing Aims and scope Submit manuscript

Abstract

One of the major concerns in Evolutionary Algorithms is the premature convergence caused by what is known as the Exploration and Exploitation Balance problem. To maintain this balance, population diversity should be maintained during the initialization/optimization process. Maintaining diversity can be done through different strategies, but they commonly answer one question: when to introduce more diversity to the population? To answer this question there should be diversity metrics upon which a decision can be made to add diversity; consequently, add/reduce exploration/exploitation. There are as many diversity metrics as many problems and representations. That is, diversity metrics are very problem-specific. This work provides diversity metrics for the variable-length chromosome Genetic Algorithm for Shortest Path. The suggested metrics consider the varying lengths of the chromosomes, problem representation, and the search space. To measure chromosome-length diversity, a novel chromosome-length-based metric has been proposed. By exploiting the fact that the possible genes that can form any chromosome are well known in this specific direct-encoded population, a new simple metric that measures the representation of genes in the initial population is proposed and experimentally investigated. The presented metrics put through an extensive simulation and comparatively studied. Relationship between the proposed metrics has been quantified using Principal Component Analysis under varying network/population sizes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Abbass HA, Deb K (2003) Searching under multi-evolutionary pressures. International conference on evolutionary multi-criterion optimization. Springer, Berlin, pp 391–404

    Chapter  Google Scholar 

  2. Ahn CW, Ramakrishna RS (2002) A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Trans Evol Comput 6(6):566–579

    Article  Google Scholar 

  3. Ayo BS et al (2017) An improved genetic algorithm for flight path re-routes with reduced passenger impact. J Comput Commun 5(07):65

    Article  Google Scholar 

  4. Back T (1996) Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford University Press, Oxford

    Book  Google Scholar 

  5. Barker AL, Martin WN (2000) Dynamics of a distance-based population diversity measure. In: Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No. 00TH8512), vol. 2, pp. 1002–1009. IEEE

  6. Beernaerts J, Debever E, Lenoir M, De Baets B, Van de Weghe N (2019) A method based on the levenshtein distance metric for the comparison of multiple movement patterns described by matrix sequences of different length. Expert Syst Appl 115:373–385

    Article  Google Scholar 

  7. Burke EK, Gustafson S, Kendall G (2004) Diversity in genetic programming: An analysis of measures and correlation with fitness. IEEE Trans Evol Comput 8(1):47–62

    Article  Google Scholar 

  8. Chen M, Wang K, Dong X, Li H (2020) Emergency rescue capability evaluation on urban fire stations in china. Process Saf Environ Prot 135:59–69

    Article  Google Scholar 

  9. Chen P, Tong R, Lu G, Wang Y (2018) The \(\alpha \)-reliable path problem in stochastic road networks with link correlations: A moment-matching-based path finding algorithm. Expert Syst Appl 110:20–32

    Article  Google Scholar 

  10. Chen Y, Zeng X, Yuan T (2017) Design and development of earthquake emergency rescue command system based on gis and gps. International symposium for intelligent transportation and smart city. Springer, Berlin, pp 126–138

    Google Scholar 

  11. Corriveau G, Guilbault R, Tahan A, Sabourin R (2012) Review and study of genotypic diversity measures for real-coded representations. IEEE Trans Evol Comput 16(5):695–710

    Article  Google Scholar 

  12. Črepinšek M, Liu SH, Mernik M (2013) Exploration and exploitation in evolutionary algorithms: A survey. ACM Comput Surv 45(3):35

    Article  Google Scholar 

  13. Dang DC, Friedrich T, Kötzing T, Krejca MS, Lehre PK, Oliveto PS, Sudholt D, Sutton AM (2017) Escaping local optima using crossover with emergent diversity. IEEE Trans Evol Comput 22(3):484–497

    Article  Google Scholar 

  14. Eiben ÁE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124–141

    Article  Google Scholar 

  15. Gao W, Nallaperuma S, Neumann F (2016) Feature-based diversity optimization for problem instance classification. In: International Conference on Parallel Problem Solving from Nature, pp. 869–879. Springer, Berlin

  16. Ghassemi Toosi F, Nikolov NS, Eaton M (2015) Evolving smart initial layouts for force-directed graph drawing. In: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 1397–1398

  17. Gouvea MM, Araujo AF (2008) Diversity control based on population heterozygosity dynamics. In: 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 3671–3678. IEEE

  18. Gupta AK, Smith KG, Shalley CE (2006) The interplay between exploration and exploitation. Acad Manag J 49(4):693–706

    Article  Google Scholar 

  19. Herrera F, Lozano M et al (1996) Adaptation of genetic algorithm parameters based on fuzzy logic controllers. Genet Algorithms Soft Comput 8:95–125

    Google Scholar 

  20. Ichikawa Y, Ishii Y (1993) Retaining diversity of genetic algorithms for multivariable optimization and neural network learning. In: IEEE International Conference on Neural Networks, pp. 1110–1114. IEEE

  21. Ismail A, Sheta A, Al-Weshah M (2008) A mobile robot path planning using genetic algorithm in static environment. J Comput Sci 4(4):341–344

    Article  Google Scholar 

  22. Jondeau E, Poon SH, Rockinger M (2007) Financial modeling under non-Gaussian distributions. Springer, Berlin

    MATH  Google Scholar 

  23. Jost L (2006) Entropy and diversity. Oikos 113(2):363–375

    Article  Google Scholar 

  24. Kashyap RL, Oommen BJ (1983) The noisy substring matching problem. IEEE Trans Software Eng 3:365–370

    Article  Google Scholar 

  25. Khankhour H, Abouchabaka J, Abdoun O (2019) Genetic algorithm for shortest path in ad hoc networks. In: International Conference on Artificial Intelligence and Symbolic Computation, pp. 145–154. Springer, Berlin

  26. Kramer O (2017) Genetic algorithm essentials, vol 679. Springer, Berlin

    Book  Google Scholar 

  27. Levenshtein VI (1966) Binary codes capable of correcting deletions, insertions, and reversals. Soviet Phys doklady 10:707–710

    MathSciNet  Google Scholar 

  28. Luger J, Raisch S, Schimmer M (2018) Dynamic balancing of exploration and exploitation: The contingent benefits of ambidexterity. Organ Sci 29(3):449–470

    Article  Google Scholar 

  29. Magurran AE (2013) Measuring biological diversity. Wiley, New Jersy

    Google Scholar 

  30. Maruyama A, Shibata N, Murata Y, Yasumoto K, Ito M (2004) A personal tourism navigation system to support traveling multiple destinations with time restrictions. In: 18th International Conference on Advanced Information Networking and Applications, 2004. AINA 2004., vol. 2, pp. 18–21. IEEE

  31. Masek WJ, Paterson MS (1980) A faster algorithm computing string edit distances. J Comput Syst Sci 20(1):18–31

    Article  MathSciNet  Google Scholar 

  32. Miao C, Liu H, Zhu GG, Chen H (2018) Connectivity-based optimization of vehicle route and speed for improved fuel economy. Trans Res Part C Emerg Technol 91:353–368

    Article  Google Scholar 

  33. Mohamed RE, Saleh AI, Abdelrazzak M, Samra AS (2018) Survey on wireless sensor network applications and energy efficient routing protocols. Wireless Pers Commun 101(2):1019–1055

    Article  Google Scholar 

  34. Mohemmed AW, Sahoo NC, Geok TK (2008) Solving shortest path problem using particle swarm optimization. Appl Soft Comput 8(4):1643–1653

    Article  Google Scholar 

  35. Morris EK, Caruso T, Buscot F, Fischer M, Hancock C, Maier TS, Meiners T, Müller C, Obermaier E, Prati D et al (2014) Choosing and using diversity indices: insights for ecological applications from the german biodiversity exploratories. Ecol Evol 4(18):3514–3524

    Article  Google Scholar 

  36. Morrison RW, De Jong KA (2001) Measurement of population diversity. In: International Conference on Artificial Evolution (Evolution Artificielle), pp. 31–41. Springer, Berlin

  37. Neumann A, Gao W, Doerr C, Neumann F, Wagner M (2018) Discrepancy-based evolutionary diversity optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 991–998

  38. Olorunda O, Engelbrecht AP (2008) Measuring exploration/exploitation in particle swarms using swarm diversity. In: 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 1128–1134. IEEE

  39. Oommen BJ (1987) Recognition of noisy subsequences using constrained edit distances. IEEE Trans Pattern Anal Mach Intell 5:676–685

    Article  Google Scholar 

  40. Pawar SN, Bichkar RS (2015) Genetic algorithm with variable length chromosomes for network intrusion detection. Int J Autom Comput 12(3):337–342

    Article  Google Scholar 

  41. Peterson JL (1980) Computer programs for detecting and correcting spelling errors. Commun ACM 23(12):676–687

    Article  Google Scholar 

  42. Rastgoo R, Sattari-Naeini V (2018) Gsomcr: Multi-constraint genetic-optimized qos-aware routing protocol for smart grids. Iran J Sci Technol Trans Electr Eng 42(2):185–194

    Article  Google Scholar 

  43. Rothlauf F (2006) Representations for genetic and evolutionary algorithms. In: Representations for Genetic and Evolutionary Algorithms, pp. 9–32. Springer, Berlin

  44. Roughan M, Tuke J, Parsonage E (2019) Estimating the parameters of the waxman random graph. In: International Workshop on Algorithms and Models for the Web-Graph, pp. 71–86. Springer, Berlin

  45. Shafiee ME, Berglund EZ (2016) Agent-based modeling and evolutionary computation for disseminating public advisories about hazardous material emergencies. Comput Environ Urban Syst 57:12–25

    Article  Google Scholar 

  46. Shannon CE, Weaver W (1998) The mathematical theory of communication. University of Illinois press

  47. She Q, Chen G, Chan RH (2016) Evaluating the small-world-ness of a sampled network: Functional connectivity of entorhinal-hippocampal circuitry. Sci Rep 6:21468

    Article  Google Scholar 

  48. Singh A, Jain L (2016) Optimization of vlsi floorplanning problem using a novel genetic algorithm. Int J Comput Sci Inf Secur 14(10):937

    Google Scholar 

  49. Squillero G, Tonda A (2016) Divergence of character and premature convergence: A survey of methodologies for promoting diversity in evolutionary optimization. Inf Sci 329:782–799

    Article  Google Scholar 

  50. Tiwari A, Chang PC (2015) A block recombination approach to solve green vehicle routing problem. Int J Prod Econ 164:379–387

    Article  Google Scholar 

  51. Ursem RK (2002) Diversity-guided evolutionary algorithms. In: International Conference on Parallel Problem Solving from Nature, pp. 462–471. Springer, Berlin

  52. Vassilevska V, Williams R (2009) Finding, minimizing, and counting weighted subgraphs. In: Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 455–464. ACM

  53. Wineberg M, Oppacher F (2003) The underlying similarity of diversity measures used in evolutionary computation. In: Genetic and evolutionary computation conference, pp. 1493–1504. Springer, Berlin

  54. Zhou S, Wang R, Ding J, Pan X, Zhou S, Fang F, Zhen W (2019) An approach for computing routes without complicated decision points in landmark-based pedestrian navigation. Int J Geogr Inf Sci 33(9):1829–1846

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Science and Technology of China, JinZhai 96, Hefei, China

    Aiman Ghannami, Jing Li, Ammar Hawbani & Naji Alhusaini

Authors
  1. Aiman Ghannami
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Jing Li
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Ammar Hawbani
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Naji Alhusaini
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Jing Li.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This paper is supported by the Strategic Priority Research Program of Chinese Academy of Sciences (A Class) NO. XDA19020102.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ghannami, A., Li, J., Hawbani, A. et al. Diversity metrics for direct-coded variable-length chromosome shortest path problem evolutionary algorithms. Computing 103, 313–332 (2021). https://doi.org/10.1007/s00607-020-00851-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00607-020-00851-4

Keywords