一种基于Tabu搜索求解维修费用的算法  

Algorithm for solving maintaining cost based on Tabu search

作　　者：高雪东[1] 董传良[1] 任政[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200240

出　　处：《计算机应用》2006年第5期1178-1179,1213,共3页journal of Computer Applications

摘　　要：在资源有限的情况下求解维修费用的算法是一个01规划的问题。目前已有的算法有可能得到局部最优,但不能保证得到全局最优。针对这类问题的特性,提出了一个基于Tabu搜索的算法。为了简化计算提出了图论的模型,用Tabu算法对其模拟,充分利用了Tabu搜索的集中性与广泛性的优点,在提高搜索速度的同时可以更加接近最优解。仿真实验表明:该算法具有快速,易收敛的特点,更适合在规模比较大的情况下应用。A new algorithm salving the maintaining with the limited resource based on Tabu search was proposed, the mathematical model was created, and the problem was converted to 0-1 programming. In order to minimize the run times, the graphic model was created, and the idea of the Tabu search was used to solve the problem. A Tabe search heuristic procedure was proposed to find tile sequence which allows one to reach a value of the cost function as close as to the global minimum. Simulation rcsults show that the algorithm based on Tabu search has excellent performance.

关 键 词：NP难 TABU搜索 0-1规划 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]