学位论文 > 优秀研究生学位论文题录展示

多目标微粒群算法研究及其在交通事故分析中的应用

作　者: 仇晨晔
导　师: 方滨兴
学　校: 北京邮电大学
专　业: 计算机科学与技术
关键词: 多目标微粒群算法全局最优引导变异算子惯性权重事故严重程度分析 ROC曲线
分类号: TP18
类　型: 博士论文
年　份: 2013年
下　载: 5次
引　用: 0次
阅　读: 论文下载

内容摘要

多目标优化是当今的热点问题,无论在科学研究还是在工程实践中都会遇到大量的问题需要同时优化多个目标。与单目标优化问题不同的是,多目标优化问题不存在单一的全局最优解,而是要在多个目标之间寻求权衡。目前采用最多的是基于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曲线的事故分析模型。实验结果证明本文提出的多目标微粒群算法求解的收敛性、多样性和覆盖性方面具备很强的竞争力；本文提出的新的惯性权重能够有效的提升多目标微粒群算法的搜索性能；本文提出的两个事故分析模型相比于以往的模型,在结果的可解读性方面具备很强的优势,新提出的分类器衡量指标比分类准确率更适合交通事故严重程度分析问题。

全文目录

摘要  5-10
ABSTRACT  10-16
目录  16-19
符号说明  19-20
第一章绪论  20-38
  1.1 研究背景及意义  20-21
  1.2 多目标优化问题的基本概念  21-23
  1.3 多目标进化算法研究现状  23-25
  1.4 群智能算法  25-26
  1.5 多目标微粒群算法研究现状  26-30
  1.6 事故严重程度分析研究现状  30-35
    1.6.1 事故严重程度分析问题  30
    1.6.2 事故严重程度分析的研究现状  30-33
    1.6.3 多目标进化算法用于数据挖掘  33-35
  1.7 本文的工作内容  35-36
    1.7.1 多目标微粒群算法的研究内容  35-36
    1.7.2 交通事故分析的研究内容  36
  1.8 本文章节安排  36-38
第二章多目标微粒群算法  38-50
  2.1 微粒群算法的介绍  38-42
    2.1.1 基本微粒群算法  38-40
    2.1.2 常见的改进  40
    2.1.3 微粒群算法的拓扑结构  40-42
  2.2 微粒群算法用于多目标优化问题  42-48
    2.2.1 非支配解的保存及归档集  43-44
    2.2.2 全局最优引导的选取  44-47
    2.2.3 种群多样性的保持  47-48
    2.2.4 多目标微粒群算法的一般步骤  48
  2.3 本章小结  48-50
第三章一种基于K-means聚类全局引导策略的多目标微粒群算法  50-71
  3.1 引言  50
  3.2 KMOPSO的流程  50-51
  3.3 基于K-means算法和比例分布的全局引导选取策略  51-53
  3.4 归档集和剪枝策略  53-54
  3.5 对称变异算子  54-55
  3.6 重新定义个体最优引导  55-56
  3.7 实验及分析  56-70
    3.7.1 衡量指标  56-57
    3.7.2 测试函数  57-58
    3.7.3 对比算法  58-59
    3.7.4 实验设置  59
    3.7.5 结果及讨论  59-68
    3.7.6 运算时间分析  68-70
  3.8 本章小结  70-71
第四章基于两阶段惯性权重的多目标微粒群算法  71-84
  4.1 引言  71
  4.2 惯性权重的相关研究  71-73
  4.3 两阶段惯性权重变量  73-75
  4.4 实验及分析  75-83
    4.4.1 实验参数设置  75-76
    4.4.2 实验结果  76-81
    4.4.3 粒子迭代状态分析  81-83
  4.5 本章小结  83-84
第五章基于偏序分类的交通事故分析模型  84-99
  5.1 引言  84-85
  5.2 交通事故数据介绍  85-86
  5.3 用于交通事故分析的偏序分类模型  86-90
    5.3.1 基本概念  87-88
    5.3.2 偏序分类用于事故分析  88-89
    5.3.3 规则的评价方式  89-90
  5.4 基于KMOPSO的交通事故严重程度分析模型  90-92
    5.4.1 粒子编码及解码  90-91
    5.4.2 算法流程  91-92
  5.5 实验及分析  92-98
    5.5.1 实验设置  92-93
    5.5.2 对比实验及分析  93-95
    5.5.3 KMOPSO挖掘的规则分析  95-98
  5.6 本章小结  98-99
第六章基于多目标微粒群算法和ROC图的交通事故分析模型  99-111
  6.1 引言  99-100
  6.2 ROC曲线简介  100-102
    6.2.1 基本概念  100-101
    6.2.2 ROC空间  101-102
    6.2.3 AUC值  102
  6.3 基于多目标微粒群算法和ROC曲线的事故分析模型  102-104
    6.3.1 规则的评价方式  102-103
    6.3.2 基于KMOPSO的规则生成方法  103-104
    6.3.3 基于规则建立分类器  104
  6.4 实验及分析  104-109
    6.4.1 实验设置  105
    6.4.2 与其它多目标微粒群算法比较  105-109
    6.4.3 与其它的规则学习方法比较  109
  6.5 本章小结  109-111
第七章总结与展望  111-114
  7.1 论文总结  111-112
  7.2 未来工作展望  112-114
参考文献  114-123
致谢  123-124
攻读博士学位期间发表的学术论文目录  124

多目标微粒群算法研究及其在交通事故分析中的应用

内容摘要

全文目录

相似论文