采用排挤机制小生境技术改进禁忌搜索算法.pdf

《采用排挤机制小生境技术改进禁忌搜索算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、过程控制化工自动化及仪表，2010，37(8)：34—36ControlandInstrumentsinChemicallndustry采用排挤机制小生境技术改进禁忌搜索算法吴俊，方锦明(义乌工商职业技术学院机电信息分院，浙江义乌322000)摘要：针对禁忌搜索算法中多样性与集中性搜索并重的情况下多样性不足的缺点。引入小生境技术对其进行改进。通过海明距离定义的排挤策略能够保证种群的多样性，拓宽搜索领域，加强多样性搜索。同时可以加快收敛速度，抑制早熟现象，避免过早收敛到局部最优。对比实验结果表明，该算法能很好的抑

2、制早熟收敛，同时在计算速度和计算结果方面都有所改进。关键词：禁忌搜索；小生境技术；组合优化；TSP问题中图分类号：TP393文献标识码：A文章编号：1000-3932(2010)08-0034-03l引言禁忌搜索算法由美国科罗拉多大学教授FredGlover在1986年左右提出，至90年代初才形成一套完整的算法⋯，是局部邻域搜索算法的推广。所谓禁忌就是禁忌苇复前面的工作，为了回避局部邻域搜索陷入局部最优的主要不足，禁忌搜索算法用一个禁忌表来记录已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或者有

3、选择的搜索这些点，以此来跳出局部最优点，最终达到全局优化的目的忙3。它的基本思想非常简单，就是基于“记忆装置”记住一些最近检查过的局部最优解，它们将成为选取下一个解的禁忌点。禁忌搜索在智能算法中独树一帜，成为一个新的研究热点，受到了国内外学者的广泛关注¨1。近年来禁忌搜索算法广泛应用于车间调度、神经网络、网络优化等领域，但也有其不足之处一J：①对初始解的依赖性较强；②多样性与集中性搜索并重的情况下，多样性不足；③确定性的搜索制约了它的灵活性。在禁忌搜索中，集中性搜索和多样性搜索是它的两个重要策略。其中多样性搜索

4、尤为重要，通常的算法都是使用基于频率记忆或改变其参数来实现多样性搜索策略。在问题规模较大时，单纯应用频率记忆或改变参数来实现多样性搜索往往得不到理想的效果一，。近年来许多学者对禁忌搜索的改进做了大量的研究工作一J1。另外，禁忌搜索通常使用局部抖动的方法来构造邻域，每次只能产生一个当前解，所以尽管禁忌搜索有很强的局部搜索能力，但当其陷入较深的谷中时，它很难跳出该谷。文献[7]提出了一种基于插入法的禁忌搜索算法TIS，摆脱了单一利用基于频率的记忆来实现多样性搜索，使搜索程序能够很快跳出以前的搜索路径，从不同的方向继

5、续进行搜索。本文针对禁忌搜索算法中集中性与多样性搜索并重的情况下多样性不足的缺点，引入小生境技术对其进行改进，小生境技术通过海明距离定义的排挤策略能够保证种群的多样性，拓宽搜索领域，加强多样性搜索。同时加快收敛速度，抑制早熟现象，避免过早收敛到局部最优，对比实验结果表明，该算法能很好地抑制早熟收敛，同时在计算速度和计算结果方面都有所改进。2基于排挤机制的小生境技术一般的进化算法对于一个优化问题只能发现一个最优解。当面临一个多模优化问题需要发现多个最优解时，一般的进化计算技术这时将无能为力哺3。即使将一般进化算法

6、多次使用，也不能保证所发现的最优解互不相同。小生境技术能使一般进化算法具有发现多个最优解的能力。小生境技术源于遗传算法(GA)，因此在遗传算法中，发现多模问题中多个最优解的能力被称为小生境技术。尽管目前很多进化计算技术，如PSO、微分进化都己经提出了自己的小生境技术，但目前遗传算法在小生境技术中仍然占据着突出的地位，对基于其他进化算法的小生境技术仍具有指导作用。其中比较典型的就是基于排挤机制的小生境技术。在生物学中，小生境(Niche)是指特定环境下的一种生存环境。在生物进化过程中，相同的物种一般生活在一起，共

7、同繁衍后代，它们往往生活在特定的区域，如热带动物很难在北极生存，而北极的动物很难在赤道存活。受大自然的物竞天择，优胜劣汰的思想启发，DeJong旧1提出了基于排收稿日期：2010-05-23(修改稿)第8期吴俊等．采用排挤机制小生境技术改进禁忌搜索算法-35·挤机制(Crowding)的小生境方法。排挤的思想源子在一个有限的空间中，各种不同的生物为了能够延续生存，它们之间必须相互竞争有限的资源。最先也是作为一种预防遗传算法早熟收敛而提高其种群差异性的技术，是作为对预选择技术的一种改进J⋯。目前该方法已经成功地用

8、于解决多峰函数的极限问题。3改进的禁忌搜索算法在禁忌搜索中，多样性搜索策略用于拓宽搜索区域尤其是未知区域，特别是当搜索陷于局部最优时，多样性搜索可改变搜索的方向，跳出局部最优，从而实现全局优化。集中性搜索策略是为了加强对当前搜索到的优良解的邻域做进一步的搜索，以便能找到全局最优解。为了使搜索更有效，在分析集中性搜索与多样性搜索后，针对禁忌搜索算法中集中性与多样性搜索并重的情况下，多样性