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

基于聚类思想的改进混合遗传算法

作　者: 徐晓艳
导　师: 杨新武
学　校: 北京工业大学
专　业: 计算机科学与技术
关键词: 遗传算法聚类种群分化局部搜索无效交叉
分类号: TP18
类　型: 硕士论文
年　份: 2013年
下　载: 10次
引　用: 0次
阅　读: 论文下载

内容摘要

现代科学理论研究和实践中存在着大量优化及自适应问题。在大规模的复杂多模态优化问题上，一般的计算方法无能为力。遗传算法是一种模拟生物遗传进化过程的自适应全局优化概率搜索算法。它依据概率对各代种群施加选择、交叉和变异等遗传操作，使种群逐步进化到包含或接近最优解的状态，是解决各类复杂优化问题的一种有效算法。早熟收敛和收敛速度之间的平衡一直是遗传算法研究的焦点。如何有效平衡这一冲突，是改善算法在复杂多模态优化问题上性能的关键。早熟收敛的主要成因是优良个体间的近亲繁殖，导致种群多样性过早丧失。针对以上问题，本文先后将K均值,层次聚类以及最小生成树等聚类方法和最优代表思想加入遗传算法中，提出了对应的改进遗传算法；并在此基础之上，又将正交实验设计方法和局部搜索技术引入其中，提出了一种混合种群分化遗传算法，并在高维，复杂和多模态函数优化问题上验证了新方法的有效性。本文的主要研究工作如下：(1)为解决早熟收敛问题，在对聚类算法和改进遗传算法进行了深入研究与实现验证基础上，提出了一种基于聚类的改进遗传算法(CGA)。该方法通过聚类操作对种群进行子种群划分，禁止同一子种群内的相似个体进行遗传操作，从而可有效抑制早熟收敛。本文还从理论上分析出CGA算法相对于标准遗传算法(SGA)能更好地克服无效交叉操作。(2)针对CGA算法在抑制早熟收敛中造成的收敛速度降低问题，在其基础之上，又提出了一种基于聚类的最优代表改进遗传算法(OCGA)。新方法通过选择子类内最优个体代替子类内其它个体进行交叉操作，加快了算法的搜索效率。(3)本文采用K均值,层次聚类以及最小生成树等聚类方法实现了相应的CGA和OCGA算法，并在基准函数优化问题进行了相关的对比数值实验。实验结果表明，与SGA相比，CGA和OCGA确实能够从一定程度上有效抑制早熟收敛现象，OCGA还能够加快算法搜索效率。(4)在OCGA基础之上，提出了一种混合种群分化遗传算法(HPDGA)。新方法提出了一种适用于局部搜索的方向单形交叉算子，能够根据父代个体的适应度有方向性的产生若干个较优子代个体；并且结合方向交叉算子，提出了一种可调控局部搜索策略，根据当代子种群数目以及子种群中的个体数目采取相应的局部操作算子，加速种群进化。(5)在14个高维基准函数优化问题上对HPDGA进行了对比测试，测试结果表明，与多种已有算法相比，新算法明显优于其它算法的性能。

全文目录

摘要  4-6
Abstract  6-11
第1章绪论  11-17
  1.1 遗传算法的发展历程与研究现状  11-12
    1.1.1 遗传算法的发展历程  11
    1.1.2 遗传算法的研究现状  11-12
  1.2 课题研究背景及意义  12-13
    1.2.1 课题研究背景  12
    1.2.2 课题研究意义  12-13
  1.3 研究内容及论文结构  13-17
    1.3.1 研究内容  13-14
    1.3.2 论文结构  14-17
第2章遗传算法  17-29
  2.1 遗传算法的基本概念和思想  17-18
  2.2 遗传算法的理论基础  18-21
    2.2.1 模式定理  18-19
    2.2.2 积木块假设与遗传算法欺骗问题  19-20
    2.2.3 隐含并行性  20-21
  2.3 标准遗传算法流程  21
  2.4 遗传算法技术实现  21-26
    2.4.1 编码  21-23
    2.4.2 种群初始化  23
    2.4.3 适应度函数  23-24
    2.4.4 遗传操作  24-26
  2.5 遗传算法的应用  26-27
  2.6 基本遗传算法分析  27-28
    2.6.1 基本遗传算法的特点  27
    2.6.2 基本遗传算法的不足  27-28
  2.7 本章小结  28-29
第3章聚类分析方法  29-39
  3.1 聚类分析概述  29-31
    3.1.1 聚类三要素  29-30
    3.1.2 聚类的数据结构  30
    3.1.3 聚类分析过程  30-31
  3.2 聚类分析主要方法  31-37
    3.2.1 基于划分的聚类方法  32-33
    3.2.2 基于层次的聚类方法  33-34
    3.2.3 基于密度的聚类方法  34-35
    3.2.4 基于网格的聚类方法  35-36
    3.2.5 其它聚类方法  36-37
  3.3 自适应最小生成树聚类  37
  3.4 本章小结  37-39
第4章基于聚类的改进遗传算法  39-59
  4.1 引言  39
  4.2 基于聚类的改进遗传算法(CGA)  39-49
    4.2.1 CGA 选择算子  39-40
    4.2.2 CGA 算法流程  40
    4.2.3 CGA 无效交叉分析  40-42
    4.2.4 数值实验  42-49
  4.3 基于聚类的最优代表遗传算法(OCGA)  49-57
    4.3.1 OCGA 选择算子  49
    4.3.2 OCGA 算法流程  49-50
    4.3.3 数值实验  50-57
  4.4 本章小结  57-59
第5章混合种群分化遗传算法  59-73
  5.1 引言  59
  5.2 混合种群分化遗传算法  59-67
    5.2.1 正交实验设计  59-61
    5.2.2 自适应正交交叉算子  61
    5.2.3 种群初始化  61-62
    5.2.4 单形交叉算子  62
    5.2.5 方向交叉算子  62-63
    5.2.6 方向单形交叉算子  63-65
    5.2.7 可调控局部搜索策略  65-66
    5.2.8 算法步骤  66-67
  5.3 数值实验  67-71
  5.4 本章小结  71-73
结论  73-75
参考文献  75-79
攻读硕士学位期间所发表的学术论文  79-81
致谢  81

基于聚类思想的改进混合遗传算法

内容摘要

全文目录

相似论文