王志强-计算智能-报告

计算智能王志强，201510105289概要

概述：什么是计算智能？

算法简介：计算机智能方法有哪几种，是怎么实现的？

经典计算智能算法模拟退火算法(1953)遗传算法(1960s)

蚁群优化算法(1990s)

粒子群优化算法(1995)新兴计算智能方法

黑洞优化算法(2013,InformationSciences)

化学反应优化算法(2015,InformationSciences)应用：计算智能算法可以用来做什么？计算智能简介

Generally,computationalintelligenceisasetofnature-inspiredcomputationalmethodologiesandapproachestoaddresscomplexreal-worldproblemstowhichmathematicalortraditionalmodellingcanbeuselessforafewreasons:theprocessesmightbetoocomplexformathematicalreasoning,itmightcontainsomeuncertaintiesduringtheprocess,ortheprocessmightsimplybestochasticinnature.

计算智能是受到大自然智慧和人类智慧的启发而设计出的一类算法的统称。

近代科学技术发展的显著特点之一是生命科学与工程科学的相互交叉、相互渗透、相互促进其他有代表性的演化算法

宇宙大爆炸算法:BigBang–BigCrunch,2006智慧水滴算法：intelligentwaterdrops,2007

依据自然界溪水大河大江海洋的原理蜜蜂社交算法:honeybeematingoptimization,2007

曲谱算法：harmonysearchoptimization,2009

GSA：gravitationalsearchalgorithms,2009

依据牛顿运动定律提出

萤火虫算法：fireflyalgorithm,2010

蝙蝠算法：BatAlgorithm,

2011…模拟退火算法模拟退火算法及模型(1)

模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。

算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。模拟退火算法及模型(2)物理退火过程加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。Metropolis发现，加热后的金属总是自发地趋于低温后稳定，低温稳定点和优化问题的最值点似乎存在着某种内在关联！模拟退火算法及模型(3)

从热力学现象中寻找启发：温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温（退火，annealing）时，可达到最低能量状态；但如果快速降温（淬火，quenching），会导致不是最低能态的非晶形。

大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最稳定。

模仿自然界中的退火首先要理解物理中的退火模型物理退火过程(1)在温度T，分子停留在状态r满足Boltzmann概率分布物理退火过程(2)

<1>0模拟退火算法基本思想：在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率1停留在最优解物理退火过程(3)Boltzman概率分布告诉我们：（1）在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率（2）温度越高，不同能量状态对应的概率相差越小；温度足够高时，各状态对应概率基本相同。（3）随着温度的下降，能量最低状态对应概率越来越大；温度趋于0时，其状态趋于1物理退火过程(4)

模拟退火算法及模型(1)Metropolis准则（1953）——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟。

若在温度T，当前状态i→新状态j若Ej<Ei，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。模拟退火算法及模型(2)p=exp[-(Ej-Ei)/kBT]在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。模拟退火算法及模型(3)组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量模拟退火算法及模型(4)基本步骤给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]

s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。遗传算法遗传算法（Geneticalgorithms）遗传算法是20世纪60~70年代主要由美国Michigon大学JohnHolland教授提出.其内涵哲理启迪于自然界生物从低级、简单到高级、复杂，乃至人类这样一个漫长而绝妙的进化过程.借鉴Darwin的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传的机理.其本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解.遗传算法的思想从一初始化的群体出发，通过随机选择(复制)（使群体中优秀的个体有更多的机会传给下一代），交叉（体现了自然界中群体内个体之间的信息交换），和变异（在群体中引入新的变种确保群体中信息的多样性）等遗传操作，使最具有生存能力的染色体以最大可能生存,群体一代一代地进化到搜索空间中越来越好的区域.

关键是要对问题的决策变量进行编码，使之适宜使用选择、交叉、变异3个算子进行操作.遗传算法的过程初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。个体评价：计算群体P(t)中各个个体的适应度。

选择运算:将选择算子作用于群体。

交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。GA算法解题的具体步骤

求解：𝐦𝐚𝐱𝒇(𝒙)=𝟏−𝒙^𝟐,𝒙∈[𝟎,𝟏]遗传算法求解该问题的思路：

对问题进行合理的基因编码

设计合适的适应函数

确定群体的规模

迭代至终止条件

选择

交叉

变异遗传算法的编码

一次迭代的结果.(交叉概率Pc

=1，变异概率Pm=0.02)x值群体

xif(xi)概率分布种群交叉位交叉结果变异？新群体x值f(xi)1/161/43/167/800010100001111100.990.930.960.230.3180.2990.3080.07500010100000100110000010100010011NYNN0000110100010011013/161/163/1610.340.990.96第0代总和3.133最小值0.234平均值0.7833最大值0.996;第1代总和3.301最小值0.340平均值0.8253最大值1.遗传算法的优越性作为数值求解方法，具有普适性.对目标函数几乎没有要求，总能以极大的概率找到全局最优解；

