Research On Solving Combinatorial Optimization Problems Based On Evolutionary Algorithms

With the continuous development of modern science and technology,combinatorial optimization problems have a wide range of applications in economic dispatch,software and hardware collaborative design,image processing,communication engineering,integrated circuits,path planning and many other fields.Due to the complexity of combinatorial optimization problems,the difficulty of solving them increases exponentially with the increase of the scale of the problems,which leads to the difficulty of solving combinatorial optimization problems with accurate algorithms.Evolutionary algorithm has the advantages of simple idea,easy to implement and strong optimization ability,and has been successfully used to solve many combinatorial optimization problems,so it has become a very important method to solve combinatorial optimization problems based on evolutionary algorithm.This paper mainly studies how to solve combinatorial optimization problems such as knapsack problem with single continuous variable(KPC),bounded knapsack problem(BKP)and hardware/software partitioning problem(HW/SW)based on genetic algorithm(GA),particle swarm optimization(PSO),differential evolution(DE),group theory optimization(GTOA)and barnacle mating optimization(BMO).The research contents are summarized as follows:1.Based on the ordered pair coding method,a new algorithm DE-GTOA,which combines DE and GTOA to solve KPC,is proposed,and the DE-GTOA is used to solve four kinds of large-scale KPC instances.It is proved that DE-GTOA is highly competitive by comparing with the existing algorithms.2.Based on modular operation to reconstruct the evolutionary formula of BMO,a discrete barnacle mating optimization algorithm(DBMO),based on modular operation is proposed,and DBMO is used to solve KPC problem and BKP problem.The efficiency of DBMO is verified by comparing with the existing algorithms.3.A new idea of using evolutionary algorithm to solve HW/SW is proposed.Firstly,a repair and optimization method for dealing with the infeasible solution of HW/SW is given,and then a general algorithm framework for solving HW/SW based on evolutionary algorithm is proposed.under this framework,the efficiency of solving HW/SW with GTOA is verified by comparing the results of several evolutionary algorithms for solving large-scale HW/SW examples.