Metaheuristics：启发式算法的综合指南

需积分: 50 173 浏览量更新于2024-08-02 收藏 10.03MB PDF 举报

"Handbook of Metaheuristics 是一本由国际运营研究与管理科学系列出版的书籍，由fred glover，被誉为‘ta教父’撰写。本书主要关注的是各种启发式算法的介绍。" 《元启发式算法手册》是Fred Glover的力作，他被誉为“ta教父”，在运筹学和管理科学领域具有显著影响力。这本书深入探讨了元启发式算法这一主题，元启发式算法是一种高级的优化技术，广泛应用于解决复杂的、难以用传统方法求解的优化问题。这些算法通常结合了多种策略，如随机搜索、局部搜索和全局搜索，旨在在较短的时间内找到接近最优或全局最优的解决方案。书中可能涵盖了以下关键知识点： 1. **启发式算法基础**：介绍了启发式算法的基本概念，包括遗传算法、模拟退火、粒子群优化、蚁群优化等，这些算法都以寻找问题解决方案为目标，但它们不保证找到全局最优解，而是追求快速找到满意解。 2. **元启发式框架**：阐述了元启发式算法的设计原则，包括如何构建算法框架，如何平衡探索与开发，以及如何通过适应度函数来评估解的质量。 3. **应用实例**：书中可能包含了大量的实际应用案例，展示了元启发式算法在组合优化、旅行商问题、网络设计、生产调度等问题中的有效应用。 4. **性能分析**：对不同元启发式算法的性能进行了比较和分析，讨论了影响算法效率的因素，如参数设置、初始化策略和迭代次数。 5. **改进与创新**：可能会讨论如何通过引入新的机制、策略或混合不同的算法来改进现有的元启发式算法，以提高其解决问题的能力。 6. **理论与实践**：理论部分可能包括了算法的数学基础，而实践部分则强调了如何在实际问题中有效地实施这些算法。 7. **未来趋势**：作者可能对未来的研究方向和元启发式算法的潜在发展进行了展望，包括多目标优化、并行计算和机器学习在启发式算法中的融合等。 8. **评估与验证**：书中可能包含了如何评估元启发式算法性能的标准和方法，以及如何通过基准测试来验证算法的性能。 9. **编程实现**：可能提供了元启发式算法的伪代码或实际编程示例，帮助读者理解算法的实现细节。《元启发式算法手册》是一本面向研究人员和实践者的权威参考书，它不仅提供了一种理解和应用启发式算法的全面途径，还鼓励读者对算法进行创新和改进，以应对不断变化的优化挑战。

Scatter Search and Path Relinking

Pivot Based Search Integrated with Branch and Bound for Binary MIPs

(Løkketangen and Woodruff)

Scatter Search to Generate Diverse MIP Solutions (Glover, Løkketangen and

Woodruff)

Path Relinking to Improve Iterated Start Procedures (Ribeiro and Resende)

A number of these applications are described in Section 4 where a collection of vignettes

is presented. They provide a diverse range of settings where SS and PR have made useful

contributions, and suggest the form of additional applications where similar successes

may be anticipated.

SCATTER SEARCH

Scatter search is designed to operate on a set of points, called reference points

which

constitute good solutions obtained from previous solution efforts. Notably, the basis for

defining “good” includes special criteria such as diversity that purposefully go beyond

the objective function value. The approach systematically generates combinations of

the reference points to create new points, each of which is mapped into an associ-

ated feasible point. The combinations are generalized forms of linear combinations,

accompanied by processes to adaptively enforce feasibility conditions, including those

of discreteness (Glover, 1977).

The SS process is organized to (1) capture information not contained separately

in the original points, (2) take advantage of auxiliary heuristic solution methods (to

evaluate the combinations produced and to actively generate new points), and (3) make

dedicated use of strategy instead of randomization to carry out component steps. SS

basically consist of five methods:

A Diversification Generation Method to generate a collection of diverse trial

solutions, using one or more arbitrary trial solutions (or seed solutions) as an

input.

An Improvement Method to transform a trial solution into one or more enhanced

trial solutions. (Neither the input nor the output solutions are required to be fea-

sible, though the output solutions are typically feasible. If the input trial solution

is not improved as a result of the application of this method, the “enhanced”

solution is considered to be the same as the input solution.)

