人工智能作业一：搜索算法案例分析_人工智能算法案例

部分资料来自网络

概述

启发式算法（heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。

启发式搜索又叫有信息的搜索，相比较与传统搜索方式它利用问题的启发信息(所求解问题相关的辅助信息)引导搜索过程，来减少搜索范围，降低问题复杂度也就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。

1.遗传算法

1.1算法概述

遗传算法( genetic algorithm,GA)是一种进化算法,其基本原理是仿效生物界中的“物竞是一种进化算法,其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息,最终生成符合优化目标的染色体。在遗传算法中,染色体对应的是数据或数组,通常是由一维的串结构数据来表示，串上各个位置对应基因的取值。基因组成的串就是染色体,或者称为基因型个体。一定数量的个体组成了群体。群体中个体的数目称为群体大小,也称为群体规模。而各个个体对环境的适应程度叫做适应度。

遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索算法难以解决的复杂和非线性优化问题。目前,遗传算法已被广泛应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域,并在这些领域中取得了良好的成果。与传统搜索算法不同，遗传算法从随机产生的初始解开始搜索,通过一定的选择、交叉、变异操作逐步迭代以产生新的解。群体中的每个个体代表问题的一个解，称为染色体，染色体的好坏用适应度值来衡量,根据适应度的好坏从上一代中选择一定数量的优秀个体，通过交叉、变异形成下一代群体。经过若干代的进化之后,算法收敛于最好的染色体,它即是问题的最优
解或次优解。

遗传算法提供了求解非线性规划的通用框架，它不依赖于问题的具体领域。遗传算法的优点是将问题参数编码成染色体后进行优化，而不针对参数本身，从而不受函数约束条件的限制;搜索过程从问题解的-一个集合开始，而不是单个个体,具有隐含并行搜索特性，可大大减少陷入局部最小的可能性。而且优化计算时算法不依赖于梯度信息,且不要求目标函数连续及可导，使其适于求解传统搜索方法难以解决的大规模、非线性组合优化问题。

遗传算法的基本步骤如下:
1.编码

GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据,这些串结构数据的不同组合便构成了不同的点。
2.初始群体的生成

随机产生N个初始串结构数据,每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始进化。
3.适应度评估

适应度表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。
4.选择

选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一-思想,进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择体现了达尔文的适者生存原则。
5.交叉

交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体,新个体组合了其父辈个体的特性。交叉体现了信息交换的思想。
6.变异

变异首先在群体中随机选择一个个体,对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样,GA中变异发生的概率很低,通常取值很小。

1.2案例讲解

1.2.1遗传算法可用于简单一元函数优化和多元函数求解的优化。
譬如：
$$f(x,y)=xcos(2\Pi y)+ysin(2\Pi x)x\in [-2,2],y\in [-2,2]$$
解题思路及步骤:
将自变量在给定范围内进行编码,得到种群编码，按照所选择的适应度函数并通过遗传算法中的选择、交叉和变异对个体进行筛选和进化,使适应度值大的个体被保留,小的个体被淘汰，新的群体继承了上一代的信息，又优于上一代,这样反复循环,直至满足条件,最后留下来的个体集中分布在最优解周围，筛选出其中最优的个体作为问题的解。

1.2.2遗传算法可用于求解旅行商问题

譬如：

解决方案：

(1)编码
采用整数排列编码方法。对于n个城市的TSP问题,染色体分为n段,其中每一段为对应城市的编号，如对10个城市的TSP问题{1,2,3,4,5,6,7,8,9,10} ,则|1|10|2|4|5|6|8|7|9|3就是一个合法的染色体。
(2)种群初始化
在完成染色体编码以后，必须产生一个初始种群作为起始解，所以首先需要决定初始化种群的数目。初始化种群的数目一般根据经验得到,一般情况下种群的数量视城市规模的大小而确定,其取值在50~200之间浮动。
(3)适应度函数
设k1|k2|… |kn|为一个采用整数编码的染色体,Dis,为城市k;到城市k;的距离，则该个体的适应度为
$$fitness=1/(\Sigma (n-1)(i=1)Dkikj+Dknk1)$$
即适应度函数为恰好走遍n个城市，再回到出发城市的距离的倒数。优化的目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体越优质,反之越劣质。
(4)选择操作
选择操作即从旧群体中以一定概率选择个体到新群体中,个体被选中的概率跟适应度值
有关,个体适应度值越大,被选中的概率越大。
(5)交叉操作
采用部分映射杂交,确定交叉操作的父代,将父代样本两两分组,每组重复以下过程(假定
城市数为10):
①产生两个[1,10]区间内的随机整数r和r2，确定两个位置，对两位置的中间数据进行
交叉,如r: =4,r2=7

