智能算法
title:智能算法author:戴挽舟（BbiHH）tags:
AI大数据categories:智能算法date:2019-10-1619:58:00↓↓千万别点↓↓
一、简介什么是群体智能优化算法群体智能优化算法属于一种生物启发式方法。群体智能优化算法主要模拟了昆虫、兽群、鸟群和鱼群的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索的方向。群体智能优化算法的突出特点就是利用了种群的群体智慧进行协同搜索，从而在解空间内找到最优解。
二、群体智能优化算法1.常见的群体智能优化算法分类常见的群体智能优化算法主要有如下几类：（1）蚁群算法（AntColonyOptimization，简称ACO）[1992年提出]；（2）粒子群优化算法（ParticleSwarmOptimization，简称PSO）[1995年提出]（简单易于实现，也是目前应用最为广泛的群体智能优化算法）；（3）菌群优化算法（BacterialForagingOptimization，简称BFO）[2002年提出]；（4）蛙跳算法（ShuffledFrogLeadingAlgorithm，简称SFLA）[2003年提出]；（5）人工蜂群算法（ArtificialBeeColonyAlgorithm，简称ABC）[2005年提出]；除了上述几种常见的群体智能算法以外，还有一些并不是广泛应用的群体智能算法，比如萤火虫算法、布谷鸟算法、蝙蝠算法以及磷虾群算法等等。
2.粒子群优化算法思想粒子群优化算法是在1995年由Eberhart博士和Kennedy博士一起提出的，它源于对鸟群捕食行为的研究。**它的基本核心是利用群体中的个体对信息的共享从而使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问题的最优解。**我们可以利用一个有关PSO的经典描述来对PSO算法进行一个直观的描述。*设想这么一个场景：一群鸟进行觅食，而远处有一片玉米地，所有的鸟都不知道玉米地到底在哪里，但是它们知道自己当前的位置距离玉米地有多远。那么找到玉米地的最佳策略，也是最简单有效的策略就是是搜寻目前距离玉米地最近的鸟群的周围区域。*PSO就是从这种群体觅食的行为中得到了启示，从而构建的一种优化模型。在PSO中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”，而问题的最优解就对应为鸟群要寻找的“玉米地”。所有的粒子都具有一个位置向量（粒子在解空间的位置）和速度向量（决定下次飞行的方向和速度），并可以根据目标函数来计算当前的所在位置的适应值（fitnessvalue），可以将其理解为距离“玉米地”的距离。在每次的迭代中，种群中的粒子除了根据自身的“经验”（历史位置）进行学习以外，还可以根据种群中最优粒子的“经验”来学习，从而确定下一次迭代时需要如何调整和改变飞行的方向和速度。就这样逐步迭代，最终整个种群的粒子就会逐步趋于最优解。
3.粒子群优化算法的基本框架在介绍PSO的算法流程之前，我们写给出PSO中常用的迭代算子的形式。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传代表粒子i的位置向量,代表粒子i的速度向量（其中n为优化问题的维度大小），最早版本的粒子群优化算法的迭代算子形式如下：其中在公式(1)中，Pbesti与Gbest分别代表粒子i历史最佳位置和种群历史最佳位置向量。根据公式(1)(2)可以看出，种群中的粒子通过不断地向自身和种群的历史信息进行学习，从而可以找出问题的最优解。但是，在后续的研究中表明，上述原始的公式中存在一个问题：**公式(1)中Vi的更新太具有随机性，从而使得整个PSO算法的全局优化能力很强，但是局部搜索能力较差。**而实际上，我们需要在算法迭代初期PSO有着较强的全局优化能力，而在算法的后期，整个种群应该具有更强的局部搜索能力。所以根据上述的弊端，Shi和Eberhart通过引入惯性权重修改了公式(1)，从而提出了PSO的惯性权重模型：其中参数w称为是PSO的惯性权重(inertiaweight)，w为控制单个粒子之前速度影响以及对后续行为影响的内置权重，它的取值介于[0,1]区间，一般应用中均采取自适应的取值方法，即一开始令w=0.9，使得PSO全局优化能力较强，随着迭代的深入，参数w进行递减，从而使得PSO具有较强的局部优化能力，当迭代结束时，w=0.1。参数c1和c2称为是学习因子(learnfactor)，一般设置为1.4961；而r1和r2为介于[0,1]之间的随机概率值。(可以用rand()代替，rand()为0~1之间的归一化随机数)整个粒子群优化算法的算法框架如下：
Step1种群初始化：可以进行随机初始化或者根据被优化的问题设计特定的初始化方法，然后计算个体的适应值，从而选择出个体的局部最优位置向量Pbesti和种群全局最优位置向量Gbest。Step2迭代设置：设置迭代次数gmax，并令当前迭代次数g=1;Step3速度更新：根据公式（3）更新每个个体的速度向量；Step4位置更新：根据公式（2）更新每个个体的位置向量；Step5局部位置向量和全局位置向量更新：更新每个个体的Pbesti和Gbest；Step6终止条件判断：判断迭代次数时都达到gmax。如果满足，输出Gbest否则继续进行迭代，跳转至Step3。对于粒子群优化算法的运用，主要是对速度和位置向量迭代算子的设计。迭代算子是否有效将决定整个PSO算法性能的优劣，所以如何设计PSO的迭代算子是PSO算法应用的研究重点和难点。
人工智能导论第 5 版 思考题 第六章
6.1遗传算法的基本步骤和主要特点是什么？
遗传算法的基本步骤：
1.实用随机方法或者其他方法，产生一个有N个染色体的初始群体；
2.对群体中的每一个染色体计算适应值；
3.若满足停止条件、则算法停止，否则以概率pi从群体中随机选择一些染色体构成一个新的群体；
4.以概率pc进行交叉产生一些新的染色体，得到一个新的种群；
5.以一个较小的概率pm使染色体的一个基因发生变异，产生一个新群体，返回步骤二。
主要特点：
1.可以直接对结构对象进行操作；
2.遗传算法不是无方向的随机搜索，而是一个利用随机技术来指导对一个编码的参数空间进行高效率搜索的方法；
3.遗传算法采用群体搜索策略，采用同时处理群体中多个个体的方法，同时对搜索空间中的多个解进行评估；
4.遗传算法的适应度函数不受连续可微的约束，定义域也可以任意设定。
6.2适应度函数在遗传算法中的作用是什么？试举例说明如何构造适应度函数。
适应度函数是用来区分群体中个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯一依据。
6.3选择的基本思想是什么？
选择的基本思想是从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。
6.4简述多种群遗传算法与基本遗传算法的异同。
多种群遗传算法是在遗传算法的基础上经过改进并引入多种群的概念。
主要有以下的改进:
1.把单个种群改变为多个种群，每个种群都有着可控制的参数，例如交叉，变异概率。给予不同的数值能够产生不同的搜索结果。
2.通过特定的操作因子来控制各种群之间的联系与协同进化，例如设定移民算子，可以得出所有种群最优的进化结果。
3.多种群的收敛条件可以根据每个种群进化的最优个体的数目来测定，各个种群中的最优个体可以增加人工选择算子来进行保留。
6.5简述多倍体遗传算法与基本遗传算法的异同。
基于种群保留遗传算法，引入了多倍体的概念，给出了一种基于种群保留的多倍体遗传算法.当该算法运行时，种群个体将由单倍体变为多倍体。
6.6群智能算法的基本思想是什么？
初始一个种群，选择种群中适应度高的个体进行交叉变异。然后再将适应度低的个体淘汰，留下适应度高的个体进行繁殖，这样不断的进化，最终留下的都是优秀的个体。
6.7群智能算法的主要特点是什么？
特点是表现生物学上的现象与对应的仿生智能计算的关系。
6.8列举几种典型的群智能算法，分析它们的主要优点、缺点。
包括：粒子群优化算法、蚁群算法和人工免疫算法。
6.9简述群智能算法与进化算法的异同。
这两种算法都是受自然现象的启发，两者都是基于种群的方法，且种群中的个体之间、个体与环境之间存在相互作用。两者都是一种元启发式随机搜索方法。
不同之处：EC方法强调种群的达尔文的进化模型，而SI优化方法则注重对群体中个体之间的相互作用与分布式协同的模拟。
6.10简述粒子群算法的流程。
1.初始化每个粒子，即在允许范围内随机设置每个粒子的初始位置和速度。
2.评价每个粒子的适应度，计算每个粒子的目标函数。
3.设置每个粒子的pi。对每个粒子，将其适应度与其经历过的最好位置pi进行比较，如果
优于pi，则将其作为该粒子的最好位置pi。
4.设置全局最优值pg。对每个粒子，将其适应度与群体经历过的最好位置p进行比较，如
果优于pg，则将其作为当前群体的最好位置pg。
5.检查终止条件。如果未达到设定条件（预设误差或者迭代的次数），则返回第2步。
6.11简述粒子群算法位置更新方程中各部分的影响。
只有第1部分：φ1=φ2=0：粒子将一直以当前的速度飞行，直至到达边界；由于它智能搜索有限的区域，所以很难找到好解。
没有第1部分：ω=0：速度只取决于粒子当前位置和其历史最好位置Pi，Pg，速度本身没有记忆性。
没有第2部分：φ1=0：粒子没有认知能力，“只有社会模型”；在粒子的互相作用下，有能力达到新的搜索空间，但对复杂问题，容易陷入局部最优解。
没有第3部分：φ2=0：粒子间没有社会共享信息，也就是“只有认知模型”。因为个体间没有交互，一个规模为M的群体等价于M个单个粒子的运行，因而得到最优解的几率非常小。
6.12举例说明粒子群算法的搜索原理，并简要叙述粒子群算法有哪些特点。
粒子群算法的基本原理是粒子种群在搜索空间以一定的速度飞行，每个粒子在搜索时，考虑自己搜索到的历史最优位置和种群内其他粒子的历史最优位置，在此基础上进行位置的变化。
粒子群算法的特点是简单易行，收敛速度快，设置参数少
6.13粒子群算法的寻优过程包含哪几个阶段？寻优的准则有哪些？
6.14粒子群算法中的参数如何选择？
粒子群算法的参数通过模糊系统进行调节。
6.15举例说明蚁群算法的搜索原理，并简要叙述蚁群算法的特点。
蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径问题，其原理是一种正反馈机制或称增强型学习系统；它通过“最优路径上蚂蚁数量的添加→信息素强度添加→后来蚂蚁选择概率增大→最优路径上蚂蚁数量更大添加”达到终于收敛于最优路径上L
它是一种通用型随机优化方法，它吸收了蚂蚁的行为特（内在搜索机制），它是使用人工蚂蚁仿真（也称蚂蚁系统）来求解问题L但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进了人类的智能L人工蚂蚁有一定的记忆;人工蚂蚁不全然是瞎的;人工蚂蚁生活的时空是离散的L
它是一种分布式的优化方法，不仅适合眼下的串行计算机，并且适合未来的并行计算机L
它是一种全局优化的方法，不仅可用于求解单目标优化问题，并且可用于求解多目标优化问题L
它是一种启示式算法,计算复杂性为o(Nc*n2*m)，当中Nc是迭代次数，m是蚂蚁数目，n是目的节点数目L
6.16蚁群算法的寻优过程包含哪几个阶段？寻优的准则有哪些？
6.17蚁群算法中的参数如何选择？
确定蚂蚁数目，根据节点规模/蚂蚁数目≈1.5来确定大概的蚂蚁数目；
参数粗调，即调整信息启发式因子、期望启发式因子和信息素强度Q等参数；
参数微调，即调整信息挥发因子。
目前蚁群算法参数的选择在理论上没有依据，主要依经验而定。