| Heuristic algorithm is one of the most common methods for solving large-scale combinatorial optimization problems.Intensification and diversification are key features of heuristic algorithms,which are highly related to each other.Intensification is to intensively explore areas of the search space with high quality solutions,and diversification is to guide the search to explore unvisited and more promising areas of search space when necessary.The dynamic balance between them is the important guarantee for heuristic algorithms to achieve high performance.In order to obtain this kind of balance,many kinds of diversification mechanisms have been proposed in the literature.For example,the perturbation operator in iterated local search,the constructive phase in greedy randomized adaptive search,the adaptive diversification strategy in breakout local search and so on.These diversification mechanisms are mainly achieved by perturbation or reconstruction procedures.They may generate solutions that differ enough from the previous solutions while rarely giving a careful consideration on the solution quality.This paper presents a systematical research on the intensification and diversification of heuristic algorithms: First,based on the research in the literature,we design a new heuristic algorithm which incorporates the adaptive diversification strategy in breakout local search to solve the single machine total weighted tardiness problem.Second,based on the experience in the application of well-known diversification mechanism,we propose a local search based diversification mechanism(QD-LS).The objective function of QD-LS considers both solution quality and distance,and the proportion between them can be adjusted by relevant parameters.In order to testify the effectiveness of QD-LS as a diversification mechanism,we propose two different heuristic algorithms to tackle the vertex separator problem and graph partition problem,respectively.Besides,we conduct computational experiments and comparisons to evaluate the performance of the algorithms.In detail,the main contribution of this paper are as follows:(1)By introducing the well-known diversification mechanisms,we propose a new diversification mechanism based on local search procedure(QD-LS)and introduce its general principle and key techniques.Different from the traditional local search procedures,QD-LS is guided by solution quality and distance,where the distance between the current solution and the best found solution is added to the objective function.Considering both solution quality and distance between the current solution and the best found solution,QD-LS can obtain a solution not only with high quality but also at a suitable distance from the best found solution.(2)For the single-machine total weighted tardiness problem,we present a breakout dynasearch algorithm(BDS)to solve it.Based on the framework of iterated local search algorithm,BDS apply the dynasearch procedure to intensify the search and the adaptive perturbation strategy to jump out of local optima.Besides,computational experiments and comparisons show that BDS virtually solves all the standard benchmark problem instances with up to 100 jobs from the literature within 0.1 s and attains a hit ratio of 100%.For larger instances with up to 300 jobs,BDS obtains all the the optimal solutions for all of them within an average computational time of 252 s and attain an average hit ratio of 87.66%.demonstrating the efficacy of BDS in terms of both solution quality and computational efficiency.Furthermore,some key features of BDS are also analyzed to identify its success factors.(3)For the vertex separator problem,we propose a quality and distance guided hybrid algorithm(QD-HA)to tackle it.Based on the framework of evolutionary algorithms,QD-HA integrates a basic tabu search procedure with a random greedy recombination operator and QD-LS strategy.Assessed on two sets of 348 common benchmark instances,QD-HA achieves highly competitive results in terms of both solution quality and computational efficiency compared with state-of-the art algorithms in the literature.Specifically,it improves the previous best known results for63 out of 244 large instances while matching the best known results for others.The impact of the quality and distance based diversification strategy is also investigated.(4)For the graph partition problem,we propose a quality and distance guided metaheuristic algorithm(QD-ILS)to tackle it.Based on the framework of iterated local search algorithm,QD-ILS integrates a basic local search procedure with QD-LS strategy,which uses an augmented evaluation function that considers both solution quality and distance between the current solution and the best found solution to guide the search to explore promising regions of the search space.Assessed on two sets of 162 common benchmark instances,QD-ILS achieves highly competitive results in terms of both solution quality and computational efficiency compared with the state-of-the-art algorithms in the literature.Specifically,it improves the previous best known results for 33 out of 162 benchmark instances and matches the best known results on all except 4 of the remaining instances compared with the stateof-the-art algorithms in the literature.The impact of the distance and quality based diversification strategy is also investigated.It can be concluded from the research that the breakout dynasearch algorithm,the quality and distance guided hybrid algorithm and the quality and distance guided metaheuristic algorithm are all effective and efficient for solving the corresponding combinatorial optimization problems.Besides,the proposed QD-LS is a novel and successful diversification mechanism for heuristics in view of the theory and computational practice.Furthermore,based on the experience in the design and application of QD-LS,the balance between intensification and diversification is vitally important in designing an effective diversification mechanism for heuristics. |
PDF Full Text Request