The Effect of Pheromone in Ant-Based Hyper-Heuristic

Abstract:

- Ant algorithms mimic the behavior of the ants where their important behavior is the ability to find the shortest path between food sources and their nest despite being almost blind. In the algorithms, as ants travel, they deposit a chemical substance called pheromone which; together with visibility values is used to make decisions. This paper investigates the effects of pheromone values on solving a routing problem; the capacitated vehicle routing problem (CVRP) In our approach, in order to produce a generalized approach, we developed an ant-based hyper-heuristic where pheromone and visibility values consider a non-domain specific knowledge. In this paper, we propose to provide all visited heuristics with some amount of pheromone. The distribution of pheromone values will be distributed proportioned to the performance done by the ants. This is to encourage the exploration of new edges that might lead to better solutions. We show that our results are better when compared to two other ant algorithm hyper-heuristics in the literature.

• Periodical: Applied Mechanics and Materials (Volumes 446-447)
• Pages: 1202-1206
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.446-447.1202
• Online since: November 2013
• Authors: Abd Aziz Zalilah
• Keywords: Ant Algorithms, Hyper-Heuristic, Pheromone, Vehicle Routing Problem

References

[1] Abd Aziz Z & Kendall G. An Investigation of an Ant-based Hyper-heuristic for the Capacitated Vehicle Routing Problem. In Proceedings of Multidiciplinary International Conference on Scheduling: Theory and Applications (MISTA), (2009).

[2] Bullnheimer B., Hartl R.F. & Strauss C. Applying the Ant System to the Vehicle Routing Problem, In MetaHeuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic, 1999a.

DOI: 10.1007/978-1-4615-5775-3_20

[3] Bullnheimer B., Hartl R. F. & Strauss C. A New Rank Based Version of the Ant System - A Computational Study. In Central European Journal of Operations Research, (volume 7, pp.25-38), 1999b.

[4] Burke E. K., Kendall G., Landa-Silva J. D., O'Brien R. & Soubeiga E. An Ant Algorithm Hyperheuristic for the Project Presentation Scheduling Problem. In Proceedings of the 2005 IEEE Congress on Evolutionary Computation, (volume 3, pp.2263-2270.

DOI: 10.1109/cec.2005.1554976

[5] Burke E.K., Kendall G., Newall J., Hart E. & Ross P. Hyper-heuristics: An Emerging Direction in Modern Search Technology. In Glover F. & Kochenberger G.A. (eds), Handbook of Metaheuristics (pp.457-474). Kluwer Academic Publishers, 2003b.

DOI: 10.1007/0-306-48056-5_16

[6] Burke E.K., Kendall G., O'Brien R.F.J., Redrup D. & Soubeiga E. An Ant Algorithm Hyper-heuristic. In Proceedings of the Fifth Meta-heuristics International Conference (MIC2003), 2003c.

[7] Braysy O. & Gendreau M. Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. In Transportation Science, (volume 39, pp.104-118), 2005a.

DOI: 10.1287/trsc.1030.0056

[8] Chen P. Hyper-heuristic Ant Algorithm for the Traveling Tournament Problem. PhD Thesis. University of Nottingham, UK., (2006).

[9] Chen P., Kendall G. & Berghe G.V. An Ant Based Hyper-heuristic for the Travelling Tournament Problem. In Proceedings of IEEE Symposium of Computational Intelligence in Scheduling (CISched 2007), (pp.19-26), (2007).

DOI: 10.1109/scis.2007.367665

[10] Cordeau J-F. & Laporte G. Tabu Search Heuristics for Vehicle Routing Problem. In Metaheuristic Optimization via Memory and Evolution, (volume 30, pp.145-163), (2005).

DOI: 10.1007/0-387-23667-8_6

[11] Cowling P., Kendall G. & Soubeiga E. Hyperheuristics: A Robust Optimisation Method Applied to Nurse Scheduling. In Seventh International Conference on Parallel Problem Solving from Nature, PPSN, (pp.851-860). LCNS Springer, 2002a.

DOI: 10.1007/3-540-45712-7_82

[12] Crowston W.B., Glover F., Thompson G.L. & Trawick J.D. Probabilistic and Parametric Learning Combinations of Local Job Shop Scheduling Rules. In ONR research memorandum. Cernegie-Mellon University Pittsburgh, (1963).

DOI: 10.21236/ad0600965

[13] Dantzig G.B. & Ramser J.H. The Truck Dispatching Problem. In Management Science, (volume 6(1), pp.80-91), (1959).

DOI: 10.1287/mnsc.6.1.80

[14] Dorigo M. & Stutzle T. Handbook of Metaheuristics, Glover F. & Kochenberger G.A. (eds) (pp.251-285). Kluwer Academic Publishers, 2003a.

[15] Dorigo M. & Di Caro G. Ant Algorithms for Discrete Optimization. Artificial Life, (volume 5, pp.137-172), 1999a.

[16] Dorigo M. & Di Caro G. The Ant Colony Optimization Meta-heuristic. New Ideas in Optimization (pp.11-32). Mc Graw Hill, 1999b.

[17] Dorigo M. & Di Caro G. Ant Colony Optimization: A New Meta-heuristic. In Proceedings of the Congress on Evolutionary Computation, (pp.1470-1477). IEEE Press, 1999c.

DOI: 10.1109/cec.1999.782657

[18] Dorigo M. & Gambardella L. M. Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem. In IEEE Transaction on Evolutionary Computation, (volume 1, pp.53-66), (1997).

DOI: 10.1109/4235.585892

[19] Dorigo M., Maniezzo V. & Colorni A. Positive feedback as a Search Strategy. In Technical Report No 91-016. Dipartimento di Eletronica, Politecnico di Milano, Italy, (1991).

[20] Dorigo M., Maniezzo V. & Colorni A. Ant system: Optimisation by a Colony of Cooperating Agents. In IEEE Transactions on Systems, Man and Cybernetics, (p.26, 29-41), (1996).

DOI: 10.1109/3477.484436

[21] Dorigo M., Maniezzo V. & Colorni A. Positive feedback as a Search Strategy. In Technical Report No 91-016. Dipartimento di Eletronica, Politecnico di Milano, Italy, (1991).

[22] Fisher H & Thompson G.L. Probabilistic Learning Combinations of Local Job-shop Scheduling Rules. In Factory Scheduling Conference. Carnegie Institute of Technology, (1961).

[23] Fisher H & Thompson G.L. Probabilistic Learning Combinations of Local Job-shop Scheduling Rules. In J.F. Muth & G.L. Thompson (eds), Industrial Scheduling, (pp.225-251). Prentice-Hall, Inc, New Jersey, (1963).

DOI: 10.21236/ad0600965

[24] O'Brien R.F.J. Ant Algorithm Hyperheuristic Approaches for Scheduling Problems. PhD Thesis, University of Nottingham. UK, (2007).

[25] Soubeiga E. Development and Application of Hyperheuristics to Personnel Scheduling. PhD thesis. School of Computer Science and Information Technology, University of Nottingham, (2003).

[26] Stutzle T. & Dorigo M. ACO Algorithms for the Quadratic Assignment Problem. New Ideas in Optimization (pp.33-50), McGraw Hill, (1999).

[27] Vehicle Routing Datasets. Website: http: /www. coin-r. org/SYMPHONY/branchandcut/ VRP/data, (2003).