The Research Of Improved Q-Learning Based On Physarum Polycephalum Algorithm On Shortest Path Problem

The shortest path problem is a classic problem in theoretical research such as graph theory analysis and algorithm design.It is also a basic problem in practical application fields such as logistics planning and driving navigation.Due to features of model free and offline learning,Q-Learning Algorithm can solve shortest path problem without establishing a specific environment model and combining with other optimization algorithm easily,and the result shows Q-Learning Algorithm performed well in solving shortest path problem.This thesis proposed improved Q-Learning Algorithm to solve shortest path problem aimed at shortcomings of Q-Learning Algorithm contains large initial search space,low searching efficiency in middle stage and unstable convergence in late stage.To solve Q-Learning Algorithm's drawbacks,an Adaptive Choosing Q-learning based on Physarum Polycephalum Algorithm(ACQPPA)is proposed.ACQPPA preprocesses network through Physarum Polycephalum Algorithm to reduce size of initial search space by replace initial Q matrix with local optimal path matrix.ACQPPA changes exploration rate dynamically to ensure diversity of solutions by giving exploration rate high initial value and converge stably by reducing exploration rate to low value with iteration of algorithm through Simulated Annealing Algorithm.Simulation results show that the success rate of the ACQPPA algorithm converges to the optimal path is 100% when the number of network nodes is 128,which is higher than 80% of the ACO algorithm and Q(?)algorithm,and the number of iterations is lower than 57.2% of Q-Learning,32.9% of ACO algorithm and 35.1% of Q(?)algorithmAiming at the problem of slow searching in middle stage,and accelerate efficiency of preprocessing of network by Physarum Polycephalum Algorithm,this thesis proposes a Bidirectional ACQPPA based on Network Compression(B-ACQPPANC).B-ACQPPANC compresses size of network by CH Algorithm to save time which cost by preprocessing of network through Physarum Polycephalum Algorithm,and starts a reverse direction exploration by combining bidirectional thoughts with Q-Learning to accelerate efficiency in middle stage through store experience in early stage.Simulation results show that average success frequencies of converging to global shortest path of B-ACQPANC lower 43.26% than ACQPPA,and the success frequencies of B-QNC Algorithm and B-Q(?)NC Algorithm reduced 39.40% and 29.76% respectively than Q-Learning Algorithm and Q(?)Algorithm.The results also show that the success rate of B-ACQPPA converges to the optimal path is 100%,which is higher than 80% of B-QNC Algorithm and 20% of B-Q(?)NC Algorithm.