第五章物流系统的智能优化方法精选文档.ppt

《第五章物流系统的智能优化方法精选文档.ppt》由会员分享，可在线阅读，更多相关《第五章物流系统的智能优化方法精选文档.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章物流系统的智能优化方法第五章物流系统的智能优化方法本讲稿第一页，共七十三页q课程内容课程内容 模拟退火算法、遗传算法、禁忌搜索算法、神经网络与神经网络优化算法q课程目标课程目标 了解智能优化的模型结构；理解模拟退火算法的收敛性条件；掌握智能优化的流程、操作、算法理论与技术物流系统优化的智能优化方法为复杂物流管理决策问题提供了重要的可行性解决方案。本讲稿第二页，共七十三页模拟退火算法模拟退火算法(Simulated Annealing)1 1、基本思想基本思想 (1)是基于是基于Monte Carlo迭代求解策略的一种随机迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退寻优

2、算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。火过程与一般组合优化问题之间的相似性。(2)结合爬山法和随机行走结合爬山法和随机行走 注：注：SA算法最早是由算法最早是由Metropolis等等(1953)提出提出本讲稿第三页，共七十三页 (3)模拟退火算法在某一初温下，伴随温度参模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优解。模解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一

3、种通用的优化算法，目前已在拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。工程中得到了广泛应用。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第四页，共七十三页2 2、物理退火过程和物理退火过程和MetropolisMetropolis准则准则简单而言，物理退火过程由以下三部分组成：简单而言，物理退火过程由以下三部分组成：加温过程。其目的是增强粒子的热运动，使其偏加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将溶解为液离平衡位置。当温度足够高时，固体将溶解为液体，从而消除系统原先可能存在的非均匀态，使体，从而消除系统原先可能存

4、在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。溶解随后进行的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程联系，系统能量也随温度过程与系统的熵增过程联系，系统能量也随温度的升高而增大。的升高而增大。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第五页，共七十三页等温过程。物理学的知识告诉我们，对于与周等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。当自由能达到最小时

5、，系统达到平衡态。冷却过程。目的是使粒子的热运动减弱并渐趋冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶有序，系统能量逐渐下降，从而得到低能的晶体结构。体结构。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第六页，共七十三页 Metropolis等在等在1953年提出了重要性采样法，即年提出了重要性采样法，即以概率接受新状态。具体而言，在温度以概率接受新状态。具体而言，在温度t,由当前状由当前状态态i产生新状态产生新状态j，两者的能量分别为，两者的能量分别为 ，若，若 则接受新状态则接受新状态j为当前状态；否则，若概率为当前状态；否则

6、，若概率 大于大于 区间内的随机数则仍旧接受新状态区间内的随机数则仍旧接受新状态j为当前为当前状态，若不成立则保留状态，若不成立则保留i为当前状态，其中为当前状态，其中k为为Boltzmann常数。常数。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第七页，共七十三页 这种重要性采样过程在高温下可接受与当前状这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态，而在低温下基本只接态能量差较大的新状态，而在低温下基本只接受与当前能量差较小的新状态，而且当温度趋受与当前能量差较小的新状态，而且当温度趋于零时，就不能接受比当前状态能量高的新状于零时，就不能接受比当前

7、状态能量高的新状态。这种接受准则通常称为态。这种接受准则通常称为Metropolis准则。准则。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第八页，共七十三页2 2、算法步骤算法步骤标准模拟退火算法的一般步骤可描述如下：标准模拟退火算法的一般步骤可描述如下：给给定定初初温温 ，随随机机产产生生初初始始状状态态 ，令令 ；Repeat:Repeat 产生新状态产生新状态 ；模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第九页，共七十三页Until 抽样稳定准则满足；抽样稳定准则满足；退温退温 ，并，并 令令 ；Until 算法终止准则满足；算

