基于遗传算法的优化研究

【摘要】：自1960年以来,人们对于模拟生物进化行为以及由此开发的针对复杂优化问题的有效算法产生了浓厚的兴趣。遗传算法作为一种强有力的随机搜索和优化方法,广泛应用于工业工程优化领域并产生了深远影响。旅行商问题(TSP)是一个典型的组合优化问题,求解起来非常困难基于遗传算法的随机优化搜索,常被作为遗传算法的应用测试实例。然而以往研究很少考虑到它的动态属性,一旦将它置于一个动态环境,现存的算法将不再适用。近年来,动态旅行商问题(DTSP)越来越吸引广大研究者的注意力,DTSP的研究也有着非常重要的实际意义。优化领域还存在一类更加复杂的优化问题,这类问题需要处理多个目标并且这些目标常常是相互冲突的。简单地将多个目标通过加权处理转换为单目标问题远不能满足决策者的要求,因此设计求解多目标优化问题的有效算法是非常有现实意义的。遗传算法在多目标优化方面也体现着它的魅力并获得了广泛应用。本文主要针对基于遗传算法的优化问题进行研究,具体说来,包括TSP求解和多目标优化两个方面。对于TSP求解,本文主要做了下面的研究工作:1、对反序杂交算子进行改进。考虑到反序操作的高度随机性,重组过程最终并不一定能得到比上一代更有优势的个体。为此我们将最优保留机制应用到反序杂交算子中,称为记忆机制,用于保留当次反序过程中出现的最好的基因序列,进而一步一步逼近最优解。

实验表明我们的改进算子能在加快收敛速度的同时和提高解的质量。2、对于一类动态环境下的旅行商问题建模和求解。对生活中出现的上下班高峰期交通阻塞的城市交通情况进行高斯建模,使得随机被阻塞的边的数目在遗传算法进化中期达到最大。进而设计了该环境下的响应算法,该算法能利用已有最优路径中未被破坏的短边对动态变化情况做出快速反应。同时为了使算法更有效,我们将改进的反序杂交算子用于优化中。实验表明算法对解这一类动态旅行商问题很有效。本文在多目标优化方面的主要研究工作有两点:1、提出用庄家法则来构造非支配集。在多目标遗传算法中,构造非支配集的时间耗费是非常大的,而这种耗费主要用于个体比较。庄家法则不同于已有构造非支配集的方法,它做为一种非回朔方法可以有效减少个体比较次数,从而提高算法效率。2、提出了基于密度的多目标遗传算法(DMOGA)。对多种算法进行分析发现,密度是维护种群分布性的一个非常重要的因素。DMOGA考虑整个种群个体之间的影响,用于计算个体密度,准确反映外部集的分布情况,得到一个时间复杂度为O(n2)的优秀的分布性保持方法。并且为了提高算法效率,DMOGA采用庄家法则来构造非支配集。实验表明DMOGA能得到很好的分布性的同时拥有较高的运行效率。

（编辑：上海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!