Tabu Search—Part I

禁忌搜索 旅行商问题 引导式本地搜索 计算机科学 数学优化 爬山 调度(生产过程) 运筹学 算法 数学
作者
Fred Glover
出处
期刊:ORSA journal on computing [Institute for Operations Research and the Management Sciences]
卷期号:1 (3): 190-206 被引量:4927
标识
DOI:10.1287/ijoc.1.3.190
摘要

This paper presents the fundamental principles underlying tabu search as a strategy for combinatorial optimization problems. Tabu search has achieved impressive practical successes in applications ranging from scheduling and computer channel balancing to cluster analysis and space planning, and more recently has demonstrated its value in treating classical problems such as the traveling salesman and graph coloring problems. Nevertheless, the approach is still in its infancy, and a good deal remains to be discovered about its most effective forms of implementation and about the range of problems for which it is best suited. This paper undertakes to present the major ideas and findings to date, and to indicate challenges for future research. Part I of this study indicates the basic principles, ranging from the short-term memory process at the core of the search to the intermediate and long term memory processes for intensifying and diversifying the search. Included are illustrative data structures for implementing the tabu conditions (and associated aspiration criteria) that underlie these processes. Part I concludes with a discussion of probabilistic tabu search and a summary of computational experience for a variety of applications. Part II of this study (to appear in a subsequent issue) examines more advanced considerations, applying the basic ideas to special settings and outlining a dynamic move structure to insure finiteness. Part II also describes tabu search methods for solving mixed integer programming problems and gives a brief summary of additional practical experience, including the use of tabu search to guide other types of processes, such as those of neural networks. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
如意的晓槐完成签到 ,获得积分10
1秒前
内向小霜完成签到 ,获得积分10
2秒前
烟花的应助被shally采纳,获得10
8秒前
8秒前
lllll完成签到 ,获得积分10
11秒前
13秒前
范yx发布了新的文献求助10
14秒前
Eric完成签到,获得积分10
14秒前
陈烨完成签到,获得积分10
14秒前
侯子完成签到 ,获得积分10
18秒前
shally发布了新的文献求助10
19秒前
ninini完成签到 ,获得积分10
19秒前
En完成签到 ,获得积分10
19秒前
慧慧34完成签到 ,获得积分10
20秒前
回首不再是少年完成签到,获得积分0
23秒前
25秒前
Singularity发布了新的文献求助20
28秒前
chenchen完成签到 ,获得积分10
29秒前
31秒前
含糊的盼波完成签到,获得积分10
32秒前
光亮如容完成签到,获得积分10
36秒前
36秒前
浩浩完成签到 ,获得积分0
39秒前
圆圆完成签到 ,获得积分10
51秒前
chunlily完成签到 ,获得积分10
51秒前
xujiahao完成签到,获得积分10
52秒前
53秒前
黑米粥发布了新的文献求助200
58秒前
58秒前
zw完成签到,获得积分10
59秒前
沉默岩完成签到,获得积分10
1分钟前
中恐完成签到,获得积分0
1分钟前
JamesPei的应助被shally采纳,获得10
1分钟前
肥猫完成签到,获得积分10
1分钟前
谦让的忆枫完成签到,获得积分10
1分钟前
lll完成签到 ,获得积分10
1分钟前
黑米粥发布了新的文献求助200
1分钟前
arniu2008的应助被科研通管家采纳,获得20
1分钟前
arniu2008的应助被科研通管家采纳,获得20
1分钟前
arniu2008的应助被科研通管家采纳,获得20
1分钟前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
八旗制度の研究 600
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8185502
求助须知:如何正确求助?哪些是违规求助? 9574220
关于积分的说明 21834553
捐赠科研通 7783121
什么是DOI,文献DOI怎么找? 3434577
关于科研通互助平台的介绍 2558949
邀请新用户注册赠送积分活动 2481357