Researches On Several Real Adjacency Matrix-coded Evolutionary Algorithms For Routing Optimization Problems

The routing optimization problem,when viewed within the fields of operational research and combinatorial optimization,has been intensively studied.In this context,it can provide intelligent logistics with a practical tool for optimization of the distribution routes.For its NPhard characteristic,evolutionary computing has been frequently applied to solve this problem.Evolutionary computing is considered a part of intelligent computing.It belongs to a computer science that uses the mechanisms inspired by biological evolution to solve complex optimization problems in the realm of mathematical reality.The key to its successful solution is coding,which must include a reliable population representation along with a mapping scheme for complete transfer of the population from the searching space to the feasible solution space.In a routing optimization problem,the contribution of a variable to fitness depends on the state of other variables.This characteristic can be referred to as “entire linkage.” Studies have shown that interactions between decision variables typically make solution of an optimization problem difficult to solve for an evolutionary algorithm(EA).As the dimensionality or constraint rules for an optimization problem increase,solving the problem can be very challenging.In this study,the authors focused on how evolutionary computing exploits information exchange between variables to solve the routing optimization problem,beginning with inspection of the coding mechanism.An evolutionary routing optimization framework named evolution with variable interaction learning(EVIL)is proposed.In the EVIL,taking the traveling salesman problem(TSP)and generalized traveling salesman problem(GTSP)as research subjects,several evolutionary algorithms are proposed for their respective solution.The principal contributions and achievements of this dissertation are summarized in what follows.First,a real adjacency matrix-coding mechanism based on a construction graph is proposed for the routing optimization problems,so that the population individuals which participate in the evolution become the carriers of interactions among variables and search for the optimal,or satisfactory real correlation matrix through an evolutionary process.By means of the construction graphs of TSP and GTSP,the corresponding real adjacency matrix-coding mechanisms are represented.In TSP,population individuals are encoded as a swarm of real adjacency matrices for adjacency vertices;and,decoded with random-proportional rule and greedy algorithm;In GTSP,population individuals are encoded as a swarm of real adjacency matrices for adjacency clusters;and,decoded with random-proportional rule,greedy algorithm,and shortest tour algorithms.The results of experiments illustrate that the proposed real adjacency matrix-coding mechanisms based on construction graph are effective in helping evolutionary computing solve TSP and GTSP.Optimum or satisfactory solutions can be found,on the average,within 4.38% to 35.17% and within 0.67% to12.17% of max fitness evaluation times(FEs),respectively.Secondly,a search scheme named as matrix recombination-difference is designed for the proposed real adjacency matrix-coding mechanisms.Harnessing this search scheme,using information from the local search results,the best-so-far global solution and the best-so-far solutions yielded by population individuals can be fed back to the present population individuals and be incorporated into the subsequent evolution.Moreover,there is no parameter in the arithmetic operators,so that application of the proposed EAs is simplified.Hence,this search scheme can effectively yield knowledge of interactions among variables in routing optimization problems,evolved and accumulated in this evolutionary process.The experimental results show that matrix recombination-difference operators combining with the proposed real adjacency matrix-coding mechanism are effective for TSP and GTSP.Last but worthy of mention is that an entire linkage index(ELI)is proposed to characterize the interaction degrees among variables in routing optimization problems.This ELI can help explore how the proposed evolution with variable interaction learning(EVIL)exploits interactions among variables in routing optimization problems.In experimental studies when ELI values of TSP instances are beyond 0.5,error values using the evolutionary algorithm based on matrix recombination-difference(MRDEA)are relatively low;at the same time it seems that the higher are the ELI values of GTSP instances with mid-larger scale,the lower are error values and FEs utilization of real adjacency matrix evolutionary algorithm(RAMEA).The results indicate that the proposed evolution with variable interaction learning(EVIL)is promising for routing optimization,especially with a high entire linkage level.