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

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

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

3、某策略确定沿该方向走的长度，即步长,信赖域方法另辟蹊径：,给定点 后，确定一个（小的）变化范围，,通常取xk为中心的球域，称为信赖域，,在此邻域内找到原问题的二次函数逼近式，以二次函数的最优解作为原问题最优解的近似点xk+1，,如此往复,北京邮电大学数学系,8,最优化算法参考书,搜索方向设计总体思路：,算法搜索前半程大致沿最速下降方向搜索，,算法搜索后半程大致沿牛顿方向搜索，即大致在两个搜索方向之间摇摆；,陈宝林，最优化理论与算法，清华大学出版社,北京邮电大学数学系,9,贪心思想与模拟退火策略,第二步：在当前解确定一个搜索方向和步长，移动到新的解,新解与老解的取舍规则,若只有新解优于老解时才保

4、留新解，则是一般的贪心算法思想，但很容易陷入一个局部最优陷阱,若在算法中不仅是见了优秀解就保留，更重要的是当获得较差的解时也有可能保留，当然可能性依概率减小，即爱富而不嫌贫！,北京邮电大学数学系,10,爱富而不嫌贫的算法模拟退火算法,模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。,根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp(-E/(kT)，其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。,用固体退火

5、模拟优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。,来源于百度百科,11,退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。,模拟退火算法的模型,(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的 起点)， 每个T值的迭代次数L,(2) 对k=1，L做第(3)

6、至第6步：,(3) 产生新解S,(4) 计算增量t=f(S)-f(S)，其中C(S)为评价函数,(5) 若t0则接受S作为新的当前解，否则以概率 exp(-t/T)接受S作为新的当前解.,(6) 如果满足终止条件则输出当前解作为最优解，结束程序。,终止条件通常取连续若干个新解都没有被接受,(7) T逐渐减少，且T-0，然后转第2步。,北京邮电大学数学系,12,二、随机方式确定搜索方向,是n维向量,演化规划和演化策略产生新解的基本迭代步骤,北京邮电大学数学系,13,自古以来，人们就对生物界有着浓厚的兴趣，生物成为许多发明家创新的灵感源泉，他们从生物现象中得到启示，制造出了从机翼、雷达、防弹衣等许

7、多产品。,从20世纪中叶开始，人们就已经开始注意对生物系统尤其是人类自身功能及结构的模仿，由此产生了许多研究领域。,生命经历从低级到高级、从简单到复杂的演化之路，人类找到生命目前的最佳结构与形式，它不仅仅能被动的适应环境，更重要的是它能够通过学习、模仿和创造来主动提高适应环境的能力。,神经网络是人类对大脑信息处理机制的模拟； 模糊系统是人类对其自身思维方式的类比； 进化计算则是人类向其自身进化这一更为宏观的过程学习；免疫优化算法则是模仿人类免疫系统的高度分布性的自适应学习系统；,北京邮电大学数学系,14,1、遗传算法与进化计算技术,自然进化过程实质上就是一个学习与优化的过程，这一优化过程的目的

8、就是使生命体达到适应环境的最佳结构与效果。,北京邮电大学数学系,15,模拟进化计算技术是模拟自然界生物进化过程与机制、求解优化与搜索问题的一类自组织、自适应的人工智能技术。 生物进化过程本身是一个自然的、并行发生的、稳健的优化过程。使生命体达到适应环境的最佳结构与效果。 遗传变异理论在优化过程中保持已有的结构，同时寻找更好的结构。,进化算法包括 遗传算法 (GA, Genetic Algorithm)、 进化规划 (EP, Evolutionary Programming)、 进化策略 (ES, Evolution Strategy)和 遗传编程 (GP, Genetic Programmin

9、g)等方法，,北京邮电大学数学系,16,进化过程的三种操作：选择，交叉，变异。 选择算子：是模拟自然选择的操作，反映“优胜劣汰”原理。 根据每一个个体的适应度，按照一定规则或方法，从第t代种群X(t)中选择出一些优良的个体，让其遗传到下一代，即第t+1代种群X(t+1)中。,交叉算子：是模拟有性繁殖的基因重组操作。 从第t代种群X(t)中选择出每一对母体，依一定概率（称为交叉概率）依某种策略交换它们的部分基因。,变异算子：是模拟基因突变的遗传操作。 对第t代种群X(t)中的每一个个体，以一定概率（称为变异概率）改变某一个或某一些基因座上的基因值为其他的等位基因。,北京邮电大学数学系,17,模拟

10、进化计算技术的一般框架,步1(初始化)，确定种群规模N及终止准则（如设置最大进化代数或期望达到的近似解精度）。随机生成N个个体作为初始种群X(0)。设置进化代数计数器t0。,步2(个体评价)，计算或估价种群X(t)中每一个个体的适应度,步3(种群进化), 3.1选择，将选择算子作用于种群X(t)。 3.2繁殖，将繁殖算子（即交叉，变异）作用于选择后的种群， 并生成下一代种群X(t+1)。,步4(终止检验)，如果X(t+1)满足终止准则，则输出X(t+1)中具有最大适应度的个体作为最优解，终止计算。否则，置tt+1，转步2。,18,2、 粒子群算法,粒子群优化算法(Particle Swarm

11、Optimization algorithm)是一种进化计算技术，其思想源于对鸟群和鱼群捕食行为的模拟，PSO同遗传算法类似，是一种基于迭代的优化工具。,设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那里，但它们依据本能的认知知道当前的位置距离食物还有多远，那么找食物的最优策略是什么呢？,系统初始化为一组随机解，通过迭代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)，而是粒子在解空间追随全局和局部最优粒子进行搜索。,最简单有效的就是搜寻目前距离食物最近的鸟的周围区域，PSO从这种模型中得到启示并用于解决优化问题

