人工智能
作者：沈聪
贪婪算法是启发式算法的代表算法之一，其核心思想是每次都选择局部最优解，但该算法并不能保证最后得出的结果是全局最优解。贪婪算法比较典型的案例就是最短路径搜索。之前，大部分的贪婪算法都是基于图的方式寻找最优路径。本篇文章主要借助路径动态规划的案例利用贪婪算法讲解树的最优路径。
相对于图来说，在树的搜索过程中，贪婪算法会遇到很多不可行解，这就需要程序能否返回到最近的一个节点，重新寻找其他的可行路径。下面通过一个示例说明贪婪最佳优先搜索和改进贪婪优化算法具体过程。
问题描述下图展示了城市之间的路径图，该图包含了城市节点，城市之间的路径以及路径的大小。利用贪婪算法寻找节点1到节点19的路径。
贪婪算法和核心思路从节点1开始，每次都选择最短的路径，直到到达节点19，其路径显示图如下：
可以看出路径经历了3次死循环后，得出了最后的路径。
在贪婪算法的基础上，我们尝试的每次搜索N个节点，并把这N个节点的路径进行比较，这就是提出的改进贪婪算法。其思路从节点1开始，每次选择N个最短路径进行比较，然后选择N个叠加后的最短路径。以N=2为例，其选择路径为：
该算法在大型的图或树中，可提高搜索效率，但对于过大的N来说，其会导致搜索来回震荡。
MATLAB程序及仿真结果（贪婪算法）functionBest_Path=Greedy_search(Distance_Matrix,Begin_Point,End_Point)%该程序主要利用贪婪算法寻找两个节点之间的最小距离%Distance_Matrix的格式为：%节点12345....21%10928600%29200830...%38600076%...%2100000%Distance_Matrix主要描述了节点和节点之间的连接关系及距离%Begin_Point为起始的节点编号%End_Point为目标的节点编号%History显示了贪婪算法历经的路径%Best_Path显示了贪婪算法最后找出的最优结果Dist_Matrix=Distance_Matrix;History=[Begin_Point];%记录了当次的寻找路径Next_Point=Begin_Point;whileNext_Point~=End_PointNext_Point1=Min_Find(Dist_Matrix(Next_Point,:));%找出当前节点下，最优的下一个节点Dist_Matrix=Trace_Find(Dist_Matrix,Next_Point,Next_Point1);%更新搜索树，把已经寻找到的路径删除Next_Point=Next_Point1;History=[HistoryNext_Point];ifisempty(Next_Point)%倒回到一个节点，如果这个节点除了上游的节点，下游的节点，begin的节点外还有其他的一个节点想相连，则说明它可以作为另外一条路的起点History(end)=[];fori=length(History):-1:1%从最后一个节点开始寻找Point=History(i);%判断这一行是否都为零，如果有不为零的，需要判断这个节点是否在History里面，如果在的也要去除该节点x=find(Dist_Matrix(Point,:)>0);if~isempty(x)forii=1:length(x)Find_x=find(History==x(ii));if~isempty(Find_x)%如果x不为空集，则说明这个节点连接了上游、下游、begin的节点之一，需要去除。Dist_Matrix=Trace_Find(Dist_Matrix,Point,x(ii));%更新搜索树，把已经寻找到的路径删除endendend%去除在History里面的连接后，寻找新的路径x=find(Dist_Matrix(Point,:)>0);if~isempty(x)Next_Point1=Min_Find(Dist_Matrix(Point,:));Dist_Matrix=Trace_Find(Dist_Matrix,Point,Next_Point1);%更新搜索树，把已经寻找到的路径删除Next_Point=Next_Point1;History=[HistoryNext_Point];break;else%如果该节点没有新的路径，寻找下一个节点的新的路径History(i)=[];continue;endendendendBest_Path=History;其结果为
functionMin_Value_Index=Min_Find(Vector)%这个函数主要是寻找一个行向量的非零的最小值Min_Value_Vector=find(Vector>0);if~isempty(Min_Value_Vector)Min_Value_Index=Min_Value_Vector(1);Min_Value=Vector(Min_Value_Index);fori=1:length(Vector)ifVector(i)>0ifMin_Value>Vector(i)Min_Value=Vector(i);Min_Value_Index=i;endelsecontinue;endendelseMin_Value_Index=[];end该程序的难点在于贪婪算法能搜索到很多不可行的路径，程序需要返回到原来的节点重新进行搜索。
改进贪婪算法（N-型贪婪算法），该程序的难点是遇到不可行解后，怎么退回找到原来的路径。这个算法对于大型的图或者树来说，能够提高搜索速度。但对于小的图来说，会引起算法的震荡。
程序为：
functionBest_Path=Greedy_search_N_Step(Distance_Matrix,Begin_Point,End_Point,N)Dist_Matrix=Distance_Matrix;History=[Begin_Point];%记录了当次的寻找路径Next_Point=Begin_Point;whileisempty(find(History==End_Point))[Min_Value_Index,Dist_Matrix]=Min_Find_N_step(Dist_Matrix,Next_Point,N,Begin_Point);if~isempty(Min_Value_Index)Next_Point=Min_Value_Index(end);elseNext_Point=[];endHistory=[HistoryMin_Value_Index];ifisempty(Next_Point)%倒回到一个节点，如果这个节点除了上游的节点，下游的节点，begin的节点外还有其他的一个节点想相连，则说明它可以作为另外一条路的起点History(end)=[];fori=length(History):-1:1%从最后一个节点开始寻找Point=History(i);%判断这一行是否都为零，如果有不为零的，需要判断这个节点是否在History里面，如果在的也要去除该节点x=find(Dist_Matrix(Point,:)>0);if~isempty(x)forii=1:length(x)Find_x=find(History==x(ii));if~isempty(Find_x)%如果x不为空集，则说明这个节点连接了上游、下游、begin的节点之一，需要去除。Dist_Matrix=Trace_Find(Dist_Matrix,Point,x(ii));%更新搜索树，把已经寻找到的路径删除endendend%去除在History里面的连接后，寻找新的路径x=find(Dist_Matrix(Point,:)>0);if~isempty(x)[Min_Value_Index,Dist_Matrix]=Min_Find_N_step(Dist_Matrix,Point,N,Begin_Point);%Next_Point1=Min_Find(Dist_Matrix(Point,:));%Dist_Matrix=Trace_Find(Dist_Matrix,Point,Next_Point1);%更新搜索树，把已经寻找到的路径删除Next_Point=Min_Value_Index(end);History=[HistoryMin_Value_Index];break;else%如果该节点没有新的路径，寻找下一个节点的新的路径History(i)=[];continue;endendendendBest_Path=History;其运行结果为：
可以看出当N=2时候，把20也加入了最后的结果。由于程序较多，只附上主程序，其它函数程序可以私信。
智能算法综述
1、什么是智能算法
智能计算也有人称之为“软计算”，是们受自然（生物界）规律的启迪，根据其原理，模仿求解问题的算法。从自然界得到启迪，模仿其结构进行发明创造，这就是仿生学。这是我们向自然界学习的一个方面。另一方面，我们还可以利用仿生原理进行设计(包括设计算法)，这就是智能计算的思想。这方面的内容很多，如人工神经网络技术、遗传算法、模拟退火算法、模拟退火技术和群集智能技术等。
2、人工神经网络算法
“人工神经网络”(ARTIFICIALNEURALNETWORK，简称ANN)是在对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行为的一种工程系统。早在本世纪40年代初期，心理学家McCulloch、数学家Pitts就提出了人工神经网络的第一个数学模型，从此开创了神经科学理论的研究时代。其后，FRosenblatt、Widrow和J.J.Hopfield等学者又先后提出了感知模型，使得人工神经网络技术得以蓬勃发展。
神经系统的基本构造是神经元(神经细胞)，它是处理人体内各部分之间相互信息传递的基本单元。据神经生物学家研究的结果表明，人的一个大脑一般有1010～1011个神经元。每个神经元都由一个细胞体，一个连接其他神经元的轴突和一些向外伸出的其它较短分支——树突组成。轴突的功能是将本神经元的输出信号(兴奋)传递给别的神经元。其末端的许多神经末梢使得兴奋可以同时传送给多个神经元。树突的功能是接受来自其它神经元的兴奋。神经元细胞体将接受到的所有信号进行简单处理(如：加权求和，即对所有的输入信号都加以考虑且对每个信号的重视程度——体现在权值上——有所不同)后由轴突输出。神经元的树突与另外的神经元的神经末梢相连的部分称为突触。
2.1、人工神经网络的特点
人工神经网络是由大量的神经元广泛互连而成的系统，它的这一结构特点决定着人工神经网络具有高速信息处理的能力。人脑的每个神经元大约有103～104个树突及相应的突触，一个人的大脑总计约形成1014～1015个突触。用神经网络的术语来说，即是人脑具有1014～1015个互相连接的存储潜力。虽然每个神经元的运算功能十分简单，且信号传输速率也较低(大约100次/秒)，但由于各神经元之间的极度并行互连功能，最终使得一个普通人的大脑在约1秒内就能完成现行计算机至少需要数10亿次处理步骤才能完成的任务。
人工神经网络的知识存储容量很大。在神经网络中，知识与信息的存储表现为神经元之间分布式的物理联系。它分散地表示和存储于整个网络内的各神经元及其连线上。每个神经元及其连线只表示一部分信息，而不是一个完整具体概念。只有通过各神经元的分布式综合效果才能表达出特定的概念和知识。
由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大，使得它具有很强的不确定性信息处理能力。即使输入信息不完全、不准确或模糊不清，神经网络仍然能够联想思维存在于记忆中的事物的完整图象。只要输入的模式接近于训练样本，系统就能给出正确的推理结论。
正是因为人工神经网络的结构特点和其信息存储的分布式特点，使得它相对于其它的判断识别系统，如：专家系统等，具有另一个显著的优点：健壮性。生物神经网络不会因为个别神经元的损失而失去对原有模式的记忆。最有力的证明是，当一个人的大脑因意外事故受轻微损伤之后，并不会失去原有事物的全部记忆。人工神经网络也有类似的情况。因某些原因，无论是网络的硬件实现还是软件实现中的某个或某些神经元失效，整个网络仍然能继续工作。
人工神经网络是一种非线性的处理单元。只有当神经元对所有的输入信号的综合处理结果超过某一门限值后才输出一个信号。因此神经网络是一种具有高度非线性的超大规模连续时间动力学系统。它突破了传统的以线性处理为基础的数字电子计算机的局限，标志着人们智能信息处理能力和模拟人脑智能行为能力的一大飞跃。
2.2、几种典型神经网络简介
2.2.1、多层感知网络(误差逆传播神经网络)
在1986年以Rumelhart和McCelland为首的科学家出版的《ParallelDistributedProcessing》一书中，完整地提出了误差逆传播学习算法，并被广泛接受。多层感知网络是一种具有三层或三层以上的阶层型神经网络。典型的多层感知网络是三层、前馈的阶层网络，即：输入层I、隐含层(也称中间层)J和输出层K。相邻层之间的各神经元实现全连接，即下一层的每一个神经元与上一层的每个神经元都实现全连接，而且每层各神经元之间无连接。
但BP网并不是十分的完善，它存在以下一些主要缺陷：学习收敛速度太慢、网络的学习记忆具有不稳定性，即：当给一个训练好的网提供新的学习记忆模式时，将使已有的连接权值被打乱，导致已记忆的学习模式的信息的消失。
2.2.2、竞争型(KOHONEN)神经网络
它是基于人的视网膜及大脑皮层对剌激的反应而引出的。神经生物学的研究结果表明：生物视网膜中，有许多特定的细胞，对特定的图形(输入模式)比较敏感，并使得大脑皮层中的特定细胞产生大的兴奋，而其相邻的神经细胞的兴奋程度被抑制。对于某一个输入模式，通过竞争在输出层中只激活一个相应的输出神经元。许多输入模式，在输出层中将激活许多个神经元，从而形成一个反映输入数据的“特征图形”。竞争型神经网络是一种以无教师方式进行网络训练的网络。它通过自身训练，自动对输入模式进行分类。竞争型神经网络及其学习规则与其它类型的神经网络和学习规则相比，有其自己的鲜明特点。在网络结构上，它既不象阶层型神经网络那样各层神经元之间只有单向连接，也不象全连接型网络那样在网络结构上没有明显的层次界限。它一般是由输入层(模拟视网膜神经元)和竞争层(模拟大脑皮层神经元，也叫输出层)构成的两层网络。两层之间的各神经元实现双向全连接，而且网络中没有隐含层。有时竞争层各神经元之间还存在横向连接。竞争型神经网络的基本思想是网络竞争层各神经元竞争对输入模式的响应机会，最后仅有一个神经元成为竞争的胜者，并且只将与获胜神经元有关的各连接权值进行修正，使之朝着更有利于它竞争的方向调整。神经网络工作时，对于某一输入模式，网络中与该模式最相近的学习输入模式相对应的竞争层神经元将有最大的输出值，即以竞争层获胜神经元来表示分类结果。这是通过竞争得以实现的，实际上也就是网络回忆联想的过程。
除了竞争的方法外，还有通过抑制手段获取胜利的方法，即网络竞争层各神经元抑制所有其它神经元对输入模式的响应机会，从而使自己“脱颖而出”，成为获胜神经元。除此之外还有一种称为侧抑制的方法，即每个神经元只抑制与自己邻近的神经元，而对远离自己的神经元不抑制。这种方法常常用于图象边缘处理，解决图象边缘的缺陷问题。
竞争型神经网络的缺点和不足：因为它仅以输出层中的单个神经元代表某一类模式。所以一旦输出层中的某个输出神经元损坏，则导致该神经元所代表的该模式信息全部丢失。
2.2.3、Hopfield神经网络
1986年美国物理学家J.J.Hopfield陆续发表几篇论文，提出了Hopfield神经网络。他利用非线性动力学系统理论中的能量函数方法研究反馈人工神经网络的稳定性，并利用此方法建立求解优化计算问题的系统方程式。基本的Hopfield神经网络是一个由非线性元件构成的全连接型单层反馈系统。
网络中的每一个神经元都将自己的输出通过连接权传送给所有其它神经元，同时又都接收所有其它神经元传递过来的信息。即：网络中的神经元t时刻的输出状态实际上间接地与自己的t-1时刻的输出状态有关。所以Hopfield神经网络是一个反馈型的网络。其状态变化可以用差分方程来表征。反馈型网络的一个重要特点就是它具有稳定状态。当网络达到稳定状态的时候，也就是它的能量函数达到最小的时候。这里的能量函数不是物理意义上的能量函数，而是在表达形式上与物理意义上的能量概念一致，表征网络状态的变化趋势，并可以依据Hopfield工作运行规则不断进行状态变化，最终能够达到的某个极小值的目标函数。网络收敛就是指能量函数达到极小值。如果把一个最优化问题的目标函数转换成网络的能量函数，把问题的变量对应于网络的状态，那么Hopfield神经网络就能够用于解决优化组合问题。
对于同样结构的网络，当网络参数(指连接权值和阀值)有所变化时，网络能量函数的极小点(称为网络的稳定平衡点)的个数和极小值的大小也将变化。因此，可以把所需记忆的模式设计成某个确定网络状态的一个稳定平衡点。若网络有M个平衡点，则可以记忆M个记忆模式。
当网络从与记忆模式较靠近的某个初始状态(相当于发生了某些变形或含有某些噪声的记忆模式，也即：只提供了某个模式的部分信息)出发后，网络按Hopfield工作运行规则进行状态更新，最后网络的状态将稳定在能量函数的极小点。这样就完成了由部分信息的联想过程。
Hopfield神经网络的能量函数是朝着梯度减小的方向变化，但它仍然存在一个问题，那就是一旦能量函数陷入到局部极小值，它将不能自动跳出局部极小点，到达全局最小点，因而无法求得网络最优解。
3、遗传算法
遗传算法（GeneticAlgorithms）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在70年代初期由美国密执根（Michigan）大学的霍兰（Holland）教授发展起来的。1975年霍兰教授发表了第一本比较系统论述遗传算法的专著《自然系统与人工系统中的适应性》（《AdaptationinNaturalandArtificialSystems》）。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。
近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用方面，取得了一些令人信服的结果，所以引起了很多人的关注。在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。
3.1、特点
遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：①首先组成一组候选解；②依据某些适应性条件测算这些候选解的适应度；③根据适应度保留某些候选解，放弃其他候选解；④对保留的候选解进行某些操作，生成新的候选解。在遗传算法中，上述几个特征以一种特殊的方式组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。
遗传算法还具有以下几方面的特点：
(1)遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。
(2)许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。
(3)遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。
(4)遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。
(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。
3.2、运用领域
前面描述是简单的遗传算法模型，可以在这一基本型上加以改进，使其在科学和工程领域得到广泛应用。下面列举了一些遗传算法的应用领域：
①优化：遗传算法可用于各种优化问题。既包括数量优化问题，也包括组合优化问题。
②程序设计：遗传算法可以用于某些特殊任务的计算机程序设计。
③机器学习：遗传算法可用于许多机器学习的应用，包括分类问题和预测问题等。
④经济学：应用遗传算法对经济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。
⑤免疫系统：应用遗传算法可以对自然界中免疫系统的多个方面建立模型，研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。
⑥进化现象和学习现象：遗传算法可以用来研究个体是如何学习生存技巧的，一个物种的进化对其他物种会产生何种影响等等。
⑦社会经济问题：遗传算法可以用来研究社会系统中的各种演化现象，例如在一个多主体系统中，协作与交流是如何演化出来的。
4、模拟退火算法
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温度升高变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
5、群体（群集）智能（SwarmIntelligence）
受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了一系列对于传统问题的新的解决方法，这些研究就是群集智能的研究。群集智能(SwarmIntelligence)中的群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解”。而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特性”。群集智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。
群集智能的特点和优点：群体中相互合作的个体是分布式的(Distributed)，这样更能够适应当前网络环境下的工作状态;没有中心的控制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解。可以不通过个体之间直接通信而是通过非直接通信(Stimergy)进行合作，这样的系统具有更好的可扩充性(Scalability)。由于系统中个体的增加而增加的系统的通信开销在这里十分小。系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性(Simplicity)。因为具有这些优点，虽说群集智能的研究还处于初级阶段，并且存在许多困难，但是可以预言群集智能的研究代表了以后计算机研究发展的一个重要方向。
在计算智能(ComputationalIntelligence)领域有两种基于群智能的算法，蚁群算法(AntColonyOptimization)和粒子群算法(ParticleSwarmOptimization)，前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。
5.1、蚁群优化算法
受蚂蚁觅食时的通信机制的启发，90年代Dorigo提出了蚁群优化算法(AntColonyOptimization，ACO)来解决计算机算法学中经典的“货郎担问题”。如果有n个城市，需要对所有n个城市进行访问且只访问一次的最短距离。
在解决货郎担问题时，蚁群优化算法设计虚拟的“蚂蚁”将摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。虚拟的“信息素”也会挥发，每只蚂蚁每次随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。根据“信息素较浓的路线更近"的原则，即可选择出最佳路线。由于这个算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选择，并且由于采用了概率算法，所以它能够不局限于局部最优解。
蚁群优化算法对于解决货郎担问题并不是目前最好的方法，但首先，它提出了一种解决货郎担问题的新思路；其次由于这种算法特有的解决方法，它已经被成功用于解决其他组合优化问题，例如图的着色(GraphColoring)以及最短超串(ShortestCommonSupersequence)等问题。
5.2、粒子群优化算法
粒子群优化算法(PSO)是一种进化计算技术(EvolutionaryComputation)，有Eberhart博士和Kennedy博士发明。源于对鸟群捕食的行为研究。
PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。
同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。
粒子群优化算法(PSO)也是起源对简单社会系统的模拟，最初设想是模拟鸟群觅食的过程，但后来发现PSO是一种很好的优化工具。
5.2.1、算法介绍
PSO模拟鸟群的捕食行为。一群鸟在随机搜索食物，在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。
PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
PSO初始化为一群随机粒子(随机解)，然后通过叠代找到最优解，在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。
5.2.2、PSO算法过程
①种群随机初始化。
②对种群内的每一个个体计算适应值(fitnessvalue)。适应值与最优解的距离直接有关。
③种群根据适应值进行复制。
④如果终止条件满足的话，就停止，否则转步骤②。
从以上步骤，我们可以看到PSO和遗传算法有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。但是，PSO没有遗传操作如交叉(crossover)和变异(mutation)，而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。
与遗传算法比较，PSO的信息共享机制是很不同的。在遗传算法中，染色体(chromosomes)互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在PSO中,只有gBest(orlBest)给出信息给其他的粒子，这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较,在大多数的情况下，所有的粒子可能更快的收敛于最优解。
现在已经有一些利用PSO代替反向传播算法来训练神经网络的论文。研究表明PSO是一种很有潜力的神经网络算法，同时PSO速度比较快而且可以得到比较好的结果。
6、展望
目前的智能计算研究水平暂时还很难使“智能机器”真正具备人类的常识，但智能计算将在21世纪蓬勃发展。不仅仅只是功能模仿要持有信息机理一致的观点。即人工脑与生物脑将不只是功能模仿，而是具有相同的特性。这两者的结合将开辟一个全新的领域，开辟很多新的研究方向。智能计算将探索智能的新概念，新理论，新方法和新技术，而这一切将在以后的发展中取得重大成就。
转自：http://xiao1jun.bokee.com/12058988.html
人工智能学习笔记：基本遗传算法及其改进算法
文章目录1引言2基本思想及发展历史3基本遗传算法详细步骤3.1编码3.2初始群体设定3.3设计适应度函数3.4遗传操作3.4.1选择3.4.2交叉3.4.3变异4基本遗传算法总结5遗传算法改进5.1双倍体遗传算法5.2双种群遗传算法5.3自适应遗传算法6参考文献1引言本次学习报告主要介绍基本遗传算法的详细过程以及三种遗传算法的改进算法，旨在回顾和整理这一学期习得的部分知识。在撰写报告的过程中，会在其中增加一些个人的思考，这些思考主要基于过去所学的知识，目的在于寻找知识与知识之间的联系。由于本人能力所限，如有不当之处，恳请读者指正并提出宝贵的意见。
2基本思想及发展历史遗传算法来源于达尔文进化论和群体遗传学，由美国的Holland教授于1975年首先提出。遗传算法既是经典的启发式算法，同时也是非确定性的拟自然算法，它为复杂系统的优化提供了一种新思路，对于诸多NP-Hard问题，遗传算法都有不错的表现。简而言之，我发现，遗传算法参考了生物遗传过程，并用于解决最优化的问题。实际上，这里的“生物遗传”就是高中生物所学的基因学问题。有趣的是，我们目前学到的某些算法均参考了生物学的相关知识，比如西瓜书第五章所介绍的BP神经网络。在链式法则和参数寻优过程中，连接权重w和阈值θ的计算对应正是我们高中所学的神经元部分知识，这可能也体现了跨学科思维。
图1神经元结构又比如我在看过赵军团队的《知识图谱》后，利用放缩的思想，发现整个知识图谱的构建过程，可能类似于学生做英语阅读理解的思维过程。在此举一个可能不太恰当的例子，我在阅读之前需要找定位词（命名实体识别），并且尽可能找到关键词之间的关系（关系抽取），之后在回到原文中找到相关段落句子，并根据一些表达情感的定语做适当的推理得到答案（知识推理），以此类推，当做完整篇文章之后，我也对这片文章的脉络有了一个初步的认知，并在脑中建立起对应的框架。
图2知识图谱生命周期说回遗传算法，它主要借用生物进化中“适者生存”的规律。在遗传算法中，染色体对应的是数据或数组，通常是由一维的串结构数据来表示的。遗传算法处理的是染色体，或者称为基因型个体。一定数量的个体组成了群体。群体中个体的数量称为种群的大小，也叫种群的规模。各个个体对环境的适应程度叫适应度。适应度大的个体被选择进行遗传操作产生新个体，体现了生物遗传中适者生存的原理。选择两个染色体进行交叉产生一组新的染色体的过程，类似生物遗传中的婚配。编码的某一个分量发生变化的过程，类似于生物遗传中的变异。 遗传算法包含两个数据转换操作，一个是从表现型到基因型的转换，将搜索空间中的参数或解转换成遗传空间中的染色体或个体，这个过程称为编码。另一个是从基因型到表现型的转换，即将个体转换成搜索空间中的参数，这个过程称为解码。图3是总结的遗传算法模拟生物遗传过程的相关环节。
图3模拟生物进程总结表1是整理的遗传算法发展历史。
表1遗传算法发展历史时间人名研究成果1965年Holland首次提出人工遗传操作的重要性1967年Bagley提出选择、交叉和变异操作；引入适应度定标概念；首次提出遗传算法自我调整概念，即引入交叉和变异的概率1971年Hollstien第一个把遗传算法用于函数优化1975年Holland系统阐述遗传算法基本理论和方法，并提出模式理论3基本遗传算法详细步骤图4是总结的一次迭代的遗传算法流程，接下来将围绕该图进行算法步骤阐述。
图4基本遗传算法流程总结3.1编码由于遗传算法不能直接处理问题空间的参数，因此，必须通过编码将要求解的问题表示成遗传空间的染色体或个体。该部分操作类似于自然语言处理中，词表示成词向量，这样我们就可以在特征空间中处理自然语言。对一个具体的应用问题如何编码是应用遗传算法的首要问题，也是遗传算法应用的难点。实际上，还不存在一种通用的编码方法，特殊的问题往往采用特殊的方法。图5是常见的编码方法的总结。
图5编码方法总结其中，位串编码是将问题空间的参数编码为一维排列的染色体的方法，称为一维染色体编码方法。一维染色体编码中最常用的符号集是二值符号集{0,1}，即采用二进制编码。实际上，整理之后发现，其余的方法都是在解决二进制编码的不足之处。 比如，二进制编码的缺点有二：一是相邻整数的二进制编码可能具有较大的Hamming距离（例如，15和16的二进制表示为01111和10000，因此算法从15改进到16必须改变所有的位），这种缺陷造成了Hamming悬崖，降低了遗传算子的搜索效率；二是在求解高维优化问题时，二进制编码将非常长，从而使得算法的搜索效率很低。 针对缺点一，可以采用Gray编码，也就是说将二进制编码通过一次异或变换进行转换，这样会克服二进制编码的Hamming悬崖。针对缺点二，可以采用实数编码，即用若干实数表示一个个体，然后在实数空间上进行遗传操作。
3.2初始群体设定由于遗传算法是对群体进行操作的，所以，必须为遗传操作准备一个由若干初始解组成的初始群体。群体设定主要包括两个方面：初始种群的产生和种群规模的确定。
图6群体设定步骤总结初始种群的个体是随机产生的，但最好采用如下策略设定：一是根据问题固有知识，设法把我最优解所占空间在整个空间中的分布范围，然后，在此分布范围内设定初始群体；二是先随机产生一定数目的个体，然后从中挑选最好的个体（类似于种子实体）加入到初始群体中，这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。针对于策略二这种反复迭代的描述，我认为类似于Bootstrapping策略。 种群规模影响遗传优化的结果和效率。当种群规模太小时，遗传算法的优化性能一般不会太好，容易陷入局部最优解。实际上，在学习完整个算法后，我发现针对于算法优化的一个关键环节就是在于如何“跳出”局部最优，进而“逼近”全局最优。这就让我联想到BP神经网络关于参数寻优部分的三种“跳出”策略，也可以说是启发式搜索策略。图7是总结的“跳出”策略。
图7“跳出”策略而种群规模太大也会带来弊端：一是群体越大，其适应度评估次数增加，所以计算量也增加，从而影响算法效率；二是群体中个体生存下来的概率大多采用和适应度成比例的方法，当群体中个体非常多时，少量适应度很高的个体会被选择而生存下来，但大多数个体却被淘汰，这会影响配对库的形成，从而影响交叉操作。
3.3设计适应度函数遗传算法遵循自然界优胜劣汰的原则，在进化搜索中基本不用外部信息，而是用适应度值表示个体的优劣，作为遗传操作的依据。适应度函数是用来区分群体中的个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯一依据。
图8适应度函数设计方法一般而言，适应度函数是由目标函数变换得到的。最直观的方法就是将待求解优化问题的目标函数作为适应度函数。 在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题。比如，如果群体中出现超级个体，即该个体的适应值大大超过群体的平均适应值，则按照适应值比例进行选择时，该个体很快就会在群体中占有绝对的比例，从而导致算法较早地收敛到一个局部最优点，这一现象称为过早收敛。这就是一种欺骗问题。 对适应度函数值域的某种映射变换称为适应度函数的尺度变换（定标）。尺度变换分为线性变换和非线性变换，这里重点介绍线性变换。 设原适应度函数为f，定标后的适应度函数为f’，则线性变换可采用下式表示为
f‘=af+bf^`=af+bf‘=af+b
系数a和b可以有多种途径设定，但要满足两个条件：
①变换后的适应度的平均值要等于原适应度平均值，以保证适应度为平均值的个体在下一代的期望复制数为1；②变换后适应度函数的最大值要等于原适应度函数平均值的指定倍数（相当于最小公倍数），以控制适应度最大的个体在下一代中的复制数。favg=afavg+bCmultfavg=afmax+bf_{avg}=af_{avg}+b\C_{mult}f_{avg}=af_{max}+bfavg=afavg+bCmultfavg=afmax+b
根据上述条件得出的推导公式，通过简单的联立方程组求解即可得出线性变换的系数a和b。 线性变换法变换了适应度之间的差距，保持了种群的多样性。如果种群里某些个体适应度远远低于平均值时，甚至出现负数，为满足最小适应度非负的条件，可以满足进行如下变换：
favg=afavg+b0=afmin+bf_{avg}=af_{avg}+b\0=af_{min}+bfavg=afavg+b0=afmin+b
这是我根据书上结果反推得出的推导公式。通过简单的计算即可得出适应值非负条件下的系数a和b。与基础条件不同之处在于将可能为负值的变换后的适应度置为0.
3.4遗传操作3.4.1选择选择操作也称为复制操作是从当前群体中按照一定概率选出优良的个体，使他们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值。 在遗传算法中，哪个个体被选择进行交叉是按照概率进行的。适应度大的个体被选择的概率大，但不是说一定能够被选上。同样，适应度小的个体被选择的概率小，但也可能被选上。这体现了遗传算法的随机性的特点。 适应度比例方法非常容易理解，就是按个体适应度在整个种群总适应度的所占比例分配概率。而排序方法根据适应度大小顺序对群体中个体进行排序，然后把事先设计好的概率按排序分配给个体，作为各自的选择概率。选择概率仅仅取决于个体在种群中的序位，而不是实际的适应度值。
图9选择流程及方法总结表2选择个体方法总结选择个体方法概述轮盘赌选择先按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉锦标赛选择从群体中随机选择k个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止最佳个体保存方法把群体中适应度最高的一个或者多个个体不进行交叉而直接复制到下一代中，保证遗传算法终止时候得到的最后结果一定是历代出现过的最高适应度的个体3.4.2交叉当两个生物体配对或者复制时，它们的染色体相互混合，产生一个由双方基因组成的全新的染色体组。这一过程称为重组或者交叉。这里的交叉操作就是高中生物中的AB和Ab进行交配产生新的基因型的过程。
图10交叉算子总结简单描述部分匹配交叉PMX。先依据均匀随机分布产生两个交叉点，定义两点之间的区域为一匹配区域，并使用位置交换操作交换两个父串的匹配区域。现在举例说明：
A=984|567|132B=871|239|546首先交换A和B的两个匹配区域，得到
A=984|239|132B=871|567|546显然，根据出现的重复任务，这就是非法调度。解决方法是将匹配区域外出现的重复任务，按照匹配区域内的位置映射关系进行交换，进而使排列成为可行调度。进一步解释，根据匹配区域的位置位置映射关系，即“2-5、3-6、9-7”，先对A中出现的重复任务“2、3”和“9”进行替换（不存在顺序关系，“3，2”也是重复的），即替换成“5，6，7”，然后将替换掉的字符“2，3，9”补到对应的B中所出现空缺的位置。最后结果即为
A=784|239|165B=891|567|243实验表明交叉概率通常取值为0.7左右是理想的。每次从群体中选择两个染色体，同时生成0和1之间的一个随机数，然后根据这个随机数确定这两个染色体是否需要交叉。如果随机数低于交叉概率，就进行交叉。
3.4.3变异对于变异操作，可以理解为高中生物中的加一段染色体或者替换染色体中的某一基因段等操作。在遗传算法中，变异是将个体编码的一些位进行随机变化。变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。变异操作是按位进行的，即把某一位的内容进行变异。变异概率是在一个染色体中按位进行变化的概率。主要的变异方法如图11所示。
图11变异算子总结在遗传算法中，变异属于辅助性的搜索操作（在做高中生物时，变异也属于题目需要特别提示的内容，并非必须）。变异概率一般不能大，以防止群体中重要的、单一的基因可能被丢失。实际上，变异概率太大将使得遗传算法趋于纯粹的随机搜索。
4基本遗传算法总结图12为基本遗传算法的流程图。遗传算法是一个利用随机技术来指导对一个编码的参数空间进行高效率搜索的方法，而不是无方向的随机搜索。许多传统搜索方法都是单解搜索方法，遗传算法采用群体搜索策略，即采用同时处理群体中多个个体的方法，同时对搜索空间中的多个解进行评估，从而使遗传算法具有较好的全局搜索性能，减少了陷于局部优解的风险，但不能保证每次都得到全局最优解。显而易见，遗传算法本身十分易于并行化。 在基本遗传算法中，基本上不用搜索空间的知识或其他辅助信息，而仅仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换。特别是遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域也可以任意设定。对适应度函数的唯一要求就是能够算出可以比较的正值。
图12基本遗传算法流程图5遗传算法改进接下来的遗传算法改进，实际上就是针对与图12的基本遗传算法流程进行改进。下面将简述三种改进算法在哪一环节进行了改进。
5.1双倍体遗传算法上文阐述的基本遗传算法属于单倍体遗传，每个基因型由一条染色体（也就是基因型AB，分别只有一个等位基因A和B）。显然，大多数动物和高级植物都采用双倍体遗传（也就是AaBb），即每个基因型由一对染色体决定。这势必会出现显隐性遗传问题。 那具体在图12的哪一部分作出调整呢？须知双倍体遗传算法采用显性遗传，并且提供了一种记忆以前有用的基因块功能。 进一步而言，在选择操作中，按照显性染色体的选择概率将个体复制到下一代群体中；同时，在交叉操作中，两个体的显性染色体和隐形染色体分别进行交叉操作；在变异操作中，显性染色体按照正常的变异概率执行操作，隐形染色体按照较大的概率进行操作。 与基本遗传算法的一个显著区别在于，执行完上述操作后，会再增加一个显隐性重排操作，因为每一轮迭代之后，并不能确定显性和隐性的在下一轮划分，有了显隐性重排操作，增加了算法的随机性，也提高了隐性染色体里优良基因的存活概率。具体来说，个体中适应度较大的染色体设定为下一轮的显性染色体，适应度较小的染色体设定为下一轮的隐性染色体。
5.2双种群遗传算法双种群遗传算法意在突破平衡态——长时间进化后某些特征处于相对优势的状态，实际上，这再次体现出算法在接近全力“逼近”全局最优，是一个具有优秀扩展性的启发式搜索算法。 对比图12，主要区别在于双种群同时进行图中操作，但在执行完上述操作后，增加一步杂交操作，即交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态以达到更高的平衡态，有利于算法跳出局部最优。 杂交算子，具体来说，设种群A和种群B，当两种群均完成了选择、交叉和变异操作后，产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者，打破平衡态。“产生随机数num”又一次体现了算法的随机性。
5.3自适应遗传算法自适应遗传算法的改进关键点在于交叉概率和变异概率，使两概率能随适应度变化自动改变。这样即可保证算法可以跳出局部最优情况，也可以利于优良个体的生存。所以，自适应遗传算法在保持群体多样性的同时，保证遗传算法的收敛性。 对比图12，区别在于交叉算子中，要使用自适应公式计算交叉概率，然后产生随机数，如果小于计算后的概率，那么交叉该对染色体对；同理，在变异算子中，也使用自适应公式计算变异概率，并产生随机数，若小于计算后的概率，那么变异该染色体。
6参考文献王万良.人工智能导论(第4版)[M]:高等教育出版社,2017.