-
题名基于禁忌搜索算法求解随机约束满足问题
被引量：12
- 1
-
-
作者
李飞龙
赵春艳
范如梦
-
机构
上海理工大学理学院
-
出处
《计算机应用》
CSCD
北大核心
2019年第12期3584-3589,共6页
-
基金
国家自然科学基金资助项目(11301339)
国家自然科学基金国际(地区)合作与交流项目(11491240108)~~
-
文摘
为了求解具有增长取值域的随机约束满足问题(CSP),提出了一种基于禁忌搜索并与模拟退火相结合的算法。首先,利用禁忌搜索得到一组启发式的初始赋值,即由一个随机初始化的可行解通过邻域构造一组候选解,再利用禁忌表使候选解向最小化目标函数值的方向移动;如果得到的最优赋值不是问题的解,就把它作为启发式的初始赋值,再执行模拟退火对这组赋值进行修正直到得到全局最优解。数值实验结果表明,所提算法在接近问题的理论相变阈值时仍然能有效地找到问题的解,与其他局部搜索算法相比,表现出了显著的优越性,可用于随机CSP的算法设计。
-
关键词
随机约束满足问题
rb模型
相变现象
禁忌搜索
模拟退火
算法效率
-
Keywords
random Constraint Satisfaction Problem(CSP)
revised b(rb) model
phase transition phenomenon
tabu search
simulated annealing
algorithm efficiency
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