12、。,这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。,北京邮电大学数学系,19,粒子群算法构成,第i个微粒表示为,本身经历过的最好位置(有最好的适应值)记为,也称为,到目前为止群体中所有微粒搜索到的最好位置记作Pg，,对每一代，其第d维根据如下方程变化,也称为gbest。,如何描述一个飞翔的鸟？,位置 和 速度！,北京邮电大学数学系,20,第k次迭代后粒子i飞行速度矢量的第d维分量；,第k次迭代后粒子i位置矢量的第d维分量；,粒子i个体最好位置pBest 的第d维分量；,群体最好位置gBest的第d维分量；,惯性权重( inertia weig

13、ht)；,速常数(acceleration constants)；,在0, 1范围内变化的随机函数。,北京邮电大学数学系,21,第3部分为“社会( social)”部分， 表示微粒间的信息共享与相互合作、学习。,第1部分为微粒先前的速度；,第2部分为“认知(cognition)”部分，表示微粒本身的思考；,北京邮电大学数学系,22,1）初始化一群粒子，随机产生每个粒子的位置和速度；,2）评价每个粒子的适应度(函数值)；,3）对每个粒子，将其适应度值与自身pbest作比较，如果当前值好于pbest，则将当前值设为该粒子的 pbest；,4）对每个粒子，将其适应度值与gbest作比较，如果当前值好

14、于gbest，则将当前值设为该群体的gbest；,5）根据方程式更新每个粒子的速度和位置；,6）如未达到终止条件（通常是足够好的适应度值或预先设定的最大代数），则返回 2）。,算法流程,标准粒子群优化算法执行过程如下：,北京邮电大学数学系,23,3、人工免疫优化算法,免疫的生物学背景,生物免疫系统是一种具有高度分布性的自适应学习系统，具有完善的机制来抵御外来病源的入侵，计算机的安全问题与生物免疫系统遇到的问题惊人的相似，于是就有人提出来：是不是可以把生物免疫系统的这些特性用于计算机领域呢？,在生物自然界中，免疫现象普遍存在，并对物种的 生存与繁衍 发挥着重要的作用；,生物的免疫功能主要是由参与

15、免疫反应的细胞或由其构成的器官来完成的；,它通过类似于生物免疫系统的机能，构造具有动态性和自适应性的信息防御体系，以此来抵制外部无用、有害信息的侵入，从而保证接受信息的有效性与无害性。,北京邮电大学数学系,24,1974年，丹麦学者 Jerne 提出了免疫系统的第一个数学模型,奠定的免疫计算的基础。1984年，由于在免疫学上的杰出贡献， Jerne 因此获得诺贝尔奖。,1994年，美国学者Forrest , Perelson 等人提出了否定选择算法，用来生成检测器，完成了检测器的耐受过程，提出了计算机免疫系统的概念。,有关计算机免疫的相关研究刚起步不久，2002年，武汉大学的梁意文教授利用免疫

16、原理对大规模网络入侵检测和预警技术进行了研究。,2003年，中国科学技术大学研制了一个“基于人工免疫的入侵预警系统”，该系统具有较好的未知入侵检测能力。,2004年，四川大学计算机网络安全与研究所提出了基于免疫的大规模网络入侵动态取证，以及网络安全风险检测与控制技术。,北京邮电大学数学系,25,2002年6月，IEEE Transaction on Evolutionary Computation 出专刊报道了有关人工免疫系统（Artificial Immune System, AIS）的研究进展,计算机免疫学（Computer Immunology）一词最早由Forrest等人提出，他认为计

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

18、己）并消除（异己）有害生物（体外入侵，体内产生）及其成分的应答过程及机制的科学。,抗原（Antigen） : 是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。,抗体（Antibody, Ab）: 能与抗原进行特异性结合的免疫细胞称为抗体。,27,自我和非我(Self and Non-self): 自我对应于机体自身的组织，非我对应于外来有害病原或者体内病变组织。,免疫系统的主要功能, 免疫防御: (immunologic defense) 即机体防御病原微生物的感染； 免疫（自身）稳定: (immunologic homeostasi

19、s) 即机体通过免疫功能经常消除那些损伤和衰老的细胞以 维持机体的生理平衡； 免疫监视: (immunologic surveillance) 即机体通过免疫功能防止或消除体内细胞在新陈代谢过程 中发生突变的和异常的细胞,自我集合和非自我集合之间的关系有:SN=X, SN=。例如，对于计算机病毒检测而言，非自体代表病毒代码，自体为计算机系统内正常的应用程序; 对于入侵检测系统，非自体代表来自网络攻击的IP数据包，而自体为正常的网络数据事务。,北京邮电大学数学系,28,免疫应答（immume response ）: 抗原进入机体后，免疫细胞对抗原分子的识别和效应过程, 称为免疫应答。可分为三个阶

