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