穷举搜索::回溯与深搜 && 禁忌搜索算法简介

文章由 算法源码吧(www.sfcode.cn)收集
计算机常用算法大致有两大类,一类叫蛮干算法,一类叫贪心算法,前者常使用的手段就是搜索,对全部解空间进行地毯式搜索,直到找到指定解或最优解。

【建立解空间】
问题的解应该如何描述,如何建立?借助图论的思想,我们可以用图来描述,图的定义为G<V,E>,由顶点集和边集构成,顶点即实实在在的数据、对象,而边可以抽象为关系,即顶点间的关系,这种关系不一定非要在数据结构上表现出来,用数据结构的语言来描述,如果关系是一对一,则为线性表,如果关系是一对多,则为树,如果关系是多对多,则为图,如果完全没有关系,则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来,譬如,你可以用一个数组表示一个线性表,也可以表示完全二叉树,同样也可以用邻接表表示一个图,对于关系的描述不是数据结构本身的描述,而是算法的描述,正如数据结构是离不开特定的算法一样,不可分开单独而谈。描述了解,那如何建立解空间,即如何对图进行搜索?

【深度优先搜索】
(Depth First Search)是用栈的机制对图的顶点进行深度优先的搜索。简易流程如下:

DFS(V0(起始顶点))
访问V0
for(v=V0的第一个子结点 到 最后一个子结点(边所对的顶点))
如果v未被访问,DFS(v);

搜索过程是先往结点深处搜索,一旦有子结点未访问就向下遍历。这样的方法类似回溯算法,先往下试探,如果不行出退回(回溯)。

【回溯】
回溯的经典例子是8皇后问题。
例:在国际象棋地图上(8×8)放上8个皇后,使任意两个皇后都不在同一行或同一列或同一斜行,找出所有解。
每一个皇后的位置可以认为是一个顶点,而皇后之间不在同一行或同一列或同一斜行的性质认为是顶点之间的关系,我们可以用回溯试探的方法考虑:先依次试探每一个皇后的位置,如果有不满足条件的情况则退回,直到完成所有解的计数和输出。

用数组存储:int pos[8];
pos[0]表示第一个皇后的位置(0,1,…7)依次类推。
流程:
dfs(c)//c从0开始
for(v=0;v<8;++v)
如果pos[c]:=v满足条件,dfs(c+1);
退回之后pos[c]:=0;

这跟书上的回溯算法不太一样,因为是采用深搜的方法写的,其实思想是一致的,要仔细体会。

附N皇后C语言代码:
/*p118.4*/
/*N Queen Problem*/
#include<stdio.h>
#define MAX 100
int s[MAX];
int n;
int m1[MAX],m2[MAX],m3[MAX];
long count=0;
void output_solution()
{
int i,j;
printf(“No.%d
“,++count);
for(i=0;i<n;++i)
{
for(j=0;j<s[i];++j)printf(” “);
printf(“Q
“);
}
printf(“—————
“);
}
void dfs(int c)
{
int i;
if(c==n)
{
/*output_solution();*/
++count;
}
else
{
for(i=0;i<n;++i)
{
if(m1[i]==0&&m2[c+i]==0&&m3[n+i-c-1]==0)
{
s[c]=i;
m1[i]=1;
m2[c+i]=1;
m3[n+i-c-1]=1;
dfs(c+1);
m1[i]=0;
m2[c+i]=0;
m3[n+i-c-1]=0;
}
}
}
}
void main()
{
scanf(“%d”,&n);
dfs(0);
printf(“total:%d
“,count);
}