20、段。,(1) 抗原提呈: 抗原提呈是指能免疫细胞能捕获、加工、处理抗原, 并将抗原提呈给抗原特异性淋巴细胞。人体内的B细胞可以利用其表面的免疫球蛋白分子（抗体）直接与抗原结合，诱导产生免疫应答。,(2) 免疫系统特异识别: 抗原被提呈后，将发生免疫系统特异识别。免疫细胞表面的受体和抗原表面的抗原决定基产生生化结合。受体和抗原决定基都是复杂的含有电荷的三维结构，二者的结构和电荷越互补，就越有可能结合，结合的强度称为亲和力（affinity）.,北京邮电大学数学系,29,(3)体细胞高频变异和免疫记忆: 人体是部最精密、最复杂的机器，人体内的免疫细胞是怎样繁殖的呢？其核心是克隆选择原理,克隆选择原

21、理主要思想： 1.免疫系统要产生数十亿种类的有抗体受体的B细胞； 2. 抗原提呈导致能与抗原结合的抗体克隆扩增和分化；,B细胞活化后，可在淋巴结内，也可在骨髓内以极高的频率分裂，同时产生克隆选择，其中一部分分化为浆细胞，它不能继续增殖，其寿命仅为数日，但是浆细胞产生抗体的能力特别强，高峰期一个浆细胞每分钟可分泌数千个抗体分子，,另一部分变成记忆细胞，形成免疫记忆，能存活数年，再被激活时，可重复以前的变化，一部分化为效应细胞，一部分仍为记忆细胞。,免疫克隆算法的基本构架,免疫算法解决具体问题，首先需要将问题的有关描述与免疫系统的有关概念及免疫原理对应起来，定义免疫系统中元素的数学表达方法，然后根

22、据实际问题的应用再设计相应的免疫算法。,定义抗原: 将需要解决的问题抽象成符合免疫系统处理的抗原形式，抗原识别则对应为问题的求解。,产生初始抗体群体: 将抗体的群体定义为问题的解，抗体与抗原之间的亲和力对应为问题的评估，初始抗体群体对应问题的一个随机解群体。,计算亲和力: 计算抗原和抗体之间的亲和力。,克隆选择和高频变异: 与抗原有较大亲和力的抗体优先得到复制，同时抑制浓度过高的抗体，淘汰亲和力低的抗体，为获得多样性，抗体在克隆过程中发生变异，克隆选择中抗体促进和克隆删除对应优化解的促进与非优化解的删除等。,评估新的抗体群体: 若不满足终止条件，则转; 否则，则当前的抗体群体为问题的最佳的求解

23、。,北京邮电大学数学系,31,北京邮电大学数学系,32,免疫遗传算法,随机创建抗体和抗原的群体; 抗体和抗原匹配; 根据抗体的亲和力对抗体做评价; 用标准遗传算法进化抗体。,这个模型使免疫系统能够通过学习，知道哪些抗体对抗原的识别有帮助。,即遗传算法的框架和免疫算法思想的融合。,北京邮电大学数学系,33,免疫系统与一般免疫算法之间的比较,北京邮电大学数学系,34,免疫算法的一个具体算例,1：随机方式产生初始抗体（n个解向量）群体；,2：计算亲和力,与最优解的距离,3. 克隆复制运算,4.高频变异和克隆选择算子:,依据某策略从选择的解出发，获得新解；,5. 免疫记忆,北京邮电大学数学系,35,初

24、始解、亲和力、克隆复制、高频变异、选择,初始抗体(解),亲和力,免疫记忆,北京邮电大学数学系,36,三、优化模型及想让大家做的问题,1、数值优化、多目标优化,多目标优化,提出好的策略，设计改进的智能优化算法，基于数值优化函数仿真、比较、写论文,北京邮电大学数学系,37,背包问题,2、组合优化：背包问题、旅行商问题,旅行商问题,多旅行商问题、动态旅行商问题等,北京邮电大学数学系,38,3、Web服务选择研究,面向服务计算作为一种新生的分布式计算理念，近年来受到了工业界和学术界的广泛关注。,但是，单个服务一般提供比较单一的功能，无法满足复杂的应用需求。因此，将多个服务组合起来，提供新的、更复杂的、功能更强大的组合服务已经成为一个新的研究热点。,Web服务应用范围的不断扩大，Web服务数量的不断增大，网络上不可避免地会出现海量的具有相同或相似功能但不同服务质量（QOS）的web服务。如果需要组合出具有某些指定功能的组合服务的话，那么，由具有相同或相似功能和不同QoS的单个服务会组合出大量的组合服务，会形成海量的服务组合方案；,北京邮电大学数学系,