A Reference Set Update Method to build and maintain a reference set consisting

of the b “best” solutions found (where the value of b is typically small, e.g., no

more than 20), organized to provide efficient accessing by other parts of the

solution procedure. Several alternative criteria may be used to add solutions to

the reference set and delete solutions from the reference set.

A Subset Generation Method to operate on the reference set, to produce a subset

of its solutions as a basis for creating combined solutions, The most common

subset generation method is to generate all pairs of reference solutions (i.e., all

subsets of size 2).

A Solution Combination Method to transform a given subset of solutions pro-

duced by the Subset Generation Method into one or more combined solutions.

Scatter Search and Path Relinking

RefSet, the new solution replaces the worst and RefSet is reordered in step 6. The

NewSolutions flag is switched to TRUE and the subset s that was just combined is

deleted from NewSubsets in steps 7 and 8, respectively.

This basic design can be expanded and improved in different ways. The SS method-

ology is very flexible, since each of its elements can be implemented in a variety of ways

and degrees of sophistication. Different improvements and designs from this basic SS

algorithm are given in Glover (1998), Glover et al. (1999, 2000), Laguna (2000) and

Laguna and Armentano (2001).

3 PATH RELINKING

One of the main goals in any search method is to create a balance between search inten-

sification and search diversification. Path relinking has been suggested as an approach

to integrate intensification and diversification strategies (Glover and Laguna, 1997).

Features that have been added to Scatter Search, by extension of its basic philosophy,

are also captured in the Path Relinking framework. This approach generates new solu-

tions by exploring trajectories that connect high-quality solutions—by starting from

one of these solutions, called an initiating solution

and generating a path in the neigh-

borhood space that leads toward the other solutions, called guiding solutions. This

is accomplished by selecting moves that introduce attributes contained in the guiding

solutions.

The approach may be viewed as an extreme (highly focused) instance of a strategy

that seeks to incorporate attributes of high quality solutions, by creating inducements to

favor these attributes in the moves selected. However, instead of using an inducement

that merely encourages the inclusion of such attributes, the path relinking approach

subordinates other considerations to the goal of choosing moves that introduce the

attributes of the guiding solutions, in order to create a “good attribute composition” in

the current solution. The composition at each step is determined by choosing the best

move, using customary choice criteria, from a restricted set—the set of those moves

currently available that incorporate a maximum number (or a maximum weighted value)

of the attributes of the guiding solutions.

The approach is called path relinking either by virtue of generating a new path

between solutions previously linked by a series of moves executed during a search, or

by generating a path between solutions previously linked to other solutions but not to

each other. Figure 1.2 shows two hypothetical paths (i.e., a sequence of moves) that link

solution A to solution B, to illustrate relinking of the first type. The solid line indicates

an original path produced by the “normal” operation of a procedure that produced a

series of moves leading from A to B, while the dashed line depicts the relinking path.

The paths are different because the move selection during the normal operation does not

“know” where solution B lies until it is finally reached, but simply follows a trajectory

whose intermediate steps are determined by some form of evaluation function. For

example, a commonly used approach is to select a move that minimizes (or maximizes)

the objective function value in the local sense. During path relinking, however, the main

goal is to incorporate attributes of the guiding solution (or solutions) while at the same

time recording the objective function values.

The effort to represent the process in a simple diagram such as the one preceding

creates some misleading impressions, however. First, the original (solid line) path,

F. Glover et al.

whch is shown to be “greedy” relative to the objective function, is likely to be signif-

icantly more circuitous along dimensions we are not able to show, and by the same

token to involve significantly more steps (intervening solutions)—an aspect not por-

trayed in Figure 1.2. Second, because the relinked path is not governed so strongly by

local attraction, but instead is influenced by the criterion of incorporating attributes of

the guiding solution, it opens the possibility of reaching improved solutions that would

not be found by a “locally myopic” search. Figure 1.2 shows one such solution (the

darkened node) reached by the dotted path. Beyond this, however, the relinked path

may encounter solutions that may not be better than the initiating or guiding solution,

but that provide fertile “points of access” for reaching other, somewhat better, solu-

