الگوریتم بهینه سازی کلونی مورچه برای زمانبندی مسئله
Abstract
I- Introduction
II- Related Work
III- The ACO Algorithm
IV- A New Multi-Population Co-Evolution Ant Colony Optimization(ICMPACO) Algorithm
V- Application of the ICMPACO Algorithm for Solving TSP
VI- APPLICATION OF THE ICMPACO ALGORITHM FOR SOLVING GATE ASSIGNMENT PROBLEM
VII- CONCLUSION AND FUTURE WORK
References
Abstract
In this paper, an improved ant colony optimization (ICMPACO) algorithm based on the multi-population strategy, co-evolution mechanism, pheromone updating strategy, and pheromone diffusion mechanism is proposed to balance the convergence speed and solution diversity, and improve the optimization performance in solving the large-scale optimization problem. In the proposed ICMPACO algorithm, the optimization problem is divided into several sub-problems and the ants in the population are divided into elite ants and common ants in order to improve the convergence rate, and avoid to fall into the local optimum value. The pheromone updating strategy is used to improve optimization ability. The pheromone diffusion mechanism is used to make the pheromone released by ants at a certain point, which gradually affects a certain range of adjacent regions. The co-evolution mechanism is used to interchange information among different sub-populations in order to implement information sharing. In order to verify the optimization performance of the ICMPACO algorithm, the traveling salesmen problem (TSP) and the actual gate assignment problem are selected here. The experiment results show that the proposed ICMPACO algorithm can effectively obtain the best optimization value in solving TSP and effectively solve the gate assignment problem, obtain better assignment result, and it takes on better optimization ability and stability.
INTRODUCTION
Ant colony optimization (ACO) algorithm was proposed by Dorigo in 1992 [1]. It is a heuristic evolutionary algorithm based on population, which is inspired by the research results of the collective behavior of the real ants in nature. It has been proved that the ACO algorithm takes on a better optimization performance in solving optimization problems. The ACO algorithm relies on the activities of many individualities and feedback of information. Although the activity of ant is very simple, the activity of whole ant colony is acceptable. The ACO algorithm has the characteristics of distributed computing, positive feedback and heuristic search. In essence, it is a heuristic global optimization algorithm in the evolutionary algorithm [2]–[11]. In process of the evolution, the information interaction based on pheromone plays a very important role. Due to the advantages of the ACO algorithm, it is widely applied in solving combinatorial optimization problems, such as the traveling salesman problem, assignment problem, job-shop scheduling problem, vehicle routing problem, graph coloring problem and network routing problem and so on [12]–[25]. A lot of experts have devoted themselves to the research of the ACO algorithm, and some improved ACO algorithms are proposed to solve the complex optimization problems.