9 5 1 |3 7 4 2 |10 8 6

10 5 4 |6 3 8 7 |2 1 9

交叉为
9 5 1 |6 3 8 7|10 * *

10 5 * |3 7 4 2|* 1 9

②交叉后,同一个个体中有重复的城市编号,不重复的数字保留,有冲突的数字(带*位置)采用部分映射的方法消除冲突，即利用中间段的对应关系进行映射。结果为
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kMwu8roX-1632321880273)(C:\Users\颜霸灿烈\AppData\Roaming\Typora\typora-user-images\image-20210922223446692.png)]
(6)变异操作
变异策略采取随机选取两个点,将其对换位置。产生两个[1,10]范围内的随机整数r和
r2,确定两个位置,将其对换位置,如r=4,r2=7
9 5 1 6 3 8 7 10 4 2
变异后为
9 5 1 7 3 8 6 10 4 2
(7)进化逆转操作
为改善遗传算法的局部搜索能力,在选择、交叉、变异之后引进连续多次的进化逆转操作。这里的“进化”是指逆转算子的单方向性,即只有经逆转后,适应度值有提高的才接受下来,否则逆转无效。产生两个[1,10]区间内的随机整数r1和r2，确定两个位置，将其对换位置,如r=4,r2=7
9 51|7 3 8|610 4 2
进化逆转后为
9 51|8 3 7|6 10 4 2
对每个个体进行交叉变异,然后代人适应度函数进行评估,x选择出适应值大的个体进行下一代的交叉和变异以及进化逆转操作。循环操作:判断是否满足设定的最大遗传代数MAXGEN,不满足则跳人适应度值的计算;否则,结束遗传操作。

1.3改进

1.使用精英策略
子代种群中的最优个体永远不会比父代最优的个体差，这样使得父代的好的个体不至于
由于交叉或者变异操作而丢失。
2.使用进化逆转操作
在本文的编码中，每一个染色体即对应一个TSP环游，如果染色体码串的顺序发生变化，
则环游路径也随之改变。因此,TSP问题解的关键地方就是码串的顺序。对照文中的交叉算
子,可以发现，纵使两个亲代完全相同,通过交叉，仍然会产生不同于亲代的子代,且子代的码
串排列顺序与亲代有较大的差异。交叉算子的这种变异效果所起的作用有两个方面，一方面
它能起到维持群体内- -定的多样性的作用，避免陷人局部最优解;但是另一方面,它却不利于
子代继承亲代的较多信息,特别是当进化过程进人到后期，群体空间中充斥着大量的高适应度
个体,交叉操作对亲代的较优基因破坏很大，使子代难以继承到亲代的优良基因，从而使交叉
算子的搜索能力大大降低。
同交叉算子相比较,逆转算子能使子代继承亲代的较多信息。假设码串为123456789,在
2和3,6和7之间发生两处断裂再逆转插人,则新码串为12- 6543 - 789,此时子代中12段、
6543段、789段与亲代对应片段顺序完全一样(6543 与3456顺序对于环游路径长度来说是等
价的)，只是在断裂点的两端环游次序发生了变化，而且本文中逆转是单方向的，即只接受朝着
好的方向的逆转，因此它搜索最优解的能力强于交叉算子。

2.蚁群算法

2.1算法概述

蚁群算法(ant colony algorithm,ACA)是由意大利学者M. Dorigo等人于20世纪90年代初提出的一种新的模拟进化算法,其真实地模拟了自然界蚂蚁群体的觅食行为。M. Dorigo等人将其用于解决旅行商问题（TSP),并取得了较好的实验结果。近年来,许多专家学者致力于蚁群算法的研究,并将其应用于交通、通信、化工、电力等领域，成功解决了许多组合优化问题，如调度问题、指派问题、旅行商问题等。

