摘要
禁忌搜索算法是求解组合优化问题的一种主要方法,是克服NP完全问题的有效的解决途径,随着计算网格的发展,将算法移植到这种弱的分布式并行计算环境中,具有广泛的应用意义。Master-Worker计算模式被认为是比较适宜于计算网格的模式。本文在分析讨论了Rolland等人提出的一种高效禁忌搜索算法的基础上,提出了两种并行化策略并进行了比较。结果表明,对于区域分解困难,同时算法复杂性低的情况,利用分散搜索的策略,可以提高求解精度。
TABU search is a well known method in finding optimal solutions of combinatorics problems. It is significantly beneficial to introduce the method into the computational grid, for the grid is becoming an important technology to co-operate amount of PCs and workstations to be a loosely coupled distributed computing environment at a low cost. It is necessary to study the parallelization strategy on such an environment. Generally the Master-Worker paradigm is considered to be a suitable one. Therefore the authors try to put forward two different parallelization strategies for the efficient TABU search method which is introduced by Rolland, etc. We argue that a scatter search strategy is better for improving the solution when the search method has a low time complexity and also the decomposition strategy is difficult to implement.
出处
《微电子学与计算机》
CSCD
北大核心
2004年第6期115-118,122,共5页
Microelectronics & Computer
基金
国家自然科学基金资助项目(40131010)
关键词
禁忌搜索算法
计算网格
并行化策略
TABU search algorithm, computational grid, parallelization strategy
