第五章 物流系统的智能优化方法

物流系统的智能优化方法物流系统工程——第5章智能优化方法2课程内容模拟退火算法、遗传算法、禁忌搜索算法、神经网络与神经网络优化算法课程目标了解智能优化的模型结构；理解模拟退火算法的收敛性条件；掌握智能优化的流程、操作、算法理论与技术物流系统优化的智能优化方法为复杂物流管理决策问题提供了重要的可行性解决方案。物流系统工程——第5章智能优化方法3模拟退火算法(SimulatedAnnealing)1、基本思想(1)是基于MonteCarlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。(2)结合爬山法和随机行走注：SA算法最早是由Metropolis等(1953)提出物流系统工程——第5章智能优化方法4(3)模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法52、物理退火过程和Metropolis准则简单而言，物理退火过程由以下三部分组成：⑴加温过程。其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将溶解为液体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程联系，系统能量也随温度的升高而增大。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法6⑵等温过程。物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。⑶冷却过程。目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法7Metropolis等在1953年提出了重要性采样法，即以概率接受新状态。具体而言，在温度t,由当前状态i产生新状态j，两者的能量分别为，若则接受新状态j为当前状态；否则，若概率大于区间内的随机数则仍旧接受新状态j为当前状态，若不成立则保留i为当前状态，其中k为Boltzmann常数。jiEE和ijEE]/)(exp[ktEEpijr)1,0[模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法8这种重要性采样过程在高温下可接受与当前状态能量差较大的新状态，而在低温下基本只接受与当前能量差较小的新状态，而且当温度趋于零时，就不能接受比当前状态能量高的新状态。这种接受准则通常称为Metropolis准则。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法92、算法步骤标准模拟退火算法的一般步骤可描述如下：⑴给定初温，随机产生初始状态，令；⑵Repeat:①Repeat产生新状态；0tt0ss0k)(sGenetesjjjssrandomsCsCif]1,0[))]}()((exp[,1min{模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法10Until抽样稳定准则满足；②退温，并令；Until算法终止准则满足；⑶输出算法搜索结果。)(1kktupdatet1kk模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法113、算法关键参数和操作的设定从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定SA算法的优化性能。此外，初温的选择对SA算法性能也有很大影响。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法12⑴状态产生函数设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法13⑵状态接受函数状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则：①在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法14②随温度的下降，接受使目标函数值上升的解的概率要逐渐减小；③当温度趋于零时，只能接受目标函数值下降的解。状态接受函数的引入是SA算法实现全局搜索的最关键的因素，SA算法中通常采用min[1,exp(-△C/t)]作为状态接受函数。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法15⑶初温初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程(annealingschedule)。实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法16①均匀抽样一组状态，以各状态目标值的方差为初温。②随机产生一组状态，确定两两状态间的最大目标值差，然后依据差值，利用一定的函数确定初温。譬如，其中为初始接受概率。③利用经验公式给出。||maxrptln/0rp模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法17⑷温度更新函数温度更新函数，即温度的下降方式，用于在外循环中修改温度值。目前，最常用的温度更新函数为指数退温函数，即，其中且其大小可以不断变化。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法18⑸内循环终止准则内循环终止准则，或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。在非时齐SA算法理论中，由于在每个温度下只产生一个或少量候选解，所以不存在选择内循环终止准则的问题。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法19而在时齐SA算法理论中，收敛条件要求在每个温度下产生候选解的数目趋于无穷大，以使相应的马氏链达到平稳概率分布，显然在实际应用算法时这是无法实现的。常用的抽样准则包括：①检验目标函数的均值是否稳定；②连续若干步的目标值变化较小；③按一定的步数抽样。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法20⑹外循环终止准则外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值是一种简单的方法。SA算法的收敛性理论中要求温度终值趋于零，这显然不合实际。通常的做法是：①设置终止温度的阈值；②设置外循环迭代次数；③算法搜索到的最优值连续若干步保持不变；④检验系统熵是否稳定。模拟退火算法(SimulatedAnnealing)物流系统工程——第5章智能优化方法21小结由于算法的一些环节无法在实际设计算法时实现，因此SA算法往往得不到全局最优解，或算法结果存在波动性。目前，SA算法参数的选择仍依赖于一些启发式准则和待求问题的性质。SA算法的通用性很强，算法易于实现，但要真正取得质量和可靠性高、初值鲁棒性好的效果，克服计算时间较长、效果较低的缺点，并适用于规模较大的问题，尚需进行大量的研究工作。物流系统工程——第5章智能优化方法221、基本概念模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。遗传算法物流系统工程——第5章智能优化方法232、基本思想对于一个求函数最大值的优化问题，一般可描述为下述数学规划模型：UΡRXX..)(maxtsf遗传算法物流系统工程——第5章智能优化方法24式中，为决策变量，f(X)为目标函数，U是基本空间，R是U的一个子集。遗传算法中，将n维决策向量用n个记号所组成的符号串X来表示：Tnxxx],,,[21X),,2,1(niiXTnnxxx],,,[2121XXXXX遗传算法物流系统工程——第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生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子(geneticoperators)作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。遗传算法物流系统工程——第5章智能优化方法30选择(selection):根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率(称为交叉概率，crossoverrate)交换它们之间的部分染色体。遗传算法物流系统工程——第5章智能优化方法31变异(mutation):对群体P(t)中的每一个个体，以某一概率(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它的等位基因。遗传算法物流系统工程——第5章智能优化方法323、特点遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，与其他一些优化算法相比，主要有下述几个特点：遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算子。遗传算法物流系统工程——第5章智能优化方法33遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法就比较方便。遗传算法物流系统工程——第5章智能优化方法34遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