元启发式算法在组合优化问题中的应用与性能分析

需积分: 37 9 浏览量更新于2024-07-09 收藏 288KB PDF 举报

"组合优化问题的元启发式算法——Mutsunori Yagiura和Toshihide Ibaraki的学术论文" 元启发式算法是解决组合优化问题的一种实用且广泛采用的方法。这类问题包括但不限于旅行商问题、车辆路径问题、网络设计问题等，它们通常具有大量的可能解和复杂的约束条件，使得传统精确算法难以找到全局最优解。元启发式算法通过在搜索空间中探索和学习，寻找接近最优或满意的解决方案。元启发式算法的代表包括遗传算法、模拟退火、禁忌搜索等。这些算法都基于一定的通用框架，如局部搜索框架，其中遗传算法利用种群进化和遗传操作（选择、交叉和变异）来探索解空间；模拟退火则借鉴了固体冷却过程中能量状态变化的物理过程，允许在某些情况下接受劣质解以避免过早收敛；禁忌搜索通过记忆最近的搜索历史，避免陷入局部最优。论文中，作者对这些元启发式算法进行了简化的实现，并进行了数值实验，以观察它们的一般性能趋势。实验结果有助于理解算法的行为并提出使用元启发式算法作为简单优化工具的建议。例如，调整参数如温度下降率（模拟退火）、禁忌长度（禁忌搜索）等，可以影响算法的效率和解决方案质量。此外，论文还探讨了一些先进的技术，用于增强元启发式算法的能力，如适应度函数的设计、多样性的保持策略以及局部搜索策略的改进。这些技术旨在提升算法的全局探索能力和局部搜索能力，使其在复杂优化问题中表现更优。最后，作者总结了关于元启发式算法的一些理论成果，包括算法的收敛性、性能保证等方面，这对于理解和设计新的元启发式算法至关重要。关键词涵盖了组合优化问题、近似算法以及元启发式方法的理论和应用。这篇论文对元启发式算法的研究者和实践者来说是一份宝贵的参考资料，它不仅提供了对基本算法的理解，还分享了如何有效应用和改进这些算法以解决实际中的组合优化挑战。

the series of papers by Johnson and colleagues [86]. See

Refs. 1 and 3 for more details of SA.

2.6. Tabu search

TS tries to enhance LS by using the memory of the

previous search. Basically the best solution in N(x)\({x} 

T) is chosen as the next solution, where the set T, called tabu

list (or short-term memory), is a set of solutions which

includes those solutions most recently visited. Within this

restricted neighborhood, a move to a new solution is always

executed even if the current solution is already locally

optimal. In this process, cycling of a short period can be

avoided as a result of introducing T. Another type of mem-

ory, called long-term memory, is often employed in the

framework of TS, which memorizes the past search infor-

mation such as the frequency that each decision variable has

been changed, the length of the term that each decision

variable takes a certain value, and so on. This memory is

used to direct the search to the unvisited region (i.e., diver-

sification).

TS was proposed by Glover [54, 55]. See Refs. 59,

6264, and 75 for details of TS.

3. General Framework of Metaheuristics

In this section, we explain essential ideas used in

metaheuristic algorithms within a generalized framework

of local search. In this paper, we regard a metaheuristic

algorithm as a method of repeating the following two basic

steps.

I. Generate initial solutions x.

II. Improve x by using (generalized) LS.

A basic framework of LS of Step II was already given

in Section 2.2. Here we define LS in the following more

general framework.

LS: Start from the given initial solution x, and repeat

replacing x with the solution in its neighborhood N(x) (i.e.,

a move) determined by a specified move strategy, until

some stopping criterion is satisfied.

We call the basic LS explained in Section 2.2 simple

LS if we want to distinguish it from more general LS. To

implement algorithm LS, therefore, we must specify:

A. the neighborhood N(x),

B. the evaluation function f of solutions,

C. the move strategy, and

D. the stopping criterion.

Rule A specifies how to generate candidate solutions from

the current solution. Rule B specifies the goodness criterion

for the solutions in the neighborhood. Rule C specifies the

order of solutions to be searched in the neighborhood, and

the rule to choose the next solution. Rule D specifies when

algorithm LS terminates. For example, in the simple LS, the

rule for C is to set x := xc if fxc  fx holds, and the rule

for D is to stop if x is locally optimal (i.e., f xc t f

 for

all xc  N(x)).

Then most ideas of metaheuristics are considered as

the contrivance on the above constituents I, II-A, II-B, II-C,

and II-D. According to this observation, we will explain

various metaheuristic ideas in the following subsections.

Note that ideas in II-A (the neighborhood) will be explained

separately in Section 5, as they are usually rather compli-

cated.

3.1. I: Initial solutions

One of the simplest ways of generating initial solu-

tions is to use random solutions. This results in the random

MLS as already explained in Section 2.3. However, it is

expected that the solution quality will be improved if the

search is started from better solutions. The following ideas

are mainly based on such consideration.

GRASP uses the initial solutions which are generated

by randomized greedy method. In the greedy method, a

feasible solution is usually constructed step by step by

choosing the element with the best local evaluation. Al-

though better initial solutions than random ones are usually

obtained, the variety of solutions constructed by this

method is quite limited, which is not desirable in the frame-

work of MLS. To overcome this, in GRASP, a feasible

solution is constructed, in each step, by randomly choosing

an element from the candidate list composed of those

elements having good evaluations.

GRASP was proposed by Feo and colleagues [e.g.,

44, 47], and applied to various combinatorial. optimization

problems by themselves and others [e.g., 43, 46, 97, 99,

137]. See Ref. 45 for details. The basic idea of randomized

greedy method has appeared in early papers such as Ref.

74, though LS was not incorporated.

In ILS, the initial solutions are generated by slightly

perturbing a good solution x

seed

found during the past

search. The initial solutions are usually generated by ran-

domly choosing a solution in the neighborhood Nc(x

seed

where a different neighborhood from N of LS is often used.

ILS was proposed by Johnson [85]. While the incumbent

solution (i.e., the best feasible solution found so far) is used

as x

seed

in the basic ILS of Ref. 85, there are variants of ILS,

called chained local optimization or large-step Markov

chain, in which x

seed

is chosen randomly according to a rule

similar to SA [104, 108110]. (Historically the preprints of

Martin and colleagues [109] inspired Johnson to propose

ILS, a simplified variant of the MartinOttoFelten algo-

rithm, as described in p. 292 of Ref. 87.)

剩余22页未读，继续阅读

weixin_38746918

粉丝: 7
资源: 900

元启发式算法在组合优化问题中的应用与性能分析

超启发式算法介绍大全

生产排程之启发式算法

数学建模启发式算法

旅行商问题用启发式算法与最优化算法

启发式算法货物配送路线优化问题Matlab

元启发式算法适用范围大全

如何使用元启发式算法解决背包客问题

花朵授粉算法组合了哪些启发式算法

贝叶斯优化算法是属于精确算法，还是属于启发式算法，还是两个都不属于？

启发式算法解决tsp

最新资源