一种禁忌搜索算法在计算网格中的并行化策略

摘要

禁忌搜索算法是求解组合优化问题的一种主要方法,是克服NP完全问题的有效的解决途径,随着计算网格的发展,将算法移植到这种弱的分布式并行计算环境中,具有广泛的应用意义。Master-Worker计算模式被认为是比较适宜于计算网格的模式。本文在分析讨论了Rolland等人提出的一种高效禁忌搜索算法的基础上,提出了两种并行化策略并进行了比较。结果表明,对于区域分解困难,同时算法复杂性低的情况,利用分散搜索的策略,可以提高求解精度。