王志强-计算智能-报告

《王志强-计算智能-报告》由会员分享，可在线阅读，更多相关《王志强-计算智能-报告（70页珍藏版）》请在金锄头文库上搜索。

1、计算智能 王志强，201510105289概要p 概述：什么是计算智能？p 算法简介：计算机智能方法有哪几种，是怎么实现的？p 经典计算智能算法p 模拟退火算法(1953)p 遗传算法(1960s)p 蚁群优化算法(1990s)p 粒子群优化算法(1995)p 新兴计算智能方法p 黑洞优化算法 (2013, Information Sciences)p 化学反应优化算法 (2015, Information Sciences)p 应用：计算智能算法可以用来做什么？计算智能简介p Generally, computational intelligence is a set of nature-i

2、nspired computational methodologies and approaches to address complex real-world problems to which mathematical or traditional modelling can be useless for a few reasons: the processes might be too complex for mathematical reasoning, it might contain some uncertainties during the process, or the pro

3、cess might simply be stochastic in nature.p 计算智能是受到大自然智慧和人类智慧的启发而设计出的 一类算法的统称。p 近代科学技术发展的显著特点之一是生命科学与工程科学的相互交叉、相互渗透、相互促进其他有代表性的演化算法p 宇宙大爆炸算法: Big BangBig Crunch, 2006p 智慧水滴算法：intelligent water drops, 2007p 依据自然界溪水大河大江海洋的原理p 蜜蜂社交算法:honey bee mating optimization, 2007p 曲谱算法：harmony search optimization

4、, 2009 p GSA：gravitational search algorithms, 2009p 依据牛顿运动定律提出p 萤火虫算法：firefly algorithm, 2010p 蝙蝠算法：Bat Algorithm, 2011p 模拟退火算法模拟退火算法及模型 (1)p 模拟退火算法最早的思想由Metropolis等（1953 ）提出，1983年Kirkpatrick等将其应用于组合优 化。p 算法的目的p 解决NP复杂性问题；p 克服优化过程陷入局部极小；p 克服初值依赖性。p 退火是指将固体加热到足够高的温度，使分子呈 随机排列状态，然后逐步降温使之冷却，最后分子 以低能状态排

5、列，固体达到某种稳定状态。模拟退火算法及模型 (2)p物理退火过程p加温过程增强粒子的热运动，消除系统原先可能存 在的非均匀态；p等温过程对于与环境换热而温度不变的封闭系统， 系统状态的自发变化总是朝自由能减少的方向进行，当 自由能达到最小时，系统达到平衡态；p冷却过程使粒子热运动减弱并渐趋有序，系统能量 逐渐下降，从而得到低能的晶体结构。p Metropolis发现，加热后的金属总是自发地趋于 低温后稳定，低温稳定点和优化问题的最值点似乎 存在着某种内在关联！模拟退火算法及模型 (3)p 从热力学现象中寻找启发：p 温度越低，物体的能量状态越低，到达足够的低点时 ，液体开始冷凝与结晶，在结晶

6、状态时，系统的能量状 态最低。缓慢降温（退火，annealing）时，可达到最低 能量状态；但如果快速降温（淬火，quenching），会导 致不是最低能态的非晶形。p 大自然知道慢工出细活：p 缓缓降温，使得物体分子在每一温度时，能够有足够 时间找到安顿位置，则逐渐地，到最后可得到最低能态 ，系统最稳定。p 模仿自然界中的退火首先要理解物理中的退火模型物理退火过程 (1)p 在温度T，分子停留在状态r满足Boltzmann概率分 布物理退火过程 (2)p 0模拟退火算法基本思想：在一定温度下，搜索从一个状态 随机地变化到另一个状态；随着温度的不断下降直到最低温度 ，搜索过程以概率1停留在最优

7、解物理退火过程 (3)p Boltzman概率分布告诉我们：（1）在同一个温度，分子停留在能量小状态的概率大于 停留在能量大状态的概率（2）温度越高，不同能量状态对应的概率相差越小；温 度足够高时，各状态对应概率基本相同。（3）随着温度的下降，能量最低状态对应概率越来越大 ；温度趋于0时，其状态趋于1物理退火过程 (4)p 模拟退火算法及模型 (1)p Metropolis准则（1953）以概率接受新状态p 固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法（计算机随机模拟方法）加以模拟。p 若在温度T，当前状态i 新状态jp若Ej=randrom0,1s=sj;Until 抽样

8、稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until 算法终止准则满足； 输出算法搜索结果。遗传算法遗传算法（Genetic algorithms）p 遗传算法是20世纪6070年代主要由美国 Michigon 大学 John Holland 教授提出. 其内涵 哲理启迪于自然界生物从低级、简单到高级、复杂 ，乃至人类这样一个漫长而绝妙的进化过程. 借鉴 Darwin 的物竞天择、优胜劣汰、适者生存的自然 选择和自然遗传的机理. 其本质是一种求解问题的 高效并行全局搜索方法，它能在搜索过程中自动获 取和积累有关搜索空间的知识，并自适应地控制搜 索过程以求得最优解.遗传算法

9、的思想p 从一初始化的群体出发， 通过随机选择(复制)（ 使群体中优秀的个体有更多的机会传给下一代）， 交叉（体现了自然界中群体内个体之间的信息交换 ），和变异（在群体中引入新的变种确保群体中信 息的多样性）等遗传操作，使最具有生存能力的染 色体以最大可能生存, 群体一代一代地进化到搜索 空间中越来越好的区域 .p 关键是要对问题的决策变量进行编码，使之适宜 使用选择、交叉、变异3个算子进行操作.遗传算法的过程p 初始化：设置进化代数计数器t=0，设置最大进化代数T， 随机生成M个个体作为初始群体P(0)。p 个体评价：计算群体P(t)中各个个体的适应度。p 选择运算:将选择算子作用于群体。