文章由 算法源码吧(www.sfcode.cn)收集
忌搜索(Tabu Search或Taboo Search,简称TS)的思想最早由Glover(1986)提出,它是对局部领域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法,TS是又一种搜索特点不同的 meta-heuristic算法。迄今为止,TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功,近年来又在函数全局优化方面得到较多的研究,并大有发展的趋势。本章将主要介绍禁忌搜索的优化流程、原理、算法收敛理论与实现技术等内容。
1. 引言 局部领域搜索是基于贪婪思想持续地在当前解的领域中进行搜索,虽然算法通用易实现,且容易理解,但其搜索性能完全依赖于领域结构和初解,尤其窥陷入局部极小而无法保证全局优化性。针对局部领域搜索,为了实现全局优化,可尝试的途径有:以可控性概率接受劣解来逃逸局部极小,如模拟退火算法;扩大领域搜索结构,如TSP的2opt扩展到k-opt;多点并行搜索,如进化计算;变结构领域搜索( Mladenovic et al,1997);另外,就是采用TS的禁忌策略尽量避免迂回搜索,它是一种确定性的局部极小突跳策略。
禁忌搜索是人工智能的一种体现,是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止循环),从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到领域(neighborhood)、禁忌表(tabu list)、禁忌长度(tabu 1ength)、候选解(candidate)、藐视准则(candidate)等概念,我们首先用一个示例来理解禁忌搜索及其各重要概念,而后给出算法的一般流程。
2.禁忌搜索示例 组合优化是TS算法应用最多的领域。置换问题,如TSP、调度问题等,是一大批组合优化问题的典型代表,在此用它来解释简单的禁忌搜索算法的思想和操作。对于 n元素的置换问题,其所有排列状态数为n!,当n较大时搜索空间的大小将是天文数字,而禁忌搜索则希望仅通过探索少数解来得到满意的优化解。
首先,我们对置换问题定义一种邻域搜索结构,如互换操作(SWAP),即随机交换两个点的位置,则每个状态的邻域解有Cn2=n(n一1)/2个。称从一个状态转移到其邻域中的另一个状态为一次移动(move),显然每次移动将导致适配值(反比于目标函数值)的变化。其次,我们采用一个存储结构来区分移动的属性,即是否为禁忌“对象”在以下示例中:考虑7元素的置换问题,并用每一状态的相应21个邻域解中最优的5次移动(对应最佳的5个适配值)作为候选解;为一定程度上防止迂回搜索,每个被采纳的移动在禁忌表中将滞留3步(即禁忌长度),即将移动在以下连续3步搜索中将被视为禁忌对象;需要指出的是,由于当前的禁忌对象对应状态的适配值可能很好,因此在算法中设置判断,若禁忌对象对应的适配值优于“ best so far”状态,则无视其禁忌属性而仍采纳其为当前选择,也就是通常所说的藐视准则(或称特赦准则)。
可见,简单的禁忌搜索是在领域搜索的基础上,通过设置禁忌表来禁忌一些已经历的操作,并利用藐视准则来奖励一些优良状态,其中领域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。需要指出的是:
(1)首先,由于TS是局部领域搜索的一种扩充,因此领域结构的设计很关键,它决定了当前解的领域解的产生形式和数目,以及各个解之间的关系。
(2)其次,出于改善算法的优化时间性能的考虑,若领域结构决定了大量的领域解(尤其对大规模问题,如TSP的SWAP操作将产生Cn2个领域解),则可以仅尝试部分互换的结果,而候选解也仅取其中的少量最佳状态。
(3)禁忌长度是一个很重要的关键参数,它决定禁忌对象的任期,其大小直接进而影响整个算法的搜索进程和行为。同时,以上示例中,禁忌表中禁忌对象的替换是采用FIFO方式(不考虑藐视准则的作用),当然也可以采用其他方式,甚至是动态自适应的方式。
(4)藐视准则的设置是算法避免遗失优良状态,激励对优良状态的局部搜索,进而实现全局优化的关键步骤。
(5)对于非禁忌候选状态,算法无视它与当前状态的适配值的优劣关系,仅考虑它们中间的最佳状态为下一步决策,如此可实现对局部极小的突跳(是一种确定性策略)。
(6)为了使算法具有优良的优化性能或时间性能,必须设置一个合理的终止准则来结束整个搜索过程。
此外,在许多场合禁忌对象的被禁次数(frequency)也被用于指导搜索,以取得更大的搜索空间。禁忌次数越高,通常可认为出现循环搜索的概率越大。
3.禁忌搜索算法流程 通过上述示例的介绍,基本上了解了禁忌搜索的机制和步骤。简单TS算法的基本思想是:给定一个当前解(初始解)和一种邻域,然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标值优于“best so far”状态,则忽视其禁忌特性,用其替代当前解和“best so far”状态,并将相应的对象加入禁忌表,同时修改禁忌表中各对象的任期;若不存在上述候选解,则选择在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的优劣,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期;如此重复上述迭代搜索过程,直至满足停止准则。
条理化些,则简单禁忌搜索的算法步骤可描述如下:
(1)给定算法参数,随机产生初始解x,置禁忌表为空。
(2)判断算法终止条件是否满足?若是,则结束算法并输出优化结果;否则,继续以下步骤。
(3)利用当前解工的邻域函数产生其所有(或若干)邻域解,并从中确定若干候选解。
(4)对候选解判断藐视准则是否满足?若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,即x=y,并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“best so far”状态,然后转步骤6;否则,继续以下步骤。
(5)判断候选解对应的各对象的禁忌属性,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。
(6)转步骤(2)。
同时,上述算法可用如下流程框图更直观地描述,如图4.1.1。

我们可以明显地看到,邻域函数、禁忌对象、禁忌表和藐视准则,构成了禁忌搜索算法的关键。其中,邻域函数沿用局部邻域搜索的思想,用于实现邻域搜索;禁忌表和禁忌对象的设置,体现了算法避免迂回搜索的特点;藐视准则,则是对优良状态的奖励,它是对禁忌策略的一种放松。需要指出的是,上述算法仅是一种简单的禁忌搜索框架,对各关键环节复杂和多样化的设计则可构造出各种禁忌搜索算法。同时,算法流程中的禁忌对象,可以是搜索状态,也可以是特定搜索操作,甚至是搜索目标值等。
同时,与传统的优化算法相比,TS算法的主要特点是:
(1)在搜索过程中可以接受劣解,因此具有较强的“爬山”能力;
(2)新解不是在当前解的邻域中随机产生,而或是优于“best so far”的解,或是非禁忌的最佳解,因此选取优良解的概率远远大于其他解。由于TS算法具有灵活的记忆功能和藐视准则,并且在搜索过程中可以接受劣解,所以具有较强的“爬山”能力,搜索时能够跳出局部最优解,转向解空间的其他区域,从而增强获得更好的全局最优解的概率,所以TS算法是一种局部搜索能力很强的全局迭代寻优算法。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>