Some Researches On Ant Colony Optimization

As a nature-inspired swarm intelligence algorithm, ant colony optimization belongs to the class of meta-heuristics. It simulates the foraging behavior of real ant colony. When foraging, ants leave a chemical pheromone trail on the path, and decide the way forward according to nearby pheromone concentration level. Ant’s individual behavior pattern is relatively simple; the colony communicates via a scalar pheromone. But independent parallel behaviors of ants make the colony intelligent. Because ant system is naturally distributed, self-learning, self-organizing, robust and simple, so when solving the optimization problem, ant colony optimization has better problem solving capability than traditional mathematical methods. Thus the algorithm has been given abroad attention and application in many fields of industry and people’s life in society.The essential trait of ant colony optimization is a parametrized probabilistic model, which is called the pheromone model. In each iteration, the system generates the population according to the model, and then in turn the model is reflected by the population information to influence the next population. The pheromone model can be seen as priori information directing the further evolution or posteriori information reflecting previously obtained solutions. So the pheromone model directly determines the performance of ant colony optimization. Therefore, this paper focus on exploring a better model to improve the performance of ant colony optimization. We study the pheromone model from the point of view of expressive power, and then discuss expressive ability of the pheromone model under different problems. Ideally, the pheromone model should be able to contain all the information of the population. But actually, for different constrained problem, traditional pheromone models suffer some degree of information missing. Although the insufficient expressing ability can be made up by the algorithm, we also note that additional VI supplementary for the pheromone model does not completely make up the loss of information. And as the problem size increases, the expressive ability to the pheromone model will severely constrain algorithm performance.To compensate the lack of expressive ability, we deduce the full probability distribution model of decision variables, and present a full pheromone model without information loss. Although the full pheromone model can get desired results, it needs a super-polynomial space. In contrast, the standard model has been greatly simplified in space. However, this simplification is done at the expense of information loss. The drop will cause the search bias in the search process, and thus affect the performance of the algorithm.In order to get enough information while pay small space price, we propose the g-order pheromone model. This model can unify the full pheromone model and the standard pheromone model(the 1-order pheromone model). According to demand, the g-order pheromone model can make a balance between apace cost and description ability. Thus using the g-order pheromone model can both avoid excessive cost of space and provide necessary description capability. We analyze the advantages of the g-order model, and explain how the g-order pheromone model further improve the algorithm performance on the basis of the standard model. In ant colony optimization, competition among individuals is the driving force of algorithm. Through a comparative analysis, we find that: the competition between individuals in the 1-order pheromone model is exclusive, while the competition between individuals in the g-order pheromone model is compatible. It is just this compatible competition that make up for the lack of the global search ability and the population diversity.In the experiment, we put forward the concept of sample location and similarity coefficient in the terms of statistics to analyze the algorithm behavior. Essentially, ant colony optimization is a probabilistic technique, and the pheromone model describes the probability distribution model of the solution space. Moreover, we consider the initial state of ants as the data sample location. At runtime, each ant probabilistically gets a sample from a sample location according to the pheromone model. In the 1-order pheromone model, all sample locations are on the same level and any solution is likely to be got from any sample location. But in the higher order pheromone model, sample locations can be divided into two types: key and assistant. It is just distinctions between sample locations makes the compatible competition between individuals in the g-order pheromone model. What’s more, we also give a method to quantify the similarity between individuals- similarity coefficient. The similarity coefficient is an effective tool to describe the population diversity and study the dynamic algorithm behavior. Through the analysis of the g-order pheromone model, we present the concept of key sample locations to explain the success of the g-order model and gives a new pheromone update rule for the g-order pheromone model.Ant colony optimization is mainly used to solve NP problems. In the search process, pheromone model may gradually deviate from the optimal solution, this phenomenon is called search deception. The algorithm tends to suffer from search bias, which is caused by the deception. As a result, the algorithm gradually deviated from the direction of the optimal solution, and eventually converge to some local optima. Typical deceptions like representation bias and construction bias both can be translated as the unfair competition among ants. In this paper, the deceive phenomenon is studied, and a new type of search bias- composite properties is proposed. In the composite properties, decision variables is not independent but interacted, and this connection cannot be separated. This paper studies the pheromone model from the perspective of expression, and it is just the composite properties which lead poor expressive ability. Composite properties exist in NP problems, and is the main reason of search bias. In this paper we discuss the effect of composite properties to algorithm performance, and use the g-order pheromone model to solve the deception phenomenon caused by composite properties.The purpose of using ant colony optimization is to find the optimal solution in combinatorial optimization problems. But as a swarm intelligence algorithm, the real tar is the whole population. Its implicit assumption is that the higher the average colony quality is, the higher probability to find the optimal solution. This is because, the lower quality limit of the best individual is the average quality of population. So for a swarm intelligence algorithm, including ant colony optimization algorithm, the idea behavior is that, the average colony quality becomes higher and higher. This means the algorithm can improve the current best individual continuously. In this paper, the population dynamic behavior of ant colony optimization using the g-order pheromone model is studied theoretically. We present and proves the conclusion of the g-order pheromone model and prove the convergence of the full pheromone model.