Simulation-Based Optimisation for Autonomous Transportation Systems Using a Parallel Real-Coded Genetic Algorithm with Scalable Nonuniform Mutation

Andranik S. Akopov; Levon A. Beklaryan; Armen L. Beklaryan

doi:10.2478/cait-2021-0034

Abstract

This work presents a novel approach to the simulation-based optimisation for Autonomous Transportation Systems (ATS) with the use of the proposed parallel genetic algorithm. The system being developed uses GPUs for the implementation of a massive agent-based model of Autonomous Vehicle (AV) behaviour in an Artificial Multi-Connected Road Network (AMСRN) consisting of the “Manhattan Grid” and the “Circular Motion Area” that are crossed. A new parallel Real-Coded Genetic Algorithm with a Scalable Nonuniform Mutation (RCGA-SNUM) is developed. The proposed algorithm (RCGA-SNUM) has been examined with the use of known test instances and compared with parallel RCGAs used with other mutation operators (e.g., standard mutation, Power Mutation (PM), mutation with Dynamic Rates (DMR), Scalable Uniform Mutation (SUM), etc.). As a result, RCGA-SNUM demonstrates superiority in solving large-scale optimisation problems when decision variables have wide feasible ranges and multiple local extrema are observed. Following this, RCGA-SNUM is applied to minimising the number of potential traffic accidents in the AMСRN.

References

