ch2智能优化算法-研究生

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

1、第二章智能优化算法第二章智能优化算法概述进化计算及其应用模拟退火算法及其应用群智能算法及其应用3参考教材王凌,《智能优化算法及其应用》,清华大学出版社,施普林格出版社,2001年10月第1版.王小玉,《遗传算法—理论、应用与软件实现》,西安交通大学出版社,2002年1月第1版王耀南,《智能信息处理技术》,高等教育出版社,2003年8月第1版.42.1概述一、最优化问题分类可分为函数优化问题和组合优化问题两大类。函数优化问题：最小化和最大化优化对象：一定区间S内的连续变量最小化问题的一般描述：求XminS使f(Xmin)在S上全局最小符号化表示为：

2、XS:f(Xmin)f(X)S为Rn上的有界子集，即变量的定义域f:S→R为n维实值函数52.1概述一、最优化问题分类函数优化问题最大化问题的一般描述：求XmaxS使f(Xmax)在S上全局最大符号化表示为：XS:f(Xmax)f(X)S为Rn上的有界子集，即变量的定义域f:S→R为n维实值函数82.1概述经典算法如：线性规划、动态规划、整数规划、分枝定界等运筹学中的传统算法。算法计算复杂性一般很大，只适于求解小规模问题，在工程中往往不实用。构造型算法用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足工程需要。调度中的典型构造型

3、算法有：Johnson法、Palmer法、基于枚举树的分区法等。92.1概述改进型算法，或称邻域搜索算法从任一解出发，通过对其邻域的不断搜索和当前解的替换来实现优化。根据搜索行为，可分为局部搜索法和指导性搜索法（如SA、GA）。基于系统动态演化的方法将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络、蚁群算法、混沌搜索等。混合型算法上述各算法从结构或操作上混合而产生的各类算法。2.2进化算法及其应用2.2.1进化算法简介2.2.2遗传算法与生物进化学说2.2.3遗传算法的计算机实现2.2.4遗传算法解决TSP问题2.2.5遗

4、传算法的特点10产生背景主要特点理论基础分类说明2.2.1进化算法简介一、产生背景对自身的大脑信息处理机制进行模拟----人工神经网络理论对自身模糊性的思维方式进行类比----模糊系统对自然界中动植物的免疫机理进行模拟----免疫系统对自身进化这一更为宏观的过程学习----进化算法(EvolutionaryComputation，EC)2.2.1进化算法简介进化算法是一种模拟生物进化过程与机制求解问题的自组织、自适应人工智能技术。优胜劣汰，适者生存进化规则繁殖、变异、竞争、选择指导思想进化算法是建立在模拟生物进化过程的基础上而产生的一种随机搜索优化技

5、术2.2.1进化算法简介2.2.1进化算法简介二、主要特点在算法中主要表现为全局搜索方式，体现在下面几个方面有指导搜索：依据是每个个体的适应度值自适应搜索：通过进化操作改进群体性能渐进式寻优：每代进化的结果都优于上一代并行式搜索：对每一代群体所有个体同时进行黑箱式结构：只要研究输入和输出而不需考虑过程全局最优解：在整个搜索区域的各个部分同时进行内在学习型：学习是一种有保留的行为稳健性强：不同的条件和环境下算法适用和有效性2.2.1进化算法简介三、理论基础进化计算是模拟生物进化理论而形成的一种全局优化自适应概率搜索的算法理论。具有深厚的生物学理论基础：

6、遗传：父代利用遗传基因将自身的基因信息交付给下一代（子代），属性特征相同或相近。变异：子代和父代，以及子代各个体之间存在着一定的差异，在进化过程中是随机发生的。生存斗争和适者生存：适应性变异较强的个体被保留下来，而适应性变异较弱的个体则被淘汰。2.2.1进化算法简介四、分类说明从进化的过程性质进行区分，与进化算法相关的算法可细分为：遗传算法：最具代表性也是最基本的进化策略：侧重于数值分析进化规划：介于数值分析与人工智能之间遗传规划：偏向以程式表现人工智能行为进化动力学：偏向进化的自组织和系统动力学特性分类系统：适应动态环境学习动态模拟系统：用以观察复

7、杂系统交互元胞自动机：研究人工生命蚁群系统：模拟蚂蚁群体行为172.2.2遗传算法与生物进化学说1885年，达尔文用自然选择来解释物种的起源和生物的进化，达尔文的自然选择学说包括三个方面：遗传变异生存斗争和适者生存182.2.2遗传算法与生物进化学说20世纪20年代，一些学者用统计生物学和种群遗传学的成就重新解释达尔文自然选择理论，形成现代综合进化论。种群遗传学认为：在一定地域中一个物种的全体成员构成一个种群；生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因库组成的变化就是这一种群的进化。192.2.2遗传算法与生物进

8、化学说GA中与生物学相关的概念与术语：个体种群适应度选择交叉变异优化问题中的描述：解解集/解空间评价函数/目