智能理论智能优化算法.ppt

1,第二章 智能优化算法,概述 遗传算法及应用 模拟退火算法及其应用 tsp问题 蚁群算法及其应用,2,参考教材：,王耀南, 智能信息处理技术, 高等教育出版社, 2003年8月第1版. 王凌, 智能优化算法及其应用, 清华大学出版社, 施普林格出版社, 2001年10月第1版.,3,2.1 概述,一、最优化问题分类 可分为函数优化问题和组合优化问题两大类。 函数优化问题 优化对象：一定区间内的连续变量 问题一般可描述为：求点xmins使f(xmin)在s上全局最小，符号化表示为：xs：f(xmin)f(x) s为rn上的有界子集，即变量的定义域 f：sr为n维实值函数,4,2.1 概述,组合优化问题 优化对象：解空间中的离散状态 问题一般可描述为：寻找最优解s*，使得si，c(s*)=minc(si) =s1, s2, , sn为所有状态构成的解空间 c(si)为状态si对应的目标函数值 典型的组合优化问题：tsp问题、加工调度问题、0-1背包问题、装箱问题等。 特点：问题的描述非常简单，有很强的工程代表性，但最优化求解很困难，主要原因就是“组合爆炸”。,5,2.1 概述,二、优化算法及其分类 优化算法就是一种搜索过程或规则，它基于某种思想和机制，通过一定途径或规则来得到满足用户要求的问题的解。 就优化机制与行为而分，目前，工程中常用的优化算法主要可分为： 经典算法 构造型算法 改进型算法 基于系统动态演化的算法 混合型算法,6,2.1 概述,经典算法 包括线性规划、动态规划等运筹学中的传统算法。 算法计算复杂性一般很大，只适于求解小规模问题，在工程中往往不实用。 构造型算法 用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足工程需要。,7,2.1 概述,改进型算法，或称邻域搜索算法 从任一解出发，对其邻域的不断搜索和当前解的替换来实现优化。 根据搜索行为，可分为局部搜索法和指导性搜索法（如sa、ga）。 基于系统动态演化的方法 将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络和混沌搜索等。 混合型算法 上述各算法从结构或操作上相混合而产生的各类算法。,8,2.2 遗传算法及其应用,1885年，达尔文用自然选择来解释物种的起源和生物的进化，达尔文的自然选择学说包括三个方面： 遗传、变异、生存斗争和适者生存 20世纪20年代，一些学者用统计生物学和种群遗传学的成就重新解释达尔文自然选择理论，形成现代综合进化论。 种群遗传学认为： 在一定地域中，一个物种的全体成员构成一个种群； 生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因库组成的变化就是这一种群的进化。,9,2.2 遗传算法及其应用,生物学中与遗传算法相关的基本概念与术语： 个体 种群 适应度 选择 交叉 变异,10,2.2 遗传算法及其应用,20世纪60年代中期，j. holland在前人工作基础上，提出了位串编码技术。 这种技术既适用于变异操作，又适用于交叉操作，并且强调将交叉作为主要的遗传操作。 随后，holland将该算法用于自然和人工系统的自适应行为研究中，在1975出版了他的开创性著作“adaptation in natural and artifical system”。 以后，holland等人将算法进行了推广，并应用到优化及及其学习中，正式将其命名为“遗传算法”(genetic algorithms，简称ga)。,11,2.2 遗传算法及其应用,例：考虑一元函数求最大值的优化问题,12,2.2 遗传算法及其应用,f(x)在区间-1, 2可微，首先用微分法求取f(x)的最大值。 上式的解有无穷多个： i是一种接近于0的实数递减序列。 i为奇数时，xi对应局部极大值点； i为偶数时，xi对应局部极小点。 x19是区间-1, 2内的最大点。,13,2.2 遗传算法及其应用,步骤1：编码 将问题的解用一种码来表示，从而将问题的状态空间与ga的码空间相对应。 解题过程中，每个具体的解就对应一个个体。 最常用的编码方法是：二进制编码 使用由二进制符号0和1组成的编码符号集。 每个个体是一个二进制符号串，串长与求解精度有关。,14,2.2 遗传算法及其应用,设：求解精度为6位小数 因为，采用二进制编码方法，不能表示小数和负数 所以，将闭区间-1, 2改为：0, 3106 又因为：2097152 = 221 3106 222 = 4194304 所以，编码的二进制串长至少需要22位,15,2.2 遗传算法及其应用,二进制串(0000000000000000000000)，表示区间端点值-1 二进制串(1111111111111111111111)，表示区间端点值2 相应地，将一个二进制串（b21b20b0）转化为区间-1, 2内对应的实数，需要采用以下步骤： 将二进制数转化为十进制数 x 将 x 转化为区间-1，2内的实数 x,16,2.2 遗传算法及其应用,步骤2：产生初始种群 产生一定数目的个体组成种群 种群的大小（或规模）是指种群中个体数目。 种群数目是影响算法优化性能和效率的因素之一。 种群太小，不能提供足够的采样点，导致算法性能很差，甚至得不到问题的可行解。 种群太大，尽管可增加优化信息以阻止早熟收敛的发生，但会增加计算量，使收敛时间太长。 本例中，假设初始种群的大小为50个。,17,2.2 遗传算法及其应用,步骤3：计算适应度 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索。 一般，适应度函数是由目标函数变换而成。 若目标函数为最大化问题：fit(x)=f(x) 若目标函数为最小化问题：fit(x)=-f(x) 本例的目标函数在定义域内均大于0，而且求函数最大值，所以直接引用目标函数作为适应度函数：f(s)=f(x)，式中，二进制串s对应变量x的值。,18,2.2 遗传算法及其应用,设某个个体的二进制为：s=(1000101110110101000111),19,2.2 遗传算法及其应用,设有三个个体的二进制为：s1 = (1000101110110101000111) s2=(0000001110000000010000) s3=(1110000000111111000101) 分别对应于变量：x1=0.637197、x2=-0.958973、x3=1.627888 个体的适应度为：f(s1)=f(x1)=2.586345、f(s2)=f(x2)=1.078878 f(s3)=f(x3)=3.250650 三个个体中s3的适应度最大，因此，s3为最佳个体。,20,2.2 遗传算法及其应用,步骤4：选择 选择操作决定从父代种群中选取哪些个体遗传到下一代种群中，它以个体的适应度值为评价指标，对种群中个体进行优胜劣汰。 最常用的算子：比例选择算子（选择的蒙特卡罗法） 基本思想：每个个体被选中的概率与其适应度值成正比。 设种群规模为m，个体i的适应度值为fi，则个体i被选中的概率pi为：,21,2.2 遗传算法及其应用,当pi给定后，产生0, 1区间内的均匀随机数来决定哪个个体参加交叉操作。 即：用赌轮方式决定个体的选择份数。,22,2.1 遗传算法及其应用,23,2.2 遗传算法及其应用,fi /fi,经选择产生的交叉种群由以下个体组成：1，2，3，5，6，9,24,2.2 遗传算法及其应用,步骤5：交叉 在选择操作基础上，根据交叉概率pc进行交叉操作：把两个父个体的部分结构进行替换重组，生成新个体。 对应于二进制编码，常用的交叉算子是：单点交叉。 交叉点的范围为：1，n-1，n为二进制串的串长。 交叉操作时，个体以该点为分界相互交换变量。,25,2.2 遗传算法及其应用,设经过选择操作，得到两个个体： s2 = (00000 | 01110000000010000) s3 = (11100 | 00000111111000101) 随机选择一个交叉点，交叉后产生新的子个体： s2 = (00000 | 00000111111000101) s3 = (11100 | 01110000000010000) f(s2)=f(-0.998113)=1.940865、f(s3)=f(1.666028)=3.459245,26,2.2 遗传算法及其应用,pc控制交叉操作频率，使部分被选择的个体进行交叉操作 pc太大，个体更新过快，高适应度值的个体很快被破坏。 pc太小，很少进行交叉操作，使搜索停滞不前。 本例中，交叉概率取为：pc = 0.25,27,2.2 遗传算法及其应用,步骤6：变异 基于二进制编码的ga中，变异是指将被选中个体的某一位进行翻转操作，即：将1换为0，将0换为1。 设以一小概率选择了第5位变异： s3=(1110000000111111000101)、s3=(1110100000111111000101) f(s3)=f(1.721638)=0.917743f(s3)=3.250650 若选择第10位变异，产生的新个体为： s3=(1110000000111111000101)、s3=(1110100001111111000101) f(s3)=f(1.630818)=3.343555f(s3)=3.250650,28,2.2 遗传算法及其应用,不是所有被选择的个体，都要进行变异操作。 变异概率是加大种群多样性的重要因素。 概率太小很难产生新个体。 概率太大会使ga成为随机搜索。 基于二进制编码的ga中，通常一个较低的变异率足以防止整个种群中任一位置的基因一直保持不变。 本例中，变异概率取为：pm = 0.01,29,2.2 遗传算法及其应用,步骤7：算法的终止判断 最常用的终止条件： 事先给定一个最大进化步数； 判断最佳优化值是否连续若干步没有明显变化。,30,2.2 遗传算法及其应用,遗传算法基本思路： 计算开始时，随机初始化一定数目的个体（即种群），并计算每个个体的适应度值，产生第一代（初始代）。 如果不满足优化准则，开始新一代的计算： 按照适应度值选择个体产生下一代； 父代通过交叉，产生子代； 所有的子代按一定概率变异。 重新计算子代的适应度值，形成新的一代。 这一过程循环执行，直到满足优化准则为止。,31,2.2 遗传算法及其应用,遗传算法基本流程,32,2.2 遗传算法及其应用,ga是一种通用的优化算法，它的优点有： 编码技术和遗传操作比较简单； 优化不受限制性条件的约束； 隐含并行性和全局解空间搜索。 随着计算机技术的发展，ga愈来愈得到人们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合优化、vlsi设计、遗传学等领域得到了成功应用。,33,2.3 模拟退火算法及其应用,模拟退火算法（simulated annealing，sa)是一种通用的优化算法。 目前，已在：生产调度、控制工程、机器学习、神经网络、图像处理等工程领域中得到了广泛应用。 1953年，metropolis等提出sa思想； 1983年，kirkpatrick等将其用于组合优化，目的在于： 为具有np复杂性的问题提供有效的近似求解算法； 克服优化过程陷入局部极小； 克服初值依赖性。,34,2.3 模拟退火算法及其应用,sa算法是基于mente carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。,35,2.3 模拟退火算法及其应用,物理退火过程由以下三部分组成： 加温过程 增强粒子热运动，使其偏离平衡位置。当温度足够高时，固体熔解为液体，消除系统可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。 等温过程 对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。 冷却过程 使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。,36,2.3 模拟退火算法及其应用,为了模拟固体在恒定温度下达到热平衡的过程，可采用 monte carlo方法，该方法简单，但必须大量采样才能得到较精确结果，计算量很大。 考虑到物理系统倾向于能量较低的状态，而热运动又妨碍它准确落到最低态的图像，采样时着重取那些有重要贡献的状态则可较快达到较好的结果。 1953年，metropolis等据此提出了重要性采样法（也称为metropolis 准则），即以概率接受新状态。,37,2.3 模拟退火算法及其应用,metropolis准则： 在温度t，由当前状态i产生新状态j，两者的能量分别为ci和cj， 若cj ci ，则接受新状态j为当前状态； 否则， 若概率pr=exp-(cj-ci)/(kt)大于0, 1)区间内的随机数，仍接受新状态j为当前状态; 若不成立，则保留状态i为当前状态。 其中，k为boltzmann常数。,38,2.3 模拟退火算法及其应用,sa算法的基本思路： 由某一较高初温开始，利用具有概率突跳特性的metropolis抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。,39,2.3 模拟退火算法及其应用,例：考虑一元函数求最大值的优化问题,40,2.3 模拟退火算法及其应用,步骤1：确定编码方式和能量函数（目标函数） 最常用的编码方案：实数编码，以实数来表示求解状态。 s=1.8 函数优化问题中，能量函数由待优化函数变换而成。 若目标函数为最大化问题：c(s)=-f(s) 若目标函数为最小化问题：c(s)=f(s),41,2.3 模拟退火算法及其应用,步骤2：确定初温 实验表明，初温t0越大，获得高质量解的几率越大，但计算时间增加。 初温的确定应折衷考虑优化质量和效率，常用方法包括： 均匀抽样一组状态，以各状态目标值的方差为初温。 随机产生一组状态，确定两两状态间的最大目标值差|max|，计算初温，t0=-max / lnpr 初始接受概率pr理论上接近于1。 初温也可选为某个较大的常数。,42,2.3 模拟退火算法及其应用,步骤3：确定初始状态（初始解） 理论上，初始状态可以随机取，但为了提高优化效率，可采用启发式算法快速得到一个解，并以此为sa的初始状态。,43,2.3 模拟退火算法及其应用,步骤4：状态产生函数 （新解产生函数） 设计的出发点是尽可能保证产生的候选解遍布全部解空间。 最常用的状态产生函数：snew=sold+ 为扰动幅度参数，为随机扰动变量。 随机扰动可服从柯西分布、高斯分布、均匀分布。,44,2.3 模拟退火算法及其应用,柯西分布： a为尺度参数 高斯分布： 为方差，均值为0 均匀分布：,45,2.3 模拟退火算法及其应用,以原点为中心的柯西和高斯分布函数曲线,46,2.3 模拟退火算法及其应用,步骤5：状态接受函数 该函数的引入是sa算法实现全局搜索的最关键因素，一般以概率方式给出。 最常用的状态接受函数： min1, exp-(c(sj)-c(si)/tkrandom0,1 ？ 设计状态接受概率，应该遵循以下原则： 固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率； 随温度下降，接受使目标函数值上升解的概率要逐渐减小 当温度趋于零时，只能接受目标函数值下降的解。,47,2.3 模拟退火算法及其应用,步骤6：内循环终止准则 或称metropolis抽样稳定准则 常用的抽样稳定准则包括： 检验目标函数的均值是否稳定； 连续若干步的目标值变化较小； 按一定的步数抽样。,48,2.3 模拟退火算法及其应用,步骤7：退温函数 温度的下降方式，用于在外循环中修改温度值。 目前，最常用的温度更新函数： 指数退温函数：tk+1=tk 为退温速率，0l，且大小可以不断变化。,49,2.3 模拟退火算法及其应用,步骤8：外循环终止准则 即算法终止准则，用于决定算法何时结束。 设置温度终值te是一种简单的方法，sa算法的收敛性理论中要求te趋于零，这显然不实际。 通常的做法包括： 设置终止温度的阈值； 设置外循环迭代次数； 算法搜索到的最优值连续若干步