An in-depth discussion of challenges related to solving Shortest Path Problems using ShortestPathACO based algorithms
[ 1 ] Katedra Sieci Telekomunikacyjnych i Komputerowych, Wydział Elektroniki i Telekomunikacji, Politechnika Poznańska | [ P ] pracownik
2013
rozdział w monografii naukowej
angielski
- shortest path problem
- ant colony optimization
- ACO
- metaheuristics
EN The studies hitherto carried out have revealed that the application of the ShortestPathACO strategy based on the Ant Colony Optimization (ACO) metaheuristics makes it possible to solve the shortest path problem in a way that differs from traditional approaches. Practical applications of algorithms that are based on the ACO metaheuristics require accurate and deep understanding of the importance of particular parameters of the algorithm and this issue is absolutely crucial. This involves deep understanding of both their influence and the degree to which they are expected to offer a possibility of the modification in their implementation. On account of the heuristic approach to the problem to be solved, it is important then to choose appropriately the mode of operation of the algorithm to be applied as well as a determination of the parameters that will ensure proper course of operation in a given specific situation. This chapter aims then to describe, analyse and interpret the observations provided by relevant studies and to present conclusions in relation to the conducted research work and subsequent analyses. The chapter mainly focuses on indicating the essential problems and defining the areas for further optimization of the ShortestPathACO approach. Limitations and constrains involved in the application of the ACO metaheuristics in solving the shortest path problem are highlighted. A particular attention is given to the greediness and convergence of the algorithm, as well as to possibilities of a secondary use of available information on the pheromone level. In addition, movement patterns of ants around the graph and the choice of their number depending on the class of graphs are analysed and are followed by a proposition of alternative approaches.
77 - 88