生物学家研究发现，自然界中的蚂蚁觅食是一个群体性行为,并非单只蚂蚁自行寻找食物源。蚂蚁在寻找食物源时,会在其经过的路径上释放一种信息素,并能够感知其他蚂蚁释放的信息素。信息素浓度的大小表征路径的远近,信息素浓度越高,表示对应的路径距离越短。通常,蚂蚁会以较大的概率优先选择信息索浓度较高的路径,并释放一定量的信息素，以增强该条路径上的信息素浓度,这样会形成一个正反馈。最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径，即最短距离。值得一提的是,生物学家同时发现,路径上的信息素浓度会随着时间的推进而逐渐衰减。

将蚁群算法应用于解决优化问题的基本思路为:用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终,整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

2.2案例分析

按照枚举法,我国31个直辖市、省会和自治区首府的巡回路径应有约1. 326X1022种,其中一条路径如图所示。试利用蚁群算法寻找到一条最佳或者较佳的路径。

问题分析：

1.不难发现这个问题其实就是蚁群算法解决TSP问题，

1.计算城市间相互距离
根据城市的位置坐标,计算两两城市间的相互距离,从而得到对称的距离矩阵(维数为31的方阵)。需要说明的是,计算出的矩阵对角线上的元素为0，将对角线上的元素修正为一个非常小的正数(如10-5等)。
2.初始化参数
3.迭代寻找最佳路径
首先构建解空间，即各个蚂蚁根据转移概率公式访问所有的城市。然后计算各个蚂蚁经过路径的长度,并在每次迭代后实时更新各个城市连接路径上的信息素浓度。经过循环迭代,记录下最优的路径及其长度。
4.结果分析
找到最优路径后,可以将之与其他方法得出的结果进行比较,从而对蚁群算法的性能进行评价。同时，也可以探究不同取值的参数对优化结果的影响，从而找到一组最佳或者较佳的参数组合。

基于蚁群算法的基本思想及解决TSP问题的基本原理,不难发现与其他优化算法相比，蚁群算法具有以下几个特点:
(1)采用正反馈机制,使得搜索过程不断收敛,最终逼近最优解。
(2)每个个体可以通过释放信息素来改变周围的环境,且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯。
(3)搜索过程采用分布式计算方式,多个个体同时进行并行计算,大大提高了算法的计算能力和运行效率。
(4)启发式的概率搜索方式不容易陷人局部最优，易于寻找到全局最优解。

蚁群算法以其分布并行式计算、启发式搜索方式等特点，在各个领域中取得了广泛的应用,解决了诸多组合优化方面的难题。针对其可能陷人局部最优的缺点,不少专家和学者提出了许多改进的方法,并将其他算法(如遗传算法、粒子群算法等)与蚁群算法相结合,对蚂蚁个数、信息素重要程度因子、启发函数重要程度因子、信息素挥发因子、信息素释放总量等参数进行优化选择,取得了不错的效果。

3.贪婪最佳优先搜索

3.1算法概述

将节点表按照距目标的距离进行排序，再以节点的估计距离为标准选择待扩展节点。搜索问题解法的时候，“目光短浅”，每一步算法会先看所有邻近节点，选择最低开销。
辅助信息一般有两类：
Evaluation Function 评价函数 f(n) : 评估总cost;—寻路任务中，从当前节点n出发，根据评价函数来选择后续节点。
当前最小cost函数g(n) ；考虑从开始到目前的cost；
后续最小cost函数h(n) ; —寻路任务中，计算从节点n到目标节点之间所形成路径的估算最小代价值，这里将两点之间的直线距离作为启发函数。
GBFS的评价函数： g(n)=h(n)

3.2 案例分析——寻路问题

① 从A出发，有前往B的路径与否？② 从A出发，哪条往B的路径最短？

解决：

