Diversity metrics for direct-coded variable-length chromosome shortest path problem evolutionary algorithms
- PDF / 1,213,730 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 203 Views
Diversity metrics for direct-coded variable-length chromosome shortest path problem evolutionary algorithms Aiman Ghannami1
· Jing Li1 · Ammar Hawbani1 · Naji Alhusaini1
Received: 17 June 2020 / Accepted: 9 October 2020 © Springer-Verlag GmbH Austria, part of Springer Nature 2020
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. Keywords Shortest path problem · Diversity · Genetic algorithm · Evolutionary algorithms
This paper is supported by the Strategic Priority Research Program of Chinese Academy of Sciences (A Class) NO. XDA19020102. Extended author information available on the last page of the article
123
A. Ghannami et al.
1 Introduction The Shortest Path (SP) problem goal is to find the shortest path between two given vertices in a given graph. In GA SP [2] problem, each individual represents a path between a pair of source-destination. Each path consists of multiple distinct and finite relaying vertices. The number of vertices that form paths between a pair of source-destination is variable thus chromosomes length is variable. Applications of GA SP emerge in various fields, included but not limited to, routing in communication networks [42], transportation [3], robotic path planning [21], optimization of VLSI floorplanning [48], data visualization [16], and network intrusion detection [40]. Genetic Algorithm (GA) [26] is an evolutionary optimization method. Basically, GA uses a number of individuals, called chromosomes, as representatives for the solution space. Chromosomes compete with each other throughout a number of iterations, cal
Data Loading...
