智能理论智能优化算法

《智能理论智能优化算法》由会员分享，可在线阅读，更多相关《智能理论智能优化算法（56页珍藏版）》请在金锄头文库上搜索。

1、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 概述,组合

2、优化问题 优化对象：解空间中的离散状态 问题一般可描述为：寻找最优解s*，使得si，C(s*)=minC(si) =s1, s2, , sn为所有状态构成的解空间 C(si)为状态si对应的目标函数值 典型的组合优化问题：TSP问题、加工调度问题、0-1背包问题、装箱问题等。 特点：问题的描述非常简单，有很强的工程代表性，但最优化求解很困难，主要原因就是“组合爆炸”。,5,2.1 概述,二、优化算法及其分类 优化算法就是一种搜索过程或规则，它基于某种思想和机制，通过一定途径或规则来得到满足用户要求的问题的解。 就优化机制与行为而分，目前，工程中常用的优化算法主要可分为： 经典算法 构造型算法

3、改进型算法 基于系统动态演化的算法 混合型算法,6,2.1 概述,经典算法 包括线性规划、动态规划等运筹学中的传统算法。 算法计算复杂性一般很大，只适于求解小规模问题，在工程中往往不实用。 构造型算法 用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足工程需要。,7,2.1 概述,改进型算法，或称邻域搜索算法 从任一解出发，对其邻域的不断搜索和当前解的替换来实现优化。 根据搜索行为，可分为局部搜索法和指导性搜索法（如SA、GA）。 基于系统动态演化的方法 将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络和混沌搜索等。 混合型算法 上述各算法从结构或操作上相

4、混合而产生的各类算法。,8,2.2 遗传算法及其应用,1885年，达尔文用自然选择来解释物种的起源和生物的进化，达尔文的自然选择学说包括三个方面： 遗传、变异、生存斗争和适者生存 20世纪20年代，一些学者用统计生物学和种群遗传学的成就重新解释达尔文自然选择理论，形成现代综合进化论。 种群遗传学认为： 在一定地域中，一个物种的全体成员构成一个种群； 生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因库组成的变化就是这一种群的进化。,9,2.2 遗传算法及其应用,生物学中与遗传算法相关的基本概念与术语： 个体 种群 适应度 选择 交叉 变异,10,2.2 遗传算法及

5、其应用,20世纪60年代中期，J. Holland在前人工作基础上，提出了位串编码技术。 这种技术既适用于变异操作，又适用于交叉操作，并且强调将交叉作为主要的遗传操作。 随后，Holland将该算法用于自然和人工系统的自适应行为研究中，在1975出版了他的开创性著作“Adaptation in Natural and Artifical System”。 以后，Holland等人将算法进行了推广，并应用到优化及及其学习中，正式将其命名为“遗传算法”(Genetic Algorithms，简称GA)。,11,2.2 遗传算法及其应用,例：考虑一元函数求最大值的优化问题,12,2.2 遗传算法及其

6、应用,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位小数 因为，采用二进制编码方法，不

7、能表示小数和负数 所以，将闭区间-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：产生初始种群 产生一定数目的个体

8、组成种群 种群的大小（或规模）是指种群中个体数目。 种群数目是影响算法优化性能和效率的因素之一。 种群太小，不能提供足够的采样点，导致算法性能很差，甚至得不到问题的可行解。 种群太大，尽管可增加优化信息以阻止早熟收敛的发生，但会增加计算量，使收敛时间太长。 本例中，假设初始种群的大小为50个。,17,2.2 遗传算法及其应用,步骤3：计算适应度 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索。 一般，适应度函数是由目标函数变换而成。 若目标函数为最大化问题：Fit(x)=f(x) 若目标函数为最小化问题：Fit(x)=-f(x) 本例的目标

9、函数在定义域内均大于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

10、.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区间内的均匀随机数来决定哪个个体参加交叉操作。 即：用赌轮方

11、式决定个体的选择份数。,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

12、 | 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：变

13、异 基于二进制编码的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 遗传算法及其应用,不是所有被

14、选择的个体，都要进行变异操作。 变异概率是加大种群多样性的重要因素。 概率太小很难产生新个体。 概率太大会使GA成为随机搜索。 基于二进制编码的GA中，通常一个较低的变异率足以防止整个种群中任一位置的基因一直保持不变。 本例中，变异概率取为：pm = 0.01,29,2.2 遗传算法及其应用,步骤7：算法的终止判断 最常用的终止条件： 事先给定一个最大进化步数； 判断最佳优化值是否连续若干步没有明显变化。,30,2.2 遗传算法及其应用,遗传算法基本思路： 计算开始时，随机初始化一定数目的个体（即种群），并计算每个个体的适应度值，产生第一代（初始代）。 如果不满足优化准则，开始新一代的计算：

15、按照适应度值选择个体产生下一代； 父代通过交叉，产生子代； 所有的子代按一定概率变异。 重新计算子代的适应度值，形成新的一代。 这一过程循环执行，直到满足优化准则为止。,31,2.2 遗传算法及其应用,遗传算法基本流程,32,2.2 遗传算法及其应用,GA是一种通用的优化算法，它的优点有： 编码技术和遗传操作比较简单； 优化不受限制性条件的约束； 隐含并行性和全局解空间搜索。 随着计算机技术的发展，GA愈来愈得到人们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合优化、VLSI设计、遗传学等领域得到了成功应用。,33,2.3 模拟退火算法及其应用,模拟退火算法（Simulat

16、ed Annealing，SA)是一种通用的优化算法。 目前，已在：生产调度、控制工程、机器学习、神经网络、图像处理等工程领域中得到了广泛应用。 1953年，Metropolis等提出SA思想； 1983年，Kirkpatrick等将其用于组合优化，目的在于： 为具有NP复杂性的问题提供有效的近似求解算法； 克服优化过程陷入局部极小； 克服初值依赖性。,34,2.3 模拟退火算法及其应用,SA算法是基于Mente Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。,35,2.3 模拟退火算法及其应用,物理退火过程由以下三部分组成： 加温过程 增强粒子热运动，使其偏离平衡位置。当温度足够高时，固体熔解为液体，消除系统可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。 等温过程 对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。 冷却过程 使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。,