A Comparative Study of Rigid and Modified Simplex Methods for Optimal Parameter Settings of ACO for Noisy Non-Linear Surfaces

Authors: Seksan Chunothaisawat, Pongchanun Luangpaiboon

Abstract:

There are two common types of operational research techniques, optimisation and metaheuristic methods. The latter may be defined as a sequential process that intelligently performs the exploration and exploitation adopted by natural intelligence and strong inspiration to form several iterative searches. An aim is to effectively determine near optimal solutions in a solution space. In this work, a type of metaheuristics called Ant Colonies Optimisation, ACO, inspired by a foraging behaviour of ants was adapted to find optimal solutions of eight non-linear continuous mathematical models. Under a consideration of a solution space in a specified region on each model, sub-solutions may contain global or multiple local optimum. Moreover, the algorithm has several common parameters; number of ants, moves, and iterations, which act as the algorithm-s driver. A series of computational experiments for initialising parameters were conducted through methods of Rigid Simplex, RS, and Modified Simplex, MSM. Experimental results were analysed in terms of the best so far solutions, mean and standard deviation. Finally, they stated a recommendation of proper level settings of ACO parameters for all eight functions. These parameter settings can be applied as a guideline for future uses of ACO. This is to promote an ease of use of ACO in real industrial processes. It was found that the results obtained from MSM were pretty similar to those gained from RS. However, if these results with noise standard deviations of 1 and 3 are compared, MSM will reach optimal solutions more efficiently than RS, in terms of speed of convergence.

Keywords: Ant colony optimisation, metaheuristics, modified simplex, non-linear, rigid simplex.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1074369

References:

[1] C. Blum and A. Roli, "Metaheuristics in Combinatorial Optimisation: Overview and Conceptual Comparison". ACM Computing surveys, vol. 35, no. 3, pp. 268-308, 2003.
[2] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, "Optimisation by Simulated Annealing". Science, vol. 220, no. 4598, pp. 671-679, 1983.
[3] F. Glover, "Tabu Search - part i". ORSA Journal on Computing, vol. 1, no. 3, pp. 190-206, 1986.
[4] M. Dorigo and T. Stutzle, Ant Colony Ooptimisation. Massachusetts, Bradford Book, 2004.
[5] E.A. Hart and J. Timmis, "Application Areas of AIS: The Past, the Present and the Future". Applied Soft Computing, vol. 8, no. 1, pp. 191-201, 2008.
[6] D.E. Goldberg, Genetic Algorithms in Search, Optimisation and machine learning. Massachusetts, Addison-Wesley, 1989.
[7] P. Merz and B. Freisleben, 1999. "A Comparison of Memetic Algorithms, Tabu Search, and Ant Colonies for the Quadratic Assignment Problem", presented at the 1999 Congress on Evolutionary Computation.
[8] S. Haykin, Neural Networks: A Comprehensive Foundation (2nd ed). NJ: Prentice Hall, 1999.
[9] J. Kennedy and R.C. Eberhart, Swarm Intelligence. San Francisco, CA: Morgan Kaufmann Publishers, 2001.
[10] M. Eusuff, K. Lansey and F. Pasha, "Shuffled Frog-Leaping Algorithm: A Memetic Metaheuristic for Discrete Optimisation". Engineering Optimisation, vol. 38, no. 2, pp. 129-154, 2006.
[11] H. Aytug, M. Knouja and F.E. Vergara, "Use of Genetic Algorithms to Solve Production and Operations Management Problems: A Review". International Journal of Production Research, vol.41, no. 17, pp. 3955-4009, 2003.
[12] S.S. Chaudhry and W. Luo, "Application of Genetic Algorithms in Production and Operations Management: A Review". International Journal of Production Research, vol.43, no. 19, pp. 4083-4101, 2005.
[13] D. Dasgupta, Artificial Immune Systems and their Applications. Springer-Verlag, 1998.
[14] M. Dorigo and C. Blum, "Ant Colony Optimisation Theory: A survey". Theoretical Computer Science, vol. 344, no.2-3, pp. 243-278, 2005.
[15] P. Ittipong, P. Luangpaiboon and P. Pongcharoen, 2008. "Solving Non-Linear Continuous Mathematical Models Using Shuffled Frog Leaping and Memetic Algorithm". Presented at the 2008 Operations Research Network Conference, Bangkok, Thailand.
[16] W.G.R. Spendley, G.R. Hext, and F.R. Himsworth, "Sequential Application of Simplex Designs in Optimisation and Evolutionary Operation". Technometrics, vol. 4, no. 4, pp. 441-461, 1962.
[17] J.A. Nelder and R. Mead, "A Simplex Method for Function Optimisation", Computer Journal, vol. 7, pp. 308-313, 1965.
[18] J.A.M. Pulgarin, A.A. Molina and M.T. Alanon Pardo, "The Use of Modified Simplex Method to Optimise the Room Temperature Phosphorescence Variables in the Determination of Antihypertensive Drug", Talanta, vol. 57, pp. 795-805, 2002.
[19] F.H. Walters, L.R. Parker, S.L. Jr.,Morgan and S.M. Deming,. Sequential Simplex Optimisation. CRC Press, Inc., Boca Raton, 1991.