GA在求解很多组合优化问题时，不需要很高的技巧和对问题有非常深入的了解，在给问题的决策变量编码后，其计算过程是比较简单的，且可较快地得到一个满意解；

与其他启发式算法有较好的兼容性，易与别的技术相结合，形成性能更优的问题求解方法.蚁群优化算法蚁群优化算法简介ACO是一种全局最优化搜索方法，解决典型组合优化问题具有明显的优越性，具有鲁棒性强、全局搜索、并行分布式计算、易于其他算法结合的优点。蚁群优化算法（ACO）由Dorigo（多里格）等人于1991年提出，是模拟自然界真实蚂蚁觅食过程的一种随机搜素算法。提出性质蚁群优化算法基本原理(1)

A

（1）蚂蚁没有发育完全的视觉感知系统，其在寻找食物的过程中是如何选择路径的呢？（2）蚂蚁往往像军队般有纪律、有秩序地搬运食物，它们通过什么方式进行群体间的交流协作呢？信息素是一种化学物质，由蚂蚁自身释放，是实现蚁群内间接通信的物质。蚂蚁随机选择路径，但是能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向前进。信息素蚁群优化算法基本原理(2)双桥实验蚁穴食物源（a）两个路具有同样的长度自身催化（正反馈）过程1.起初两条分支上不存在信息素，蚂蚁以相同的概率进行选择。2.随机波动的出现，选择某一条分支的蚂蚁数量可能比另外一条多。3.实验最终结果：所有的蚂蚁都会选择同一分支。蚁群优化算法基本原理(3)双桥实验（b）两条分支具有不同长度1.起初两条分支上不存在信息素，蚂蚁随机选择一条路径。2.短分支上的信息素积累速度比长分支的快。3.实验最终结果：所有的蚂蚁都会选择较短的分支。4.有很小比例的蚂蚁会选择较长的分支。路径探索蚁群优化算法基本原理(4)蚁穴食物源（c）30分钟后添加短分支30分钟后双桥实验1.实验最终结果：除了极少的蚂蚁选择较短的分支以外，整个群体几乎都困在较长的分支上。2.长分支上的信息素浓度高，而信息素的蒸发速度过于缓慢。蚁群优化算法基本原理(5)双桥实验总结1选择路径是一个概率随机过程，启发式信息多以及信息浓度大的路径被选中概率更大。2信息素会不断的蒸发。3路径探索也是必需的，否则容易陷入局部最优。蚁群优化算法基本原理(6)自然界蚂蚁觅食行为蚁群优化算法蚁群搜索空间的一组有效解问题的搜索空间信息素浓度变量一个有效解问题的最优解觅食空间信息素蚁巢到食物的一条路径找到的最短路径对应关系蚂蚁间的通信启发式搜索蚁群优化算法基本原理(7)蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。算法流程(1)路径构建每只蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。ACO基本要素信息素更新当所有蚂蚁构建完路径后，算法将会对所有的路径进行全局信息素的更新。注意，我们所描述的是AS的ant-cycle版本，更新是在全部蚂蚁均完成了路径的构造后才进行的，信息素的浓度变化与蚂蚁在这一轮中构建的路径长度相关。算法流程(2)蚂蚁系统（AntSystem，AS）是最基本的ACO算法，是以TSP作为应用实例提出的。假设四个城市间的距离矩阵如下：用贪婪算法求解：例如从城市A出发得ACDBA路径长度为：1+2+4+3=10贪婪算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。算法流程(3)AS算法（蚂蚁圈版本）对TSP的求解流程主要有两大步骤：路径构建和信息素更新1.路径构建

算法流程(4)由公式知，长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。和是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重。时算法演变成了传统的随机贪婪算法；当蚂蚁完全只根据信息素浓度确定路径，算法快速收敛，构建出的最优路径与实际目标有较大的差异。实验表明：设置，比较合适。算法流程(5)2.信息素更新初始化时：算法流程(6)参数设置参数参数的意义蚂蚁数目m影响着算法的搜素能力和计算量信息素挥发因子影响蚂蚁个体之间相互影响的强弱，关系到算法的全局搜索能力和收敛速度初始信息素量决定算法在初始化阶段的探索能力，影响算法的收敛速度算法流程(7)结束条件1将最大循环数设定为500、1000、5000，或者最大的函数评估次数，等等。也可以使用算法求解到一个可接受的解作为终止条件。23当算法在很长一段迭代中没有得到任何改善时。算法流程(8)初始化每条边上的信息素量1对每只蚂蚁，随机选择一个出发城市2对每只蚂蚁根据启发式信息和信息素浓度选择下一个访问城市3计算每只蚂蚁构建的路径长度，更新每条边上的信息素量4判断是否满足结束条件5粒子群优化算法粒子群优化算法简介

由Kennedy和Eberhart于1995年提出．群体迭代，粒子在解空间追随最优的粒子进行搜索.

简单易行

粒子群算法:收敛速度快

设置参数少

粒子群优化算法

