Research On The Initialization And Diversity Of Genetic Algorithm For Shortest Path Problem

In the era of big data and machine learning,graphs are gaining more attention,and there are study fields dedicated to applying neural networks on graphs(e.g.,Graph Neural Networks GNN).A graph is a data structure that represents dependencies between data elements.The possibilities of using graphs for data modeling are widely spanning many fields.Computer networks,software engineering,graph databases,social networks,brain connectivity(Neuroscience),traffic management,and such others.The typical pattern among these applications of graph data is that the data elements have dependent relationships.Numerous real-world data are modeled as graphs;the shortest path computation is a typical operation performed on those graphs.A shortest-path algorithm aims to find a path containing the minimal cost between two nodes/vertices in a given network/graph.The shortest path problem is a classical optimization problem in computer science.It is one of the most fundamental problems in graph theory.Typically,there are two main types of shortest-path problem algorithms.The first is the single-source shortest-path(SSSP).The basic concept of an SSSP algorithm is as follows.Given a graph G,that has V vertices E edges with a weight function f(w,v)=fw,v,and a single source vertex S,the SSSP algorithm finds the shortest path between the single source S to all the other vertices.If the goal is to find the shortest path between S and a single destination D,the algorithm can be stopped after finding that path.The second is all-pairs shortestpath(APSP).Given a graph G,that has V vertices E edges with a weight function f(w,v)=fw,v,an APSP algorithm finds all shortest paths between every pair of vertices for all(w,v)in V.The traditional algorithms that solve the shortest path have some shortcomings;these algorithms search only for a single optimal solution(shortest path),but they provide no information about other solutions that could be near-optimal.This problem is well known as the kth shortest path problem.An example of such a situation is a proactive network failure recovery mechanism when more than a solution is needed.For example,we might have n solutions,one may be employed as an immediate solution,and the other n-1 as backup solutions in case of failure.GAs can provide a single solution and n solutions,where n is as big as the size of the population.Besides,GAs are not expected to find the optimal solution always;a near-optimal solution in practical cases is all that we need as long as it meets time constraints.The sub-optimal solutions are often used in some real-time processing system scenarios.Moreover,genetic algorithms are inherently parallel,they can be used in parallel and distributed processing technologies to achieve further acceleration.Even though Genetic Algorithm for the Shortest-Path problem(GA SP)with variable-length chromosomes has found widespread applications in many fields,the research on this field is far from satisfactory.This work consists of two main parts;the first part is dedicated to deriving diversity metrics for the direct-coded genetic algorithm for the shortest path problem with variable length chromosomes.The second part provides a novel initialization method for the same algorithm—the suggested initialization algorithm(called Stratified Opposition-Based sampling,SOBS)inspired by the opposition-based learning concept.SOBS is diversity-aware,and simple to implement.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).The first step of the searching process is to have an initial guess(the initial population).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 bad initial guess may hinder the algorithm’s ability to find the optimal solution.The definition ofg ood 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 population 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 Exploration/Exploitation Balance(EEB)problem.In a given optimization space,exploration aims to search for solutions in new regions,while exploitation aims to evaluate(exploits)current regions.Thus,increasing exploration will decrease exploitation 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.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 relationship among metrics and between metrics and population fitness quantified using comprehensive data analysis.·In the second part of this work,we focus on a new,simple,and diversityaware 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 simulate real-world graphs.Statistical analysis showed that SOBS yields solutions with higher accuracy in 68%-100%of the time.Additionally,this work provides an insight into the effect of the repair function on chromosome 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 representation,such as particle swarm optimization(PSO).