8、法终止准则满足；输出算法搜索结果。输出算法搜索结果。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十页，共七十三页3 3、算法关键参数和操作的设定算法关键参数和操作的设定 从算法流程上看，模拟退火算法包括三函数两从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定这些环节的设计将决定SA算法的优化性能。此算法的优化性能。此外，初温的选择对外，初温的选择对SA算法性能也有很大影响。算法性能也有很大影

9、响。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十一页，共七十三页状态产生函数状态产生函数 设计状态产生函数（邻域函数）的出发点应该设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。选解的方式和候选解产生的概率分布。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十二页，共七十三页状态接受函数状态接受函数 状状态态接接受受函函数数一一般般以以概概率率的的

10、方方式式给给出出，不不同同接接受受函函数数的的差差别别主主要要在在于于接接受受概概率率的的形形式式不不同同。设计状态接受概率，应该遵循以下原则：设计状态接受概率，应该遵循以下原则：在固定温度下，接受使目标函数值下降的候选在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；解的概率要大于使目标值上升的候选解的概率；模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十三页，共七十三页随温度的下降，接受使目标函数值上升的解的概随温度的下降，接受使目标函数值上升的解的概率要逐渐减小；率要逐渐减小；当温度趋于零时，只能接受目标函数值下降的解。当温度趋

11、于零时，只能接受目标函数值下降的解。状态接受函数的引入是状态接受函数的引入是SA算法实现全局搜索的最算法实现全局搜索的最关键的因素，关键的因素，SA算法中通常采用算法中通常采用min1,exp(-C/t)作为状态接受函数。作为状态接受函数。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十四页，共七十三页初温初温 初始温度、温度更新函数、内循环终止准则和初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程外循环终止准则通常被称为退火历程(annealing schedule)。实验表明，初温越大，。实验表明，初温越大，获得高质量解的几率越大，但花费

12、的计算时间获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：量和优化效率，常用方法包括：模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十五页，共七十三页均匀抽样一组状态，以各状态目标值的方差为初均匀抽样一组状态，以各状态目标值的方差为初温。温。随随机机产产生生一一组组状状态态，确确定定两两两两状状态态间间的的最最大大目目标标值值差差 ，然然后后依依据据差差值值，利利用用一一定定的的函函数数确确定定初初温温。譬譬如如 ，其其中中 为为初初始始接接受受概概率。率。利用经验公

13、式给出。利用经验公式给出。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十六页，共七十三页温度更新函数温度更新函数温温度度更更新新函函数数，即即温温度度的的下下降降方方式式，用用于于在在外外循循环环中修改温度值。中修改温度值。目前，最常用的温度更新函数为指数退温函数，即，目前，最常用的温度更新函数为指数退温函数，即，其中且其大小可以不断变化。其中且其大小可以不断变化。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十七页，共七十三页内循环终止准则内循环终止准则 内循环终止准则，或称内循环终止准则，或称MetropolisMetropolis

14、抽样稳定准抽样稳定准则，用于决定在各温度下产生候选解的数目。则，用于决定在各温度下产生候选解的数目。在非时齐在非时齐SASA算法理论中，由于在每个温度下只算法理论中，由于在每个温度下只产生一个或少量候选解，所以不存在选择内循产生一个或少量候选解，所以不存在选择内循环终止准则的问题。环终止准则的问题。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十八页，共七十三页 而在时齐而在时齐SASA算法理论中，收敛条件要求在每个算法理论中，收敛条件要求在每个温度下产生候选解的数目趋于无穷大，以使相温度下产生候选解的数目趋于无穷大，以使相应的马氏链达到平稳概率分布，显然在实际应应

15、的马氏链达到平稳概率分布，显然在实际应用算法时这是无法实现的。常用的抽样准则包用算法时这是无法实现的。常用的抽样准则包括：括：检验目标函数的均值是否稳定；检验目标函数的均值是否稳定；连续若干步的目标值变化较小；连续若干步的目标值变化较小；按一定的步数抽样。按一定的步数抽样。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第十九页，共七十三页外循环终止准则外循环终止准则 外循环终止准则，即算法终止准则，用于决定算外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值是一种简单的方法。法何时结束。设置温度终值是一种简单的方法。SASA算法的收敛性理论中要求温度终