(ParticleSwarmOptimization,PSO)粒子群优化算法的由来PSO算法最早源于对鸟群觅食行为的研究。研究者发现鸟群在飞行过程中经常会突然改变方向、散开、聚集,其行为不可预测,但其整体总保持一致性,个体与个体间也保持着最适宜的距离。通过对类似生物群体的行为的研究,发现生物群体中存在着一种社会信息共享机制,它为群体的进化提供了一种优势,这也是PSO算法形成的基础。

设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在那里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO的直观描述(1)

在PSO中，每个优化问题的潜在解都可以想象成D维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值（FitnessValue）。搜索正是在这样一群随机粒子而组成的一个种群中进行的。

PSO算法中每个粒子就是解空间中的一个解,它根据自己的飞行经验和同伴的飞行经验来调整自己的飞行。每个粒子在飞行过程所经历过的最好位置,就是粒子本身找到的最优解。整个群体所经历过的的最好位置,就是整个群体目前找到的最优解。前者叫做个体极值(pBest),后者叫做全局极值(gBest)。每个粒子都通过上述两个极值不断更新自己,从而产生新一代群体。PSO的直观描述(2)适应值每个优化问题的解都是搜索空间中的一只鸟。称之为“粒子(Particle)”。粒子所有的粒子都有一个由被优化的函数决定的适应值(FitnessValue)，表明现在所处位置的优劣,用于评价粒子的“好坏”程度。速度每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO的数学描述(1)（1）假设在一个N维空间进行搜索，由m个粒子组成初始种群X。粒子i的位置信息用N维向量来表示：粒子i的速度为：i=1,2,…mi=1,2,…mPSO的数学描述(2)：是粒子i在第k次迭代中的速度与位置；（2）计算所有m个粒子的适应值。在找到两个最优解后，粒子i即可根据下式来更新自己的速度和位置：PSO的数学描述(3)(1)动量部分，表示粒子对当前自身运动状态的信任，为粒子提供了一个必要动量，使其依据自身速度进行惯性运动；对应多样化(diversification)的特点(2)个体认知部分，代表了粒子自身的思考行为，鼓励粒子飞向自身曾经发现的最优位置；(3)社会认知部分，表示粒子间的信息共享与合作，它引导粒子飞向粒子群中的最优位置。(1)对应多样化(diversification)的特点(2)(3)对应于搜索过程的集中化特点，三项之间的相互平衡和制约决定了算法的主要性能。PSO的数学描述(4)参数说明及意义(1)m：种群大小，i=1，2，3…，m。种群大小的选择视具体问题而定，一般设置粒子数为20-50。对于大部分的问题10个粒子已经可以取得很好的结果，不过对于比较难的问题或者特定类型的问题，也可以取到100或200。粒子数目越多，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，算法运行的时间也较长。参数说明及意义(2)c1和c2：学习因子或称加速系数。分别调节向Pbest和Gbest方向飞行的最大步长，反映粒子个体经验和群体经验对粒子运行轨迹的影响，反映粒子群之间的信息交流。如c1=0，则粒子只有群体经验，收敛速度较快，但易陷入局部最优；如c2=0，则无群体共享信息，即运行了m个各行其是的粒子，得到解的几率非常小，因此一般设置c1=c2。使二者具有相同重要的影响力，最优解更精确。较低的c1和c2值使得粒子徘徊在远离目标的区域，较高则产生陡峭的运动或越过目标区域，通常取c1=c2=2，并且范围在0和4之间参数说明及意义(3)rand1和rand2：介于［0,1］的随机数，增加粒子飞行的随机性。：是整个种群的全局极值点的位置。：是粒子i在个体极值点的位置；迭代终止条件：一般设为最大迭代次数Tmax、计算精度或最优解的最大停滞步数△t。参数说明及意义(4)最大速度限制vmax：为防止粒子远离搜索空间，粒子的每一维速度应满足[－vmax，+vmax]之间，假设搜索空间的定义为区间[－xmax，+xmax]。当vi≥vmax时，令vi=xmax

当vi≤-vmax时，令vi=-xmax

vmax如果太大，粒子们也许会飞过优秀区域，如果该值太小，则粒子们可能无法对局部最优区域以外的区域进行充分的探测，而陷入局部最优。PSO算法流程黑洞优化算法黑洞现象

黑洞算法Star可能的解Blackhole最优解化学反应优化算法化学反应优化原理

化学反应总是朝着体系熵增加的方向进行，进行到一定程度后停止

化学反应和优化问题有着诸多相似的地方，化学反应达到平衡时的元素状态可以认为是优化问题的最优解

化学元素一个可能的解

化学反应达到平衡寻找到了最优解化学反应的描述

CRA算法流程图CRA中的基本概念(1)

CRA中的基本概念(2)

优化实例实例解析(1)假设四个城市间的距离矩阵如下：用贪婪算法求解：例如从城市A出发得ACDBA路径长度为：1+2+4+3=10假设蚂蚁种群的规模m