西安交通大学：《工程优化方法及其应用》研究生课程教学课件（PPT讲稿）11-12 全局优化算法之遗传算法

全局优化算法

1 全局优化算法

主要内容概论遗传算法

2 主要内容 ⚫概论 ⚫遗传算法

概论--全局优化问题最优化问题的一般形式为min f(x)(1.1)xeQs.t.如果存在x* 使得Vx E2, f(x") ≤ f(x)称x*为优化问题（1.1）的全局最优解f*=f(x*）称为全局最优值；寻找全局最优解的优化问题称为全局优化问题3

3 概论-全局优化问题 ⚫ 最优化问题的一般形式为 x  f x s.t. min ( ) 如果存在   * x , ( ) ( ) * x   f x  f x * x ( ) * * f = f x 使得 称 为优化问题（1.1）的全局最优解. 称为全局最优值； 寻找全局最优解的优化问题称为全局优化问题。 （1.1）

概论-----全局优化问题特别地，如果决策变量是一定区间内的连续变量，则最优化问题（1.1）称为函数优min f(x)化问题；s.t.xe Q如果决策变量是离散状态，司时可行域是由有限个点组成的集合，则最优化问题（1.1）称为组合优化问题

4 概论-全局优化问题 ⚫ 特别地，如果决策变量是一 定区间内的连续变量，则最 优化问题（1.1）称为函数优 化问题； ⚫ 如果决策变量是离散状态， 同时可行域是由有限个点组 成的集合，则最优化问题 （1.1）称为组合优化问题。 x  f x s.t. min ( )

组合优化问题组合优化问题常常写为minf(x)s.t. g(x) ≥ 0xED其中D为有限点组成的集合组合优化问题往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支。5

5 组合优化问题 ⚫ 组合优化问题常常写为 s.t. ( ) 0 min ( ) g x  f x x  D 其中D为有限点组成的集合 组合优化问题往往涉及排序、分类、筛选等 问题，它是运筹学的一个重要分支

典型组合优化问题(TSP)旅行商问题Traveling SalesmanProblem给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线48城市TSP问题

6 典型组合优化问题 ⚫ 旅行商问题（TSP） Traveling Salesman Problem 给定n个城市和两两 城市之间的距离，要 求确定一条经过各城 市当且仅当一次的最 短路线。 48城市TSP问题

典型组合优化问题0-1背包问题对于n个体积分别为a;、价值分别为c的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大。图着色问题对于n个顶点的无环图，要求对其各个顶点进行着色，使得任意两个相邻的顶点都有不同的颜色，且所用颜色种类最少

7 典型组合优化问题 ⚫ 0-1背包问题 对于n个体积分别为ai、价值分别为ci的物品，如 何将它们装入总体积为b的背包中，使得所选物 品的总价值最大。 ⚫ 图着色问题 对于n个顶点的无环图，要求对其各个顶点进行 着色，使得任意两个相邻的顶点都有不同的颜 色，且所用颜色种类最少

全局优化方法概述确定性全局优化方法一类是处理具有特殊结构的全局优化问题的算法，如D.C.规划，单调规划等；一类主要是处理具有一般结构的全局优化问题的算法，如广义下降法、填充函数法、区间方法等，随机性全局优化方法传统的：有随机方向法、多头方法、聚类法等现代优化算法（智能优化方法）?

8 全局优化方法概述 ⚫ 确定性全局优化方法 一类是处理具有特殊结构的全局优化问题 的算法，如D.C.规划，单调规划等； 一类主要是处理具有一般结构的全局优化 问题的算法，如广义下降法、填充函数法、区 间方法等. ⚫ 随机性全局优化方法 传统的：有随机方向法、多头方法、聚类法等 现代优化算法(智能优化方法）

智能优化算法现代优化算法，文称智能优化算法，是80年代初兴起的优化算法，这些算法包括禁忌搜索（tabusearch），模拟退火，遗传算法，蚁群算法，粒子群算法，人工神经网络等，它们主要用于解决大量的实际应用问题。它们共同的目标是求NP.hard组合问题的全局最优解

9 智能优化算法 现代优化算法，又称智能优化算法，是80 年代初兴起的优化算法，这些算法包括禁 忌搜索（tabu search），模拟退火，遗 传算法，蚁群算法，粒子群算法，人工神 经网络等，它们主要用于解决大量的实际 应用问题。 它们共同的目标是求NP￾hard组合问题的全局最优解

智能优化算法的特点及发展对目标函数和约束函数的要求十分宽松：不追求精确最优解和理论最优，只追求满意解或近似解以实际问题为导向，更注重计算的速度和效率，实用性强基本思想都来自于对某种自然规律的模仿，具有人工智能的特点：多数算法含有一个多个体的种群，寻优过程实际上就是种群的进化过程：算法理论基础薄弱，不能保证收敛到最优解。1975年，Holland提出遗传算法，模仿生物进化机制1977年，Glover提出禁忌搜索算法，模仿人类记忆功能：1983年，Krikpatrick提出模拟退火算法，模拟热力学中的退火过程；20世纪90年代，Dorigo提出蚁群算法，模拟蚂蚁信息素机制：1995年，Kennedy提出粒子群优化算法，模拟鸟类和鱼类群体觅食行为：1999年，Linhares提出捕食搜索算法，模拟猛兽捕食行为：3

3 智能优化算法的特点及发展 ⚫ 对目标函数和约束函数的要求十分宽松； ⚫ 不追求精确最优解和理论最优，只追求满意解或近似解， ⚫ 以实际问题为导向，更注重计算的速度和效率，实用性强； ⚫ 基本思想都来自于对某种自然规律的模仿，具有人工智能的特点； ⚫ 多数算法含有一个多个体的种群，寻优过程实际上就是种群的进化过程； ⚫ 算法理论基础薄弱，不能保证收敛到最优解。 ⚫ 1975年，Holland提出遗传算法，模仿生物进化机制； ⚫ 1977年，Glover提出禁忌搜索算法，模仿人类记忆功能； ⚫ 1983年，Krikpatrick提出模拟退火算法，模拟热力学中的退火过程； ⚫ 20世纪90年代，Dorigo提出蚁群算法，模拟蚂蚁信息素机制； ⚫ 1995年，Kennedy提出粒子群优化算法，模拟鸟类和鱼类群体觅食行为； ⚫ 1999年，Linhares提出捕食搜索算法，模拟猛兽捕食行为； ⚫