禁忌搜索基础与应用 - Fred Glover

需积分: 9 14 浏览量更新于2024-08-01 收藏 1.81MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

"Tabu搜索基础与应用——Fred Glover" Fred Glover的《Tabu搜索基础与应用》深入探讨了这一优化问题解决方法的核心概念及其广泛应用。Tabu搜索自诞生以来已经在资源管理、流程设计、物流、技术规划以及组合优化等众多领域取得了显著的成功。通过与其他启发式和算法的混合应用，它也催生了许多富有成效的结果。文章的摘要指出，Tabu搜索的成功在于其主要特征，这些特征不仅解释了它的有效性，也为未来改进解决方案提供了基础。作者深入分析了这些关键特性，包括但不限于： 1. **禁忌列表策略（Candidate List Strategies）**：Tabu搜索的核心是禁忌列表，它记录了近期被禁止或不鼓励的选择，以避免陷入局部最优。该版本增加了关于如何有效地管理和更新禁忌列表的额外信息，这对于避免早熟收敛至关重要。 2. **概率性Tabu搜索（Probabilistic Tabu Search）**：在经典Tabu搜索的基础上，概率性Tabu搜索引入了随机元素，允许在禁忌之外的决策有一定的选择概率。这有助于在探索与开发之间取得平衡，提高搜索效率。 3. **策略振荡（Strategic Oscillation）**：这是一种策略，通过在不同搜索策略之间交替，防止算法陷入特定模式，从而增强全局探索能力。 4. **并行处理选项（Parallel Processing Options）**：随着计算能力的提升，将Tabu搜索应用于并行计算环境中可以显著加快求解速度。文章可能包含了关于如何有效利用并行计算来加速Tabu搜索的信息。 5. **智能搜索原则（Principles of Intelligent Search）**：新增的章节阐述了如何利用智能搜索策略指导Tabu搜索过程，包括适应性调整、信息反馈和学习机制等，以提高搜索的智能性和效率。此外，这项研究得到了加拿大国家科学与工程理事会的部分资助，表明其在学术界和工业界的广泛认可。总体来说，Fred Glover的这份扩展版论文对理解Tabu搜索的原理和实践应用具有极高的价值，对于想要掌握和应用这一优化工具的研究者和实践者来说，是一份宝贵的资源。

资源详情

资源推荐

criteria. The tabu status of a solution is not an absolute, but can be overruled if certain conditions are

met, expressed in the form of aspiration levels. In effect, these aspiration levels provide thresholds of

attractiveness that govern whether the solutions may be considered admissible in spite of being classified

tabu. Clearly a solution better than any previously seen deserves to be considered admissible. Similar

aspiration criteria can be defined over subsets of solutions that belong to common regions or that share

specified features (such as a particular functional value or level of infeasibility). For example, one such

aspiration criterion is based on identifying "conditionally best" objective function values that can be

attained by moves that start from particular intervals of values for f(x). Then a move is deemed

acceptable if it can attain a new best value for the interval it starts from.

The foregoing approach naturally generalizes by replacing intervals of objective function values

with other types of intervals. In this case it is often preferable to stipulate that the move attains an

improved objective function value in relation to the interval at the end of a move rather than at the start

of a move. This corresponds more closely to a standard tabu restriction, except that it is used to

override other tabu restrictions. (Implicitly it corresponds to a special type of conjunction.) Additional

examples of aspiration criteria are provided later.

Candidate List Strategies: The aggressive aspect of TS is reinforced by seeking the best

available move that can be determined with an appropriate amount of effort. It should be kept in mind

that the meaning of best is not limited to the objective function evaluation. (As already noted, tabu

evaluations are affected by penalties and inducements determined by the search history. They are also

affected by considerations of influence as subsequently characterized.) For situations where N*(x) is

large or its elements are expensive to evaluate, candidate list strategies are used to restrict the number of

solutions examined on a given iteration.

Because of the importance TS attaches to selecting elements judiciously, efficient rules for

generating and evaluating good candidates are critical to the search process. Even where candidate list

The representation of penalties in Diagram 2 either as "large" or "very small" expresses a thresholding

effect. In the illustration of Diagram 1, we treated tabu status as an all-or-none type of condition, but

differentiation is clearly possible, as by reference to different numbers of tabu-active attributes or to

different levels of unexpired tabu tenures. Tabu status generally corresponds to using penalties that yield

a greatly deteriorated evaluation or else that chiefly served to break ties among solutions with highest

evaluations. (Tie breaking occurs for moves that are no longer tabu in an all-or-none sense, by allowing

a lingering diminished influence according to the age of tenures that might otherwise be considered to be

expired.) Such an effect of course can be modulated to shift evaluations across levels other than these

extremes. If all moves currently available lead to solutions that are tabu (with evaluations that normally

would exclude them from being selected), the penalties result in choosing a "least tabu" solution.

It may be noted that the sequence of the Tabu Test and the Aspiration Test in Diagram 2 can be

interchanged (that is, by employing the tabu test only if the aspiration threshold is not satisfied). Also,

the tabu evaluation can be modified by creating inducements based on the aspiration level, just as it is

modified by creating penalties based on tabu status. In this sense, aspiration conditions and tabu

conditions can be conceived roughly as "mirror images" of each other.

The TS variant called probabilistic tabu search follows a corresponding design, with a short

term component that can be represented by the same diagram. The approach additionally keeps track

of tabu evaluations generated during the process that results in selecting a move. Based on this record,

the move is chosen probabilistically from the pool of those evaluated (or from a subset of the best

members of this pool), weighting the moves so that those with higher evaluations are especially favored.

Fuller discussions of probabilistic tabu search are found in Glover (1989, 1993), Soriano and

Gendreau (1993) and Crainic et al. (1993). Recently, several highly successful implementations of

probabilistic tabu search have been developed, particularly for problems involving noisy evaluations.

The elements underlying these approaches are discussed further in Section 3.6.

剩余84页未读，继续阅读

wangpu608

粉丝: 4
资源: 91

禁忌搜索基础与应用 - Fred Glover

tabu search --fred glover

Tabu Search

tabu search python

tabu search

Tabu search algorithm

Tabu Search（禁忌搜索）

Tabu Search解决图染色问题

在matlab中写出可以画出用贪婪算法和禁忌算法解决导频分配的仿真图的代码

用Tabu Search（禁忌搜索）java代码实现图染色问题

tabu search algorithm

java 路径规划_转 | 禁忌搜索算法（Tabu Search）求解带时间窗的车辆路径规划问题详解（附Java代码）...

Tabu(1,:)=R_best(NC-1,:);

禁忌搜索matlab

禁忌搜索 tabu python

先遗传算法后蚁群算法路径规划代码

Can you tell me the method and model for solving the maximum cut problem?

与时间线规划车辆行驶路径有关的文献

帮我写一份蚁群算法的matlab代码

用禁忌搜索算法解决TSP问题，用C++代码实现，且能通过读取文本文件中的数据作为输入，表明注释

最新资源