The Research Of Genetic Algorithm And Ant Colony Optimization Algorithm And Their Applications In Traveling Salesman Problem And Distribution Network Reconfiguration

The genetic algorithm and the ant colony optimization algorithm are seriously studied, some new ideas and novel algorithms are proposed, and these novel algorithms are successfully applied to the traveling salesman problem (TSP) and distribution network reconfiguration. The main achievements are as follows:Based on the analysis of fitness landscape of TSP, a variable neighborhood search mutation operator, called GIIM, is designed by combining simple inversion mutation operator with insertion mutation operator. The GIIM can adaptively adjust the size of neighborhood search, and has very strong ability of local search. Based on GIIM, an efficient genetic algorithm for TSP, called EGA, is presented by combining partially matched crossover (PMX) and annealing selection with elitist strategy. The simulation for TSP shows that EGA has not only very strong global search ability but also very fast convergence speed, whose testing results are the same or even more superior ones in comparison with the optimal path in the newest literatures and TSPLIB.Based on the analyses of human evolution's properties, a novel genetic algorithm (GTGA) is proposed with analogies to the gene pool and two basis gene operation methods in gene therapy theory. The core of GTGA lies on construction of a gene pool and a therapy operator, which consists of insertion operation and removing operation. The methods of creation and updating of the gene pool and construction of the therapy operator are given and demonstrated by TSP. The theoretical analysis and simulation results of TSP show that GTGA can restrain the degeneration and premature convergence phenomenon effectively during the evolutionary process while greatly increasing the convergence speed.Based on the deep analysis of the domain knowledge of TSP, a candidate set strategy based on Delauney triangulation (DT), called CSDT, is designed. A novel ant colony system based on Delaunay triangulation and mutation for TSP, called DMACS, is proposed by applying GIIM and CSDT to ant colony system. Tovalidate DMACS, some representative TSP instances are tested. The results of simulation show DMACS is superior to the similar algorithms in the literatures.By applying the idea of health care and the treatment method to ant colony system (ACS), a novel ant colony system (MCACS) is proposed. The core of MCACS lies on the design of a solution components pool and nourishing operator and remedying operator. The implement methods of MCACS are demonstrated by TSP. To validate the superiority of MCACS, MCACS and ACS and DMACS are compared as regards TSP. The simulation results show that MCACS promises excellent performance not only in the convergence speed but also in the quality of solution.In order to apply GTGA to distribution network reconfiguration, the codification strategy based on the basic loops is adopted; by regarding the loops and the islands as inferior gene and regarding the gene from superior chromosomes as the eminent gene, the methods of creation and updating of gene pool are given; by designing the removing operation and the insertion operation, the therapy operator is constructed. The simulation results show that GTGA has the same or even more superior performance in not only searching efficiency and convergence stability but also finding the global optimal solution when compared with the algorithms in the newest literatures.Distribution network reconfiguration using MCACS is proposed. A codification strategy based on the basic loops is adopted. By regarding the solution components from superior solutions as the eminent ones, the methods of creation and updating of eminent solution components pool is given. By making ants to select solution components form the eminent solution components pool at proper probability, nourishing operator is formed. By regarding the loops and the islands as morbid solution components, the remedying operator is created. The simulation results show that MCACS has the more superior performance when compared with not only ant colony optimization algorithms but also other algorithms in the newest literatures.