Diversity And Initialization;Genetic Algorithm

Genetic Algorithm(GA)is an evolutionary optimization method.GA uses some individuals(population/chromosomes)as representatives for the solution space.Throughout some iterations,called generations,chromosomes compete;a fitness function evaluates the individuals' quality and determines the competition result at each generation.In the Genetic Algorithm for the Shortest Path prob-lem(GA SP)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,chromosome lengths vary.The first step of searching process is to have an initial guess(the initial popu-lation).The quality of the initial population is directly related to the quality of the solution obtained by the GA.A good initial guess gives the GA a better chance of finding a good solution,and a initial guess may hinder the algorithm's ability to find the optimal solution.The definition of good and bad of an initial population is a problem-specific matter,as there is no general rule of initialization that can be applied to every type of problem.As crucial as initialization,diversity has a say in the quality of the initial population and the searching process in general.A GA needs not only a good initial population,but a diverse initial popu-lation is as important.The diversity of the population needs to be maintained throughout the optimization process.The goal of diversity maintenance in GA is to counter premature convergence,which is a significant concern in evolutionary searching.The leading cause of premature convergence is known as the Explo-ration/Exploitation Balance(EEB)problem.In a given optimization space,explo-ration aims to search for solutions in new regions,while exploitation aims to evalu-ate(exploits)current regions.Thus,increasing exploration will decrease exploita-tion and vice versa.The balance between these two actions is challenging.As a result,the community of Evolutionary Algorithms(EAs)proposed diversity as a metric of EEB.Genotype diversity metrics measure exploration,and phenotype diversity metrics measure exploitation.Genotype diversity refers to the degree of heterogeneity/homogeneity of the population at the gene level,while phenotype diversity metrics measure the difference in fitness among the populations.High diversity is an indication of high exploration,while less diversity indicates high exploitation.However,many diversity metrics measure EEB,depending on the problem-specific characteristics such as its representation.Therefore,it is crucial to have ad-hoc diversity metrics to exploit the problem under consideration and its specific characteristics.There are many applications of the GA SP in different fields,including,but not limited to,routing communication networks,transportation,robotic path plan-ning,and the design of very-large-scale integrated circuits and navigation systems,to name a few.However,even though the direct-coded genetic algorithm with variable-length chromosomes for the shortest path problem has found widespread applications in many fields,this field of research is far from satisfactory.This work focuses on deriving and analyzing diversity metrics for the genetic algorithm variable-length chromosome shortest path problem.Besides,it provides a novel opposition-based learning initialization algorithm.The contribution of this work can be summarized as follows:·The first part of this work provides gene-based and length-based diversity metrics with a comparative study.Moreover,to our best knowledge,this is the first work focusing on chromosome length diversity.Finally,the rela-tionship among metrics and between metrics and population fitness quanti-fied using comprehensive data analysis.·In the second part of this work,we focus on a new,simple,and diversity-aware initialization method.The suggested initialization algorithm,called stratified opposition-based sampling(SOBS),considers phenotype and genotype diversity while striving to achieve the best quality of the initial population.SOBS has been tested with four network models used to sim-ulate real-world graphs.Statistical analysis showed that SOBS yields so-lutions with higher accuracy in 68%-100%of the time.Additionally,this work provides an insight into the effect of the repair function on chromo-some length diversity.Although this work focuses on the genetic algorithm for the simulation part,the diversity metrics and the new initial population algorithm suggested in this work can be applied to other population-based EAs that solve the shortest path problem and use the same population encoding method,the direct population rep-resentation,such as particle swarm optimization(PSO).