我们需要找到从Arad到Bucharest的最短路线。其中路线的辅助信息已经给出。GBFS的实现，要求我们使用一个priority queue优先队列，所谓优先队列，其一般不在遵循队列的先入先出原则，元素按照其自然顺序进行排序，或者根据构造队列时提供的Comparator进行排序。 一般分为以下两种情况：
1.最大优先队列——无论入队顺序，当前最大的元素优先出队；
2.最小优先队列——无论入队顺序，当前最小的元素优先出队；
pq队列的头值排序规则最小的那个元素，若多个元素都是最小值，则随机选择一个即可。同时，pq是一个无界队列，随着不断向优先级队列添加元素，其容量会自动扩容。
在GBFS的算法中，其主要过程如下：
1.建立一个已经排序好的初始节点表A（从小到大）；
2.若A为空集，退出，给出失败信号；
3.a取为A的首节点（优先队列首节点原则)，并在A中删除节点a，讲其放入已访问节点列表;
4.若a为目标节点，退出，给出成功信号；否则，将a的后续节点加到A中，记为A’，对A‘中的节点按距目标的估计距离排序，并返回2.

改进与思考：

贪婪最佳优先搜索有如下的弊端：
1.不一定最优(不考虑总距离)
2.容易陷入死循环
3.有可能一直沿着一条道，但是这条道到不了终点… （不完备性)

4.A*搜索

算法概述

A* 算法，就是解决在一个平面 grid地图中寻找起点到终点的最短路径问题的算法，类似于Dijkstra算法和BFS算法一样，属于广度优先搜索。但不同于BFS和DFS在子节点选择上盲目，A搜索就是利用评估函数在平面中对所有的待搜索点进行评估，找出最佳的搜索点问题。可以说A算法集中了Dijkstra算法和贪婪最佳优先算法。它的评价函数为f(n)=g(n)+h(n)。

5.爬山法

5.1算法概述

爬山法是指经过评价当前的问题状态后，限于条件去增加这一状态与目标状态的差异，经过迂回前进，最终达到解决问题的总目标。就如同爬山一样，为了到达山顶，有时不得不先上矮山顶，然后再下来，这样翻越一个个的小山头，直到最终达到山顶。可以说，爬山法是一种"以退为进"的方法，往往具有"退一步进两步"的作用，后退乃是为了更有效地前进。爬山法也叫逐个修改法、瞎子摸象法。

5.2案例分析——八皇后问题

问题

八皇后问题，一个古老而著名的问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

解决

爬山法是指从当前的节点开始，和周围的邻居节点的值进行比较。 如果当前节点是最大的，那么返回当前节点，作为最大值，即山峰最高点；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。我们采用爬山法分别对八皇后和八数码进行算法设计，其中在爬山法求解八数码的问题中，我们采用曼哈顿距离作为启发式函数进行计算。

改进

高地问题：搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低
山脊问题：搜索可能会在山脊的两面来回震荡，前进步伐很小当出现以上问题后，只能随机重启爬山算法来解决。
随机重启爬山法的思想是通过随机生成初始状态来导引爬山法搜索，直到找到目标状态。对于八皇后问题来说是合情合理的，因为八皇后问题目标就是找到最终状态，所有初始状态随机改变是可以允许的。但是对于八数码问题不合理，因为八数码问题的目标就是给定初始状态，从而找到到达最终状态的路线，初始状态是不能随意改变的，如果使用了随机重启算法，则违反了规则。因此，此处不采用随机重启法对八数码问题进行设计和求解。

6.模拟退火算法

算法概述

模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。在迭代更新可行解时，以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。
  算法步骤：给出初始温度，初始解，退火系数等参数。（1）在温度没有达到降到最终设定的温度时，进行退火过程即进行循环迭代。（2）在该温度下，产生新解，并计算目标函数值。如果目标函数值更优，接受新解。否则，会以一定的概率接受错误解。该过程完成，即完成一次退火。算法的核心，在与接受概率的设定。
反应在代码上：外循环控制执行次数（进行退火）。（2）内循环搜索最优解。

7.对抗搜索

算法概述

对抗搜索（Adversarial Search）也称为博弈搜索（Game Rearch）

在一个竞争的环境中，智能体（agents）之间通过竞争实现相反的利益，一方最大化这个利益，另一方最小化。

对抗搜索的方法主要有三个：
最小最大搜索（Minmax Search）
Alpha-Beta剪枝搜索（Pruning Search）
蒙塔卡洛树搜索（Monte-Caelo Tree Search）

最大最小搜索为对抗搜索中最基本的搜索方法；剪枝搜索是一种对最大最小搜索进行改进的算法，即在搜索过程中可以减去无需搜索的分支节点，且不影响搜索结果。蒙特卡洛树搜索通过采样而非穷举方法来实现搜索。