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

北京邮电大学数学系 北京邮电大学 提 纲 一、搜索算法一般框架 贪心思想与模拟退火策略 二、随机方式确定搜索方向 1、遗传算法与进化计算技术 2、 粒子群算法 粒子群算法构成 3、人工免疫优化算法 免疫克隆算法的基本构架 免疫系统与一般免疫算法之间的比较 免疫算法的一个具体算例 三、优化模型及想让大家做的问题 参考资料 免疫遗传算法 ①随机创建抗体和抗原的群体; ②抗体和抗原匹配; ③根据抗体的亲和力对抗体做评价; ④用标准遗传算法进化抗体。 这个模型使免疫系统能够通过学习，知道哪些抗体对抗原的识别有帮助。 即遗传算法的框架和免疫算法思想的融合。 利用遗传算子产生新抗体 抗体增加(细胞克隆) 剩余候选解的消除 细胞抑制 优良解(记忆)的保持 淋巴细胞分化 联想过去的成功 从记忆细胞产生抗体 问题识别 抗原识别 最佳解向量 抗体 要解决的问题 抗原 免疫算法 免疫系统 1：随机方式产生初始抗体(n个解向量)群体； 2：计算亲和力 与最优解的距离 3. 克隆复制运算 4.高频变异和克隆选择算子: 依据某策略从选择的解出发，获得新解； 5. 免疫记忆 初始解、亲和力、克隆复制、高频变异、选择 初始抗体(解) 亲和力 免疫记忆 1、数值优化、多目标优化 多目标优化 提出好的策略，设计改进的智能优化算法，基于数值优化函数仿真、比较、写论文 背包问题 2、组合优化：背包问题、旅行商问题 旅行商问题 多旅行商问题、动态旅行商问题等 3、Web服务选择研究 面向服务计算作为一种新生的分布式计算理念，近年来受到了工业界和学术界的广泛关注。 但是，单个服务一般提供比较单一的功能，无法满足复杂的应用需求。因此，将多个服务组合起来，提供新的、更复杂的、功能更强大的组合服务已经成为一个新的研究热点。 Web服务应用范围的不断扩大，Web服务数量的不断增大，网络上不可避免地会出现海量的具有相同或相似功能但不同服务质量(QOS)的web服务。如果需要组合出具有某些指定功能的组合服务的话，那么，由具有相同或相似功能和不同QoS的单个服务会组合出大量的组合服务，会形成海量的服务组合方案； 同时，用户在对组合服务提出功能要求之外，也会对组合服务的QOS(可用性、可靠性、价格、服务提供者的声誉等)提出要求，因此在海量的具有相同功能的组合方案中选择满足用户QoS需求的最优方案就成为服务选择中的关键问题之一。 * 赵新超 信息与计算数学中心 数学系，理学院 xc.bupt@ 主楼814 最优化算法、智能优化算法及其应用 智能算法、最优化算法 方法 问题 数值优化、多目标优化 组合优化：背包问题、旅行商问题 Web服务选择 优化搜索算法一般框架 网络路由优化等 北京邮电大学数学系 第二步：在当前解确定一个搜索方向和步长，移动到新的解 第一步：产生初始解 一元问题是个实数 多元问题是个向量 第三步：算法终止条件，否则循环。 步长：一维搜索或线搜索 方向：最速下降、牛顿方向 新解与老解的取舍规则 一维搜索的数学模型 单变量函数的最优解问题 精确、非精确的一维搜索方法 北京邮电大学数学系 搜索方向与最优化算法 《高等数学》：多元函数梯度 已知知识：负梯度方向是函数在当前点处函数值下降最快的方向； 方法：随机产生一点作为初始解，按该点的负梯度方向搜索确定下一点，直至找到最优解为止； 算法终止条件：梯度等于零。 最速下降方向 前半程收敛快，后半程慢(Zigzag) 牛顿搜索方向 优点：二次终止性，收敛速度快 计算量大(求导和解方程组)； 要求Hessen矩阵正定，矩阵可能病态更糟糕； 不保证新解一定比老解好； 缺点： 信赖域算法 无约束优化方法通常策略是，给定点 后， 某确定策略找到搜索方向 再某策略确定沿该方向走的长度，即步长 信赖域方法另辟蹊径： 给定点 后，确定一个(小的)变化范围， 通常取xk为中心的球域，称为信赖域， 在此邻域内找到原问题的二次函数逼近式，以二次函数的最优解作为原问题最优解的近似点xk+1， 如此往复…… 最优化算法参考书 搜索方向设计总体思路： 算法搜索前半程大致沿最速下降方向搜索， 算法搜索后半程大致沿牛顿方向搜索，即大致在两个搜索方向之间摇摆； 陈宝林，《最优化理论与算法》，清华大学出版社 第二步：在当前解确定一个搜索方向和步长，移动到新的解 新解与老解的取舍规则 若只有新解优于老解时才保留新解，则是一般的贪心算法思想，但很容易陷入一个局部最优陷阱 若在算法中不仅是见了优秀解就保留，更重要的是当获得较差的解时也有可能保留，当然可能性依概率减小，即爱富而不嫌贫！ 爱富而不嫌贫的算法—模拟退火算法 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时