最优化算法、智能优化算法及其应用

《最优化算法、智能优化算法及其应用》由会员分享，可在线阅读，更多相关《最优化算法、智能优化算法及其应用（43页珍藏版）》请在金锄头文库上搜索。

1、北京邮电大学赵新超信息与计算数学中心 数学系，理学院 主楼814最优化算法、智能优化算法及其应用1北京邮电大学数学系提 纲智能算法、最优化算法方法问题数值优化、多目标优化组合优化：背包问题、旅行商问题Web服务选择优化搜索算法一般框架网络路由优化等2北京邮电大学数学系一、搜索算法一般框架第二步：在当前解确定一个搜索方向和步长， 移动到新的解第一步：产生初始解一元问题是个实数多元问题是个向量第三步：算法终止条件，否则循环。步长：一维搜索或线搜索方向：最速下降、牛顿方向新解与老解的取舍规则3一维搜索的数学模型单变量函数的最优解问题精确、非精确的一维搜索方法4北京邮电大学数学系搜索方向与最优化算法

2、高等数学：多元函数梯度已知知识：负梯度方向是函数在当前点处 函数值下降最快的方向；方法：随机产生一点作为初始解，按该 点的负梯度方向搜索确定下一点，直至 找到最优解为止；算法终止条件：梯度等于零。最速下降方向前半程收敛快，后半程慢（Zigzag）5牛顿搜索方向优点：二次终止性，收敛速度快计算量大（求导和解方程组）；要求Hessen矩阵正定，矩阵可能病态更糟糕；不保证新解一定比老解好；缺点：6北京邮电大学数学系信赖域算法无约束优化方法通常策略是，给定点 后，某确定策略找到搜索方向再某策略确定沿该方向走的长度，即步长信赖域方法另辟蹊径：给定点 后，确定一个（小的）变化范围，通常取xk为中心的球域，

3、称为信赖域，在此邻域内找到原问题的二次函数逼近式，以二次函 数的最优解作为原问题最优解的近似点xk+1，如此往复7北京邮电大学数学系最优化算法参考书搜索方向设计总体思路：算法搜索前半程大致沿最速下降方向搜索，算法搜索后半程大致沿牛顿方向搜索，即大致 在两个搜索方向之间摇摆；陈宝林，最优化理论与算法，清华大学出版社8北京邮电大学数学系贪心思想与模拟退火策略第二步：在当前解确定一个搜索方向和步长， 移动到新的解新解与老解的取舍规则若只有新解优于老解时才保留新解，则是一般的贪心 算法思想，但很容易陷入一个局部最优陷阱若在算法中不仅是见了优秀 解就保留，更重要的是当获 得较差的解时也有可能保留 ，当然