16、值趋于零，这算法的收敛性理论中要求温度终值趋于零，这显然不合实际。通常的做法是：显然不合实际。通常的做法是：设置终止温度的阈值；设置终止温度的阈值；设置外循环迭代次数；设置外循环迭代次数；算法搜索到的最优值连续若干步保持不变；算法搜索到的最优值连续若干步保持不变；检验系统熵是否稳定。检验系统熵是否稳定。模拟退火算法模拟退火算法(Simulated Annealing)本讲稿第二十页，共七十三页小结小结q由于算法的一些环节无法在实际设计算法时实现，由于算法的一些环节无法在实际设计算法时实现，因此因此SA算法往往得不到全局最优解，或算法结算法往往得不到全局最优解，或算法结果存在波动性。果存在波动性

17、。q目前，目前，SA算法参数的选择仍依赖于一些启发式准算法参数的选择仍依赖于一些启发式准则和待求问题的性质。则和待求问题的性质。SA算法的通用性很强，算法的通用性很强，算法易于实现，但要真正取得质量和可靠性高、算法易于实现，但要真正取得质量和可靠性高、初值鲁棒性好的效果，克服计算时间较长、效果初值鲁棒性好的效果，克服计算时间较长、效果较低的缺点，并适用于规模较大的问题，尚需进较低的缺点，并适用于规模较大的问题，尚需进行大量的研究工作。行大量的研究工作。本讲稿第二十一页，共七十三页1、基本概念、基本概念 模拟生物在自然环境中的遗传和进化过程而形模拟生物在自然环境中的遗传和进化过程而形成的一种成的

18、一种自适应全局优化概率搜索算法。搜索算法。遗传算法遗传算法本讲稿第二十二页，共七十三页2、基本思想基本思想 对对于于一一个个求求函函数数最最大大值值的的优优化化问问题题，一一般般可可描描述为下述数学规划模型：述为下述数学规划模型：遗传算法遗传算法本讲稿第二十三页，共七十三页式中，式中，为决策变量，为决策变量，f(X)为目标函数，为目标函数，U是基本空间，是基本空间，R是是U的一个子集。的一个子集。遗传算法中，将遗传算法中，将n维决策向量用维决策向量用n个记号个记号所组成的符号串所组成的符号串X来表示：来表示：遗传算法遗传算法本讲稿第二十四页，共七十三页 把每一个把每一个 看作一个遗传基因，它的

19、所有可能取值称为等看作一个遗传基因，它的所有可能取值称为等位基因，这样，位基因，这样，X就可看作是由就可看作是由n个遗传基因所组成的一个个遗传基因所组成的一个染色体。染色体的长度可以是固定的，也可以是变化的。染色体。染色体的长度可以是固定的，也可以是变化的。等位基因可以是一组整数，也可以是某一范围内的实数等位基因可以是一组整数，也可以是某一范围内的实数值，或者是记号。最简单的等位基因是由值，或者是记号。最简单的等位基因是由0和和1这两个整这两个整数组成的，相应的染色体就可表示为一个二进制符号串。数组成的，相应的染色体就可表示为一个二进制符号串。遗传算法遗传算法本讲稿第二十五页，共七十三页 这种

20、编码所形成的排列形式这种编码所形成的排列形式X是个体的基因型，与它对应的是个体的基因型，与它对应的X值是个体的表现型。染色体值是个体的表现型。染色体X也称为个体也称为个体X，对于每一个个，对于每一个个体体X，要按照一定的规则确定出其适应度。个体的适应度与，要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型其对应的个体表现型X的目标函数值相关联，的目标函数值相关联，X越接近于目标越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。函数的最优点，其适应度越大；反之，其适应度越小。遗传算法遗传算法本讲稿第二十六页，共七十三页 遗传算法中，决策变量遗传算法中，决策变量X组成了问题

