Problem-driven Differential Evolution And Its Application To Intelligent Transportation Systems

Differential evolution algorithm is a kind of intelligent optimization algorithms with strong global optimization ability.It has become an important way to solve many optimization problems in engineering practice.However,existing improvements of the differential evolution are usually for the general field with the research carried out on the standard test sets,so they are difficult to be directly used for solving practical complex optimization problems.Meanwhile,intelligent transportation system is an important part of the modern society.With its development,a large number of NP-hard complex optimization problems have emerged.Especially in large-scale and complex environments,the practical complex optimization problems involved in intelligent transportation systems usually have the characteristics of mixed variables,multiple optimization objectives and hierarchical optimization.However,owing to the insufficient use of the scene information or heuristic information of the problem,existing differential evolution algorithms have limited efficiency in solving complex problems with three above characterizes,whose limitations are described as below.(1)For mixed variable optimization,only the types of decision variables are distinguished,but the relationship between decision variables is ignored,which limits the quality of the optimization results.(2)For multi-objective optimization,attention is mainly paid on how to make the Pareto front as close to the optimal solutions as possible,and to make its nondominated solutions distribute as uniformly and widely as possible.However,little attention is paid on how to make the Pareto front contain more representative trade-off solutions according to user's preference,which affects the quality of the system outcome and the flexibility of the decision-maker after multiple optimizations in a time-sharing system.(3)Nested evolution strategy adopted in hierarchical optimization usually consumes a lot of computational resources,which limits the algorithm performance on applications to largescale scenes.This thesis aims to design effective optimization methods based on differential evolution,according to the characteristics of electric vehicle charging scheduling problem and traffic signal control problem in intelligent transportation system.By being combined with the specific information of the problem,the search ability of the differential evolution is enhanced in solving the above complex optimization problems.The main innovations and contributions of this thesis are described as follows:(1)A hierarchical mixed-variable differential evolution algorithm is proposed to solve the electric vehicle collaborative charging scheduling problem,for its coupling characteristics of mixed variables.The electric vehicle collaborative charging scheduling problem is a complex optimization problem based on several known charging stations in the traffic network,which requires to reasonably arrange the charging schedules for each member of an electric vehicle fleet to complete their respective trips and optimize the overall performance of the fleet.When modeling the problem,the decision variables include not only the conventional charging station stops,but also the charging mode and charging volume at each charging station stop.Because the charging station and charging mode are discrete variables,while the charging volume is a continuous variable,the problem is a mixed-variable optimization problem.According to the dependence of the charging mode on the charging station stop,the masterslave relationship between these two discrete variables is defined.Subsequently,this thesis proposes a hierarchical mixed-variable differential evolution algorithm,where three problemspecific operators are specially designed,including the charging station path construction,hierarchical mixed variable mutation operator and constraint-aware evaluation operator.According to the state of charge of each electric vehicle,the charging station path construction operator sequentially selects a feasible charging station from the origin to the destination,which completes the most critical part for constructing a solution.The hierarchical mixed variable mutation operator integrates a master-slave discrete mutation operator and a classical continuous mutation operator to better preserve the information of better solutions during the population evolution.The constraint-aware evaluation operator guarantees a solution to meet all predefined constraints,by dealing with the local charging scheduling of each vehicle and coordinating the global charging scheduling at the same charging station.In the experiments,the effectiveness of the proposed algorithm is verified by comparing with other existing algorithms based on the real-world transportation networks.(2)A preference-based multi-objective differential evolution algorithm is proposed to solve the multi-objective electric vehicle charging scheduling problem,for the multiobjective characteristics of the time-sharing scheduling system.The electric vehicle charging scheduling problem can be also modeled as a complex multiobjective optimization problem because it needs to consider multiple conflicting optimization objectives such as time cost,charging cost and final state of charge.The multi-objective electric vehicle charging scheduling system needs time-sharing and repeated optimizations.After each optimization,users need to select a trade-off solution from the Pareto Front as the optimization result to make the system continue to run.In order to ensure the continuity of the system,the user can set a default preference in advance,and the system can automatically select a trade-off solution according to the user preference after each multi-objective optimization.Accordingly,this thesis proposes a preference-based multi-objective differential evolution algorithm,which optimizes the non-dominated solution set of each generation by maintaining four heterogeneous sub-populations.Besides,the proposed algorithm identifies knee solutions and boundary solutions and performs a priority reservation scheme on these solutions,so that the Pareto Front contains more representative trade-off solutions with higher qualities.Experimental results show that the proposed algorithm outperforms other existing methods in terms of the quality of system operation results and the flexibility of decision makers.(3)An off-line nested differential evolution algorithm is proposed to solve large-scale traffic signal control problem,for its bi-level optimization characteristics.The traffic signal control problem is a complex optimization problem based on the traffic flow demand of a traffic network.It requires to reasonably set signal control parameters for all intersections,to optimize the overall performance of the network in the user equilibrium state.The problem is usually modeled as a bi-level optimization problem,with the upper level to be the signal timing optimization and the lower level to be the traffic assignment process.To solve this problem,an off-line nested differential evolution algorithm is proposed,and a bi-level traffic signal control system is constructed.The upper level of the system uses an adaptive differential evolution algorithm to optimize the signal control parameters of all intersections,and the algorithm embeds a user equilibrium stochastic traffic assignment process into its evaluation operator.The traffic assignment usually includes two steps,i.e.,the dynamic route selection and the iterative flow transfer to deal with each Origin-Destination(OD)pair of the traffic demand.Hence,the computational burden of nested differential evolution algorithm will increase sharply,as the road network scale and traffic demand increase.Considering the stability of the traffic infrastructure and the probabilistic fault tolerance of the stochastic traffic assignment model,this thesis further proposes to separate the dynamic path selection step from the nested evolution process,and designs a niching ant colony optimization algorithm to generate multiple optimal candidate paths for each OD pair in advance.By conducting the route selection task offline,the proposed system avoids repeatedly constructing candidate paths for the lower-leveled traffic assignment process,thus greatly saving the computational cost of the nested evolutionary algorithm and extending its application in large-scale traffic network.In the experiment,the effectiveness of the proposed algorithm in terms of solution quality and running time is verified in comparison with the existing methods based on synthetic traffic networks and real-world traffic networks.In summary,this thesis designs a hierarchical mixed variable differential evolution algorithm,a preference-based multi-objective differential evolution algorithm and an offline nested differential evolution algorithm,respectively for the complex optimization problems with characteristics of mixed variables,multiple optimization objectives or hierarchical optimization.Such algorithm designs improve the performance of differential evolution algorithm for these three kinds of complex optimization problems and effectively promotes the development and application of the differential evolutionary algorithm.