Path Relinking In Hybrid Heuristic Algorithms For Combinatorial Optimization Problems

Combinatorial optimization problems(COPs)have wide practical applications in many areas.The most of COPs are NP-hard,which no method can find the optimal solution within polynomial time.Finding approximate solutions that can found by heuristic algorithms in a reasonable time would be useful in practice.However,computational time of heuristic algorithms increases as problem sizes increase.With growing data availability,problems are also growing in size,and therefore,there is a growing demand to develop computationally efficient heuristic algorithms for dealing larger problems.The key elements of designing efficient heuristic algorithms are understanding nature of the problems being considered,and integrating intensification tool in a right way.Path relinking is one of the main intensification techniques for hard optimization problems.The main focus of this dissertation is to improve the performance of heuristic algorithms by integrating path relinking and understanding nature of the problems.In this dissertation,two concrete optimization problems,the Critical Node Detection Problem(CNDP),and the QoS-aware Service Selection Problem(QSSP),are considered mainly.The contents of the dissertation are as follows:(1)Performance improvement on hybridization of exterior path relinking with Greedy Randomized Adaptive Search Procedure(GRASP),which is a well-established meta-heuristics,is investigated in the context of single objective optimization.Exterior path relinking is a recently purposed meta-heuristics.Even though path relinking is extensively used as intensification tool for GRASP,it is limited to interior variant of path relinking.Hence,the hybridization of exterior path relinking with GRASP is needed to be studied.A new hybridization scheme of GRASP with exterior path relinking is proposed for solving the CNDP.In the new scheme,the resulting solution obtained from GRASP iteration is relinked with a previously discovered high quality solution by using exterior path relinking.Exterior path relinking creates a path by exploring neighbors beyond the two solutions.The computational experiments show that the exterior path relinking based algorithm outperforms other variants of path relinking for solving the CNDP.Moreover,the proposed algorithm finds higher quality solutions compared with other approaches,and improves the best known values for 8 of 16 instances in the well-known dataset in the literature.(2)Performance improvement on hybridization of path relinking with interactive evolutionary multi-objective optimization(EMO)is investigated in the context of multi-objective optimization.Since many COPs have multiple objectives in nature,incorporating user preference information to the optimization process is the only way to find the most preferred solution.We propose a new interactive EMO procedure(called cdEMO)that periodically incorporates user preference information during optimization,and models the information as convex cone.The algorithm classifies Pareto incomparable solutions into several ordered classes by using the user preference information.Then,we study how path relinking can support the performance of the cdEMO algorithm.Path relinking improves upon 14.3 percent the performance of the cdEMO algorithm in terms of the requirement of user feedback.The computational experiments demonstrate that the cdEMO algorithm can converge to the preferred solution faster.Since the cdEMO is a general purpose optimization algorithm,it can be used for any COPs.(3)A modified version of the previously proposed cdEMO algorithm is applied for the QSSP,which is a real world problem with high importance,and has multiple objectives in nature.We critically analyse the scalarization methods,which are used by the most of current approaches for solving the QSSP,and identify serious drawbacks such as difficulty of defining right weight vector for aggregation,and lack of ability for finding non-convex part of Pareto front.The cdEMO algorithm solves the two drawbacks by incorporating user preference information.The experimental results show that the modified cdEMO with path relinking can be an efficient andd effective method for the QSSP.(4)A main topic of our research is also the development of efficient algorithms for the CNDP.By understanding nature of the CNDP,a computationally efficient heuristic algorithm is proposed for the CNDP on large planar graphs.NP-hardness of the CNDP on planar graphs is proved.Since the computational cost of objective function is O(n),where n is the problem size,the computational time of heuristic algorithms for the CNDP increases sharply as the problem size increase.The objective function is transformed into bi-objective function.We propose a mechanism that can compute the transformed bi-objective function in constant time by using special properties of planar graphs.This enables us to develop an efficient method for the CNDP on large graphs under the requirement of the planarity of graphs.The computational experiments demonstrate the superiority of the proposed algorithm compared with state-of-the-art approaches in terms of running time and solution quality.