بهینه سازی کلونی مورچه ها ترکیبی برای دامنه های پیوسته

Research on optimization in continuous domains gains much of focus in swarm computation recently. A hybrid ant colony optimization approach which combines with the continuous population-based incremental learning and the differential evolution for continuous domains is proposed in this paper. It utilizes the ant population distribution and combines the continuous population-based incremental learning to dynamically generate the Gaussian probability density functions during evolution. To alleviate the less diversity problem in traditional population-based ant colony algorithms, differential evolution is employed to calculate Gaussian mean values for the next generation in the proposed method. Experimental results on a large set of test functions show that the new approach is promising and performs better than most of the state-of-the-art ACO algorithms do in continuous domains.

Inspired by the ants’ foraging behavior, the first ant colony algorithm was proposed in (Dorigo, 1992). The core idea of an ant system is based on the fact that each ant deposits pheromone on the foraging path. In the early research, ant colony algorithms have been successfully applied for solving combinatorial optimization problems, including the traveling salesman problem (TSP) (Dorigo & Gambardella, 1997), the quadratic assignment problem (QAP) (Maniezzo, Colorni, & Dorigo, 1999) and the job shop scheduling problem (JSP) (Colorni, Dorigo, Maniezzo, & Trubian, 1994). The extension of the original ant colony algorithm to continuous domain can be accomplished by either discretizing the continuous domain into several regions or shifting from using a discrete probability distribution to using a continuous one such as a Gaussian probability density function (pdf). The first extension of ant colony algorithms to continuous domain is CACO (continuous ant colony optimization) (Bilchev & Parmee, 1995). CACO discretized the continuous neighborhood with nest structure. It initialized a nest on a given point of the search space and generates random vectors. The direction vector chosen was updated by the ants with better fitness values. In API (ant pachycondyla apicalis) (Monmarché, Venturini, & Slimane, 2000) each ant searched independently for a solution and the ants’ nest is periodically moved. CIAC (continuous interacting ant colony) (Dréo & Siarry, 2002) used some attractive points on the search space and direct communication between ants to improve the exploration. COAC (continuous orthogonal ant colony) (Hu, Zhang, & Li, 2008) also discretized the continuous search space and utilized the orthogonal design method to search the continuous domain completely. Another ensemble of ant colony optimization algorithms for continuous domain is mainly based on Gaussian probability density function sampling. CACS (continuous ant colony system) (Pourtakdoust & Nobahari, 2004) employed a Gaussian probability density function whose mean and variance are adjusted during evolution to sample the continuous search space. MACACO (multivariate ant colony algorithm for continuous optimization) (Franca, Coelho, Von Zuben, & de Faissol Attux RR, 2008) optimized the search space with multivariate Gaussian pdf which is created by the information contained in the covariance matrix of the ant population. Speak of population, there are some work which fully utilize the information in previous ant population to generate the next one. PB-ACO (population-based ACO) (Guntsch & Middendorf, 2002) kept track of a certain number of best solutions found so far and used the archive to update the pheromone. PB-ACO was applied to the TSP and QAP problems while ACOR (ant colony optimization in Rn) (Socha & Dorigo, 2008) extended the population-based ACO with Gaussian pdf as pheromone update. ACOR evolved several Gaussian pdfs in parallel and adopted the rank-based selection mechanism. ACOR also allowed exploiting the correlation between variables by coordinate rotation which is time-consuming. Inspired by PB-ACO and ACOR, our motivation for introducing a population based scheme is the dynamic generation of probability density functions in continuous domains. A hybrid ant colony optimization (HACO) incorporating with continuous population-based incremental learning (PBILc) and differential evolution (DE) (Sebag & Ducoulombier, 1998) is proposed in this paper. HACO employs the multi-Gaussian pdfs sampling in parallel and learns the next generation’s mean and variance values dynamically by PBILc. The rank-based selection method in ACOR may suffer local optima when the solutions in the archive are very close to each other. To alleviate this, HACO involves a differential evolution operator with linear combination of the one best and two random individuals (Montes and Velazquez-Reyes, 2006) in the current population. The combination of differential evolution and ant colony has been applied to feature selection and power systems (Chiou et al., 2004 and Khushaba et al., 2008). The rest of this paper is organized as follows. Section 2 describes HACO in detail. The pheromone representation and Gaussian pdf generation are elaborated in Section 2. Experimental results and analysis are presented in Section 3. Section 4 discusses how two different DE operators affect HACO. We conclude this paper and outline the future works in Section 5.

This paper has introduced a hybrid ACO algorithm with continuous population-based learning and differential evolution (HACO) for continuous optimization. HACO uses two kinds of Gaussian sampling in continuous domain. One is generated by the rank-based scheme and the other is learned by continuous population-based incremental learning with differential evolution operator. Experimental results on both low dimension and high dimension test functions show that the proposed algorithm is effective and efficient. Comparison experiments of two variants of differential evolutions are conducted and the best/1/bin wins. As future direction of research, we will explore the handling of variable correlation problems and conduct more experiments on more variants of differential evolution operators in ant colony optimization algorithms.