Research On Multi-objective Particle Swarm Optimization And Its Application In Accident Severity Analysis

Multi-objective (MO) optimization is a hot topic nowadays. There are many real-world optimization problems involving multiple objectives that should be optimized simultaneously in scientific research or engineering practice. Contrary with single objective (SO) optimization problem, there is no single optimal solution in MO problem, but a set of trade-off solutions. The most frequently used method in recent years is Pareto dominance concept. MO optimization algorithm based on the Pareto dominance concept is to generate a set of non-dominated solutions which is near to the true Pareto front while preserving diversity. Evolutionary algorithms can deal with a set of possible solutions simultaneously which allows us to find a set of optimal solutions in a single run of the algorithm. So it is very promising to apply evolutionary algorithms to MO problems. Recently, many evolutionary algorithms have been proposed to solve MO problems and they have been successfully used in various areas.Particle swarm optimization (PSO) is a relatively new evolutionary algorithm, which is inspired by the social interaction of bird flocking. A standard particle swarm optimization includes a swarm of particles. Each particle represents a candidate solution of the problem. Particles fly in a multi-dimensional search space looking for the optimal position according to its own flying experience and the experience of the best particle in the swarm. PSO has been proved to be very effective in a wide variety of optimization problems due to its fast convergence and ease of implementation PSO was first extended to MO problem in1999, but this area didn’t begin to develop rapidly until2002. Nevertheless, there are many types of MO particle swarm optimization algorithms nowadays and they have been applied to many real-world problems, such as jobshop scheduling, water distribution system, business management, etc. Extending original PSO to MO problems requires some modifications of the original algorithm. There are three main issues needed to be considered:(1) How to define the global best (gbest) in order to obtain a set of non-dominated solutions? The gbest in the PSO has a great impact on convergence and diversity of solutions. Contrary with the SO optimization, there is no single gbest, but a set of non-dominated solutions which brings us the problem of how to choose gbest.(2) How to keep the non-dominated solutions generated during the running of the algorithm? The whole swarm would generate a large number of non-dominated solutions. From the prospect of keeping good solution, these non-dominated solutions need to be stored. In the algorithm, it is very important to keep and manage these solutions.(3) How to maintain diversity of the swarm? PSO is known for its fast convergence which would lead to the rapid loss of swarm diversity. The loss of diversity means the algorithm is easy to converge to local optima. There are many local optima in complex MO problems. Hence, it’s crucial to take measures to maintain diversity of the swarm.This paper will research into multi-objective particle swarm optimization (MOPSO) based on the abovementioned three important issues.On the basis of the research on MOPSO, we apply MOPSO to solve accident severity analysis problem. The emergence and development of a new technique is derived from its application in real-world problems, or else this technique is lack of vitality. MO optimization is gaining more and more attention because it can be used in diverse areas.Traffic accidents have been one of the most leading causes of death and injury worldwide, resulting in estimated1.2million deaths and50million injuries worldwide each year (World Health Organization,2009). As a developing country, there are more than50,000people died in traffic accidents in China each year. Beijing, as the capital of China, is one of the biggest and most populous cities in the world. Its traffic situation isn’t optimistic, with many accidents and injuries every year. Therefore, traffic safety is a hot issue nowadays.For researchers in traffic safety, they do not only care about the number of accidents, but also the accident severity, as fatal accidents brings much more casualties and property loss. Reducing accident severity is an effective way to improve road safety. In order to accomplish the goal of reducing accident severity, we must identify the most probable factors or conjunctions of factors that affect accident severity.Accident severity can be considered as a random output which is affected by many factors, such as roadway characteristics, vehicle type, driver information, weather information and accident information. Until now, many accident severity analysis models have been proposed, such as multiple regression model, neural networks, decision tree model, Bayesian network, etc. There are two main problems in the existing methods. One is the interpretation ability of these models are relatively poor. It’s difficult to get easy and comprehensible knowledge from these models. The other is the evaluation metric. Most models use classification accuracy to evaluate the performance. However, this metric is not suitable for the accident severity analysis problem with unbalanced data distribution. Aiming at the disadvantages of existing methods, MOPSO will be applied to accident severity analysis in this dissertation and accident severity analysis model based on MOPSO will be proposed.The content of this dissertation consists two parts:research on the MOPSO and its application in traffic accident severity analysis. This paper proposes a novel MOPSO based on a K-means algorithm and proportional distribution guide selection strategy and a novel MOPSO with a two-stage inertia weight. Two accident severity models based on MOPSO are proposed and testified with the real accident data of Beijing. The specific research content and contributions of this dissertation are as follows:(1) The key techniques of MO problems and MOPSO are summarized. This part provides a solid foundation for further research.(2) A multi-objective particle swarm optimization algorithm based on a K-means algorithm and proportional distribution guide selection strategy (KMOPSO) is proposed. The proposed algorithm incorporates an external archive to store all the non-dominated solutions found during the search process and chooses gbest from the archive. The gbest selection strategy based on K-means algorithm and proportional distribution can capture the distribution of all the solutions in the non-dominated front and consider both global and local information of the non-dominated front. Gbest chosen by this strategy can lead the whole swarm move towards the entire Pareto front while encouraging diversity. Also, a symmetric mutation operator is presented to strengthen the exploratory capabilities of the proposed algorithm. The mutation operator works on the entire population. It can lead the particles explore unexpected areas. This can help maintaining diversity of the swarm.The symmetric mutation operator can help MOPSO to overcome its disadvantages by providing PSO the ability of jumping out of local optimum and finding the true Pareto front. The proposed algorithm is compared with three classical MO algorithms on seven benchmarks. For all test problems, KMOPSO can approximate the true Pareto front. The experimental results indicate that KMOPSO can approximate the true Pareto front in all test functions. The solutions generated by KMOPSO show the best diversity as KMOPSO takes the first place in all test problems in terms of diversity. KMOPSO can cover the full Pareto front in all test problems.(3) A two-stage inertia weight is proposed. Inertia weight plays an important role in balancing global search and local search. In the previous researches on MOPSO, researchers did not focus on this variable. They just use constant or random inertia weight. In fact, many complex MO problems have many local optima. Proper inertia weight can improve the global search ability of the algorithm and avoid from falling into local optimum. A novel two-stage inertia weight is proposed. In the first stage of the algorithm, the normal constant inertia weight is used. But in the second stage of the algorithm, a negative inertia weight is employed. In all the previous researches, inertia weight is a positive number:This dissertation proves the algorithm can jump out of optimum with the help of negative inertia weight in the second stage of the algorithm. The new inertia weight is applied to three MOPSOs. They are tested on four test functions to show the effectiveness of the inertia weight. Besides, we analyze why the negative inertia weight can help the algorithm jumping out of local optimum based on the search process of the swarm.(4) A partial classification model based on KMOPSO is proposed to solve accident severity analysis problem. Partial classification, also known as nugget discovery, aims at finding valuable information from data. It is the problem of finding simple rules that represent strong descriptions of a specified class. To the best of our knowledge, this dissertation employs partial classification to solve accident severity analysis problem for the first time. In order to extend MOPSO to partial classification, each particle is encoded to represent a classification rule. The proposed method can get a set of rules for each class by the global searching ability of MOPSO. The experimental results indicate the proposed approach have some advantages:(1) it can generate moderate number of rules which are easy for users to choose;(2) the rules mined by KMOPSO show better accuracy compared with several classical rule learning algorithms;(3) the rules found by KMOPSO have good comprehensibility. Users can combine them with their own experience to make decision.(5) An accident severity analysis model based on KMOPSO and ROC curve is proposed. This dissertation proposes a classifier based on rules, on the foundation of the partial classification model. The proposed approach gets a set of rules by KMOPSO and builds a classification model based on the rules with a weighted voting method. ROC curve is used to evaluate the performance of the classifier. A receiver operating characteristics (ROC) graph is a technique for visualizing classifier’s performance in two-class problem. ROC curve is not sensitive to the distribution of the data. Therefore, it is very suitable for problems such as accident severity analysis. The proposed approach is first compared with another MOPSO. The results show the rules generated by our approach show better convergence, diversity, and spread. In terms of AUC value, our approach outperforms several other classical rule learning algorithms.In summary, this dissertation proposes a novel MOPSO based on a K-means algorithm and proportional distribution guide selection strategy and a MOPSO with a two-stage inertia weight. Then KMOPSO is applied to accident severity analysis problem and two models are proposed: partial classification model based on KMOPSO; accident severity model based on KMOPSO and ROC curve. The experimental results indicate KMOPSO is highly competitive in terms of convergence, diversity, and spread; the two-stage inertia weight can improve the exploration ability of MOPSO; the two accident severity analysis models shows better comprehensibility, and ROC curve is a more sutiable metric in accident severity analysis problem than classification accuracy.