10、交叉运算：将交叉算 子作用于群体。遗传算法中起核心作用的就是交叉算子。变 异运算：将变异算子作用于群体。即是对群体中的个体串的 某些基因座上的基因值作变动。p 群体P(t)经过选择、交叉、变异运算之后得到下一代群体 P(t+1)。p 终止条件判断:若t=T,则以进化过程中所得到的具有最大 适应度个体作为最优解输出，终止计算。GA算法解题的具体步骤p 求解： ()=, ,p遗传算法求解该问题的思路：p 对问题进行合理的基因编码p 设计合适的适应函数p 确定群体的规模p 迭代至终止条件p 选择p 交叉p 变异遗传算法的编码p 一次迭代的结果 . (交叉概率 Pc = 1，变异概率 Pm = 0.0

11、2)x 值 群体 xif (xi) 概率分布 种群 交叉位 交叉结果 变异？新群体 x 值 f (xi) 1/16 1/4 3/16 7/80001 0100 0011 11100.99 0.93 0.96 0.230.318 0.299 0.308 0.0750001 0100 0001 00110000 0101 0001 0011N Y N N0000 1101 0001 00110 13/16 1/16 3/161 0.34 0.99 0.96第 0 代 总和 3.133 最小值0.234 平均值 0.7833 最大值 0.996;第 1 代 总和 3.301 最小值0.340 平均值

12、 0.8253 最大值 1 .遗传算法的优越性p 作为数值求解方法，具有普适性 . 对目标函数几 乎没有要求，总能以极大的概率找到全局最优解；p GA 在求解很多组合优化问题时，不需要很高的技 巧和对问题有非常深入的了解，在给问题的决策变量编码后，其计算过程是比较简单的，且可较快地 得到一个满意解；p 与其他启发式算法有较好的兼容性，易与别的技 术相结合，形成性能更优的问题求解方法 .蚁群优化算法蚁群优化算法简介ACO是一种全局最优化搜索方法，解决典型组 合优化问题具有明显的优越性，具有鲁棒性 强、全局搜索、并行分布式计算、易于其他 算法结合的优点。蚁群优化算法（ACO）由Dorigo（多里格

13、） 等人于1991年提出，是模拟自然界真实蚂蚁 觅食过程的一种随机搜素算法。提 出性 质蚁群优化算法基本原理(1)A （1）蚂蚁没有发育完全的视觉 感知系统，其在寻找食物的过 程中是如何选择路径的呢？ （2）蚂蚁往往像军队般有纪 律、有秩序地搬运食物，它们 通过什么方式进行群体间的交 流协作呢？信息素是一种化学物质，由蚂蚁自身释放，是实现蚁群内 间接通信的物质。蚂蚁随机选择路径，但是能感知当前地 面上的信息素浓度，并倾向于往信息素浓度高的方向前进。信息素蚁群优化算法基本原理(2)双桥实验蚁穴食物源（a）两个路具有同样的长度自身催化（正反馈）过程自身催化（正反馈）过程1.起初两条分支上不存在信息

14、 素，蚂蚁以相同的概率进行选择。 2.随机波动的出现，选择某一条分支的蚂蚁数量可能比另外一条多。 3.实验最终结果：所有的蚂蚁都会选择同一分支。蚁群优化算法基本原理(3)双桥实验（b）两条分支具有不同长度1.起初两条分支上不存在信息 素，蚂蚁随机选择一条路径 。 2.短分支上的信息素积累速度 比长分支的快。 3.实验最终结果：所有的蚂蚁都会选择较短的分支。 4.有很小比例的蚂蚁会选择较 长的分支。路径探索蚁群优化算法基本原理(4)蚁穴食物源（c）30分钟后添加短分支30分钟后双桥实验1.实验最终结果：除了极少的蚂蚁选择较短的分支以外，整个群体几乎都困在较长的分支上。 2.长分支上的信息素浓度高

15、，而信息素的蒸发速度过于缓慢。蚁群优化算法基本原理(5)双桥实验总结1 1选择路径是一个概率随机过程，启发式信 息多以及信息浓度大的路径被选中概率更 大。2 2信息素会不断的蒸发。3 3路径探索也是必需的，否则容易陷入 局部最优。蚁群优化算法基本原理(6)自然界蚂蚁觅食行为蚁群优化算法蚁群搜索空间的一组有效解问题的搜索空间信息素浓度变量一个有效解问题的最优解觅食空间信息素蚁巢到食物的一条路径找到的最短路径对 应 关 系蚂蚁间的通信启发式搜索蚁群优化算法基本原理(7)p 蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并 倾向于往信息素浓度高的方向行进。信息素由蚂

16、蚁自身释放，是实现蚁群内间接通信的物质。 由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累 速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选 择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上 行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。算法流程(1)路径构建 每只蚂蚁都随机选择 一个城市作为其出发 城市，并维护一个路 径记忆向量，用来存 放该蚂蚁依次经过的 城市。蚂蚁在构建路 径的每一步中，按照 一个随机比例规则选 择下一个要到达的城 市。ACO基本要素信息素更新 当所有蚂蚁构建完路 径后，算法将会对所 有的路径进行全局信 息素的更新。注意， 我们所描述的是AS的 ant-cycle版本，更 新是在全部蚂蚁均完 成了路径的构造后才 进行的，信息素的浓 度变化与蚂蚁在这一 轮中构建的路径长度 相关。算法流程(2