【作者】 仇晨晔；

【导师】 方滨兴；

【作者基本信息】 北京邮电大学 ， 计算机科学与技术， 2013， 博士

【摘要】 多目标优化是当今的热点问题,无论在科学研究还是在工程实践中都会遇到大量的问题需要同时优化多个目标。与单目标优化问题不同的是,多目标优化问题不存在单一的全局最优解,而是要在多个目标之间寻求权衡。目前采用最多的是基于Pareto支配概念的方法。基于Pareto支配概念的多目标优化算法的求解目标是一组尽量接近Pareto最优前端且分布均匀的非支配解。进化算法可以同时处理一组解,算法运行一次就能得到一组非支配解,因此非常适合于解决多目标优化问题。近年来出现了多种多目标进化算法,并已成功运用于很多领域。微粒群算法是一种相对较新的进化算法。它是一种模仿鸟类觅食行为而产生的群智能算法。标准的微粒算法中包含一群粒子,每个粒子代表问题的一个候选解。粒子在多维的搜索空间中飞行,根据自身飞行经验和种群中最优粒子的飞行经验调整自己的飞行速度和方向。微粒群算法具有操作简单、收敛速度快等特点,自产生以来受到了广泛关注,已成功应用于很多领域。将微粒群算法用于多目标优化问题的尝试始于1999年,但该领域直到2002年才开始蓬勃发展。这些年来越来越多的多目标微粒群算法被提出,并被应用于车间调度、水资源调度、企业管理等领域。将微粒群算法用于多目标优化问题需要对算法的结构进行一定的调整,主要包括以下几个方面：(1)如何定义算法中的全局最优引导。全局最优引导在微粒群算法中占有非常重要的位置,它直接关系到算法的收敛性和多样性。在单目标微粒群算法中,全局最优引导可以直接根据单一目标的适应度值来确定。而在多目标优化问题中,存在一组非支配解,这就带来了如何从中选取全局最优引导的问题。(2)如何保持搜索过程中产生的大量非支配解。整个种群在多次迭代的过程中会产生大量的非支配解。从保持优秀解的角度考虑,必须要保存找到的非支配解。在实际操作中,如何进行保存和维护是一个值得关注的问题。(3)如何保持种群的多样性。微粒群算法收敛度速快,这会导致种群多样性的快速流失。种群多样性的快速流失意味着算法容易陷入局部最优。很多复杂的多目标优化问题中包含非常多的局部最优解,因此采取何种方式保持种群多样性对算法的性能至关重要。因此本文将从上述三个方面对多目标微粒群算法展开深入的研究。在研究多目标微粒群算法的基础上,我们将采用多目标微粒群算法解决交通事故严重程度分析问题。任何一门新技术的产生与发展都源于它的应用,否则这门新技术是缺乏生命力的。多目标优化问题之所以越来越引人关注,正是因为它在各种实际问题中的广泛应用。在全球范围内,交通事故是带来人员伤亡的一个重要因素。交通事故每年造成120万人死亡及超过5000万人受伤(世界健康组织,2009)。作为一个发展中国家,中国每年因交通事故死亡的人数超过5万人。北京作为中国的首都,是世界上最大及人口最多的城市之一,交通现状不容乐观,每年都有大量交通事故发生,带来了大量的人员伤亡。因此交通安全是一个当前的热点问题。现在交通安全的研究者们在研究交通事故时,不仅仅关注事故的数量,同样关注事故的严重程度。因为严重事故带来的人员伤亡、财产损失远远大于轻微事故。如果能降低事故的严重程度,同样能起到提高道路交通安全水平的效果。如果希望降低事故严重程度,首先就必须了解哪些因素或哪些因素的组合会影响到事故的严重程度。事故严重程度可以看成一个随机事件,影响它的因素非常多,包括：道路因素,车辆因素,驾驶员因素,天气因素及事故信息。到目前为止,很多研究者尝试了各种交通事故严重程度分析模型,如多元回归模型、神经网络、决策树、贝叶斯网络等。在现存的方法中,主要存在两方面的问题,一是模型的可解读性较弱,无法从中得到直观的、容易理解的知识；二是大多数模型采用了分类准确率来衡量模型的性能好坏,而该指标并不适合于交通事故分析这种不均衡数据集的问题。针对当前模型的不足,本文把多目标微粒群算法引入到交通事故严重程度分析中,提出了基于多目标微粒群算法的交通事故严重程度分析方法。本文的研究内容包括两部分：多目标微粒群算法的理论研究和多目标微粒群算法在交通事故严重程度分析问题中的应用。针对前面的分析,本文提出了一种新的基于K-means聚类和比例分布的全局最优引导策略的多目标微粒群算法,以及一种采用新的惯性权重的多目标微粒群算法,然后将其用于事故严重程度分析问题,构造了两个交通事故分析模型,并用北京市实际的交通事故数据对模型进行了验证。本文具体的研究内容及创新点概括如下：(1)对多目标优化问题和多目标微粒群算法中的关键技术进行了归纳和总结,指出了其中值得深入研究的部分,为进一步的研究奠定了理论基础。(2)提出了一种基于K-means算法和比例分布全局最优引导策略的多目标微粒群算法(KMOPSO)。该算法采用了一个外部归档集保存搜索过程中找到的所有非支配解,然后从中选取全局最优引导。基于K-means算法和比例分布的全局最优引导策略充分考虑了非支配前端上所有解的分布情况,能够很好地考虑到非支配前端的全局信息和局部信息。该全局最优引导选择方法可以保证选取出的全局最优引导能够引导种群中的粒子均匀地飞往整个Pareto前端,同时侧重稀疏区域的搜索。为了提升算法的局部搜索能力,提出了一个对称变异算子。该算子作用于整个种群,它能引导粒子探索原先无法到达的区域,增加了种群多样性,能够帮助算法跳出局部最优,找到真正的全局最优解。本文将该算法与其它三种经典的多目标进化算法进行比较,在七个标准测试函数中比较算法多方面的性能：收敛性、多样性和覆盖性。实验结果表明本文提出的算法在所有函数中都能找到全局最优解,而且解的多样性表现出色,在所有测试函数中都排名第一,在七个测试函数中都能覆盖整个Pareto前端。(3)提出了一种新的两阶段惯性权重。惯性权重对于平衡微粒群算法的全局搜索和局部搜索起到关键性的作用。以往在多目标微粒群算法的研究中,研究人员对惯性权重的研究还相对较少,大多采用固定的惯性权重或者随机的惯性权重。实际上,很多复杂的多目标优化问题中存在着非常多的局部最优解。而如果惯性权重取值得当,可以使得算法具备更强的全局搜索能力,从而避免陷入局部最优。本文提出了一种全新的两阶段惯性权重。该方法在算法迭代的前半段采用普通的惯性权重,在算法的后半段采用了负的惯性权重。在以往的研究中,惯性权重均为正值。本文论证了在算法迭代的后半段,负的惯性权重能够帮助算法跳出局部最优。本文将提出的两阶段惯性权重用于三种多目标微粒群算法,通过四个测试函数,验证了该惯性权重的有效性。此外还结合种群的迭代过程详细地说明了为何负的惯性权重能起到帮助算法跳出局部最优的作用。(4)提出了一种基于多目标微粒群算法(KMOPSO)的偏序分类技术用于事故严重程度分析问题。偏序分类又称金块挖掘,目标是从大量数据中找到有价值的信息。偏序分类的任务是求得一组具有很强描述性的规则,能揭示某一类数据背后的规律。本文首次将该方法用于交通事故分析领域。对微粒群算法中的粒子采用了新的编码方式,每个粒子代表一条规则。该方法利用了微粒群算法的全局搜索能力,通过算法的不断迭代可以针对严重事故数据集和不严重事故数据集分别得到一组规则。该方法的主要优点包括：(1)挖掘到的规则数目适中,方便使用者从中挑选；(2)规则的准确性高于其它几种经典的规则学习方法；(3)规则具备很强的可理解性,用户可以将挖掘得到的结果和自身经验结合,更好地进行决策。(5)提出了一种基于多目标微粒群算法(KMOPSO)和ROC曲线的事故严重程度分析模型。本文在偏序分类模型的基础上,提出了一种基于规则的分类器。该方法通过多目标微粒群算法产生规则,然后采用了加权投票的方式产生了一个基于规则的分类器。采用了基于ROC曲线的方法衡量分类器的效果。ROC曲线是一种描述两分类方式下分类器敏感度的图像,它对于数据的分布不敏感,因此很适合处理这种不均衡数据集的问题。本文首先将该方法与另一种多目标微粒群算法进行对比,证明了KMOPSO挖掘到的规则质量更高,分类效果更好,然后将提出的算法与另外几种经典的规则学习方法进行对比,证明了提出的算法具备良好的分类效果。综上所述,本文提出了一种基于K-means算法和比例分布全局最优引导策略的多目标微粒群算法(KMOPSO),一种新的两阶段惯性权重。随后将KMOPSO用于交通事故严重程度分析问题,提出了两个模型：基于KMOPSO的偏序分类模型；基于KMOPSO和ROC曲线的事故分析模型。实验结果证明本文提出的多目标微粒群算法求解的收敛性、多样性和覆盖性方面具备很强的竞争力；本文提出的新的惯性权重能够有效的提升多目标微粒群算法的搜索性能；本文提出的两个事故分析模型相比于以往的模型,在结果的可解读性方面具备很强的优势,新提出的分类器衡量指标比分类准确率更适合交通事故严重程度分析问题。更多还原

【Abstract】 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.更多还原