1. Akopov, A. S., L. A. Beklaryan, A. L. Beklaryan. Cluster-Based Optimization of an Evacuation Process Using a Parallel Bi-Objective Real-Coded Genetic Algorithm. – Cybernetics and Information Technologies, Vol. 20, 2020, No 3, pp. 45-63.10.2478/cait-2020-0027
Search in Google Scholar Back to article
2. Akopov, A. S., L. A. Beklaryan, M. Thakur, B. D. Verma. Parallel Multi-Agent Real-Coded Genetic Algorithm for Large-Scale Black-Box Single-Objective Optimisation. – Knowledge-Based Systems, Vol. 174, 2019, pp. 103-122.10.1016/j.knosys.2019.03.003
Search in Google Scholar Back to article
3. Akopov, A. S., L. A. Beklaryan, A. K. Saghatelyan. Agent-Based Modelling of Interactions between Air Pollutants and Greenery Using a Case Study of Yerevan, Armenia. – Environmental Modelling and Software, Vol. 116, 2019, pp. 7-25.10.1016/j.envsoft.2019.02.003
Search in Google Scholar Back to article
4. Akopov, A. S., L. A. Beklaryan. An Agent Model of Crowd Behavior in Emergencies. – Automation and Remote Control, Vol. 76, 2015, No 10, pp. 1817-1827.10.1134/S0005117915100094
Search in Google Scholar Back to article
5. Akopov, A. S. Parallel Genetic Algorithm with Fading Selection. – International Journal of Computer Applications in Technology, Vol. 49, 2014, No 3-4, pp. 325-331.10.1504/IJCAT.2014.062368
Search in Google Scholar Back to article
6. Astsatryan, H., A. Kocharyan, D. Hagimont, A. Lalayan. Performance Optimization System for Hadoop and Spark Frameworks. – Cybernetics and Information Technologies, Vol. 20, 2020, No 6, pp. 5-17.10.2478/cait-2020-0056
Search in Google Scholar Back to article
7. Audet, C., M. Kokkolaras. Blackbox and Derivative-Free Optimization: Theory, Algorithms and Applications. – Optimization and Engineering, Vol. 17, 2016, No 1, pp. 1-2.10.1007/s11081-016-9307-4
Search in Google Scholar Back to article
8. Beklaryan, G. L., A. S. Akopov, N. K. Khachatryan. Optimisation of System Dynamics Models Using a Real-Coded Genetic Algorithm with Fuzzy Control. – Cybernetics and Information Technologies, Vol. 19, 2019, No 2, pp. 87-103.10.2478/cait-2019-0017
Search in Google Scholar Back to article
9. Beklaryan, A. L., A. S. Akopov. Simulation of Agent-Rescuer Behaviour in Emergency Based on Modified Fuzzy Clustering. – In: Proceedings of the International Joint Conference on Autonomous Agents and Multigene Systems, AAMAS, 2016, pp. 1275-1276.
Search in Google Scholar Back to article
10. Conn, A. R., K. Scheinberg, L. N. Vicente. Introduction to Derivative-Free Optimization. – MPS-SIAM Book Series on Optimization. Philadelphia, SIAM, 2009.10.1137/1.9780898718768
Search in Google Scholar Back to article
11. Deep, K., M. Thakur. A New Mutation Operator for Real Coded Genetic Algorithms. – Applied Mathematics and Computation, Vol. 193, 2007, No 1, pp. 211-230.10.1016/j.amc.2007.03.046
Search in Google Scholar Back to article
12. Helbing, D. Traffic and Related Self-Driven Many-Particle Systems. – Review of Modern Physics, Vol. 73, 2001, No 4, pp. 1067-1141.10.1103/RevModPhys.73.1067
Search in Google Scholar Back to article
13. Herrera, F., M. Lozano. Gradual Distributed Real-Coded Genetic Algorithms. – IEEE Transactions on Evolutionary Computation, Vol. 4, 2000, No 1, pp. 43-63.10.1109/4235.843494
Search in Google Scholar Back to article
14. Heywood, P., P. Richmond, S. Maddock. Road Network Simulation Using FLAME GPU. – In: S. Hunold et al., Eds. Proc. of Euro-Par 2015: Parallel Processing Workshops. Euro-Par 2015. Lecture Notes in Computer Science. Vol. 9523. Cham, Springer, 2015, pp. 430-441.
Search in Google Scholar Back to article
15. Hong, T., H. Wang. A Dynamic Mutation Genetic Algorithm. – In: Proc. of IEEE International Conference on Systems, Man and Cybernetics. Information Intelligence and Systems, Vol. 3, 1996, pp. 2000-2005.
Search in Google Scholar Back to article
16. Jameel, F., M. A. Javed, D. T. Ngo. Performance Analysis of Cooperative V2V and V2I Communications Under Correlated Fading. – IEEE Transactions on Intelligent Transportation Systems, Vol. 21, No 8, pp. 3476-3484.10.1109/TITS.2019.2929825
Search in Google Scholar Back to article
17. Jurgen, R. V2V/V2I Communications for Improved Road Safety and Efficiency. SAE International, 2012.
Search in Google Scholar Back to article
18. Khachatryan, N. K., A. S. Akopov. Model for Organizing Cargo Transportation with an Initial Station of Departure and a Final Station of Cargo Distribution. – Business Informatics, Vol. 1, 2017, No 39, pp. 25-35.10.17323/1998-0663.2017.1.25.35
Search in Google Scholar Back to article
19. Kim, K., P. R. Kumar. An MPC-Based Approach to Provable System-Wide Safety and Liveness of Autonomous Ground Traffic. – IEEE Transactions on Automatic Control, Vol. 59, 2014, No 12, pp. 3341-3356.10.1109/TAC.2014.2351911
Search in Google Scholar Back to article
20. Kiran, M., P. Richmond, M. Holcombe, C. L. Shawn, D. Worth, C. Greenough. FLAME Simulating Large Populations of Agents on Parallel Platforms. – In: Proc. of 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’10), 2010, pp. 1633-1636.
Search in Google Scholar Back to article
21. Müllner, D. Fastcluster: Agglomerative Clustering Routines for R and Python. – Journal of Statistical Software, Vol. 53, 2013, No 9, pp. 1-18.10.18637/jss.v053.i09
Search in Google Scholar Back to article
22. Naqvi, F. B., M. Y. Shad, M. S. Khan. A New Logistic Distribution Based Crossover Operator for Real-Coded Genetic Algorithm. – Journal of Statistical Computation and Simulation, Vol. 91, 2021, No 4, pp. 817-835.10.1080/00949655.2020.1832093
Search in Google Scholar Back to article
23. Paden, B., M. Čáp, S. Z. Yong, D. Yershov, E. Frazzoli. A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles. – IEEE Transactions on Intelligent Vehicles, Vol. 1, 2016, No 1, pp. 33-55.10.1109/TIV.2016.2578706
Search in Google Scholar Back to article
24. Premalatha, M., V. Viswanathan. Course Sequence Recommendation with Course Difficulty Index Using Subset Sum Approximation Algorithms. – Cybernetics and Information Technologies, Vol. 19, 2019, No 3, pp. 25-44.10.2478/cait-2019-0024
Search in Google Scholar Back to article
25. Sarma, S. S., K. Sinha, G. Chakraborty, P. Bhabani, B. P. Sinha. Distributed Algorithm for Traffic Dissemination in Manhattan Networks with Optimal Routing-Time. – In: Proc. of Symposium on Applied Computing (SAC’17), 2017, pp. 499-505.10.1145/3019612.3019702
Search in Google Scholar Back to article
26. Shiller, Z., Y. Gwo. Dynamic Motion Planning of Autonomous Vehicles. – IEEE Transactions on Robotics and Automation, Vol. 7, 1991, No 2, pp. 241-249.10.1109/70.75906
Search in Google Scholar Back to article
27. Thierens, D. Adaptive Mutation Rate Control Schemes in Genetic Algorithms. – In: Proc. of Congress on Evolutionary Computation. CEC’02 (Cat. No 02TH8600), Honolulu, HI, USA, Vol. 1, 2002, pp. 980-985.
Search in Google Scholar Back to article
28. Tomas-Gabarron, J., E. Egea-Lopez, J. Garcia-Haro. Vehicular Trajectory Optimization for Cooperative Collision Avoidance at High Speeds. – IEEE Transactions on Intelligent Transportation Systems, Vol. 14, 2013, No 4, pp. 1930-1941.10.1109/TITS.2013.2270009
Search in Google Scholar Back to article
29. Toshev, A. Particle Swarm Optimization and Tabu Search Hybrid Algorithm for Flexible Job Shop Scheduling Problem – Analysis of Test Results. – Cybernetics and Information Technologies, Vol. 19, 2019, No 4, pp. 26-44.10.2478/cait-2019-0034
Search in Google Scholar Back to article
30. Yuriy, R., L. Viatcheslav. A Novel Multi-Epoch Particle Swarm Optimization Technique. – Cybernetics and Information Technologies, Vol. 18, 2018, No 3, pp. 62-74.10.2478/cait-2018-0039
Search in Google Scholar Back to article
31. Zhang, J., H. S. Chung, W. Lo. Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms. – IEEE Transactions on Evolutionary Computation, Vol. 11, 2007, No 3, pp. 326-335.10.1109/TEVC.2006.880727
Search in Google Scholar Back to article
32. Zhou, Q., Y. Li. Directed Variation in Evolutionary Strategies. – IEEE Transactions on Evolutionary Computation, Vol. 7, 2003, No 4, 356-366.10.1109/TEVC.2003.812215
Search in Google Scholar Back to article

Simulation-Based Optimisation for Autonomous Transportation Systems Using a Parallel Real-Coded Genetic Algorithm with Scalable Nonuniform Mutation

Abstract

Paradigm

My account