21、的解组成了问题的解空间。对问题最优解的搜索是通过对染色体空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。就组成了问题的搜索空间。生物的进化是以集团为主体的。与此相对生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由应，遗传算法的运算对象是由M个个体所组成个个体所组成的集合，称为群体。的集合，称为群体。遗传算法遗传算法本讲稿第二十七页，共七十三页与生物一代一代的自然进化过程相似，遗传算法的运算过与生物一代一代的自然进化过程相似，遗传算法的运算过程也是一个反复迭代过程，第程也是一个反复迭代过程

22、，第t代群体记做代群体记做P(t),经过一代遗传和经过一代遗传和进化后，得到第进化后，得到第t+1代群体，它们也是由多个个体组成的集合，记代群体，它们也是由多个个体组成的集合，记做做P(t+1)。这个群体不断地经过遗传和进化操作，并且每次都按照。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体在群体中将会得到一个优良的个体X，它所对应的表现型，它所对应的表现型X将达到将达到或接近于问题的最优解或接近于问题的最优解 。遗传算法遗传算法本讲稿第二十八

23、页，共七十三页生物的进化过程主要是通过染色体之间的交生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。遗传算法中最优解叉和染色体的变异来完成的。遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子谓的遗传算子(genetic operators)作用于群体作用于群体P(t)中，进行下述遗传操作，从而得到新一代群中，进行下述遗传操作，从而得到新一代群体体P(t+1)。遗传算法遗传算法本讲稿第二十九页，共七十三页q选择选择(selection):(selection):根据各个个体的适应度，按照根据各个个体的适应度，按照一定

24、的规则或方法，从第一定的规则或方法，从第t t代群体代群体P(t)P(t)中选择出一中选择出一些优良的个体遗传到下一代群体些优良的个体遗传到下一代群体P P(t t+1)+1)中。中。q交叉交叉(crossover):(crossover):将群体将群体P(t)P(t)内的各个个体随机内的各个个体随机搭配成对，对每一个个体，以某个概率搭配成对，对每一个个体，以某个概率(称为交叉称为交叉概率，概率，crossover rate)crossover rate)交换它们之间的部分染色交换它们之间的部分染色体。体。遗传算法遗传算法本讲稿第三十页，共七十三页q变异变异(mutation):对群体对群体P

