A Mahalanobis Distance-based Diversification and Nelder-Mead Simplex Intensification Search Scheme for Continuous Ant Colony Optimization

Ant colony optimization (ACO) and its variants are applied extensively to resolve various continuous optimization problems. As per the various diversification and intensification schemes of ACO for continuous function optimization, researchers generally consider components of multidimensional state space to generate the new search point(s). However, diversifying to a new search space by updating only components of the multidimensional vector may not ensure that the new point is at a significant distance from the current solution. If a minimum distance is not ensured during diversification, then there is always a possibility that the search will end up with reaching only local optimum. Therefore, to overcome such situations, a Mahalanobis distance-based diversification with Nelder-Mead simplex-based search scheme for each ant is proposed for the ACO strategy. A comparative computational run results, based on nine nonlinear standard test problems, confirms that the performance of ACO is improved significantly with the integration of the proposed schemes in the ACO.

Authors:

• Sasadhar Bera
• Indrajit Mukherjee

Keywords:

• Ant Colony Optimization
• Diversification Scheme
• Intensification
• Mahalanobis Distance
• Nelder-Mead Simplex.

References:

[1] I. Mukherjee, and P.K. Ray, "A review of Optimization Techniques in
Metal Cutting Processes," Computers and Industrial Enginering, Vol.
50, pp. 15-34, 2006.
[2] I. Mukherjee, and P.K. Ray, "Artificial Neural Network and
Metaheuristic Strategies: Emerging Tools for Metal Cutting Process
Optimization," in Handbook on Computational Intelligence in
Manufacturing and Production Management, Idea Group Inc (IGI),
2008 , pp 366-397, Ch. XIX.
[3] M. Dorigo, "Optimization, Learning and Natural Algorithms (in
Italian)," Ph.D. thesis, ipartimento di Elettronica, Politecnico di Milano,
Italy, 1992.
[4] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant System: Optimization by
a Colony of Cooperating Agents," IEEE Transactions on Systems, Man,
and Cybernetics, Vol. 26, no. 1, Part B, 1996, pp. 29-41.
[5] T. Stutzle, and H. H Hoos, "MAX-MIN, Ant System," Future
Generation Computer Systems, Vol. 16, no. 8, pp. 889-914, 2000.
[6] M. Dorigo, and L. M. Gambardella, "Ant Colony System: A cooperative
learning approach to the traveling salesman problem," IEEE
Transactions on Evolutionary Computation, Vol. 1, no. 1, pp. 53-66,
1997.
[7] G. Bilchev, and I. C. Parmee, "The Ant Colony Metaphor for Searching
Continuous Design Spaces," Lecture Notes in Computer Science,
Volume 993, pp. 25-39, 1995.
[8] M. Wodrich, and G. Bilchev, "Cooperative distributed search: the ant-s
way." Control Cybernetics, Vol. 26, no. 3, pp. 413-446, 1997.
[9] M. Mathur, , S.B. Karale, S Priye, V.K. Jyaraman, and B.D. Kulkarni,
"Ant colony approach to continuous function optimization," Industrial
and Engineering Chemistry Research, Volume 39, pp. 3814-3822, 2000.
[10] J. Dreo, and P. Siarry, "Continuous interacting ant colony algorithm
based on dense hierarchy," Future Generation Computer Systems, Vol.
20, pp. 841-856, 2004.
[11] K. Socha, and M. Dorigo, "Ant colony optimization for continuous
domains," European Journal of Operational Research, Vol. 185, pp.
1155-1173, 2008.
[12] M. Schluter, J. A. Egea, and J. R Banga, "Extended ant colony
optimization for non-convex mixed integer nonlinear programming,"
Computers & Operations Research, Vol. 36, pp. 2217-2229, 2009.
[13] P.C. Mahalanobis, "On the generalized distance in statistics," in Proc. of
the National Institute of Science, India, Vol. 2, no. 1, 1936, pp. 49-55.
[14] J. A. Nelder, and R. Mead, "A Simplex Method for Function
Minimization," Computer Journal, Vol. 7, pp. 308-313, 1965.
[15] L. Chen, J. Shen, L. Qin, and J. Fan, "A Method for Solving
Optimization Problem in Continuous Space Using Improved Ant Colony
Algorithm," Lecture Notes in Computer Science, Vol. 3327, pp. 61-70,
2004.