A Study Of Distance Selection In Estimating Solution Difference For Probabilistic Memetic Framework In Combinatorial Optimization

Memetic algorithm(MA)is a population based heuristic search algorithm that integrates global search with individual lifetime learning process(i.e.,local search).It has been widely used in many real world applications for solving complex optimization problems.In MA,the balance between global search and local search affects its performance greatly.The probabilistic memetic framework(PMF)was thus introduced to separates the global search from the local search as an independent optimization behavior and models the memetic algorithm as a decision process for selecting global search and local search.PMF balances global search and local search by controlling the local search intensity of each individual.The trade-off is based on the theoretical upper bound of the local search intensity that is calculated while the search progresses.According to the work in [1],when using the PMF to solve the combinatorial optimization problem,the appropriate selection of distance metric plays an important role in estimating the local search intensity.However,to the best of our knowledge,little or no research works in the literature has studied the selection of suitable distance metric in PMF for combinatorial optimization.Our study thus try to fill this research gap by embarking a study on the selection of distance metrics in PMF with two well-known NP hard combinatorial optimization problems,i.e.,Capacitated Arc Routing Problem(CARP)and Vehicle Routing Problem with Time Windows(VRPTW).In particular,here we first analyze the suitability of 4 commonly used distance metrics in the combinatorial optimization problem for measuring the similarity between CARP candidate solutions.Next,we propose a score based on closeness of neighborhood and fitness landscape correlation to quantify the suitability of a distance metric in estimating the local search intensity for PMF in the context of combinatorial optimization.Further,we have conducted comprehensive experiments with 24 egl CARP instances.In the empirical results,PMF have found 4 new best known CARP solutions when Edit distance is employed.The Edit Distance outperformed the Improved Jaccard Distance with 9 better solutions obtained.Lastly,experimental study on 24 Solomon's VRPTW benchmark instances are also presented.The PMF significantly outperformed the Nacima's MA with 10 better VRPTW solution found when the Edit Distance is used;Comparing to the Improved Jaccard Distance,the Edit Distance has found 12 superior solutions with PMF.In summary,the experimental results obtained,on one hand,confirmed that the distance metric can affect the performance of PMF significantly,and on the other hand,highlighted the effectiveness of the proposed score of distance suitability in the context of CARP and VRPTW.