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

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.

• Seksan Chunothaisawat
• Pongchanun Luangpaiboon

• Ant colony optimisation
• metaheuristics
• modified simplex
• non-linear
• rigid simplex.

[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.