matlab&一维离散数据的极值及极值位置的计算-原创
******************对一维数组求局部极大值或局部极小值*******************
获得一维离散数据y的局部极大值：extrMaxValue =
y(find(diff(sign(diff(y)))==-2)+1);
获得一维离散数据y的局部极大值的位置：extrMaxIndex =
find(diff(sign(diff(y)))==-2)+1;
获得一维离散数据y的局部极小值：extrMaxValue =
y(find(diff(sign(diff(y)))==+2)+1);
获得一维离散数据y的局部极小值的位置：extrMaxIndex =
find(diff(sign(diff(y)))==+2)+1;
举例说明：y= [1 2 3 4 5 6 7 8 1] diff(y)= 1 1 1 1 1 1 1 -7
%说明：用后面一个数减去前面一个数。
sign(diff(y))=1 1 1 1 1 1 1 -1 %说明：返回正负数的判断逻辑值值，正的为1，负的为-1 。
diff(sign(diff(y)))=0 0 0 0 0 0 -2
find(diff(sign(diff(y)))==-2)+1
%说明：find（diff==-2）的位置+1才对应局部极大值的位置
y(find(diff(sign(diff(y)))==-2)+1)： 返回局部极大值。 同理：y= [1 2 3 4 5 6 7
9 4]------15个数 1 1 1 1 1 1 1 -7 1 1 -2
4 4 -5 ------14个数 1 1 1 1 1 1 1 -1 1 1 -1 1 1 -1 ------14个数 0 0 0 0
-2 ------13个数 extrMaxValue = 8 3
9extrMaxIndex = 8 11 14 总体就是类似于找拐点（数学）--头尾均不考虑在内。
方法二：matlab2009以上有一个函数fingpeaks，可以对一维数组直接求解局部极大值：
举例说明：
y= [1 2 3 4 5 6 7& 8 1 2& 3 1
x=findpeaks(y);则x =8&3&9
******************对二维矩阵求局部极大值或局部极小值*******************
matlab自带函数imregionalmax和imregionalmin。格式：imregionalmax(A,n)
说明：A可以使2D数据或3D数据，n为求局部极值所采用的方法，默认2D时n=8（八邻域法）；3D时n=26.2D时，n=4/8；3D时，n=6/18/26
返回值：一个二值逻辑矩阵，结构与A相同（1：表示局部极大值；0表示：非局部极大值）。
举例说明：某10*10矩阵
&四邻域求局部极大值：A1=imregionalmax(A,4)；得到A1
八邻域秋局部极大值：A1=imregionalmax(A)；得到的结果与上面的结果略有差别。
利用matalab的点乘命令：A2=A1.*A，得到与原始矩阵A相对应的局部极大值矩阵。
&&&&&0&&&&
0&&&&&0&&&&
*****************矩阵最大值的求解************************
B=zeros(size(A));
idx=find(A==max(max(A)));
for k=1:size(idx,1);
[i,j]=ind2sub(size(A),idx(k));
&& B(i,j)= A(i,j);
&&&&&45&&&
9&&&&&45&&&
得到原矩阵A对应的最大值矩阵：
&&&&&45&&&
0&&&&&45&&&
如果不需要算最大值的位置，直接用max(max(A))或者max(A(:))，都可以求出矩阵A的最大值。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。最近看到一个有意思的求数组局部极小值，极大值的代码，贴出来分享一下，源代码是matlab版的，我用我的较为暴力的诸多for循环将其修改为C++版的，不得不感叹matlab在矩阵运算上确实是很方便的！
&局部极大值和极小值都能够求得，以代码中&Arr[NUM] = { 1.31,2.52, 2.52, 6.84, 5.48, 2.10, 6.77, 6.77, 1.22, 1.35,9.02 }为例，可以得到局部极大值三个，6.84, 6.77,9.02. 局部极小值三个：1.31,2.10,1.22. &
如有错误，请指出，谢谢！
Matlab版，源版
Gets the global extrema points from a time series.
[XMAX,IMAX,XMIN,IMIN] = EXTREMA(X) returns the global minima and maxima
points of the vector X ignoring NaN's, where
XMAX - maxima points in descending order
IMAX - indexes of the XMAX
XMIN - minima points in descending order
IMIN - indexes of the XMIN
DEFINITION (from http://en.wikipedia.org/wiki/Maxima_and_minima):
In mathematics, maxima and minima, also known as extrema, are points in
the domain of a function at which the function takes a largest value
(maximum) or smallest value (minimum), either within a given
neighbourhood (local extrema) or on the function domain in its entirety
(global extrema).
x = <span style="color: #*pi*linspace(-<span style="color: #,<span style="color: #);
y = cos(x) - <span style="color: #.5 + <span style="color: #.5*rand(size(x)); y(<span style="color: #:<span style="color: #) = <span style="color: #.85; y(<span style="color: #:<span style="color: #)=NaN;
[ymax,imax,ymin,imin] = extrema(y);
plot(x,y,x(imax),ymax,'g.',x(imin),ymin,'r.')
See also EXTREMA2, MAX, MIN
Written by
Lic. on Physics Carlos Adri醤 Vargas Aguilera
Physical Oceanography MS candidate
UNIVERSIDAD DE GUADALAJARA
Mexico, <span style="color: #04
: http:///matlabcentral/fileexchange
: <span style="color: #275
% Submited at: <span style="color: #06-<span style="color: #-<span style="color: #
% <span style="color: #06-<span style="color: #-<span style="color: # : English translation from spanish.
% <span style="color: #06-<span style="color: #-<span style="color: # : Accept NaN's.
% <span style="color: #07-<span style="color: #-<span style="color: # : Change name to MAXIMA, and definition added.
%**********尊重原创，以上是代码具体来源*****************
x=[<span style="color: #.31, <span style="color: #.52, <span style="color: #.52, <span style="color: #.84, <span style="color: #.48, <span style="color: #.10, <span style="color: #.77, <span style="color: #.77, <span style="color: #.22, <span style="color: #.35];
xmax = [];
imax = [];
xmin = [];
imin = [];
% Vector input?
Nt = numel(x);
if Nt ~= length(x)
error('Entry must be a vector.')
inan = find(isnan(x));
indx = <span style="color: #:Nt;
if ~isempty(inan)
indx(inan) = [];
x(inan) = [];
Nt = length(x);
% Difference between subsequent elements:
dx = diff(x);
% Is an horizontal line?
if ~any(dx)
% Flat peaks? Put the middle element:
a = find(dx~=<span style="color: #);
% Indexes where x changes
lm = find(diff(a)~=<span style="color: #) + <span style="color: #;
% Indexes where a do not changes
d = a(lm) - a(lm-<span style="color: #);
% Number of elements in the flat peak
a(lm) = a(lm) - floor(d/<span style="color: #);
% Save middle elements
a(end+<span style="color: #) = Nt;
% Serie without flat peaks
b = (diff(xa) & <span style="color: #);
% <span style="color: #
positive slopes (minima begin)
% <span style="color: #
negative slopes (maxima begin)
= diff(b);
% -<span style="color: # =&
maxima indexes (but one)
% +<span style="color: # =&
minima indexes (but one)
imax = find(xb == -<span style="color: #) + <span style="color: #; % maxima indexes
imin = find(xb == +<span style="color: #) + <span style="color: #; % minima indexes
imax = a(imax);
imin = a(imin);
nmaxi = length(imax);
nmini = length(imin);
% Maximum or minumim on a flat peak at the ends?
if (nmaxi==<span style="color: #) && (nmini==<span style="color: #)
if x(<span style="color: #) & x(Nt)
xmax = x(<span style="color: #);
imax = indx(<span style="color: #);
xmin = x(Nt);
imin = indx(Nt);
elseif x(<span style="color: #) & x(Nt)
xmax = x(Nt);
imax = indx(Nt);
xmin = x(<span style="color: #);
imin = indx(<span style="color: #);
% Maximum or minumim at the ends?
if (nmaxi==<span style="color: #)
imax(<span style="color: #:<span style="color: #) = [<span style="color: # Nt];
elseif (nmini==<span style="color: #)
imin(<span style="color: #:<span style="color: #) = [<span style="color: # Nt];
if imax(<span style="color: #) & imin(<span style="color: #)
imin(<span style="color: #:nmini+<span style="color: #) =
imin(<span style="color: #) = <span style="color: #;
imax(<span style="color: #:nmaxi+<span style="color: #) =
imax(<span style="color: #) = <span style="color: #;
if imax(end) & imin(end)
imin(end+<span style="color: #) = Nt;
imax(end+<span style="color: #) = Nt;
xmax = x(imax);
xmin = x(imin);
if ~isempty(inan)
imax = indx(imax);
imin = indx(imin);
% Same size as x:
imax = reshape(imax,size(xmax));
imin = reshape(imin,size(xmin));
% Descending order:
[temp,inmax] = sort(-xmax);
clear temp
xmax = xmax(inmax);
imax = imax(inmax);
[xmin,inmin] = sort(xmin);
imin = imin(inmin);
C++版，较挫，for循环多，但是也能用
#include &iostream&
#include &vector&
using namespace
#define NUM 11
void main()
float Arr[NUM] = { <span style="color: #.31,<span style="color: #.52, <span style="color: #.52, <span style="color: #.84, <span style="color: #.48, <span style="color: #.10, <span style="color: #.77, <span style="color: #.77, <span style="color: #.22, <span style="color: #.35,<span style="color: #.02 };
int num = NUM;
float diff[NUM-<span style="color: #];
vector &int& indexA, indexLm;
//Difference between subsequent elements
int n = <span style="color: #;
for (int i = <span style="color: #; i & NUM - <span style="color: #; i++)
diff[i] = Arr[i + <span style="color: #] - Arr[i];
if (diff[i] != <span style="color: #)
indexA.push_back(i);
//元素发生变化
// Flat peaks? Put the middle element
vector &int& diffIndexA;
for (int i = <span style="color: #; i & indexA.size()-<span style="color: #; i++)
int tmpdiff = indexA.at(i + <span style="color: #) - indexA.at(i);
if (tmpdiff != <span style="color: #)
indexLm.push_back(i + <span style="color: #);
vector &int&
for (int i = <span style="color: #; i & indexLm.size(); i++)
int index = indexLm.at(i);
int tmp = indexA.at(index)-indexA.at(index-<span style="color: #);
d.push_back(tmp);
for (int i = <span style="color: #; i & d.size(); i++)
int lmValue = indexLm.at(i);
int dvalue = d.at(i) / <span style="color: #;
int tmp = indexA.at(lmValue) -
indexA.at(lmValue) =
indexA.push_back(num-<span style="color: #);
vector &float& ArrIndexA;
//Seris without flat peaks
for (int i = <span style="color: #; i & indexA.size(); i++)
int tmpIndex = indexA.at(i);
float value = Arr[tmpIndex];
ArrIndexA.push_back(value);
vector &int& indexB;
for (int i = <span style="color: #; i & ArrIndexA.size()-<span style="color: #; i++)
float diff = ArrIndexA.at(i + <span style="color: #) - ArrIndexA.at(i);
if (diff&<span style="color: #)
indexB.push_back(<span style="color: #);
//<span style="color: #
positive slopes (minima begin)
else indexB.push_back(<span style="color: #);
//<span style="color: # negative slopes(maxima begin)
vector &int&
for (int i = <span style="color: #; i & indexB.size()-<span style="color: #; i++)
int diff = indexB.at(i + <span style="color: #) - indexB.at(i);
xb.push_back(diff);
//-1 0 minima indexes
vector &int& imax, imin, max, // minima indexes
for (int i = <span style="color: #; i & xb.size(); i++)
if (xb.at(i) == -<span style="color: #)
imax.push_back(i + <span style="color: #);
if (xb.at(i) == <span style="color: #)
imin.push_back(i + <span style="color: #);
for (int i = <span style="color: #; i & imax.size(); i++)
int index = imax.at(i);
int value = indexA.at(index);
max.push_back(value);
for (int i = <span style="color: #; i & imin.size(); i++)
int index = imin.at(i);
int value = indexA.at(index);
min.push_back(value);
int nmax = max.size();
int nmin = min.size();
//Maximum or minumin on a flat peak at the ends?
vector &float& xmin,
if (nmax == <span style="color: # && nmin == <span style="color: #)
if (Arr[<span style="color: #]&Arr[num - <span style="color: #])
xmax.push_back(Arr[<span style="color: #]);
max.push_back(<span style="color: #);
xmin.push_back(Arr[num - <span style="color: #]);
min.push_back(num - <span style="color: #);
else if (Arr[<span style="color: #] & Arr[num - <span style="color: #])
xmax.push_back(Arr[num - <span style="color: #]);
max.push_back(num - <span style="color: #);
xmin.push_back(Arr[<span style="color: #]);
min.push_back(<span style="color: #);
//Maximum or minumin at the ends?
if (<span style="color: # == nmax)
max.push_back(<span style="color: #);
max.push_back(num - <span style="color: #);
else if (<span style="color: # == nmin)
min.push_back(<span style="color: #);
min.push_back(num - <span style="color: #);
if (max.at(<span style="color: #) & min.at(<span style="color: #))
vector &int&
tmp.swap(min);
min.push_back(<span style="color: #);
for (int i = <span style="color: #; i & i++)
min.push_back(tmp[i]);
vector &int&
tmp.swap(max);
max.push_back(<span style="color: #);
for (int i = <span style="color: #; i & i++)
max.push_back(tmp[i]);
if (max.back()&min.back())
min.push_back(num - <span style="color: #);
max.push_back(num - <span style="color: #);
for (int i = <span style="color: #; i & max.size(); i++)
int index = max[i];
float value = Arr[index];
xmax.push_back(value);
for (int j = <span style="color: #; j & min.size(); j++)
int index = min[j];
float value = Arr[index];
xmin.push_back(value);
//Descending Order,
bubble sort
for (int j = <span style="color: #; j & xmax.size()-<span style="color: #; j++)
for (int i = <span style="color: #; i & xmax.size() - j -<span style="color: #; i++)
if (xmax[i] & xmax[i + <span style="color: #])
tmp = xmax[i];
xmax[i] = xmax[i + <span style="color: #];
xmax[i + <span style="color: #] =
system("pause");
阅读(...) 评论()为了避免小生境遗传算法存在的早期成熟和陷入局部极值点等问题，提出了一种改进的小生境遗传算法。
In order to avoid premature convergence and occurance of minimal deceptive problems, an improved niche genetic algorithm (NGA) is presented.
所提出的算法将粒子群优化算法和混沌算法相结合，既摆脱了算法搜索后期易陷入局部极值点的缺点，同时又保持了前期搜索的快速性。
It can not only overcome the disadvantage of easily getting into the local extremum in the later evolution period, but also keep the rapidity of the previous period.
为了避免神经网络的学习过程陷入局部极值点，采用人工免疫网络优化神经网络的参数。
In order to prevent neural network learning from getting into local extreme point, artificial immune network algorithm was used to optimize neural network′s parameters.
针对基本粒子群算法在处理高维复杂问题时易陷入局部极值点的不足，提出自适应随机惯性权的粒子群优化算法，并基于此算法建立起洪水过程的放大模型。
Aiming at the deficiency of the traditional particle swarm optimization, the new zoom model calculated by particle swarm optimization based on adaptive random inertia weight is put forward.
在聚类分析中，模糊k均值算法是目前应用最为广泛的方法之一，然而该算法对初始化敏感，容易陷入局部极值点。
In cluster analysis, Fuzzy K-Means (FKM) algorithm is one of the most widely used methods. However, FKM algorithm is much more sensitive to the initialization, and easy to fall into local optimum.
针对粒子群算法用于高维数、多局部极值点的复杂函数寻优时易陷入局部最优解现象，提出一种改进的带扰动项粒子群算法并进行收敛性分析。
Traditional particle swarm optimization(PSO) algorithms often trap into local minima easily when used for the optimization of high-dimensional complex functions with a lot of local minima.
实验表明，模糊互信息函数比互信息函数具有更少的局部极值点和更好的优化特性。
Experiment results show that similarity measure based on fuzzy mutual information has less local extremums and better optimization character.
该方法通过在遥感图像上选取局部极值点来构成平面散乱数据点集，并在此基础上进行三角剖分、优化和三角插值曲面构造。
It gets the plane scattered data points through selecting the local extremum points on the remote image, and then triangulates, constructs the triangular interpolating surface on it.
最大膛压点的确定是内弹道零维模型求解的一个重要环节，传统的优选方法存在着可能陷入局部极值点的问题。
Determination of the bore maxi-pressure point is an important link in solution of internal ballistics zero dimension model. Traditional optimizing methods probably have some problems of local pole.
函数测试表明，改进后的算法使收敛速度显著加快，而且不易陷入局部极值点。
From experimental results it can be concluded that using a dynamic inertia weight makes the rapidity of convergence accelerate and is not easy to trap in the local extreme points.
固定点算法在没有足够多样本的情况下容易收敛到局部极值点，而遗传算法因过于复杂，在运算时间上有一定的劣势。
Fixed-point algorithm is easy to converge to a local extremum points if it does not have enough variety, and the genetic algorithm has a disadvantage in the computation time because of its complexity.
该算法基本保持了粒子群优化算法简单容易实现的特点，但改善了粒子群优化算法摆脱局部极值点的能力，提高了算法的收敛速度和精度。
The proposed algorithm is almost as simple for implement as particle swarm optimizer, but can improve the abilities of seeking the global excellent result and evolution speed.
方法依据视觉心理学的理论，提取人的视觉系统对之敏感的纹理信息，如纹理的全局灰度极值点，局部灰度极值点，基元的边缘等特征。
It reflects the psychophysical evidence that the human visual system is sensitive to global and local gray level extremums and edge information.
这种方法通过寻找局部极值快速确定噪声点，并对图像的所有像素做分类标记，处理的过程中只考虑标记为噪声的点，采用邻域内非噪声点的均值作为滤波输出。
Using this method, the noisy point is determined quickly by looking for the local extremum and the classified markers are made for all pixels of the image.
针对粒子群优化算法（PSO）应用于多极值点函数易陷入局部极小值，提出旋转曲面变换（RST）方法。
Aimed at particle swarm optimization (PSO) algorithm being easily trapped into local minima value in multimodal function, a rotating surface transformation (RST) method was proposed.
这种方法只需在求局部极值算法程序中加入一个初值点选择模块就可获得总极值点求解程序。
The program for searching global minimum point can be made by adding an initial iteration point selection module to the program of searching local minimum point.
粒子群优化算法应用于多极值点函数优化时，存在陷入局部极小点和搜寻效率低的问题。
Particle Swarm Optimization(PSO) algorithm is a population-based global optimization algorithm, but it is easy to be trapped into local minima in optimizing multimodal function.
当解逼近当前极小点的后，动态方程又能使解逃逸局部极值，使其具有全局寻优能力。
At the same time it can make the solution escape local extreme value and cause the overall optimization capacity when the solution approximates the minimum point.
但是当变换后像素坐标位于非采样网格点时，插值算法有时会使目标函数产生局部极值，使得最优化搜索终止于局部极值，得到错误的配准结果。
However, the object function suffers from the local extremum induced by interpolation, which obstructs optimization algorithms and leads to the wrong result of registration.
文章讨论了管道最深点蚀孔深度的统计规律以及局部腐蚀深度最大极值估计值的确定方法，并给出了实际算例。
This paper discusses the statistical rule of maximum corrosive pit depth and determination method of extremum estimation for local corrosion depth, and presents a practical example of calculation.
利用局部窗口极值的快速搜索算法提取出不同尺度空间的特征点，提高了匹配的实时性；
A multi-scale feature extraction algorithm, which computes the maximum of the features in moving windows, is used to improve the real-time performance.
对于特征点较少的曲线，根据曲率极值点将曲线划分为多条曲线段，采用局部线性搜索法实现曲线的部分匹配。
For curves with few feature points, we divide each curve into several curve segments according to curvature maxima and make use of a local linear search algorithm find the partial matches.
对于特征点较少的曲线，根据曲率极值点将曲线划分为多条曲线段，采用局部线性搜索法实现曲线的部分匹配。
For curves with few feature points, we divide them into small curve segments according to curvature maxima and make use of a local line search method to find the matches.
对于特征点较少的曲线，根据曲率极值点将曲线划分为多条曲线段，采用局部线性搜索法实现曲线的部分匹配。
For curves with few feature points, we divide them into small curve segments according to curvature maxima and make use of a local line search method to find the matches.
$firstVoiceSent
- 来自原声例句
请问您想要如何调整此模块？
感谢您的反馈，我们会尽快进行适当修改！
请问您想要如何调整此模块？
感谢您的反馈，我们会尽快进行适当修改！局部搜索算法 - JiePro - 博客园
Blog Stats
Posts - 10
Stories - 0
Comments - 8
Trackbacks - 0
1、数学定义
2、过程描述
3、算法简介
1、数学定义
　　局部搜索是解决最优化问题的一种启发式算法。对于某些计算起来非常复杂的最优化问题，比如各种NP完全问题，要找到最优解需要的时间随问题规模呈指数增长，因此诞生了各种启发式算法来退而求其次寻找次优解，是一种近似算法（Approximate algorithms），以时间换精度的思想。局部搜索就是其中的一种方法。
　　对于组合问题，给出如下定义：
其中，S为搜索空间（解空间），其中的每一元素都是问题一个可能解。解决组合问题，即是找到一个s* & S，使得目标函数f值最小。s*称为全局最优解。
　　对于邻域动作定义如下：
邻域动作是一个函数，通过这个函数，对当前解s，产生其相应的邻居解集合。例如：对于一个bool型问题，其当前解为：s = 1001，当将邻域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)={11,1000}，其中N(s)&& S。同理，当将邻域动作定义为互换相邻bit时，得到的邻居解的集合N(s)={10}.
2、过程描述
　　局部搜索算法从一个初始解开始，通过邻域动作，产生其邻居解，判断邻居解的质量，根据某种策略，来选择邻居解，重复上述过程，至到达终止条件。不同局部搜索算法的区别就在于：邻域动作的定义和选择邻居解的策略，也是决定算法好坏的关键（集中性和发散性，Intensification and Diversification）。
3、算法简介
　　对于优化问题相关算法有如下分类：
　　下文分别简单介绍几个局部搜索相关算法，也是基于个体的启发式算法（Single solution）。
3.1 爬山法（Hill-climbing）
　　爬山法与Iterative Improvement的思想是一样的，区别在于前者寻找最大值，后者寻找最小值。一种完全的贪心的思想，有更好的，则选择更好的，没有更好的，则终止。
　　流程如上图所示，判断当前解s的邻居解质量，若其中有比当前解更好的解，则s = Improve(N(S))，令当前解等于邻居解中质量最好的解，重复上述过程，直至邻居解中没有更好的解为止。
　　缺点：很容易陷入局部极值，最终解的好坏与初始解的选择有很大关系。
3.2 模拟退火（Simulated annealing）
&　　为了防止陷入局部最优，模拟退火算法以一定概率接受比当前解差的解，接受差解的概率随着迭代次数的增加而下降，或者说是随着温度T的下降而下降。先看流程图，如下：
&　　该算法从一个初始解开始，这个初始解可以是随机选择的，也可以是启发式方式得到的，并初始化一个温度。在每次迭代过程中，从当前解的邻居解中随机的选择一个解，若随机选择的一个邻居解比当前解的质量好，则替换当前解，若质量比当前解差，则以一定的概率接受这个差解，来替换当前解。最后更新温度T，进行下一次迭代。
接受差解的概率是一个关于 T 和 (f(s') - f(s)) 的函数。函数形式为：p(T,s',s) = exp(- (&f(s') - f(s)&) / T)
温度T随着搜索的过程而减小，由上述表达式可知，随着T减小（对于最小值问题，解的质量最好，f(x)的值越小），接受差解的概率越小，因此模拟退火算法将慢慢收敛于一个 simple iterative improvement algorithm。
该算法由两个阶段：random walk and iterative improvement，这两者体现了启发式算法核心思想：Diversification&and Intensification，前者提供了一个广阔的搜索空间，后者使其收敛于最小值（或者局部最小值）。
3.3 禁忌搜索（Tabu/Taboo Search, TS）
　　禁忌搜索，顾名思义，禁止某些选项。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免暂时的迂回搜索。
　　举个简单的例子：一日三餐，为了寻找最好的搭配。
当10月1日（初始日）中午随机选了几样东西作为食物，早上：面包，中午：米饭，晚上：面条；
当10月2日（第二次迭代），在众多相近的选择中（邻居解集合），我选择效果最好的，早上：面包，中午：面条，晚上：面条，
2日整体效果比1日好，那么其变化为：中午由 米饭-&面条， &中午：米饭&这个属性被我记住了（禁忌表），在接下来几天（禁忌长度）中，对于邻居解中任何有&中午：米饭&的解，我将不会考虑，除非该解比历史最好的效果都好（解禁条件）。
　　通过上例，引出一下几个概念：
　　禁忌表（tabu list）：记录被禁止的属性，其值为禁忌长度（tabu tenure），该长度范围内，该属性被禁止。
　　解禁条件（aspiration condition）：当含有禁忌属性的解，效果好于历史最好解时，我们选择这个被禁忌的解，其他情况，被禁忌的解不予考虑。
对于禁忌算法，每次一迭代都要更新禁忌表，禁忌表的维护决定了算法的快慢，对于禁忌长度，可以是恒定的长度，也可以是动态的长度。具体的细节，可以参见博文的。
3.4&Explorative Local Search methods&
　　注：此节中，伪代码中提到的 LocalSearch(s) 为简单的局部搜索，上面三种算法的任意一种。c
3.4.1&迭代局部搜索（Iterated Local Search, ILS）
　　在局部搜索得到的局部最优解上，加入了扰动，再重新进行局部搜索。其思想是：物以类聚，好的解之间会有一些共性，所以在局部最优解上做扰动，比随机的选择一个初始解在进行局部搜索，效果更好。
过程描述如下：
其伪代码如下：
对与其中的接受准则：这里采用了模拟退火中的概率函数：
3.4.2&变邻域搜索（Variable Neighborhood Search, VNS）
变邻域搜索算法的主要思想是：采用多个不同的邻域进行系统搜索。首先采用最小的邻域搜索，当无法改进解时，则切换到稍大一点的邻域。如果能继续改进解，则退回到最小的邻域，否则继续切换到更大的邻域。
变邻域搜索的特点是利用不同的动作构成的邻域结构进行交替搜索，在集中性和疏散性之间达到很好的平衡。
其思想可以概括为&变则通&。
过程描述如下：
每变换一次邻域，相对于切换了搜索的地形（landscape）。效果如下：
伪代码如下图：
　　启发式算法蕴含着许多人生哲学，它虽不是数学方法，其思想更类似于人类解决问题的思想和一些人生中总结的道理，值得好好体会。最后用网上一段描述局部搜索的例子来作为总结：
　　为了找出地球上最高的山，一群有志气的兔子们开始想办法。
兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是Iterative Improvement，它不能保证局部最优值就是全局最优值。
兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。
兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。
兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。
参考资料：
Metaheuristicsin Combinatorial Optimization: Overview and Conceptual Comparison
华中科技大学吕志鹏老师：启发式优化课件