logo资料库

智能算法学习笔记 pdf版.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.16M 资料格式：pdf 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    智能算法学习笔记 作者:hisky(苍竹琴声) 这是我自己看智能算法的时候的一些笔记，贴出来给大家看一下，如果有理解错误的地方，千 万请指出，小生在这里先谢过了^_^ 一个比方 在工程实践中，经常会接触到一些比较“新颖”的算法或理论，比如模拟退火，遗传算法，禁忌 搜索，神经网络等。这些算法或理论都有一些共同的特性（比如模拟自然过程），通称为“智 能算法”。它们在解决一些复杂的工程问题时大有用武之地。 这些算法都有什么含义？首先给出个局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻： 为了找出地球上最高的山，一群有志气的兔子们开始想办法。 1．兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆 朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。 2．兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但 是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。 3．兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道 自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会 找到珠穆朗玛峰。这就是遗传算法。 4.兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一 座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。 智能优化算法的概述 智能优化算法要解决的一般是最优化问题。最优化问题可以分为（1）求解一个函数中，使得 函数值最小的自变量取值的函数优化问题和（2）在一个解空间里面，寻找最优解，使目标函 数值最小的组合优化问题。典型的组合优化问题有：旅行商问题（Traveling Salesman Problem，TSP），加工调度问题（Scheduling Problem），0－1 背包问题（Knapsack Problem），以及装箱问题（Bin Packing Problem）等。 优化算法有很多，经典算法包括：有线性规划，动态规划等；改进型局部搜索算法包括爬山 法，最速下降法等，本文介绍的模拟退火、遗传算法以及禁忌搜索称作指导性搜索法。而神经 网络，混沌搜索则属于系统动态演化方法。 优化思想里面经常提到邻域函数，它的作用是指出如何由当前解得到一个（组）新解。其具体 实现方式要根据具体问题分析来定。 一般而言，局部搜索就是基于贪婪思想利用邻域函数进行搜索，若找到一个比现有值更优的解 就弃前者而取后者。但是，它一般只可以得到“局部极小解”，就是说，可能这只兔子登“登泰 山而小天下”，但是却没有找到珠穆朗玛峰。而模拟退火，遗传算法，禁忌搜索，神经网络等 从不同的角度和策略实现了改进，取得较好的“全局最小解”。 模拟退火算法（Simulated Annealing，SA） 模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热的时 候，粒子间的布朗运动增强，到达一定强度后，固体物质转化为液态，这个时候再进行退火， 粒子热运动减弱，并逐渐趋于有序，最后达到稳定。 模拟退火的解不再像局部搜索那样最后的结果依赖初始点。它引入了一个接受概率 p。如果新 的点（设为 pn）的目标函数 f（pn）更好，则 p=1，表示选取新点；否则，接受概率 p 是当前 点（设为 pc）的目标函数 f（pc），新点的目标函数 f（pn）以及另一个控制参数“温度”T 的 函数。也就是说，模拟退火没有像局部搜索那样每次都贪婪地寻找比现在好的点，目标函数差 一点的点也有可能接受进来。随着算法的执行，系统温度 T 逐渐降低，最后终止于某个低温， 在该温度下，系统不再接受变化。
    模拟退火的典型特征是除了接受目标函数的改进外，还接受一个衰减极限，当 T 较大时，接受 较大的衰减，当 T 逐渐变小时，接受较小的衰减，当 T 为 0 时，就不再接受衰减。这一特征意 味着模拟退火与局部搜索相反，它能避开局部极小，并且还保持了局部搜索的通用性和简单 性。 在物理上，先加热，让分子间互相碰撞，变成无序状态，内能加大，然后降温，最后的分子次 序反而会更有序，内能比没有加热前更小。就像那只兔子，它喝醉后，对比较近的山峰视而不 见，迷迷糊糊地跳一大圈子，反而更有可能找到珠峰。 值得注意的是，当 T 为 0 时，模拟退火就成为局部搜索的一个特例。 模拟退火的伪码表达： procedure simulated annealing begin t:=0; initialize temperature T select a current string vc at random; evaluate vc; repeat repeat select a new string vn in the neighborhood of vc; (1) if f(vc)
    “物竞天择，适者生存”，是进化论的基本思想。遗传算法就是模拟自然界想做的事。遗传算法 可以很好地用于优化问题，若把它看作对自然过程高度理想化的模拟，更能显出它本身的优 雅——虽然生存竞争是残酷的。 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进 行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设 定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、健壮性强、适于并行处理以及高 效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能 算法之一。 遗传算法的伪码： procedure genetic algorithm begin initialize a group and evaluate the fitness value ; （1） while not convergent （2） begin select; （3） if random[0,1]
    导，是否连续等性质，所以适用性很强；并且，它开始就对一个种群进行操作，隐含了并行 性，也容易找到“全局最优解”。 禁忌搜索算法（Tabu Search，TS） 为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对 某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分 局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了 泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找 到的几个山峰一比较，珠穆朗玛峰脱颖而出。 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有 一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的 兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已 经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌 搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归 队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就 是说，当一个有兔子留守的地方优越性太突出，超过了“best to far”的状态，就可以不顾及 有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这 三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。 伪码表达： procedure tabu search; begin initialize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va>best_to_far then {va is a string in the tabu list} begin cur:=va; let va take place of the oldest string in the tabu list; best_to_far:=va; end else begin cur:=vn; let vn take place of the oldest string in the tabu list; end; until (termination-condition); end; 以上程序中有关键的几点： （1）禁忌对象：可以选取当前的值（cur）作为禁忌对象放进 tabu list，也可以把和当然值 在同一“等高线”上的都放进 tabu list。
    （2）为了降低计算量，禁忌长度和禁忌表的集合不宜太大，但是禁忌长度太小容易循环搜 索，禁忌表太小容易陷入“局部极优解”。 （3）上述程序段中对 best_to_far 的操作是直接赋值为最优的“解禁候选解”，但是有时候会 出现没有大于 best_to_far 的，候选解也全部被禁的“死锁”状态，这个时候，就应该对候选解 中最佳的进行解禁，以能够继续下去。 （4）终止准则：和模拟退火，遗传算法差不多，常用的有：给定一个迭代步数；设定与估计 的最优解的距离小于某个范围时，就终止搜索；当与最优解的距离连续若干步保持不变时，终 止搜索； 禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记 忆）达到接纳一部分较差解，从而跳出局部搜索的目的。 人工神经网络（Artificial Neural Network，ANN） 神经网络从名字就知道是对人脑的模拟。它的神经元结构，它的构成与作用方式都是在模仿人 脑，但是也仅仅是粗糙的模仿，远没有达到完美的地步。和冯·诺依曼机不同，神经网络计算 非数字，非精确，高度并行，并且有自学习功能。 生命科学中，神经细胞一般称作神经元，它是整个神经结构的最基本单位。每个神经细胞就像 一条胳膊，其中像手掌的地方含有细胞核，称作细胞体，像手指的称作树突，是信息的输入通 路，像手臂的称作轴突，是信息的输出通路；神经元之间错综复杂地连在一起，互相之间传递 信号，而传递的信号可以导致神经元电位的变化，一旦电位高出一定值，就会引起神经元的激 发，此神经元就会通过轴突传出电信号。 而如果要用计算机模仿生物神经，就需要人工的神经网络有三个要素：（1）形式定义人工神 经元；（2）给出人工神经元的连接方式，或者说给出网络结构；（3）给出人工神经元之间信 号强度的定义。 历史上第一个人工神经网络模型称作 M－P 模型，非常简单： 其中， 表示神经元 i 在 t 时刻的状态，为 1 表示激发态，为 0 表示抑制态； 是神经元 i 和 j 之间的连接强度； 表示神经元 i 的阈值，超过这个值神经元才能激发。 这个模型是最简单的神经元模型。但是功能已经非常强大：此模型的发明人 McCulloch 和 Pitts 已经证明，不考虑速度和实现的复杂性，它可以完成当前数字计算机的任何工作。 以上这个 M－P 模型仅仅是一层的网络，如果从对一个平面进行分割的方面来考虑的话，M－P 网络只能把一个平面分成个半平面，却不能够选取特定的一部分。而解决的办法就是“多层前 向网路”。 图 2 图 2 是多层前向网络的示意图。最下面的 称作输入层，最上面一层称作输出层，任何一个中 间层都接受来自前一层的所有输入，加工后传入后一层。每一层的神经元之间没有联系，输入 输出层之间也没有直接联系，并且仅仅是单向联系，没有反馈。这样的网络被称作“多层前向 网络”。数据在输入后，经过每一层的加权，最后输出结果。 图 3 如图 3，用可覆盖面来说明多层网络的功能：单层网络只能把平面分成两部分，双层网络就可 以分割任意凸域，多层网络则可以分割任意区域。 为了让这种网络有合适的权值，必须给网络一定的激励，让它自己学习，调整。一种方法称作 “向后传播算法（Back Propagation，BP）”，其基本思想是考察最后输出解和理想解的差异， 调整权值，并把这种调整从输出层开始向后推演，经过中间层，达到输入层。 可见，神经网络是通过学习来达到解决问题的目的，学习没有改变单个神经元的结构和工作方 式，单个神经元的特性和要解决的问题之间也没有直接联系，这里学习的作用是根据神经元之 间激励与抑制的关系，改变它们的作用强度。学习样本中的任何样品的信息都包含在网络的每 个权值之中。 BP 算法中有考察输出解和理想解差异的过程，假设差距为 w，则调整权值的目的就是为了使得 w 最小化。这就又包含了前文所说的“最小值”问题。一般的 BP 算法采用的是局部搜索，比如最
    速下降法，牛顿法等，当然如果想要得到全局最优解，可以采用模拟退火，遗传算法等。当前 向网络采用模拟退火算法作为学习方法的时候，一般成为“波尔兹曼网络”，属于随机性神经网 络。 在学习 BP 算法学习的过程中，需要已经有一部分确定的值作为理想输出，这就好像中学生在 学习的时候，有老师的监督。如果没有了监督，人工神经网络该怎么学习？ 就像没有了宏观调控，自由的市场引入了竞争一样，有一种学习方法称作“无监督有竞争的学 习”。在输入神经元 i 的若干个神经元之间开展竞争，竞争之后，只有一个神经元为 1，其他均 为 0，而对于失败的神经元，调整使得向对竞争有利的方向移动，则最终也可能在一次竞争中 胜利； 人工神经网络还有反馈网络如 Hopfield 网络，它的神经元的信号传递方向是双向的，并且引 入一个能量函数，通过神经元之间不断地相互影响，能量函数值不断下降，最后能给出一个能 量比较低的解。这个思想和模拟退火差不多。 人工神经网络应用到算法上时，其正确率和速度与软件的实现联系不大，关键的是它自身的不 断学习。这种思想已经和冯·诺依曼模型很不一样。 总结 模拟退火，遗传算法，禁忌搜索，神经网络在解决全局最优解的问题上有着独到的优点，并 且，它们有一个共同的特点：都是模拟了自然过程。模拟退火思路源于物理学中固体物质的退 火过程，遗传算法借鉴了自然界优胜劣汰的进化思想，禁忌搜索模拟了人类有记忆过程的智力 过程，神经网络更是直接模拟了人脑。 它们之间的联系也非常紧密，比如模拟退火和遗传算法为神经网络提供更优良的学习算法提供 了思路。把它们有机地综合在一起，取长补短，性能将更加优良。 这几种智能算法有别于一般的按照图灵机进行精确计算的程序，尤其是人工神经网络，是对计 算机模型的一种新的诠释，跳出了冯·诺依曼机的圈子，按照这种思想来设计的计算机有着广 阔的发展前景 智能算法学习笔记 作者:hisky(苍竹琴声) 这是我自己看智能算法的时候的一些笔记，贴出来给大家看一下，如果有理解错误的地方，千 万请指出，小生在这里先谢过了^_^ 一个比方 在工程实践中，经常会接触到一些比较“新颖”的算法或理论，比如模拟退火，遗传算法，禁忌 搜索，神经网络等。这些算法或理论都有一些共同的特性（比如模拟自然过程），通称为“智 能算法”。它们在解决一些复杂的工程问题时大有用武之地。 这些算法都有什么含义？首先给出个局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻： 为了找出地球上最高的山，一群有志气的兔子们开始想办法。 1．兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆 朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。 2．兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但 是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。 3．兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道 自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会 找到珠穆朗玛峰。这就是遗传算法。 4.兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一 座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。 智能优化算法的概述 智能优化算法要解决的一般是最优化问题。最优化问题可以分为（1）求解一个函数中，使得 函数值最小的自变量取值的函数优化问题和（2）在一个解空间里面，寻找最优解，使目标函 数值最小的组合优化问题。典型的组合优化问题有：旅行商问题（Traveling Salesman Problem，TSP），加工调度问题（Scheduling Problem），0－1 背包问题（Knapsack Problem），以及装箱问题（Bin Packing Problem）等。
    优化算法有很多，经典算法包括：有线性规划，动态规划等；改进型局部搜索算法包括爬山 法，最速下降法等，本文介绍的模拟退火、遗传算法以及禁忌搜索称作指导性搜索法。而神经 网络，混沌搜索则属于系统动态演化方法。 优化思想里面经常提到邻域函数，它的作用是指出如何由当前解得到一个（组）新解。其具体 实现方式要根据具体问题分析来定。 一般而言，局部搜索就是基于贪婪思想利用邻域函数进行搜索，若找到一个比现有值更优的解 就弃前者而取后者。但是，它一般只可以得到“局部极小解”，就是说，可能这只兔子登“登泰 山而小天下”，但是却没有找到珠穆朗玛峰。而模拟退火，遗传算法，禁忌搜索，神经网络等 从不同的角度和策略实现了改进，取得较好的“全局最小解”。 模拟退火算法（Simulated Annealing，SA） 模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热的时 候，粒子间的布朗运动增强，到达一定强度后，固体物质转化为液态，这个时候再进行退火， 粒子热运动减弱，并逐渐趋于有序，最后达到稳定。 模拟退火的解不再像局部搜索那样最后的结果依赖初始点。它引入了一个接受概率 p。如果新 的点（设为 pn）的目标函数 f（pn）更好，则 p=1，表示选取新点；否则，接受概率 p 是当前 点（设为 pc）的目标函数 f（pc），新点的目标函数 f（pn）以及另一个控制参数“温度”T 的 函数。也就是说，模拟退火没有像局部搜索那样每次都贪婪地寻找比现在好的点，目标函数差 一点的点也有可能接受进来。随着算法的执行，系统温度 T 逐渐降低，最后终止于某个低温， 在该温度下，系统不再接受变化。 模拟退火的典型特征是除了接受目标函数的改进外，还接受一个衰减极限，当 T 较大时，接受 较大的衰减，当 T 逐渐变小时，接受较小的衰减，当 T 为 0 时，就不再接受衰减。这一特征意 味着模拟退火与局部搜索相反，它能避开局部极小，并且还保持了局部搜索的通用性和简单 性。 在物理上，先加热，让分子间互相碰撞，变成无序状态，内能加大，然后降温，最后的分子次 序反而会更有序，内能比没有加热前更小。就像那只兔子，它喝醉后，对比较近的山峰视而不 见，迷迷糊糊地跳一大圈子，反而更有可能找到珠峰。 值得注意的是，当 T 为 0 时，模拟退火就成为局部搜索的一个特例。 模拟退火的伪码表达： procedure simulated annealing begin t:=0; initialize temperature T select a current string vc at random; evaluate vc; repeat repeat select a new string vn in the neighborhood of vc; (1) if f(vc)
    T:=t+1; until (stop-criterion) (5) end; 上面的程序中，关键的是(1)新状态产生函数，(2)新状态接受函数，(3)抽样稳定准则，(4)退 温函数，(5)退火结束准则 （简称三函数两准则）是直接影响优化结果的主要环节。虽然实验 结果证明初始值对于最后的结果没有影响，但是初温越高，得到高质量解的概率越大。所以， 应该尽量选取比较高的初温。 上面关键环节的选取策略： （1）状态产生函数：候选解由当前解的邻域函数决定，可以取互换，插入，逆序等操作产 生，然后根据概率分布方式选取新的解，概率可以取均匀分布、正态分布、高斯分布、柯西分 布等。 （2）状态接受函数：这个环节最关键，但是，实验表明，何种接受函数对于最后结果影响不 大。所以，一般选取 min [1, exp ((f (vn)-f (vc))/T)]。 （3）抽样稳定准则：一般常用的有：检验目标函数的均值是否稳定；连续若干步的目标值变 化较小；规定一定的步数； （4）退温函数：如果要求温度必须按照一定的比率下降，SA 算法可以采用 ，但是温度下降 很慢；快速 SA 中，一般采用 。目前，经常用的是 ， 是一个不断变化的值。 （5）退火结束准则：一般有：设置终止温度；设置迭代次数；搜索到的最优值连续多次保持 不变；检验系统熵是否稳定。 为了保证有比较优的解，算法往往采取慢降温、多抽样、以及把“终止温度”设的比较低等方 式，导致算法运行时间比较长，这也是模拟退火的最大缺点。人喝醉了酒办起事来都不利索， 何况兔子？ 遗传算法（Genetic Algorithm, GA） “物竞天择，适者生存”，是进化论的基本思想。遗传算法就是模拟自然界想做的事。遗传算法 可以很好地用于优化问题，若把它看作对自然过程高度理想化的模拟，更能显出它本身的优 雅——虽然生存竞争是残酷的。 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进 行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设 定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、健壮性强、适于并行处理以及高 效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能 算法之一。 遗传算法的伪码： procedure genetic algorithm begin initialize a group and evaluate the fitness value ; （1） while not convergent （2） begin select; （3） if random[0,1]
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料