元启发式方法在组合优化中的应用与概念比较

5星 · 超过95%的资源需积分: 10 136 浏览量更新于2024-07-29 收藏 713KB PDF 举报

"元启发式在组合优化中的应用：概述与概念比较" 本书“Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison”由Christian Blum和Andrea Roli合著，是一本针对元启发式优化算法的入门级读物，特别适合对这个领域感兴趣的研究者和学生。元启发式方法是当前研究领域的热点，因其在解决组合优化问题中的广泛应用而受到广泛关注。组合优化问题在科学界和工业界都有着广泛且重要的应用。元启发式是一种高级的搜索策略，设计用于寻找复杂优化问题的近似最优解。它们通常比传统的精确算法更灵活，能够在较短的时间内找到质量较好的解决方案，尽管可能不是全局最优。作者在这本书中，从概念的角度出发，详细介绍了目前最重要的一些元启发式算法，包括它们的基本组件和概念，旨在分析这些算法之间的相似性和差异性。书中强调了元启发式中的两个核心概念：强化（Intensification）和多样化（Diversification）。强化是指算法集中在搜索空间的特定区域，以深入探索可能的解决方案；而多样化则鼓励算法探索不同的区域，以避免陷入局部最优。这两种力量相互矛盾但又相辅相成，共同决定了元启发式算法的行为模式。作者提出了一个名为“I&D框架”的概念，用以关联不同的强化和多样化组件，以便更好地理解它们如何相互作用并影响算法的整体性能。通过这本书，读者可以了解到各种元启发式算法的优缺点，例如遗传算法、模拟退火、粒子群优化、蚁群优化等。此外，书中还可能探讨了如何根据问题特性选择合适的元启发式策略，以及如何设计和调整算法参数以获得最佳性能。这本书对于想要深入了解元启发式优化算法及其在实际问题中应用的人来说，是一份宝贵的资源。它不仅提供了理论背景，还可能包含了一些实际案例和实验结果，帮助读者将理论知识转化为实践技能。通过阅读此书，读者可以全面地掌握元启发式的基本思想，为解决实际的组合优化问题打下坚实的基础。

GenerateInitialSolution()

TabuList

while termination conditions not met do

ChooseBestOf(N



76

TabuList)

Update(TabuList)

endwhile

Figure 3: Algorithm: Simple Tabu Search (TS)

neighborhood search technique [153]. The algorithm stops when a termination condition is met. It might

also terminate if the allowed set is empty, that is, if all the solutions in N





are forbidden by the tabu list.

The use of a tabu list prevents from returning to recently visited solutions, therefore it prevents from

endless cycling

and forces the search to accept even uphill moves. The length l of the tabu list (i.e., the

tabu tenure) controls the memory of the search process. With small tabu tenures the search will concentrate

on small areas of the search space. On the opposite, a large tabu tenure forces the search process to

explore larger regions, because it forbids revisiting a higher number of solutions. The tabu tenure can be

varied during the search, leading to more robust algorithms. An example can be found in [157], where

the tabu tenure is periodically reinitialized at random from the interval [l

min



max

]. A more advanced use

of a dynamic tabu tenure is presented in [12, 11], where the tabu tenure is increased if there is evidence

for repetitions of solutions (thus a higher diversiﬁcation is needed), while it is decreased if there are no

improvements (thus intensiﬁcation should be boosted). More advanced ways to create dynamic tabu tenure

are described in [68].

However, the implementation of short term memory as a list that contains complete solutions is not

practical, because managing a list of solutions is highly inefﬁcient. Therefore, instead of the solutions

themselves, solution attributes are stored.

Attributes are usually components of solutions, moves, or

differences between two solutions. Since more than one attribute can be considered, a tabu list is introduced

for each of them. The set of attributes and the corresponding tabu lists deﬁne the tabu conditions which

are used to ﬁlter the neighborhood of a solution and generate the allowed set. Storing attributes instead

of complete solutions is much more efﬁcient, but it introduces a loss of information, as forbidding an

attribute means assigning the tabu status to probably more than one solution. Thus, it is possible that

unvisited solutions of good quality are excluded from the allowed set. To overcome this problem, aspiration

criteria are deﬁned which allow to include a solution in the allowed set even if it is forbidden by tabu

conditions. Aspiration criteria deﬁne the aspiration conditions that are used to construct the allowed set.

The most commonly used aspiration criterion selects solutions which are better than the current best one.

The complete algorithm, as described above, is reported in Figure 4.

