An Multiobjective Memetic Algorithm For Combination Optimization Problems

Combinatorial Optimization Problems(COPs), such as traveling salesman problem, job-fowshop scheduling problem, software next release problem, etc., are very pervasive in the real-world applications. Due to the huge search space and many local optima of such problems, no exact algorithms can solve them in the reasonable time. Memetic algorithms(MAs) belong to advanced evolutionary algorithms, used to obtain good approximate solutons. MAs usually adopt the global search to locate promising regions, and then use local search to refine such regions in the hope of obtaining the optimal solutions. This paper studies the multiobjective memetic algorithms for combinatorial optimization, as follows.1) The representatives of decomposition based algorithm(MOEA/D) and domination based algorithm(NSGA-II) are introduced.2) This thesis adopts a new framework of MAs based on decomposition, in which the genetic algorithm(GA) is used as the global search, and simulated annealing algorithm(SA) as the local search.3) In addition, this thesis compares two adaptive mechanisms, both of which use the historical information to guide the local search process, so as to further enhance the efficiency of the proposed algorithm.4) The proposed algorithm is applied to the software next release problem(NRP) and vehicle routing problems(VRP). The experimental results show that our proposed approach is very competitive. In addition, according to the real data of NRP model, we have established models of single target NRP and two objective NRP under the condition of constraints, respectively(we regard degree of constraint violations as the second goal), then respectively the multiobjective algorithm are compared with the state-of-the art of single objective optimization algorithm, And we usually intuitive that a single objective problem easier to solve, the experimental results show that multiobjective algorithm on real NRP is superior to single target.