基于簇搜索遍历的自适应遗传算法在多峰NP组合问题中的.doc

《基于簇搜索遍历的自适应遗传算法在多峰NP组合问题中的.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于簇搜索遍历的自适应遗传算法在多峰NP组合问题中的研究与应用摘要：NP组合问题在应用中大量存在，这类问题的求解复杂度一般都随问题规模呈指数增长，而把多峰组合问题的所有解搜索出来就更加困难。为了求解多峰优化问题，本文将遗传算法分成了两个阶段。第一个阶段，把个体不重复的均匀的散布在整个解空间内，不仅提高群体的多样性，而且要把所有可能的峰值点搜集起来。第二阶段，把每一个候选峰值点作为簇中心，在每一个簇附近进行局部求精搜索，并且每个簇根据搜索情况不断迁移，一直到所有候选峰值点搜索完。用这种方法可以比较细密

2、的搜遍整个可行解域，能起到密网捕鱼一个不漏的效果，对求多峰函数比较适合。在用N皇后问题进行试验验证中收到较好的效果。关键字：遗传算法、簇搜索、自适应、距离密度、进化趋势、N皇后前言许多优化问题中都有多个全局最优解和多个局部最优解，我们更多的是要把所有的全局最优解和局部最优解全部找出，然后决策人员结合生产生活的实际情况，权衡各方利弊，在所有的最优或较优解中选出适合的某几个最优解，这类问题常称为多峰搜索问题或多模态函数优化问题，见文献[1]。这就需要寻解能力较强的遗传算法，一次寻找多个最优解以供参考选择

3、，但传统的遗传算法通常只能求一个最优解难以满足要求，见文献[2]和[3]。目前研究遗传算法求多峰优化问题主要集中在数值问题上，例如文献[1]提出用协同多群体并结合小生境的思想取得较好的效果。文献[4]提出了基于淘汰相似结构机制的小生境遗传算法实现多峰问题的求解，该方法通过惩罚相似个体中的较差个体来保持多样性，但也仅限于数值优化问题。与数值优化问题相比组合问题具有离散性强，差异性大，不规则等特点，而且很多组合问题是NP难的，用通常的方法求解非常困难，因此有必要专门研究讨论该问题。虽然文献[1]也提出了

4、解决多峰组合问题的思路，但是不仅需要求适应值与海明距离的函数关系，而且需要对其进行平滑，相当繁琐。文献[5]提出一种求组合多峰问题的方法：在交叉之后将父代子代混合成新群体，然后对新群体中的一半进行变异并择优替换，最后用小生境惩罚淘汰相似个体。其他的遗传算法解决多峰的组合问题还是凤毛麟角。本文以求最大值为例提出一种改进的自适应的基于簇搜索遍历的遗传算法，试图提高对多峰组合问题的寻优能力，寻找尽可能多的解，经实验效果比较明显。这里的簇是指分布集中在某一范围内的个体集合，同一簇内两两个体的距离比较近或者相

5、似度比较高，两个不同的簇间两两个体的距离比较远或者相似度比较低。簇中心是指簇内一个最优个体，簇的范围通常用簇半径衡量，即与簇中心的距离或相似性小于簇半径的所有个体都属于同一个簇。算法描述算法基本思想1.算法思想简介通常随机生成的初始群体并不一定保证均匀覆盖整个解空间（如图一），因此我们必须通过一定的措施使初始群体更加均匀的散满整个解空间，形成分布最均匀的群体，然后每隔一定距离选择其中适应值较优的个体作为候选的簇中心（如图二）。然后一次选择一定数目的候选簇中心，并保证群体中的个体都集中在这些簇内，这样

6、就可以在这些簇周围进行局部的细致搜索(如图三)。如果在某一个簇内找到一个比该簇当前中心个体更优的个体，则可假设这个更优个体附近更接近全局最优解，因此以这个更优个体为新簇中心，下一次迭代时对这个簇的搜索就迁移到更优的新簇附近（如图四）。当在某个簇内找到一个最优解或该簇与某个已求解距离很近或搜索时间超过一定代数后，为了减少重复搜索算法就停止对当前簇的搜索，转而搜索候选簇中心中没有搜索过的其他簇，周而复始一直搜索遍历完所有候选簇中心。图一初始群体图二均匀群体图三在每个小生境内搜索图四小生境向更优解迁移2.

7、算法基本流程为了寻找尽可能多的解，我们需要算法尽可能的搜遍整个解空间，为此必须满足以下两个要求：首先让个体尽可能的均匀分散在整个解空间中；然后尽量不重复的遍历整个解空间。据此把算法分为两个阶段：第一阶段主要是让初始群体尽可能的均匀化；第二阶段主要在每一个簇局部内进行细致的搜索，并不断的把每一个簇向较优区域内迁移，完成不重复遍历解空间的任务。第一阶段首先计算群体中两两个体的距离和每个个体的距离密度，选择距离密度比较大的若干对个体，每一对个体按照距离密度进行交叉变异，然后用子个体替换父个体，这个过程一直

8、重复直到连续几代群体的多样性不再增加为止，在这个过程中记下多样性最好的几代群体，最后在这些多样性最好的群体中选择分布均匀的适应度较优的个体作为候选簇中心，并放到预备簇中心队列中。第二阶段迭代主要在一定量的簇内进行进化，根据进化程度和适应值来调整簇中心和交叉变异策略，并且随着迭代代数的增加不断减小簇半径。整个算法流程如下所述：1.第一阶段a)初始化参数，随机产生初始群体。b)评价群体多样性。c)比较每一代群体的多样性，并保留多样性最优的几代群体。d)计算群体中两两个体的