Stratified Opposition-Based Initialization for Variable-Length Chromosome Shortest Path Problem Evolutionary Algorithms

Ghanami, Aiman; Li, Jing; Hawbani, Ammar; Al-Dubai, Ahmed

Abstract

Initialization is the first and a major step in the implementation of evolutionary algorithms (EAs). Although there are many common general methods to initialize EAs such as the pseudo-random number generator (PRNG), there is no single method that can fit every problem. This study provides a new, flexible, diversity-aware, and easy-to-implement initialization method for a genetic algorithm for the shortest path problem. The proposed algorithm, called stratified
opposition-based sampling (SOBS), considers phenotype and genotype diversity while striving to achieve the best fitness for the initialization population.
SOBS does not depend on a specific type of sampling, because the main goal is to stratify the sampling space. SOBS aims at an initial population with higher fitness and diversity in the phenotype and genotype. To investigate the performance of SOBS, four network models were used to simulate real-world networks. Compared with the most frequently used initialization method, that is, PRNG, SOBS provides more accurate solutions, better running time with less memory usage, and an initial population with higher fitness. Statistical analysis showed that SOBS yields solutions with higher accuracy in 68%–100% of the time. Although this study was focused on the genetic algorithm, it can be applied to other population-based EAs that solve the shortest path problem and use the same direct population representation such as particle swarm optimization (PSO).

Citation

Ghanami, A., Li, . J., Hawbani, A., & Al-Dubai, A. (2021). Stratified Opposition-Based Initialization for Variable-Length Chromosome Shortest Path Problem Evolutionary Algorithms. Expert Systems with Applications, 170, Article 114525. https://doi.org/10.1016/j.eswa.2020.114525

• Journal Article Type: Article
• Acceptance Date: Dec 20, 2020
• Online Publication Date: Dec 24, 2020
• Publication Date: 2021-05
• Deposit Date: Dec 21, 2020
• Publicly Available Date: Jun 25, 2022
• Journal: Expert Systems with Applications
• Print ISSN: 0957-4174
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 170
• Article Number: 114525
• DOI: https://doi.org/10.1016/j.eswa.2020.114525
• Keywords: Shortest Path Problem, Initialization, Genetic Algorithm, Network, Kriging
• Public URL: http://researchrepository.napier.ac.uk/Output/2712670