基于空间搜索的遗传算法研究

《基于空间搜索的遗传算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于空间搜索的遗传算法研究重庆大学硕士学位论文(学术学位)学生姓名：陈飞指导教师：陈自郁讲师专业：计算机软件与理论学科门类：工学重庆大学计算机学院二O一六年四月TheStudyonGeneticAlgorithmbasedonSpaceSearchAThesisSubmittedtoChongqingUniversityinPartialFulfillmentoftheRequirementfortheMaster’sDegreeofEngineeringByChenfeiSupervisedbyLec.ChenZiyuSpecialty:Compu

2、terSoftwareandTheorySystemCollegeofComputerScienceofChongqingUniversity,Chongqing,China.April2016重庆大学硕士学位论文中文摘要摘要遗传算法是最早的进化算法之一，它具有良好的稳定性和全局寻优能力，广泛的应用于实际问题中。相比于现今粒子群，差分等进化算法，它的收敛速度相对很慢，在局部寻优上存在不足。但是，众多学者长期致力于遗传算法的理论基础研究，构建不同的遗传算法模型，完善的分析其收敛性和有效性，提供了良好的基础。我们将遗传算法结合各种不同机制或者提出新的改进

3、策略，增加算法的应用领域，提高算法效率。本文基于空间搜索的方式，通过了解种群在变量空间的分布状态，提出了改进的策略对遗传算法进行相关的研究分析。论文的主要工作如下：1)研究遗传算法的理论基础，仔细分析其收敛过程。遗传算法是一种基于启发式搜索的并行性算法，它具有良好的寻优能力和简单的流程。从模式定理中，我们可以了解到，对于遗传算法中的编码，通常难以保留较长的模式，它们有很大的几率被破坏，交叉与变异操作就是让个体的编码可以随机分布在变量空间。在由适应度值引导的过程中，只有趋向相同的编码才可以保留相对稳定的编码个体，因此才容易让遗传算法陷入早熟。本文主要是

4、提出一种可以产生新的编码个体的方式，保持种群的多样性。2)在单目标遗传算法中，提出结合自适应算法的空间划分策略。为了避免自适应遗传算法在后期陷入局部较优，提高搜索的效率，文中提出一种通过种群中个体的变量空间分布来划分区间的方式，来重新分配部分个体，从而加速收敛过程的方法。在遗传算法迭代过程中，对种群个体的分布统计分析，查看种群分布的区间状态，观测收敛的过程。改进的自适应遗传算法了解在整个变量空间内种群个体的分布状态，在重新分配部分种群时，增加个体的多样性从而加速收敛的过程。通过实验可以发现，改进后的自适应遗传算法在种群的多样性上具有差异性，同时可以快

5、速的收敛到全局最优解。3)在多目标遗传算法中，提出构建空间决策树。在高维度空间中，解集的偏好空间难以取舍，记录种群个体的所在位置，将个体在进化中保留的相对稳定的部分位值构造成树。通过生成的空间决策树引导种群的搜索方向，可以有效的保证个体在寻优过程中保持一定的距离具有多样性，又可以快速的向全局进行搜索。通过实验可以发现，增加了空间决策树的NSGA2算法对于目标维数较高的高维多目标优化问题能够取得较好的效果。关键词：遗传算法，空间划分，自适应算法，NSGA2，空间决策树I重庆大学硕士学位论文英文摘要ABSTRACTGeneticalgorithmison

6、eoftheearliestevolutionaryalgorithm,ithaswellstabilityandglobalsearchcapability,widelyusedinpracticalproblems.Althoughcomparedwiththecurrentparticleswarmanddifferentialevolutionalgorithm,ithasshortcomingsinlocaloptimizationandconvergencespeed.Wecommitmenttothetheoreticalbasisfo

7、rresearchofgeneticalgorithm,builddifferentgeneticalgorithmmodel,analysisitsconvergenceandprovidesagoodfoundation.Wewillgeneticalgorithmcombinedwithavarietyofdifferentmechanismsorputforwardanewimprovementstrategy,increasetheapplicationdomainalgorithm,improvetheefficiencyofalgori

8、thm.Inthispaper,basedonspatialsearchway,wecouldhaveakn