Effective Heuristic Algorithms For The Minimum Weight Vertex Cover And The Linear Ordering Optimization Problems

Many optimization problems with NP-hard nature exist in various scientific research and industrial engineering applications,such as wireless communication,VLSI design,network flows and flight scheduling,etc.These complex practical industrial application problems are core issues and bottlenecks in their respective fields.However,previous research on computational complexity theory has shown that,for all NP-hard problems,it is commonly believed that there exists no polynomial time algorithm guaranteeing an optimal solution.In recent decades of research,heuristic algorithms have exhibited good performance in solving combinatorial optimization problems with NP-hard nature.Especially,good heuristic algorithms can usually find high-quality solutions for many challenging problems in a reasonable computational time.This provides a realistic solution to NP-hard problems in practical applications.Study shows that those NP-hard problems mentioned above can be solved by being modeled into the vertex cover problem and linear ordering problem.In this thesis,we first present a brief overview of the related theories of heuristic algorithms,the solution ideas and evaluation criteria of heuristic algorithms.Then,our research here mainly focus on two classic and extremely important problems: the minimum weight vertex cover problem(MWVCP)and the linear ordering problems(including the linear ordering problem with cumulative costs,LOPCC and the classic linear ordering problem,LOP).We propose four effective heuristic optimization algorithms for these problems,respectively.Finally,by computational experiments on the public benchmark instances,the proposed algorithms here are analyzed and evaluated.The contributions of this dissertation are summarized as follows:(1)A multi-start iterated tabu search algorithm(MS-ITS)is proposed for the minimum weight vertex cover problem.The MS-ITS algorithm consists of three main procedures and one framework: an initial solution construction procedure,an iterated tabu search procedure,a perturbation procedure and a multi-start mechanism.The first procedure selects several key vertices to form a legal initial solution by introducing two strategies of random and greedy.By introducing two characteristics,namely the neighborhood structure based on simultaneous multi-point movement,the fast neighborhood evaluation mechanism based on incremental calculation and the double table tabu strategy,we propose an efficient tabu search procedure which expects to explore larger neighborhood space and quickly generate local optimal solution.The third procedure introduces a perturbation strategy based on vertex weight and correlation information to jump out of a local optimum trap.In addition,a multi-start iteration mechanism extends the global search capability of the algorithm.The proposed algorithm is tested on a total of 126 standard benchmark instances on three sets(Class SPI,MPI and LPI).Compared to the best-known results reported in the literature,we can find the best upper bound for 44 instances compared to the best-known results reported in the literature.(2)Another more effective hybrid evolution algorithm(HGA)is proposed for the minimum weight vertex cover problem.By incorporating the MS-ITS algorithm into the framework of genetic algorithm(GA),the algorithm then begins a periodic iterative solution when an initial population with certain quality and diversity guarantees is constructed by introducing an initial solution generation strategy based on the GRASP framework.In each iteration cycle,by introducing a problem-independent crossover operator based on the common gene inheritance mechanism,the two parent solutions randomly selected are evolved to generate high quality good offspring.Then,the current offspring is further improved from the existing configuration to a better local optimal solution by using the MS-ITS algorithm.To maintain the diversity of the population and the good quality of individuals in the population,an elite value scoring mechanism is used to update the population.Among them,the MS-ITS algorithm used here emphasizes search intensification while the framework of GA strengthen search diversification.The proposed algorithm is tested on a total of 176 standard benchmark instances on four sets(SPI,MPI,LPI and RLPI).Compared with all the previous results,we can find the best upper bound for 27 instances and obtain the current best solution or optimal solution for all the remaining ones.(3)An effective hybrid evolution algorithm(FBLS-E)is proposed for the linear ordering problem with cumulative costs.The linear ordering problem with cumulative costs is a special variant of linear ordering problem.Each item of its solution sequence contains a non-linear cumulative cost,which presents a higher computational complexity.The FBLS-E algorithm combines a Memetic framework with a new local search procedure.A f orward-backward neighborhood structure is first proposed,which extends the neighborhood search space of the current solution,providing more opportunities for moving one neighbor to a better one.Then,a fast neighborhood evaluation method based on multiple swap move is introduced.Based on this,an effective local search procedure(FBLS)is proposed to produce a better local optimal solution.In each iteration of the algorithm,the initial solution construction procedure combines two steps: the random permutation method and the FBLS to produce high quality initial solutions.Then,by introducing a sequence recombination operator,a new offspring with better goodness is generated from two selected parents and improved by the FBLS procedure.In order to drive the search process to extend search space for more promising solutions,a special strategy based on the solution quality replacement criteria is applied to update the population.The proposed algorithm is tested on a total of 118 standard benchmark instances.Compared to the best-known results reported in the literature,we can find the best upper bound for 46 instances in a short period of time.(4)An improved hybrid evolutionary algorithm(MPM)based on multi-parent recombination operation is proposed for the classical linear ordering problem.The MPM algorithm incorporates an effective local search procedure into a Memetic framework.First,through repeatedly operation of a random permutation method and a local search procedure,a high quality initial population is obtained.In each iteration cycle of the algorithm,by introducing special selection strategy based on the distance feature and considering the diversity of the population,the multi-parent selection is carried out.Then,a multi-parent recombination operator is proposed to develop evolution operations so that the offspring generated can inherit more outstanding features from parents.For further enhancing the global optimization ability of the algorithm,a scoring strategy based on the quality and health of the population is applied to maintain the diversity of the population.The proposed algorithm is tested on a total of 484 LOP benchmark instances.Compared to the best-known results reported in the literature,we can successfully obtain the best results for all the instances for which the optimal solutions are known.Furthermore,on the other255 difficult instances whose optimal solutions are unknown,we can still find the latest lower bound for 66 ones while successfully matching the best results for the remaining ones.All these research results show that the multi-start iterative tabu search algorithm,hybrid evolution algorithm and improved hybrid evolution algorithm proposed in this thesis are effective and efficient for solving the corresponding vertex cover and linear ordering optimization problems.Through the research of this thesis,our understanding of the heuristic optimization algorithm for solving combinatorial optimization problems with NP-hard feature is deepened.