اعتبار،چابکی،پاسخگویی

Analyzing the impact of ant colony optimization parameters for path searching behavior

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشجوی دکتری، گروه برنامه‌ریزی حمل‌و‌نقل، دانشکده فنی‌ومهندسی، دانشگاه بین‌المللی امام خمینی(ره)، قزوین، ایران.

2 استاد، گروه برنامه‌ریزی حمل‌و‌نقل، دانشکده فنی‌ومهندسی، دانشگاه بین‌المللی امام خمینی(ره)، قزوین، ایران.

چکیده
Ant-inspired metaheuristic algorithms, such as Ant Colony Optimization (ACO), are dependable for addressing intricate problems in discrete and continuous domains. This study examines the influence of the pheromone significance factor (α), heuristic importance factor (β), and pheromone decay rate (ρ) on the effectiveness of ACO for path-searching. We analyze the algorithm's convergence rate and effectiveness in identifying the shortest path by simulating various parameter configurations on a standard graph. The value α= 2 was chosen based on prior research on the behavior of real ants. Our simulations demonstrated that α= 2 is a superior choice to α= 1, which the naïve approach would recommend. The experiments demonstrated that setting β to 1 and ρ to 10% resulted in the optimal convergence speed and the minor average path lengths. Also, by examining the effect of the number of ants on the convergence of the simulation, it was found that the selection of more ants shows more paths. Using more ants for the initial stop leads to a marginal decrease in the average path length.

کلیدواژه‌ها

موضوعات

Agarwal, P., & Mehta, S. (2014). Nature-inspired algorithms: State-of-art, problems and prospects. International Journal of Computer Applications, 100(14), 14–21.

Bäck, T. (2018). Evolutionary computation 1: Basic algorithms and operators. CRC Press.

Bonyadi, M. R., & Michalewicz, Z. (2017). Particle swarm optimization for single objective continuous space problems: A review. Evolutionary Computation, 25(1), 1–54. https://doi.org/10.1162/EVCO_r_00180

Carlisle, A. G., & Dozier, G. B. (2001). An off-the-shelf PSO. In Proceedings of the Workshop on Particle Swarm Optimization (pp. 1–6).

Colorni, A., Dorigo, M., & Maniezzo, V. (1991). Distributed optimization by ant colonies. In Proceedings of the First European Conference on Artificial Life (pp. 134–142).

Deneubourg, J.-L., Aron, S., Goss, S., & Pasteels, J. M. (1990). The self-organizing exploratory pattern of the Argentine ant. Journal of Insect Behavior, 3, 159–168. https://doi.org/10.1007/BF01417909

Dorigo, M., & Di Caro, G. (1999). Ant colony optimization: A new meta-heuristic. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC99) (Vol. 2, pp. 1470–1477). IEEE. https://doi.org/10.1109/CEC.1999.782657

Dorigo, M., Di Caro, G., & Gambardella, L. M. (1999). Ant algorithms for discrete optimization. Artificial Life, 5(2), 137–172. https://doi.org/10.1162/106454699568728

Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66. https://doi.org/10.1109/4235.585892

Forrest, S. (1996). Genetic algorithms. ACM Computing Surveys, 28(1), 77–80. https://doi.org/10.1145/234313.234350

Hassanat, A., Almohammadi, K., Alkafaween, E., Abunawas, E., Hammouri, A., & Prasath, V. S. (2019). Choosing mutation and crossover ratios for genetic algorithms—A review with a new dynamic approach. Information, 10(12), 390. https://doi.org/10.3390/info10120390

He, J., Sun, X., Li, W., & Chen, J. (2017). A new pheromone update strategy for ant colony optimization. Journal of Intelligent & Fuzzy Systems, 32(5), 3355–3364.

Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN’95 – International Conference on Neural Networks (Vol. 4, pp. 1942–1948). IEEE. https://doi.org/10.1109/ICNN.1995.488968

Maniezzo, V., & Colorni, A. (1999). The ant system applied to the quadratic assignment problem. IEEE Transactions on Knowledge and Data Engineering, 11(5), 769–778. https://doi.org/10.1109/69.806935

Mavrovouniotis, M., Ellinas, G., & Polycarpou, M. (2019). Electric vehicle charging scheduling using ant colony system. In 2019 IEEE Congress on Evolutionary Computation (CEC). IEEE.

Mavrovouniotis, M., Li, C., Ellinas, G., & Polycarpou, M. (2019). Parallel ant colony optimization for the electric vehicle routing problem. In 2019 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE.

Mavrovouniotis, M., & Yang, S. (2013). Dynamic vehicle routing: A memetic ant colony optimization approach. In Automated Scheduling and Planning: From Theory to Practice (pp. 283–301). Springer.

Nannen, V., & Eiben, A. E. (2006). A method for parameter calibration and relevance estimation in evolutionary algorithms. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (pp. 183–190). ACM.

Ostfeld, A. (2011). Ant colony optimization for water resources systems analysis—Review and challenges. In Ant Colony Optimization: Methods and Applications.

Parsons, S. (2005). Ant Colony Optimization by Marco Dorigo and Thomas Stützle, MIT Press, 305 pp., $40.00, ISBN 0-262-04219-3. The Knowledge Engineering Review, 20(1), 92–93.

Rezvanian, A., Vahidipour, S. M., & Sadollah, A. (2023). An overview of ant colony optimization algorithms for dynamic optimization problems.

Schoonderwoerd, R., Holland, O. E., Bruten, J. L., & Rothkrantz, L. J. (1997). Ant-based load balancing in telecommunications networks. Adaptive Behavior, 5(2), 169–207. https://doi.org/10.1177/105971239700500203

Shami, T. M., El-Saleh, A. A., Alswaitti, M., Al-Tashi, Q., Summakieh, M. A., & Mirjalili, S. (2022). Particle swarm optimization: A comprehensive survey. IEEE Access, 10, 10031–10061. https://doi.org/10.1109/ACCESS.2022.3142859

Teodorović, D., & Dell’Orco, M. (2005). Bee colony optimization—A cooperative learning approach to complex transportation problems. Advanced OR and AI Methods in Transportation, 51–60.

Trelea, I. C. (2003). The particle swarm optimization algorithm: Convergence analysis and parameter selection. Information Processing Letters, 85(6), 317–325. https://doi.org/10.1016/S0020-0190(02)00447-7

Van den Bergh, F., & Engelbrecht, A. P. (2006). A study of particle swarm optimization particle trajectories. Information Sciences, 176(8), 937–971. https://doi.org/10.1016/j.ins.2005.02.003

Vassiliadis, V., & Dounias, G. (2009). Nature-inspired intelligence: A review of selected methods and applications. International Journal on Artificial Intelligence Tools, 18(4), 487–516. https://doi.org/10.1142/S0218213009000241

Wagner, I. A., Lindenbaum, M., & Bruckstein, A. M. (1998). Efficiently searching a graph by a smell-oriented vertex process. Annals of Mathematics and Artificial Intelligence, 24, 211–223.

Yang, L., Wang, Y., & Zhang, J. (2020). Parameter analysis and simulation experiment of ant colony optimization on small-scale TSP problem. IOP Conference Series: Materials Science and Engineering.

  • تاریخ دریافت 18 شهریور 1403
  • تاریخ بازنگری 06 مهر 1403
  • تاریخ پذیرش 23 مهر 1403
  • تاریخ اولین انتشار 23 مهر 1403
  • تاریخ انتشار 01 بهمن 1403