基于双禁忌对象的并行禁忌搜索算法.pdf

C0 ，“ 西 e 册 铆 ，fc口加 计算机工程与应用 基于双禁忌对象的并行禁忌搜索算法 朱颢东，李红婵 ZHU Haodong，LIHongchan 郑州轻工业学院 计算机与通信工程学院，郑州 450002 SchoolofComputerandCommunic~ion Engineering，ZhengzhouUniversity ofLightIndustry，Zhengzhou 450002，China zHU Haodong．LIHongchan．Paralleltabu search algorithm based on doubletabu objects．ComputerEngineeringand Applications，2011，47(29)：31-33． Abstract：TabuSearch(TS)algorithm isoneofmani methodstosolvecombinatorialoptimizationproblem nadna effective approach to overcomeNP completeproblem．Wiht htedevelopmentofcomputationalgrid，ithaswideapplication valueot ni— troduce atbu serach algorithm into distributed parallelcomputing environment．A atbu serach algorithm based on double atbu objectsisproposed．Praallelscattersearchstrategyisusedot improvealgorithm precision．Experimenatlresultsshow htathte praallelatbu serach algorithm hasbetterperformance． Keywords：atbu serach；combniatorialoptimizationproblem ；compuattionalgrid；praallelscatterserach srtateyg 摘 要：禁忌搜索算法是解决组合优化 问题的一种主要方法，是克服NP完全问题的一个有效途径。随着计算网格的发展，将禁 忌搜索算法引入到这种分布式并行计算环境中，具有广泛的应用价值。提出了一个基于双禁忌对象的禁忌搜索算法，在此算法 的基础上，利用并行化分散搜索策略来提高算法的求解精度。实验结果表明该并行禁忌搜索算法性能较高。 关键词：禁忌搜索；组合优化问题；计算网格；分散搜索策略 DOI：10．3778／j．issn．1002．8331．2011．29．009 文章编号：1002．8331(2011)29-0031—03 文献标识码：A 中图分类号：TP301 组合优化问题是 日常生活中经常要面临的问题 ，例如0／1 背包问题n，它已被广泛应用于货物装载、材料切割等问题之 中 。对于解决组合优化问题，禁忌搜索算法是一种行之有效 步骤1选定—个初始解 —及给以禁忌表 = 。 的方法 。该算法采用一定的藐视准则使搜索过程跳出局部 步骤2若满足停止规则，停止计算；否则，在 的领域 最优解，从而提高获得全局最优解的可能性 。但是，大部分 N(H， )中选择满足禁忌要求的侯选集 CanN(x~)；在 _ 组合最优化问题属于NP．hrad问题，计算复杂性都比较高、耗 CanN(x~)中选一个评价值最佳的解 ，一：i ；更新历史 _ 时长。因此，除了研究如何提高该算法的搜索能力外，如何提 记录日，重复步骤2。 高算法的时间效率或计算精度也是一个重要的研究方面。文 献