物流系统的智能优化方法

1第第5章章 智能优化方法智能优化方法2q课程内容课程内容 模拟退火算法、遗传算法、禁忌搜索算法、神经网络与神经网络优化算法q课程目标课程目标 了解智能优化的模型结构；理解模拟退火算法的收敛性条件；掌握智能优化的流程、操作、算法理论与技术物流系统优化的智能优化方法为复杂物流管理决策问题提供了重要的可行性解决方案。第第5章章 智能优化方法智能优化方法3模拟退火算法模拟退火算法(Simulated Annealing)1 1、基本思想基本思想 (1)是基于是基于Monte Carlo迭代求解策略的一种随机迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。火过程与一般组合优化问题之间的相似性。(2)结合爬山法和随机行走结合爬山法和随机行走 注：注：SA算法最早是由算法最早是由Metropolis等等(1953)提出提出第第5章章 智能优化方法智能优化方法4 (3)模拟退火算法在某一初温下，伴随温度参模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优解。模解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一种通用的优化算法，目前已在拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。工程中得到了广泛应用。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法52 2、物理退火过程和物理退火过程和MetropolisMetropolis准则准则简单而言，物理退火过程由以下三部分组成：简单而言，物理退火过程由以下三部分组成：加温过程。其目的是增强粒子的热运动，使其偏加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将溶解为液离平衡位置。当温度足够高时，固体将溶解为液体，从而消除系统原先可能存在的非均匀态，使体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。溶解随后进行的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程联系，系统能量也随温度过程与系统的熵增过程联系，系统能量也随温度的升高而增大。的升高而增大。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法6等温过程。物理学的知识告诉我们，对于与周等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。当自由能达到最小时，系统达到平衡态。冷却过程。目的是使粒子的热运动减弱并渐冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的趋有序，系统能量逐渐下降，从而得到低能的晶体结构。晶体结构。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法7 Metropolis等在等在1953年提出了重要性采样法，即年提出了重要性采样法，即以概率接受新状态。具体而言，在温度以概率接受新状态。具体而言，在温度t,由当前状由当前状态态i产生新状态产生新状态j，两者的能量分别为，两者的能量分别为 ，若，若 则接受新状态则接受新状态j为当前状态；否则，若概率为当前状态；否则，若概率 大于大于 区间内的随机数则仍旧接受新状态区间内的随机数则仍旧接受新状态j为当为当前状态，若不成立则保留前状态，若不成立则保留i为当前状态，其中为当前状态，其中k为为Boltzmann常数。常数。jiEE 和ijEE/)(expktEEpijr)1,0模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法8 这种重要性采样过程在高温下可接受与当前状这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态，而在低温下基本只接态能量差较大的新状态，而在低温下基本只接受与当前能量差较小的新状态，而且当温度趋受与当前能量差较小的新状态，而且当温度趋于零时，就不能接受比当前状态能量高的新状于零时，就不能接受比当前状态能量高的新状态。这种接受准则通常称为态。这种接受准则通常称为Metropolis准则。准则。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法92 2、算法步骤算法步骤标准模拟退火算法的一般步骤可描述如下：标准模拟退火算法的一般步骤可描述如下：给定初温给定初温 ，随机产生初始状态，随机产生初始状态 ，令，令 ；Repeat:Repeat 产生新状态产生新状态 ；0tt 0ss 0k)(sGenetesjjjssrandomsCsCif 1,0)()(exp,1min模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法10Until 抽样稳定准则满足；抽样稳定准则满足；退温退温 ，并，并 令令 ；Until 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜索结果。)(1kktupdatet1 kk模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法113 3、算法关键参数和操作的设定算法关键参数和操作的设定 从算法流程上看，模拟退火算法包括三函数两从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定这些环节的设计将决定SA算法的优化性能。算法的优化性能。此外，初温的选择对此外，初温的选择对SA算法性能也有很大影算法性能也有很大影响。响。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法12状态产生函数状态产生函数 设计状态产生函数（邻域函数）的出发点应该设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。选解的方式和候选解产生的概率分布。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法13状态接受函数状态接受函数 状态接受函数一般以概率的方式给出，不同状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则：设计状态接受概率，应该遵循以下原则：在固定温度下，接受使目标函数值下降的候选在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；解的概率要大于使目标值上升的候选解的概率；模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法14随温度的下降，接受使目标函数值上升的解的概随温度的下降，接受使目标函数值上升的解的概率要逐渐减小；率要逐渐减小；当温度趋于零时，只能接受目标函数值下降的解。当温度趋于零时，只能接受目标函数值下降的解。状态接受函数的引入是状态接受函数的引入是SA算法实现全局搜索的最算法实现全局搜索的最关键的因素，关键的因素，SA算法中通常采用算法中通常采用min1,exp(-C/t)作为状态接受函数。作为状态接受函数。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法15初温初温 初始温度、温度更新函数、内循环终止准则和初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程外循环终止准则通常被称为退火历程(annealing schedule)。实验表明，初温越。实验表明，初温越大，获得高质量解的几率越大，但花费的计算大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：化质量和优化效率，常用方法包括：模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法16均匀抽样一组状态，以各状态目标值的方差为初均匀抽样一组状态，以各状态目标值的方差为初温。温。随机产生一组状态，确定两两状态间的最大目标随机产生一组状态，确定两两状态间的最大目标值差值差 ，然后依据差值，利用一定的函数确定，然后依据差值，利用一定的函数确定初温。譬如初温。譬如 ，其中，其中 为初始接受概为初始接受概率。率。利用经验公式给出。利用经验公式给出。|maxrptln/0rp模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法17温度更新函数温度更新函数温度更新函数，即温度的下降方式，用于在外循环温度更新函数，即温度的下降方式，用于在外循环中修改温度值。中修改温度值。目前，最常用的温度更新函数为指数退温函数，即，目前，最常用的温度更新函数为指数退温函数，即，其中且其大小可以不断变化。其中且其大小可以不断变化。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法18内循环终止准则内循环终止准则 内循环终止准则，或称内循环终止准则，或称MetropolisMetropolis抽样稳定准抽样稳定准则，用于决定在各温度下产生候选解的数目。则，用于决定在各温度下产生候选解的数目。在非时齐在非时齐SASA算法理论中，由于在每个温度下只算法理论中，由于在每个温度下只产生一个或少量候选解，所以不存在选择内循产生一个或少量候选解，所以不存在选择内循环终止准则的问题。环终止准则的问题。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法19 而在时齐而在时齐SASA算法理论中，收敛条件要求在每个算法理论中，收敛条件要求在每个温度下产生候选解的数目趋于无穷大，以使相温度下产生候选解的数目趋于无穷大，以使相应的马氏链达到平稳概率分布，显然在实际应应的马氏链达到平稳概率分布，显然在实际应用算法时这是无法实现的。常用的抽样准则包用算法时这是无法实现的。常用的抽样准则包括：括：检验目标函数的均值是否稳定；检验目标函数的均值是否稳定；连续若干步的目标值变化较小；连续若干步的目标值变化较小；按一定的步数抽样。按一定的步数抽样。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法20外循环终止准则外循环终止准则 外循环终止准则，即算法终止准则，用于决定算外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值是一种简单的方法。法何时结束。设置温度终值是一种简单的方法。SASA算法的收敛性理论中要求温度终值趋于零，这算法的收敛性理论中要求温度终值趋于零，这显然不合实际。通常的做法是：显然不合实际。通常的做法是：设置终止温度的阈值；设置终止温度的阈值；设置外循环迭代次数；设置外循环迭代次数；算法搜索到的最优值连续若干步保持不变；算法搜索到的最优值连续若干步保持不变；检验系统熵是否稳定。检验系统熵是否稳定。模拟退火算法模拟退火算法(Simulated Annealing)第第5章章 智能优化方法智能优化方法21小结小结q由于算法的一些环节无法在实际设计算法时实现，由于算法的一些环节无法在实际设计算法时实现，因此因此SA算法往往得不到全局最优解，或算法结算法往往得不到全局最优解，或算法结果存在波动性。果存在波动性。q目前，目前，SA算法参数的选择仍依赖于一些启发式算法参数的选择仍依赖于一些启发式准则和待求问题的性质。准则和待求问题的性质。SA算法的通用性很强，算法的通用性很强，算法易于实现，但要真正取得质量和可靠性高、算法易于实现，但要真正取得质量和可靠性高、初值鲁棒性好的效果，克服计算时间较长、效果初值鲁棒性好的效果，克服计算时间较长、效果较低的缺点，并适用于规模较大的问题，尚需进较低的缺点，并适用于规模较大的问题，尚需进行大量的研究工作。行大量的研究工作。第第5章章 智能优化方法智能优化方法221、基本概念、基本概念 模拟生物在自然环境中的遗传和进化过程而形模拟生物在自然环境中的遗传和进化过程而形成的一种成的一种自适应全局优化概率搜索算法。搜索算法。遗传算法遗传算法第第5章章 智能优化方法智能优化方法232、基本思想基本思想 对于一个求函数最大值的优化问题，一般可描对于一个求函数最大值的优化问题，一般可描述为下述数学规划模型：述为下述数学规划模型：URXX.)(maxtsf遗传算法遗传算法第第5章章 智能优化方法智能优化方法24式中，式中，为决策变量，为决策变量，f(X)为目标函为目标函数，数，U是基本空间，是基本空间，R是是U的一个子集。的一个子集。遗传算法中，将遗传算法中，将n维决策向量用维决策向量用n个记号个记号所组成的符号串所组成的符号串X来表示：来表示：Tnxxx,21X),2,1(niiXTnnxxx,2121XXXXX遗传算法遗传算法第第5章章 智能优化方法智能优化方法25 把每一个把每一个 看作一个遗传基因，它的所有可能取值称看作一个遗传基因，它的所有可能取值称为等位基因，这样，为等位基因，这样，X就可看作是由就可看作是由n个遗传基因所组个遗传基因所组成的一个染色体。染色体的长度可以是固定的，也可成的一个染色体。染色体的长度可以是固定的，也可以是变化的。等位基因可以是一组整数，也可以是某以是变化的。等位基因可以是一组整数，也可以是某一范围内的实数值，或者是记号。最简单的等位基因一范围内的实数值，或者是记号。最简单的等位基因是由是由0和和1这两个整数组成的，相应的染色体就可表示这两个整数组成的，相应的染色体就可表示为一个二进制符号串。为一个二进制符号串。iX遗传算法遗传算法第第5章章 智能优化方法智能优化方法26 这种编码所形成的排列形式这种编码所形成的排列形式X是个体的基因型，与它对是个体的基因型，与它对应的应的X值是个体的表现型。染色体值是个体的表现型。染色体X也称为个体也称为个体X，对，对于每一个个体于每一个个体X，要按照一定的规则确定出其适应度。，要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型个体的适应度与其对应的个体表现型X的目标函数值相的目标函数值相关联，关联，X越接近于目标函数的最优点，其适应度越大；越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。反之，其适应度越小。遗传算法遗传算法第第5章章 智能优化方法智能优化方法27 遗传算法中，决策变量遗传算法中，决策变量X组成了问题的解组成了问题的解空间。对问题最优解的搜索是通过对染色体空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。就组成了问题的搜索空间。生物的进化是以集团为主体的。与此相对生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由应，遗传算法的运算对象是由M个个体所组成个个体所组成的集合，称为群体。的集合，称为群体。遗传算法遗传算法第第5章章 智能优化方法智能优化方法28与生物一代一代的自然进化过程相似，遗传算法的运与生物一代一代的自然进化过程相似，遗传算法的运算过程也是一个反复迭代过程，第算过程也是一个反复迭代过程，第t代群体记做代群体记做P(t),经过经过一代遗传和进化后，得到第一代遗传和进化后，得到第t+1代群体，它们也是由多个代群体，它们也是由多个个体组成的集合，记做个体组成的集合，记做P(t+1)。这个群体不断地经过遗。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体得到一个优良的个体X，它所对应的表现型，它所对应的表现型X将达到或接将达到或接近于问题的最优解近于问题的最优解 。*X遗传算法遗传算法第第5章章 智能优化方法智能优化方法29生物的进化过程主要是通过染色体之间的交生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。遗传算法中最优解叉和染色体的变异来完成的。遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子谓的遗传算子(genetic operators)作用于群体作用于群体P(t)中，进行下述遗传操作，从而得到新一代群中，进行下述遗传操作，从而得到新一代群体体P(t+1)。遗传算法遗传算法第第5章章 智能优化方法智能优化方法30q选择选择(selection):(selection):根据各个个体的适应度，按照根据各个个体的适应度，按照一定的规则或方法，从第一定的规则或方法，从第t t代群体代群体P(t)P(t)中选择出一中选择出一些优良的个体遗传到下一代群体些优良的个体遗传到下一代群体P P(t t+1)+1)中。中。q交叉交叉(crossover):(crossover):将群体将群体P(t)P(t)内的各个个体随机内的各个个体随机搭配成对，对每一个个体，以某个概率搭配成对，对每一个个体，以某个概率(称为交叉称为交叉概率，概率，crossover rate)crossover rate)交换它们之间的部分染色交换它们之间的部分染色体。体。遗传算法遗传算法第第5章章 智能优化方法智能优化方法31q变异变异(mutation):对群体对群体P(t)中的每一个个体，中的每一个个体，以某一概率以某一概率(称为变异概率，称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它的等改变某一个或一些基因座上基因值为其它的等位基因。位基因。遗传算法遗传算法第第5章章 智能优化方法智能优化方法323 3、特点特点遗传算法是一类可用于复杂系统优化计算的鲁遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，与其他一些优化算法相比，主要有棒搜索算法，与其他一些优化算法相比，主要有下述几个特点：下述几个特点：q遗传算法以决策变量的编码作为运算对象。传统遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算对象，从而可以很方便地引入和应用遗传操作算子。子。遗传算法遗传算法第第5章章 智能优化方法智能优化方法33q遗传算法直接以目标函数值作为搜索信息。传遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值，还需统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法标函数无法求导或很难求导的函数，遗传算法就比较方便。就比较方便。遗传算法遗传算法第第5章章 智能优化方法智能优化方法34q遗传算法同时进行解空间的多点搜索。传统的优遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种隐含以不断进化。这些是遗传算法所特有的一种隐含并行性。并行性。遗传算法遗传算法第第5章章 智能优化方法智能优化方法35q遗传算法使用概率搜索技术遗传算法使用概率搜索技术 。遗传算法属于一。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都已证明了了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率在一定条件下遗传算法总是以概率1 1收敛于问题收敛于问题的最优解。的最优解。遗传算法遗传算法第第5章章 智能优化方法智能优化方法363 3、应用应用 遗传算法提供了一种求解复杂系统优化问题遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。学科。下面列举一些遗传算法的主要应用领域。遗传算法遗传算法第第5章章 智能优化方法智能优化方法37q组合优化：遗传算法是寻求组合优化问题满意解组合优化：遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合的最佳工具之一，实践证明，遗传算法对于组合优化问题中的优化问题中的NP完全问题非常有效。完全问题非常有效。遗传算法遗传算法第第5章章 智能优化方法智能优化方法38q生产调度问题：生产调度问题在很多情况下所生产调度问题：生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。已经成为解决复杂调度问题的有效工具。遗传算法遗传算法第第5章章 智能优化方法智能优化方法39q自动控制：遗传算法已经在自动控制领域中得自动控制：遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权传算法进行人工神经网络的结构优化设计和权值学习等。值学习等。遗传算法遗传算法第第5章章 智能优化方法智能优化方法40q机器人学：机器人是一类复杂的难以精确建模的机器人学：机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学自然成为遗传算适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。法的一个重要应用领域。遗传算法遗传算法第第5章章 智能优化方法智能优化方法41q图象处理：图像处理是计算机视觉中的一个重图象处理：图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。面得到了很好的应用。遗传算法遗传算法第第5章章 智能优化方法智能优化方法42q人工生命：人工生命是用计算机、机械等人工人工生命：人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。是研究人工生命现象的重要理论基础。遗传算法遗传算法第第5章章 智能优化方法智能优化方法43q机器学习：基于遗传算法的机器学习，在很多领机器学习：基于遗传算法的机器学习，在很多领域中都得到了应用。例如基于遗传算法的机器学域中都得到了应用。例如基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可以用习可用来调整人工神经网络的连接权，也可以用于人工神经网络的网络结构优化设计。于人工神经网络的网络结构优化设计。遗传算法遗传算法第第5章章 智能优化方法智能优化方法444 4、基本遗传算法基本遗传算法 基本遗传算法（基本遗传算法（Simple Genetic Algorithms,简称简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。的应用价值。遗传算法遗传算法第第5章章 智能优化方法智能优化方法45 基本遗传算法的构成要素基本遗传算法的构成要素q 染色体编码方法。基本遗传算法使用固定长染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集基因是由二值符号集00，11所组成的。初始群体所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生中各个个体的基因值可用均匀分布的随机数来生成。成。遗传算法遗传算法第第5章章 智能优化方法智能优化方法46q个体适应度评价。基本遗传算法按与个体适个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为这个概率，这里要求所有个体的适应度必须为正数或零。正数或零。q遗传算子。基本遗传算法使用下述三种遗传遗传算子。基本遗传算法使用下述三种遗传算子：选择运算使用比例选择算子，交叉运算算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异使用单点交叉算子，变异运算使用基本位变异算子或均匀变异算子。算子或均匀变异算子。遗传算法遗传算法第第5章章 智能优化方法智能优化方法47 基本遗传算法的运行参数。基本遗传算法有基本遗传算法的运行参数。基本遗传算法有下述下述4 4个运行参数需要提前设定：群体大小个运行参数需要提前设定：群体大小M M，即群体中所含个体数目，一般取为即群体中所含个体数目，一般取为2010020100；遗；遗传运算的终止进化代数传运算的终止进化代数T T，一般取为，一般取为100500100500；交叉概率交叉概率P Pc c，一般取为；，一般取为；变异概率变异概率P Pm m，一般取，一般取为。为。遗传算法遗传算法第第5章章 智能优化方法智能优化方法48基本遗传算法的形式化定义基本遗传算法的形式化定义基本遗传算法可定义为一个基本遗传算法可定义为一个8 8元组：元组：),(0TMPECSGA遗传算法遗传算法第第5章章 智能优化方法智能优化方法49C C-个体的编码方法；个体的编码方法；E E-个体适应度评价函数；个体适应度评价函数；P P0 0-初始群体；初始群体；M M-群体大小；群体大小；-选择算子；选择算子；-变异算子；变异算子；-交叉算子；交叉算子；T T-遗传运算终止条件。遗传运算终止条件。遗传算法遗传算法第第5章章 智能优化方法智能优化方法50 基本遗传算法的实现基本遗传算法的实现个体适应度评价个体适应度评价q在遗传算法中，以个体适应度的大小来确定该个在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负求所有个体的适应度必须为正数或零，不能是负数。数。遗传算法遗传算法第第5章章 智能优化方法智能优化方法51 为满足适应度取非负值的要求，基本遗传算法为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换一般采用下面两种方法之一将目标函数值变换为个体的适应度。为个体的适应度。q方法一：对于目标函数是求极大化，方法为：方法一：对于目标函数是求极大化，方法为：0)(00)(,)()(minminminCXfCXfCXfXF当，时当遗传算法遗传算法第第5章章 智能优化方法智能优化方法52 式中，式中，为一个适当地相对比较小的数，为一个适当地相对比较小的数，它可用下面几种方法之一来选取它可用下面几种方法之一来选取:预先指定的一个预先指定的一个较小的数；进化到当前代为止的最小目标函数值；较小的数；进化到当前代为止的最小目标函数值；当前代或最近几代群体中的最小目标值。当前代或最近几代群体中的最小目标值。minC遗传算法遗传算法第第5章章 智能优化方法智能优化方法53比例选择算子比例选择算子q比例选择实际上是一种有退还随机选择比例选择实际上是一种有退还随机选择,也叫做赌也叫做赌盘盘(Roulette Wheel)(Roulette Wheel)选择选择,因为这种选择方式与赌因为这种选择方式与赌博中的赌盘操作原理非常相似。博中的赌盘操作原理非常相似。q比例选择算子的具体执行过程是：先计算出群体比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操到下一代群体中的概率；最后再使用模拟赌盘操作（即作（即0 0到到1 1之间的随机数）来确定各个个体被选之间的随机数）来确定各个个体被选中的次数。中的次数。遗传算法遗传算法第第5章章 智能优化方法智能优化方法54单点交叉算子单点交叉算子q单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率对每一对相互配对的个体，依设定的交叉概率 在其交叉点处相互交换两个个体的部分染色体，在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。从而产生出两个新个体。cp遗传算法遗传算法第第5章章 智能优化方法智能优化方法55基本位变异算子基本位变异算子q基本位变异算子的具体执行过程为：对个体的每基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率一个基因座，依变异概率 指定其为变异点；指定其为变异点；对每一个指定的变异点，对其基因值做取反运算对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新或用其他等位基因值来代替，从而产生出一个新的个体。的个体。mp遗传算法遗传算法第第5章章 智能优化方法智能优化方法56 遗传算法的应用步骤遗传算法的应用步骤 遗传算法提供了一种求解复杂系统优化问遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤题的通用框架。对于具体问题，可按下述步骤来构造：来构造：q确定决策变量及其各种约束条件，即确定出确定决策变量及其各种约束条件，即确定出个体的表现型个体的表现型X和问题的解空间；和问题的解空间；q建立优化模型，即描述出目标函数的类型及建立优化模型，即描述出目标函数的类型及其数学描述形式或量化方法；其数学描述形式或量化方法；遗传算法遗传算法第第5章章 智能优化方法智能优化方法57q确定表示可行解的染色体编码方法，即确定出确定表示可行解的染色体编码方法，即确定出个体的基因型个体的基因型X及遗传算法的搜索空间；及遗传算法的搜索空间；q确定解码方法，即确定出由个体基因型确定解码方法，即确定出由个体基因型X到个到个体表现型体表现型X的对应关系或转换方法；的对应关系或转换方法；q确定个体适应度的量化评价方法，即确定出由确定个体适应度的量化评价方法，即确定出由目标函数值目标函数值 到个体适应度的转换规则；到个体适应度的转换规则；)(Xf遗传算法遗传算法第第5章章 智能优化方法智能优化方法58q设计遗传算子，即确定出选择运算、交叉运算、设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法；变异运算等遗传算子的具体操作方法；q确定遗传算法的有关运行参数，即确定出遗传确定遗传算法的有关运行参数，即确定出遗传算法的算法的 等参数。等参数。mcppTM、遗传算法遗传算法第第5章章 智能优化方法智能优化方法59第第5章章 智能优化方法智能优化方法605 5、免疫遗传算法免疫遗传算法 基于免疫的改进遗传算法，是免疫原理与传统遗基于免疫的改进遗传算法，是免疫原理与传统遗传算法的结合。传算法的结合。算法的核心在于免疫算子的构造，而免疫算子又算法的核心在于免疫算子的构造，而免疫算子又是通过接种疫苗和免疫选择两个步骤完成的。是通过接种疫苗和免疫选择两个步骤完成的。在理论上，免疫算法是概率在理论上，免疫算法是概率1 1收敛的。收敛的。遗传算法遗传算法第第5章章 智能优化方法智能优化方法61例子例子第第5章章 智能优化方法智能优化方法62第第5章章 智能优化方法智能优化方法63第第5章章 智能优化方法智能优化方法64第第5章章 智能优化方法智能优化方法65第第5章章 智能优化方法智能优化方法661 1、基本思想基本思想 是对局部邻域搜索的一种扩展，是一种全局逐步是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法。其最重要的思想是标记对应已搜索到寻优算法。其最重要的思想是标记对应已搜索到的局部最优解的一些对象，并在进一步的迭代搜的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。从而保证对不同的有效搜索途径的探索。禁忌搜索算法禁忌搜索算法(Tabu Search)第第5章章 智能优化方法智能优化方法672 2、算法步骤算法步骤 (1)(1)给定算法参数，随机产生初始解给定算法参数，随机产生初始解x x，置禁忌表，置禁忌表为空。为空。(2)(2)判断算法终止条件是否满足？若是，则结束判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。算法并输出优化结果；否则，继续以下步骤。(3)(3)利用当前解利用当前解x x的邻域函数产生其所有（或若干）的邻域函数产生其所有（或若干）邻域解，并从中确定若干个候选解。邻域解，并从中确定若干个候选解。(4)(4)对候选解判断藐视准则是否满足？若成立，对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态则用满足藐视准则的最佳状态y y代替代替x x成为新的当成为新的当前解，即前解，即x=yx=y，并用与，并用与y y对应的禁忌对象替换最早对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用进入禁忌表的禁忌对象，同时用y y替换替换“best so best so far”far”状态，然后转步骤状态，然后转步骤2 2；否则，继续以下步骤。；否则，继续以下步骤。禁忌搜索算法禁忌搜索算法(Tabu Search)第第5章章 智能优化方法智能优化方法68 (5)(5)判断候选解对应的各对象的禁忌属性，选择判断候选解对应的各对象的禁忌属性，选择候选解集合中非禁忌对象对应的最佳状态为新的候选解集合中非禁忌对象对应的最佳状态为新的当前解，同时，用与之对应的禁忌对象替换最早当前解，同时，用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。进入禁忌表的禁忌对象元素。(6)(6)转步骤转步骤(2)#(2)#注：注：1)1)其中，邻域函数、禁忌对象、禁忌表和藐其中，邻域函数、禁忌对象、禁忌表和藐视准则构成了禁忌搜索算法的关键。视准则构成了禁忌搜索算法的关键。2)2)对于邻域函数，沿用局部邻域搜索的思想，用对于邻域函数，沿用局部邻域搜索的思想，用于实现邻域搜索；于实现邻域搜索；3)禁忌表和禁忌对象的设置，体现了算法避免迂禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；回搜索的特点；4)藐视准则，则是对优良状态的奖励，它是对禁藐视准则，则是对优良状态的奖励，它是对禁忌策略的一种放松。忌策略的一种放松。禁忌搜索算法禁忌搜索算法(Tabu Search)第第5章章 智能优化方法智能优化方法691 1、基本原理基本原理 (1)(1)蚂蚁觅食时，在它走过的路上，留下外激素，蚂蚁觅食时，在它走过的路上，留下外激素，这些外激素就象留下路标一样，留给后来这些外激素就象留下路标一样，留给后来“蚁蚁”一个路径的标志。一个路径的标志。(2)(2)后面的蚂蚁，就会沿着有外激素的路径行走后面的蚂蚁，就会沿着有外激素的路径行走（外激素越多引诱蚂蚁的能力就越强）。（外激素越多引诱蚂蚁的能力就越强）。蚂蚁算法蚂蚁算法第第5章章 智能优化方法智能优化方法702 2、算法算法 (1)(1)一群蚂蚁随机从出发点出发，遇到食物，衔一群蚂蚁随机从出发点出发，遇到食物，衔住食物，沿原路返回住食物，沿原路返回 (2)(2)蚂蚁在往返途中，在路上留下外激素标志蚂蚁在往返途中，在路上留下外激素标志 (3)(3)外激素将随时间逐渐蒸发（一般可用负指数外激素将随时间逐渐蒸发（一般可用负指数函数来描述，即乘上因子函数来描述，即乘上因子e e-at-at）(4)(4)由蚁穴出发的蚂蚁由蚁穴出发的蚂蚁,其选择路径的概率与各路其选择路径的概率与各路径上的外激素浓度成正比径上的外激素浓度成正比 注：利用同样原理可以描述蚁群进行多食物源的注：利用同样原理可以描述蚁群进行多食物源的寻食情况寻食情况 蚂蚁算法蚂蚁算法第第5章章 智能优化方法智能优化方法713 3、算法应用算法应用 (1)(1)用于重建通讯路由用于重建通讯路由 (2)(2)用于求解用于求解TSPTSP（流动货郎问题（流动货郎问题)一群蚂蚁由一群蚂蚁由A A点同时出发，进行漫游，倾向选点同时出发，进行漫游，倾向选较近的城市较近的城市 把所有城市都游过后，返回，把所有城市都游过后，返回，并留下外激素，并留下外激素，其量与路程长度成反比其量与路程长度成反比 所有蚂蚁都返回后，图上留下外激素的标志所有蚂蚁都返回后，图上留下外激素的标志进行第二轮的漫游（倾向选激素多的路径）进行第二轮的漫游（倾向选激素多的路径）蚂蚁算法蚂蚁算法第第5章章 智能优化方法智能优化方法72第三章第三章 搜索技术搜索技术 (3)(3)蚂蚁清除垃圾蚂蚁清除垃圾 蚂蚁能将巢里的垃圾或死蚂蚁蚂蚁能将巢里的垃圾或死蚂蚁,打扫成几大堆打扫成几大堆给以清除给以清除 一群蚂蚁随机出发一群蚂蚁随机出发,遇到垃圾遇到垃圾,就将其拉走（方就将其拉走（方向也是随机的）向也是随机的）拉垃圾时拉垃圾时,若碰到某一堆垃圾时若碰到某一堆垃圾时,就放下就放下 放下垃圾后放下垃圾后,再随时机进行打扫工作再随时机进行打扫工作 第第5章章 智能优化方法智能优化方法73神经网络与神经网络优化算法神经网络与神经网络优化算法