25、(t)中的每一个个体，中的每一个个体，以某一概率以某一概率(称为变异概率，称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它的等改变某一个或一些基因座上基因值为其它的等位基因。位基因。遗传算法遗传算法本讲稿第三十一页，共七十三页3 3、特点特点遗传算法是一类可用于复杂系统优化计算的鲁遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，与其他一些优化算法相比，主要有棒搜索算法，与其他一些优化算法相比，主要有下述几个特点：下述几个特点：q遗传算法以决策变量的编码作为运算对象。传统遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身的优化算

26、法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算对象，从而可以很方便地引入和应用遗传操作算子。子。遗传算法遗传算法本讲稿第三十二页，共七十三页q遗传算法直接以目标函数值作为搜索信息。传遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值，还需统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难

27、求导的函数，遗传算法标函数无法求导或很难求导的函数，遗传算法就比较方便。就比较方便。遗传算法遗传算法本讲稿第三十三页，共七十三页q遗传算法同时进行解空间的多点搜索。传统的优遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种隐含以不断进化。这些是遗传算法所特有的一种隐含并行性。并行性。遗传算法遗传算法本讲稿第三十四

28、页，共七十三页q遗传算法使用概率搜索技术遗传算法使用概率搜索技术 。遗传算法属于一。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都已证明了了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率在一定条件下遗传算法总是以概率1 1收敛于问题收敛于问题的最优解。的最优解。遗传算法遗传算法本讲稿第三十五页，共七十三页3 3、应用应用 遗传算法提供了一种求解复杂系统优化问题遗传算法提供了一种求解复杂系统优化问题的通用

29、框架，它不依赖于问题的具体领域，对问的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。学科。下面列举一些遗传算法的主要应用领域。遗传算法遗传算法本讲稿第三十六页，共七十三页q组合优化：遗传算法是寻求组合优化问题满意解组合优化：遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合的最佳工具之一，实践证明，遗传算法对于组合优化问题中的优化问题中的NP完全问题非常有效。完全问题非常有效。遗传算法遗传算法本讲稿第三十七页，共七十三页q生产调度问题：生产调度问题在很

30、多情况下所生产调度问题：生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。已经成为解决复杂调度问题的有效工具。遗传算法遗传算法本讲稿第三十八页，共七十三页q自动控制：遗传算法已经在自动控制领域中得自动控制：遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参

31、数辨识、制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权传算法进行人工神经网络的结构优化设计和权值学习等。值学习等。遗传算法遗传算法本讲稿第三十九页，共七十三页q机器人学：机器人是一类复杂的难以精确建模的机器人学：机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学自然成为遗传算适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。法的一个重要应用领域。遗传算法遗传算法本讲稿第四十页

32、，共七十三页q图象处理：图像处理是计算机视觉中的一个重图象处理：图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。面得到了很好的应用。遗传算法遗传算法本讲稿第四十一页，共七十三页q人工生命：人工生

33、命是用计算机、机械等人工人工生命：人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。是研究人工生命现象的重要理论基础。遗传算法遗传算法本讲稿第四十二页，共七十三页q机器学习：基于遗传算法的机器学习，在很多领机器学习：基于遗传算法的机器学习，在很多领域中都得到了应用。例如

34、基于遗传算法的机器学域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。于人工神经网络的网络结构优化设计。遗传算法遗传算法本讲稿第四十三页，共七十三页4 4、基本遗传算法基本遗传算法 基本遗传算法（基本遗传算法（Simple Genetic Algorithms,简称简称SGA）是）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，这三种基本遗传算子，其遗传进化操作过程简单，容易

35、理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。提供了一个基本框架，同时也具有一定的应用价值。遗传算法遗传算法本讲稿第四十四页，共七十三页 基本遗传算法的构成要素基本遗传算法的构成要素q 染色体编码方法。基本遗传算法使用固定长染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集基因是由二值符号集00，11所组成的。初始群体所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生中各个个体的基因值可

36、用均匀分布的随机数来生成。成。遗传算法遗传算法本讲稿第四十五页，共七十三页q个个体体适适应应度度评评价价。基基本本遗遗传传算算法法按按与与个个体体适适应应度度成成正正比比的的概概率率来来决决定定当当前前群群体体中中每每个个个个体体遗遗传传到到下下一一代代群群体体中中的的机机会会多多少少。为为正正确确计计算算这这个个概概率率，这这里里要要求求所所有有个个体体的的适适应应度度必必须须为为正数或零。正数或零。q遗传算子。基本遗传算法使用下述三种遗传遗传算子。基本遗传算法使用下述三种遗传算子：选择运算使用比例选择算子，交叉运算算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位

37、变异使用单点交叉算子，变异运算使用基本位变异算子或均匀变异算子。算子或均匀变异算子。遗传算法遗传算法本讲稿第四十六页，共七十三页 基本遗传算法的运行参数。基本遗传算法有基本遗传算法的运行参数。基本遗传算法有下述下述4 4个运行参数需要提前设定：群体大小个运行参数需要提前设定：群体大小M M，即群体中所含个体数目，一般取为即群体中所含个体数目，一般取为2010020100；遗；遗传运算的终止进化代数传运算的终止进化代数T T，一般取为，一般取为100500100500；交叉概率交叉概率P Pc c，一般取为，一般取为0.40.990.40.99；变异概率变异概率P Pm m，一般取为，一般取为0

38、.00010.10.00010.1。遗传算法遗传算法本讲稿第四十七页，共七十三页基本遗传算法的形式化定义基本遗传算法的形式化定义基本遗传算法可定义为一个基本遗传算法可定义为一个8 8元组：元组：遗传算法遗传算法本讲稿第四十八页，共七十三页C C-个体的编码方法；个体的编码方法；E E-个体适应度评价函数；个体适应度评价函数；P P0 0-初始群体；初始群体；M M-群体大小；群体大小；-选择算子；选择算子；-变异算子；变异算子；-交叉算子；交叉算子；T T-遗传运算终止条件。遗传运算终止条件。遗传算法遗传算法本讲稿第四十九页，共七十三页 基本遗传算法的实现基本遗传算法的实现个体适应度评价个体适

39、应度评价q在遗传算法中，以个体适应度的大小来确定该个在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要为正确计算不同情况下各个个体的遗传概率，

40、要求所有个体的适应度必须为正数或零，不能是负求所有个体的适应度必须为正数或零，不能是负数。数。遗传算法遗传算法本讲稿第五十页，共七十三页 为满足适应度取非负值的要求，基本遗传算法为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换一般采用下面两种方法之一将目标函数值变换为个体的适应度。为个体的适应度。q方法一：对于目标函数是求极大化，方法为：方法一：对于目标函数是求极大化，方法为：遗传算法遗传算法本讲稿第五十一页，共七十三页 式中，式中，为一个适当地相对比较小的数，为一个适当地相对比较小的数，它可用下面几种方法之一来选取它可用下面几种方法之一来选取:预先指定的一个预

41、先指定的一个较小的数；进化到当前代为止的最小目标函数值；较小的数；进化到当前代为止的最小目标函数值；当前代或最近几代群体中的最小目标值。当前代或最近几代群体中的最小目标值。遗传算法遗传算法本讲稿第五十二页，共七十三页比例选择算子比例选择算子q比比例例选选择择实实际际上上是是一一种种有有退退还还随随机机选选择择,也也叫叫做做赌赌盘盘(Roulette(Roulette Wheel)Wheel)选选择择,因因为为这这种种选选择择方方式式与与赌赌博中的赌盘操作原理非常相似。博中的赌盘操作原理非常相似。q比例选择算子的具体执行过程是：先计算出群体比例选择算子的具体执行过程是：先计算出群体中所有个体的适

42、应度之和；其次计算出每个个体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操到下一代群体中的概率；最后再使用模拟赌盘操作（即作（即0 0到到1 1之间的随机数）来确定各个个体被选之间的随机数）来确定各个个体被选中的次数。中的次数。遗传算法遗传算法本讲稿第五十三页，共七十三页单点交叉算子单点交叉算子q单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的单点交叉算子的具体执行过程如下：对群体中的个体进行

43、两两随机配对；对每一对相互配对的个个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率 在其交叉点处相互交换两个个体的部分染色体，在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。从而产生出两个新个体。遗传算法遗传算法本讲稿第五十四页，共七十三页基本位变异算子基本位变异算子q基本位变异算子的具体执行过程为：对个体的每基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率一个基因座，依变异概率 指定其为变异点；指定其为变

44、异点；对每一个指定的变异点，对其基因值做取反运算对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新或用其他等位基因值来代替，从而产生出一个新的个体。的个体。遗传算法遗传算法本讲稿第五十五页，共七十三页 遗传算法的应用步骤遗传算法的应用步骤 遗遗传传算算法法提提供供了了一一种种求求解解复复杂杂系系统统优优化化问问题题的的通通用用框框架架。对对于于具具体体问问题题，可可按按下下述述步步骤骤来构造：来构造：q确定决策变量及其各种约束条件，即确定出确定决策变量及其各种约束条件，即确定出个体的表现型个体的表现型X和问题的解空间；和问题的解空间；q建立优化模型，即描述出目

45、标函数的类型及建立优化模型，即描述出目标函数的类型及其数学描述形式或量化方法；其数学描述形式或量化方法；遗传算法遗传算法本讲稿第五十六页，共七十三页q确确定定表表示示可可行行解解的的染染色色体体编编码码方方法法，即即确确定定出出个体的基因型个体的基因型X及遗传算法的搜索空间；及遗传算法的搜索空间；q确确定定解解码码方方法法，即即确确定定出出由由个个体体基基因因型型X到到个个体体表现型表现型X的对应关系或转换方法；的对应关系或转换方法；q确定个体适应度的量化评价方法，即确定出由确定个体适应度的量化评价方法，即确定出由目标函数值目标函数值 到个体适应度的转换规则；到个体适应度的转换规则；遗传算法遗

46、传算法本讲稿第五十七页，共七十三页q设设计计遗遗传传算算子子，即即确确定定出出选选择择运运算算、交交叉叉运运算算、变异运算等遗传算子的具体操作方法；变异运算等遗传算子的具体操作方法；q确定遗传算法的有关运行参数，即确定出遗传确定遗传算法的有关运行参数，即确定出遗传算法的算法的 等参数。等参数。遗传算法遗传算法本讲稿第五十八页，共七十三页本讲稿第五十九页，共七十三页5 5、免疫遗传算法免疫遗传算法 基于免疫的改进遗传算法，是免疫原理与传统遗基于免疫的改进遗传算法，是免疫原理与传统遗传算法的结合。传算法的结合。算法的核心在于免疫算子的构造，而免疫算子又算法的核心在于免疫算子的构造，而免疫算子又是通

47、过接种疫苗和免疫选择两个步骤完成的。是通过接种疫苗和免疫选择两个步骤完成的。在理论上，免疫算法是概率在理论上，免疫算法是概率1 1收敛的。收敛的。遗传算法遗传算法本讲稿第六十页，共七十三页例子例子本讲稿第六十一页，共七十三页本讲稿第六十二页，共七十三页本讲稿第六十三页，共七十三页本讲稿第六十四页，共七十三页本讲稿第六十五页，共七十三页1 1、基本思想基本思想 是对局部邻域搜索的一种扩展，是一种全局逐步是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法。其最重要的思想是标记对应已搜索到寻优算法。其最重要的思想是标记对应已搜索到的局部最优解的一些对象，并在进一步的迭代搜的局部最优解的一些对象，并在

48、进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。从而保证对不同的有效搜索途径的探索。禁忌搜索算法禁忌搜索算法(Tabu Search)本讲稿第六十六页，共七十三页2 2、算法步骤算法步骤 (1)(1)给定算法参数，随机产生初始解给定算法参数，随机产生初始解x x，置禁忌表，置禁忌表为空。为空。(2)(2)判断算法终止条件是否满足？若是，则结束算判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。法并输出优化结果；否则，继续以下步骤。(3)(3)利用当前解利用当前解x x的邻域函数

49、产生其所有（或若干）的邻域函数产生其所有（或若干）邻域解，并从中确定若干个候选解。邻域解，并从中确定若干个候选解。(4)(4)对候选解判断藐视准则是否满足？若成立，则对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态用满足藐视准则的最佳状态y y代替代替x x成为新的当前成为新的当前解，即解，即x=yx=y，并用与，并用与y y对应的禁忌对象替换最早进对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用入禁忌表的禁忌对象，同时用y y替换替换“best so“best so far”far”状态，然后转步骤状态，然后转步骤2 2；否则，继续以下步骤。；否则，继续以下步骤。禁忌搜索算

50、法禁忌搜索算法(Tabu Search)本讲稿第六十七页，共七十三页 (5)(5)判断候选解对应的各对象的禁忌属性，选择判断候选解对应的各对象的禁忌属性，选择候选解集合中非禁忌对象对应的最佳状态为新的候选解集合中非禁忌对象对应的最佳状态为新的当前解，同时，用与之对应的禁忌对象替换最早当前解，同时，用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。进入禁忌表的禁忌对象元素。(6)(6)转步骤转步骤(2)#(2)#注：注：1)1)其中，邻域函数、禁忌对象、禁忌表和藐其中，邻域函数、禁忌对象、禁忌表和藐视准则构成了禁忌搜索算法的关键。视准则构成了禁忌搜索算法的关键。2)2)对于邻域函数，沿用局部