Genetic Algorithms For Solving Two Types Of Combinatorial Optimization Problems

Combinatorial optimization is a kind of common optimization problems,which is characterized by discrete variable values.This kind of problem is widely used in artificial intelligence,machine learning,software engineering and production management,etc.The traveling salesman problem(TSP)and the knapsack problem(KP)are typical NP-hard problems in combinatorial optimization.The traveling thief problem(TTP)combines these two types of problems.In a TTP problem,the interaction between the two kinds of sub-problems makes TTP problem become more challenging.In addition,when more than one optimization objectives are considered in the traveling salesman problem,this problem is called a multi-objective traveling salesman problem(MOTSP).MOTSP is the extension of single objective TSPs,and the optimal solutions can provide decision makers with additional choices.This thesis presents a new model of TTP with uncertain information,and based on the information of problems,develops genetic algorithms for this kind of TTP and bi-objective TSP(BOTSP),respectively.1.TTP is a composite optimization problem which combines TSP with KP,and has an accumulated computational complex caused by these two problems.In this paper,based on the original version of TTP,a new optimization model with probability distribution information is first proposed by considering that the thief doesn't explicitly know the item location in advance in all cities.Then,by calculating the effective value of each item,a selection scheme of items is provided.Finally,taking advantage of an existing genetic algorithm for solving TSP and a designed local search scheme,a new hybrid genetic algorithm is developed for dealing with the new TTP model.The simulation results show the proposed algorithm is feasible and efficient.2.For BOTSP with minimizing the distance and the cost,firstly,two satisfaction degree indices are provided by considering the influences of the distance weight and the cost weight of each edge.The first satisfaction degree is used to select edges in a "rough" way,while the second satisfactiondegree is executed for a more "refined" choice.Secondly,two satisfaction degrees are also applied to generate new individuals in the iteration process.Finally,based on genetic algorithm framework as well as 2-opt selection strategy,a hybrid genetic algorithm is proposed.The simulation illustrates the effectiveness of the proposed algorithm.