基于遗传算法和禁忌搜索算法的混合策略及其应用.pdf

《基于遗传算法和禁忌搜索算法的混合策略及其应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第32卷第3期北京工业大学学报Vo1．32NO．32006年3月JOURNAIOFBEIJINGUNIVERSITYOFTECHNOLOGYMar．2006基于遗传算法和禁忌搜索算法的混合策略及其应用孙艳丰(北京工业大学计算机学院，北京100022)摘要：为了提高遗传算法的局部搜索能力，根据遗传算法和禁忌搜索算法自身的特点，通过分析2者的优势和不足，提出了一种将2者混合使用的求解优化问题的方法．本算法用遗传算法作全局搜索，用禁忌搜索算法作局部搜索，可以加快收敛速度，得到满意的计算结果．同时，为抑制早熟现象，避免收敛到局

2、部最优点，提出了一种应对策略．实验结果表明，该算法在计算速度和计算结果方面都有改进．关键词：遗传算法；收敛；全局最优中圉分类号：TP301．6文献标识码：A文章编号：0254—0037(2006)03—0258—05遗传算法(geneticalgorithm，简称GA)和禁忌搜索(tabusearch，简称TS)算法是2种十分有效的全局搜索算法，前者源于生物遗传学，模拟自然界生物的优胜劣汰、适者生存的过程，后者模拟一种智力过程．这2种算法都与问题无关，通用性与优化性较好，能处理复杂、大规模优化问题，但并不是对所有问题都适用．文献[1]根据2者的特点提出将2者混合使用

3、的策略，但其缺点是调用TS算法过于频繁，计算量大；而不调用Ts算法又易早熟(群体中的个体过早地收敛到某点附近，不能使搜索转向解空间的其他区域)，产生局部最优解．作者首先对GA和TS算法进行了分析比较，有效结合它们各自优势，提出混合使用的方法；同时对于早熟现象，提出一种早熟判定与应对策略；最后进行了计算试验．GA及TS算法简介1．1GA的特点与不足目前，已经有许多GA的变形，但人们习惯上把1975年Holland提出的GA称为标准GA[4】．与传统的优化算法相比，标准GA具有如下特点：1)搜索过程不直接作用在变量上，而是作用在将变量编码后的字符串上；2)搜索过程是从一

4、组解迭代到另一组解，这样可降低陷入局部最优解的概率；3)使用随机搜索过程而不是确定性搜索过程；4)只利用目标函数和约束函数的函数值信息，不需要导数等其他辅助信息，因此通用性更大，适用范围更广．5)作为一种优化算法，寻求最优点不是GA的唯一目的，更重要的目的是进步，即它的优化过程是一个不断改进的过程．GA具有并行搜索能力，从解空间中多点出发搜索问题的最优解，能在一定程度上保留历史信息，适合求解大规模任意目标函数的全局优化问题．但它也有不足，进行局部搜索能力差，导致发生早熟．这是因为算法的变异概率太小，引入新染色体的机会少。如果变异概率取大些，传统的变异算子将导致算法随

5、机性很大，使搜索过程过于盲目．收稿日期：2004—09—07．基金项目：北京市教育委员会科技发展计划资助项目(Km200310005025)作者简介：孙艳丰(1964一)，女，黑龙江齐齐哈尔人，教授．维普资讯http://www.cqvip.com第3期孙艳丰：基于遗传塑法茎垦塑窒篁望竺垒堕堕垦苎些垄11．2Ts算法的特点与不足TS算法是由Glover于1986年提出的引，它是一种全局逐步寻优的搜索算法，也是一种模拟智力过程的“爬山，，算法，它通过一个灵活的记忆功能和藐视准则达到搜索解空间的目的．算法的基本思想如下：假设给出1个解和1个邻域，首先在这邻域中找出1个最

6、好的局部解作为当前解z，令当前最优解z：z，然后再在这个当前解的邻域中搜索最好的局部解．但是，这个最好解有可能与前次的相同，为避免这种循环的现象，设置1个记忆近期操作的禁止操作表，如果当前操作是记录在此表中的操作，那么，这一操作就被禁止，否则用z取代z．此时z点的目标函数值可能劣于点的目标值，所以Ts算法以一定概率接受劣解．但对那些特别有益的操作，如果改善了目前找到的最优解，可以忽视被禁止的特性(即此时仍令z=z，z：z)，以便迅速找到更好的解，同时为保证搜索更大的解空间，对每个被禁止的操作，设定1个期限，在下次操作时，这个值被减1．当这个值为0时，该操作可重新变成

7、不被禁止的操作．在搜索过程中有些操作出现的频率很高，为了不重复这样的操作，对每个操作再设定1个频率值，该操作每出现1次，频率值就加1，当频率值超过某一设定值时，该操作也被列为禁止操作．重复上述搜索迭代过程，直至满足停止计算准则．与传统的优化算法相比，TS算法的主要特点是：1)在搜索过程中可以接受劣解，所以具有较强的“爬山”能力；2)新解不是在当前解的邻域中随机产生，而是从中选取最好解，即最好解的产生概率远远大于其他解．TS算法由于具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣解，所以具有较强的“爬山”能力．这样，搜索时能跳出局部最优解，而转向解空间的其