Research On Improved Performance Of Ant Colony Algorithm By Genetic Algorithm

Ant colony algorithm (ACA) has emerged recently as a new meta-heuristic which belong to the class of problem-solving strategies derived from nature. It is based on the research on the ant finding the shortest road from the nest to the destination. It simulate the cooperating process which ant colony search route from nest to food. It is a kind of stochastic explorative algorithms. It iterates to the best answer according to selective strategy and information element, which is generated by each ant. The characteristic of parallel, positive feedback and robust is strongly showed in the running of ACA. It has showed a great deal of salient character and performed great value in its application special for solving the combination-optimize questions. So the research of theory and utility of ACA has great merit.As a new algorithm, ACA has no systematic analyzing method and stable foundation of mathematics, and has no theory to guide the choosing of parameters; at the initial stage of algorithm, the pheromone is very scarcity which result the search speed is very slowly; algorithms have the problems of early converged or stopped; can not enlarge the searching space of the solution; can not make good use of the pheromone which the current solutions taken etc.Choosing the analysis of character of the basic algorithms of ant colony as the research background, this paper analyses the effect of five parameters which are: heuristic factorα, expectation factorβ, evaporation factorρ, number of ant m and the amount of pheromone Q by experiment. The results show that the parametersα,β,ρhave strong effect on the basic ACA and find that their effects are coupling tightly. At present, the enactment of the parameters of an ant system is determined by experience and experiment. This leads to heavy work load and makes the optimal combination of the parameters difficult to obtain. So this paper proposed using GA to optimize parametersα,β,ρ, the method applied to the travelinn salesman problem shows hood performance feasibility and effectiveness.On the base of consulting literatures both here and abroad, this paper introduces a new solution for making up some defect of basic ACA: using a hybrid algorithm named GA-ACA which connects the GA and ACA for solving problem. The basic idea : at the beginning the algorithm using GA to solve the problem , the result is generating the distribution of inimical pheromone ,because of GA has the good merit of speed ability,random city and convergences in the large; then solve the problem using ACA. In addition, the GA-ACA improved in the following aspect in contrast to the basic ACA :①using the choosing strategy based on determinacy and random city , in order to avoiding local optimization②updating the local pheromone and the total pheromone by adjusting the pheromone adaptively , in order to make good use of the current solution③introduce a local search algorithms named 2-opt, in order to extend the searching-space.At last, using the hybrid algorithm to solve the problem of TSP and QAP , the result of experiment showed that the improved algorithms has better performance of speed ability and accuracy.