Tabu lists are only one of the possible ways of taking advantage of the history of the search. They

are usually identiﬁed with the usage of short term memory. Information collected during the whole search

process can also be very useful, especially for a strategic guidance of the algorithm. This kind of long term

memory is usually added to TS by referring to four principles: recency, frequency, quality and inﬂuence.

Recency-based memory records for each solution (or attribute) the most recent iteration it was involved

in. Orthogonally, frequency-based memory keeps track of how many times each solution (attribute) has

been visited. This information identiﬁes the regions (or the subsets) of the solution space where the search

was conﬁned, or where it stayed for a high number of iterations. This kind of information about the past

is usually exploited to diversify the search. The third principle (i.e., quality) refers to the accumulation

and extraction of information from the search history in order to identify good solution components. This

information can be usefully integrated in the solution construction. Other metaheuristics (e.g., Ant Colony

Optimization) explicitly use this principle to learn about good combinations of solution components. Fi-

nally, inﬂuence is a property regarding choices made during the search and can be used to indicate which

Strategies for avoiding to stop the search when the allowed set is empty include the choice of the least recently visited solution,

even if it is tabu.

Cycles of higher period are possible, since the tabu list has a ﬁnite length l which is smaller than the cardinality of the search

space.

In addition to storing attributes, some longer term TS strategies also keep complete solutions (e.g., elite solutions) in the memory.

GenerateInitialSolution()

InitializeTabuLists(TL



T L

)

while termination conditions not met do

AllowedSet





$











s does not violate a tabu condition,

or it satisﬁes at least one aspiration condition



ChooseBestOf(AllowedSet







)

UpdateTabuListsAndAspirationConditions()

endwhile

Figure 4: Algorithm: Tabu Search (TS)

while termination conditions not met do

ConstructGreedyRandomizedSolution() % see Figure 6

ApplyLocalSearch(s)

MemorizeBestFoundSolution()

endwhile

Figure 5: Algorithm: Greedy Randomized Adaptive Search Procedure (GRASP)

choices have shown to be the most critical. In general, the TS ﬁeld is a rich source of ideas. Many of these

ideas and strategies have been and are currently adopted by other metaheuristics.

TS has been applied to most CO problems; examples for successful applications are the Robust Tabu

Search to the QAP [157], the Reactive Tabu Search to the MAXSAT problem [11], and to assignment prob-

lems [31]. TS approaches dominate the Job Shop Scheduling (JSS) problem area (see for example [123])

and the Vehicle Routing (VR) area [64]. Further current applications can be found at [156].

3.4 Explorative Local Search methods

In this section we present more recently proposed trajectory methods. These are the Greedy Randomized

Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS), Guided Local Search (GLS)

and Iterated Local Search (ILS).

3.4.1 GRASP

The Greedy Randomized Adaptive Search Procedure (GRASP), see [50, 131], is a simple metaheuristic

that combines constructive heuristics and local search. Its structure is sketched in Figure 5. GRASP is an

iterative procedure, composed of two phases: solution construction and solution improvement. The best

found solution is returned upon termination of the search process.

The solution construction mechanism (see Figure 6) is characterized by two main ingredients: a dy-

namic constructive heuristic and randomization. Assuming that a solution s consists of a subset of a set of

elements (solution components), the solution is constructed step-by-step by adding one new element at a

time. The choice of the next element is done by picking it uniformly at random from a candidate list. The

elements are ranked by means of a heuristic criterion that gives them a score as a function of the (myopic)

beneﬁt if inserted in the current partial solution. The candidate list, called restricted candidate list (RCL),

is composed of the best α elements. The heuristic values are updated at each step, thus the scores of ele-

ments change during the construction phase, depending on the possible choices. This constructive heuristic

is called dynamic, in contrast to the static one which assigns a score to elements only before starting the

construction. For instance, one of the static heuristics for the TSP is based on arc costs: the lower the cost

剩余41页未读，继续阅读

xsssunny

粉丝: 0
资源: 1

元启发式方法在组合优化中的应用与概念比较

Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison

Handbook of graph theory, combinatorial optimization, and algorithms

metaheuristics : from design to implementation.

元启发算法比较的英文

配送中心选址问题参考文献

防止陷入局部最优的算法改进手段

用python写一个求解带时间窗的车辆路径问题的代码

nginx支持的功能介绍，openresty安装配置简介

公众号图文自动批量发布软件

psycopg2-2.9.3-cp37-cp37m-win_amd64.whl

最新资源