tions. For this reason it is valuable to examine neighboring solutions along a relinked

path, and keep track of those of high quality which may provide a starting point for

continued search.

The incorporation of attributes from elite parents in partially or fully constructed

solutions was foreshadowed by another aspect of scatter search, embodied in an accom-

panying proposal to assign preferred values to subsets of consistent and strongly

determined variables. The theme is to isolate assignments that frequently or influ-

entially occur in high quality solutions, and then to introduce compatible subsets of

these assignments into other solutions that are generated or amended by heuristic pro-

cedures. (Such a process implicitly relies on a form of frequency-based memory to

identify and exploit variables that qualify as consistent.)

Multiparent path generation possibilities emerge in path relinking by considering

the combined attributes provided by a set of guiding solutions, where these attributes

are weighted to determine which moves are given higher priority. The generation of

such paths in neighborhood space characteristically “relinks” previous points in ways

not achieved in the previous search history, hence giving the approach its name. This

multiparent Path relinking approach generates new elements by a process that emulates

the strategies of the original Scatter Search approach at a higher level of generalization.

The reference to neighborhood spaces makes it possible to preserve desirable solution

properties (such as complex feasibility conditions in scheduling and routing), without

Scatter Search and Path Relinking

requiring artificial mechanisms to recover these properties in situations where they may

otherwise become lost.

The PR approach benefits from a tunneling strategy that often encourages a differ-

ent neighborhood structure to be used than in the standard search phase. For example,

moves for Path relinking may be periodically allowed that normally would be excluded

due to creating infeasibility. Such a practice is protected against the possibility of

becoming “lost” in an infeasible region, since feasibility evidently must be recovered

by the time the guiding solution is reached.

A natural variation of path relinking occurs by using constructive neighborhoods

for creating offspring from a collection of parent solutions. In this case the guiding

solutions consist of subsets of elite solutions, as before, but the initiating solution

begins as a partial (incomplete) solution or even as a null solution, where some of the

components of the solutions, such as subsets of free variables, are not yet assigned.

The use of a constructive neighborhood permits such an initiating solution to “move

toward” the guiding solutions, by a neighborhood path that progressively introduces

elements contained in the guiding solutions, or that are evaluated as attractive based

on the composition of the guiding solutions.

4 SS/PR VIGNETTES

This section provides a collection of “vignettes” that briefly summarize applications

of SS and PR in a variety of settings. These vignettes are edited versions of reports

by researchers and practitioners who are responsible for the applications. A debt of

gratitude is owed to the individuals whose contributions have made this summary

possible.

4.1

The Linear Ordering Problem

Given a matrix of weights the linear ordering problem (LOP) consists

of finding a permutation p of the columns (and rows) in order to maximize the sum of

the weights in the upper triangle. In mathematical terms, we seek to maximize:

where p(i) is the index of the column (and row) in position i in the permutation. In

the LOP, the permutation p provides the ordering of both the columns and the rows.

The equivalent problem in graphs consists of finding, in a complete weighted graph,

an acyclic tournament with a maximal sum of arc weights. In economics, the LOP

is equivalent to the so-called triangulation problem for input-output tables (Reinelt,

1985).

Campos et al. (1999) propose a solution method for the linear ordering problem

based on the scatter search template in Glover (1998). The procedure combines the

following elements:

(a)

(b)

Diversification Generator

Improvement Method

剩余569页未读，继续阅读

fireq525

粉丝: 0
资源: 4

Metaheuristics：启发式算法的综合指南

Metaheuristics-A New Class of Algorithms

Handbook of Metaheuristics（第2版）

Metaheuristics

Handbook.of.Approximation.Algorithms.and.Metaheuristics

Handbook of Combinatorial Optimization.pdf

Handbook of graph theory, combinatorial optimization, and algorithms

Spring Boot Starter-kit：含多种技术应用，如数据库、认证机制，有应用结构.zip

包含 Spring Boot 等系列技术参考指南中文版及相关资源的仓库.zip

Unity3d 3D模型描边代码 懒人直接上代码

java毕业设计-基于SSM的超市管理系统【代码+部署教程】

最新资源

Unity3d 3D模型描边代码懒人直接上代码