智能理论智能优化算法课件

《智能理论智能优化算法课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章智能优化算法概述遗传算法及应用模拟退火算法及其应用TSP问题蚁群算法及其应用1参考教材：王耀南,《智能信息处理技术》,高等教育出版社,2003年8月第1版.王凌,《智能优化算法及其应用》,清华大学出版社,施普林格出版社,2001年10月第1版.22.1概述一、最优化问题分类可分为函数优化问题和组合优化问题两大类。函数优化问题优化对象：一定区间内的连续变量问题一般可描述为：求点XminS使f(Xmin)在S上全局最小，符号化表示为：XS：f(Xmin)f(X)S为Rn上的有界子集，即变量的定义域f：S→R为n

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

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

4、为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络和混沌搜索等。混合型算法上述各算法从结构或操作上相混合而产生的各类算法。72.2遗传算法及其应用1885年，达尔文用自然选择来解释物种的起源和生物的进化，达尔文的自然选择学说包括三个方面：遗传、变异、生存斗争和适者生存20世纪20年代，一些学者用统计生物学和种群遗传学的成就重新解释达尔文自然选择理论，形成现代综合进化论。种群遗传学认为：在一定地域中，一个物种的全体成员构成一个种群；生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因

5、库组成的变化就是这一种群的进化。82.2遗传算法及其应用生物学中与遗传算法相关的基本概念与术语：个体种群适应度选择交叉变异92.2遗传算法及其应用20世纪60年代中期，J.Holland在前人工作基础上，提出了位串编码技术。这种技术既适用于变异操作，又适用于交叉操作，并且强调将交叉作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为研究中，在1975出版了他的开创性著作“AdaptationinNaturalandArtificalSystem”。以后，Holland等人将算法进行了推广，并应用

6、到优化及及其学习中，正式将其命名为“遗传算法”(GeneticAlgorithms，简称GA)。102.2遗传算法及其应用例：考虑一元函数求最大值的优化问题112.2遗传算法及其应用f(x)在区间[-1,2]可微，首先用微分法求取f(x)的最大值。上式的解有无穷多个：εi是一种接近于0的实数递减序列。i为奇数时，xi对应局部极大值点；i为偶数时，xi对应局部极小点。x19是区间[-1,2]内的最大点。122.2遗传算法及其应用步骤1：编码将问题的解用一种码来表示，从而将问题的状态空间与GA的码空间相对应。解题过程中，每个

7、具体的解就对应一个个体。最常用的编码方法是：二进制编码使用由二进制符号0和1组成的编码符号集。每个个体是一个二进制符号串，串长与求解精度有关。132.2遗传算法及其应用设：求解精度为6位小数因为，采用二进制编码方法，不能表示小数和负数所以，将闭区间[-1,2]改为：[0,3106]又因为：2097152=221<3×106<222=4194304所以，编码的二进制串长至少需要22位142.2遗传算法及其应用二进制串(0000000000000000000000)，表示区间端点值-1二进制串(11111111111111

8、11111111)，表示区间端点值2相应地，将一个二进制串（b21b20…b0）转化为区间[-1,2]内对应的实数，需要采用以下步骤：将二进制数转化为十进制数x’将x’转化为区间[-1，2]内的实数x152.2遗传算法及其应用步骤2：产生初始种群产生一定数目的个体组成种群种群的大小（或规模）是指种群中个体数目。种群数