4、可能性依概率减小， 即爱富而不嫌贫！9北京邮电大学数学系爱富而不嫌贫的算法模拟退火算法模拟退火算法来源于固体退火原理，将固体加温至充分高，再让 其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增 大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最 后在常温时达到基态，内能减为最小。 根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp(- E/(kT)，其中E为温度T时的内能，E为其改变量，k为 Boltzmann常数。 用固体退火模拟优化问题，将内能E模拟为目标函数值f，温度T 演化成控制参数t，即得到解优化问题的模拟退火算法：由初始 解i和控制参数初值t开始，对当

5、前解重复“产生新解计算目标 函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当 前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一 种启发式随机搜索过程。 来源于百度百科10北京邮电大学数学系退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的 初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。模拟退火算法的模型 (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的 起点)， 每个T值的迭代次数L (2) 对k=1，L做第(3)至第6步： (3) 产生新解S (4) 计算增量t=f(S)-f(S)，其中C(S)为评价函数 (5) 若t0，然

6、后转第2步。 11二、随机方式确定搜索方向是n维向量演化规划和演化策略产生新解的基本迭代步骤12北京邮电大学数学系自古以来，人们就对生物界有着浓厚的兴趣，生物成为许多发 明家创新的灵感源泉，他们从生物现象中得到启示，制造出了 从机翼、雷达、防弹衣等许多产品。从20世纪中叶开始，人们就已经开始注意对生物系统尤其是 人类自身功能及结构的模仿，由此产生了许多研究领域。生命经历从低级到高级、从简单到复杂的演化之路，人类找到生 命目前的最佳结构与形式，它不仅仅能被动的适应环境，更重要 的是它能够通过学习、模仿和创造来主动提高适应环境的能力。神经网络是人类对大脑信息处理机制的模拟； 模糊系统是人类对其自身

7、思维方式的类比； 进化计算则是人类向其自身进化这一更为宏观的过程学习； 免疫优化算法则是模仿人类免疫系统的高度分布性的自适应 学习系统；13北京邮电大学数学系1、遗传算法与进化计算技术自然进化过程实质上就是一个学习与优化的过程，这一优化 过程的目的就是使生命体达到适应环境的最佳结构与效果。14北京邮电大学数学系 模拟进化计算技术是模拟自然界生物进化过程与机制、 求解优化与搜索问题的一类自组织、自适应的人工智能 技术。 生物进化过程本身是一个自然的、并行发生的、稳健的 优化过程。使生命体达到适应环境的最佳结构与效果。 遗传变异理论在优化过程中保持已有的结构，同时寻找 更好的结构。进化算法包括 遗

8、传算法 (GA, Genetic Algorithm)、 进化规划 (EP, Evolutionary Programming)、 进化策略 (ES, Evolution Strategy)和 遗传编程 (GP, Genetic Programming)等方法，15北京邮电大学数学系 进化过程的三种操作：选择，交叉，变异。 选择算子：是模拟自然选择的操作，反映“优胜劣汰”原理。 根据每一个个体的适应度，按照一定规则或方法，从第t代种群X(t)中选择出一些优良的个体，让其遗传到下一代，即第t+1代种群X(t+1)中。交叉算子：是模拟有性繁殖的基因重组操作。 从第t代种群X(t)中选择出每一对母体

9、，依一定概率（称 为交叉概率）依某种策略交换它们的部分基因。变异算子：是模拟基因突变的遗传操作。 对第t代种群X(t)中的每一个个体，以一定概率（称为变异概率 ）改变某一个或某一些基因座上的基因值为其他的等位基因。16北京邮电大学数学系模拟进化计算技术的一般框架步1(初始化)，确定种群规模N及终止准则（如设置最大进化代 数或期望达到的近似解精度）。随机生成N个个体作为初始种 群X(0)。设置进化代数计数器t0。步2(个体评价)，计算或估价种群X(t)中每一个个体的适应度步3(种群进化),3.1选择，将选择算子作用于种群X(t)。3.2繁殖，将繁殖算子（即交叉，变异）作用于选择后的种群， 并生成

10、下一代种群X(t+1)。步4(终止检验)，如果X(t+1)满足终止准则，则输出 X(t+1)中具有最大适应度的个体作为最优解，终止计算。 否则，置tt+1，转步2。17北京邮电大学数学系2、 粒子群算法 粒子群优化算法(Particle Swarm Optimization algorithm)是一种 进化计算技术，其思想源于对鸟群和鱼群捕食行为的模拟， PSO同遗传算法类似，是一种基于迭代的优化工具。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里 只有一块食物，所有的鸟都不知道食物在那里，但它们依据 本能的认知知道当前的位置距离食物还有多远，那么找食物 的最优策略是什么呢？系统初始化为

11、一组随机解，通过迭代搜寻最优值。但是并没有 遗传算法用的交叉(crossover)以及变异(mutation)，而是粒子在 解空间追随全局和局部最优粒子进行搜索。 最简单有效的就是搜寻目前距离食物最近的鸟的周围区域， PSO从这种模型中得到启示并用于解决优化问题。 这种算法以其实现容易、精度高、收敛快等优点引起了学术界 的重视,并且在解决实际问题中展示了其优越性。 18粒子群算法构成第i个微粒表示为本身经历过的最好位置(有最好的适应值)记为 也称为到目前为止群体中所有微粒搜索到的最好位置记作Pg，对每一代，其第d维根据如下方程变化表示。微粒 i 的速度用也称为gbest。如何描述一个飞翔的鸟？

12、位置 和 速度！19北京邮电大学数学系第k次迭代后粒子i飞行速度矢量的第d维分量； 第k次迭代后粒子i位置矢量的第d维分量； 粒子i个体最好位置pBest 的第d维分量； 群体最好位置gBest的第d维分量； 惯性权重( inertia weight)； 速常数(acceleration constants)；在0, 1范围内变化的随机函数。 20北京邮电大学数学系第3部分为“社会( social)”部分，表示微粒间的信息共享与相互合作、学习。第1部分为微粒先前的速度；第2部分为“认知(cognition)”部分，表示微粒本身的思考；21北京邮电大学数学系1）初始化一群粒子，随机产生每个粒子的

13、位置和速度；2）评价每个粒子的适应度(函数值)；3）对每个粒子，将其适应度值与自身pbest作比较，如果 当前值好于pbest，则将当前值设为该粒子的 pbest；4）对每个粒子，将其适应度值与gbest作比较，如果当前值 好于gbest，则将当前值设为该群体的gbest；5）根据方程式更新每个粒子的速度和位置；6）如未达到终止条件（通常是足够好的适应度值或预先设定 的最大代数），则返回 2）。算法流程标准粒子群优化算法执行过程如下：22北京邮电大学数学系3、人工免疫优化算法免疫的生物学背景生物免疫系统是一种具有高度分布性的自适应学习系统，具有 完善的机制来抵御外来病源的入侵，计算机的安全问题

14、与生物 免疫系统遇到的问题惊人的相似，于是就有人提出来：是不是 可以把生物免疫系统的这些特性用于计算机领域呢？在生物自然界中，免疫现象普遍存在，并对物种的 生存与繁衍 发挥着重要的作用；生物的免疫功能主要是由参与免疫反应的细胞或由其构成 的器官来完成的；它通过类似于生物免疫系统的机能，构造具有动态性和自适应 性的信息防御体系，以此来抵制外部无用、有害信息的侵入， 从而保证接受信息的有效性与无害性。23北京邮电大学数学系1974年，丹麦学者 Jerne 提出了免疫系统的第一个数学模型,奠 定的免疫计算的基础。1984年，由于在免疫学上的杰出贡献， Jerne 因此获得诺贝尔奖。1994年，美国学

15、者Forrest , Perelson 等人提出了否定选择算法 ，用来生成检测器，完成了检测器的耐受过程，提出了计算机 免疫系统的概念。有关计算机免疫的相关研究刚起步不久，2002年，武汉大学 的梁意文教授利用免疫原理对大规模网络入侵检测和预警技 术进行了研究。2003年，中国科学技术大学研制了一个“基于人工免疫的入 侵预警系统”，该系统具有较好的未知入侵检测能力。2004年，四川大学计算机网络安全与研究所提出了基于免疫的 大规模网络入侵动态取证，以及网络安全风险检测与控制技术 。24北京邮电大学数学系2002年6月，IEEE Transaction on Evolutionary Compu

16、tation 出专 刊报道了有关人工免疫系统（Artificial Immune System, AIS） 的研究进展计算机免疫学（Computer Immunology）一词最早由Forrest等人 提出，他认为计算机免疫学是一门基于生物免疫学、人工免疫 、以及计算机科学等的交叉学科，主要利用最新计算机科学技 术，研究有关人工免疫的理论、规则、算法、模型等，并将这 些理论应用于具体的应用系统中，解决实际的应用课题。 总之，计算机免疫学是一门多学科领域的、边缘交叉学科。现在，计算机免疫学的同义词有很多。例如，计算机免疫系统 、免疫计算、免疫计算机、人工免疫、基于免疫的系统等。25北京邮电大学数学系免疫学中一些基本概念免疫（Immunity）: 指机体识别和排除抗原异物，维持机体生理平衡和稳定的功能 。 免疫学（Immunology): 研究机体免疫系统的组成（免疫器官、免疫细胞和免疫分子） ，识别（自己、异己）并消