智能优化方法课件PPT-东北大学+王俊伟

null智能优化方法 AI-Based Optimization Methods智能优化方法 AI-Based Optimization MethodsBy Wang Junwei PhD Northeastern University China 2007课程进度课程进度No.1 导言、伪随机数的产生方法 No.2 遗传算法(GA) No.3 遗传算法(GA) No.4 遗传算法(GA) No.5 禁忌搜索(TS)课程进度课程进度No.6 模拟退火(SA) No.7 新发展起来的算法 蚁群优化(ACO)，粒子群优化(PSO) 捕食搜索（PS）,群落选址算法（CLA） No.8 考试教材教材《智能优化方法》 汪定伟 王俊伟 王洪峰 张瑞友 郭哲 编著 高等教育出版社 中英文文献 第一章 导言第一章 导言第一章 导言第一章 导言〇.最优化的重要性 一.传统优化方法的基本步骤——三步曲 二.传统优化方法的局限性 三.实际问题中对最优化方法的要求 四.智能优化算法的产生与发展 五.应用前景局限性和研究方向、注意事项〇.最优化的重要性（1）〇.最优化的重要性（1） 人类的一切活动都是认识世界和改造世界的过程 即： 认识世界 → 改造世界 ↓ ↓ (建模) (优化) 〇.最优化的重要性（2）〇.最优化的重要性（2） 一切学科都是建模与优化在某个特定领域中的应用 概念模型(定性) → 结构模型(图)→ → 数学模型 → 智能模型 〇.最优化的重要性（3）〇.最优化的重要性（3）最优化理论的发展 极值理论； 运筹学的兴起(Operation Research)； 数学规划：线性规划(LP)；非线性规划(NLP)；动态规划(PP)；马尔托夫规划(MDP)；排队轮；决策论；存储论。 最优化理论在国民经济中的广泛应用 一.传统优化方法的基本步骤—三步曲（1）一.传统优化方法的基本步骤—三步曲（1） 如下面框图所示 选一个初始解 LP:大M，二阶段法 NLP:任意点或一个内点 一.传统优化方法的基本步骤—三步曲（2）一.传统优化方法的基本步骤—三步曲（2） 停止判据——停止规则最优性检验 LP:检验数 当∏≥0时有可能减小 NLP:一.传统优化方法的基本步骤—三步曲（3）一.传统优化方法的基本步骤—三步曲（3） 向改进方向移动——改进解 LP:转轴变换(进基、退基) NLP:向负梯度方向移动(共轭梯度方向、牛顿方向) 一.传统优化方法的基本步骤—三步曲（4）一.传统优化方法的基本步骤—三步曲（4）二.传统优化方法的局限性（1）二.传统优化方法的局限性（1） 对问题中目标函数、约束函数有很高的要求——有显式表达，线性、连续、可微，且高阶可微; 2. 只从一个初始点出发，难以进行并行、网络计算，难以提高计算效率； 二.传统优化方法的局限性（2）二.传统优化方法的局限性（2） 最优性达到的条件太苛刻——问题的函数为凸，可行域为凸； 在非双凸条件下，没有跳出局部最优解的能力。 三.实际问题中对最优化方法的要求（1）三.实际问题中对最优化方法的要求（1）对问题的描述要宽松(目标和约束函数)—— 可以用一段程序来描述(程序中带判断、循环)，函数可以非连续、非凸、非可微、非显式； 并不苛求最优解——通常满意解、理想解就可以了；三.实际问题中对最优化方法的要求（2）三.实际问题中对最优化方法的要求（2）计算快速、高效,可随时终止(根据时间定解的质量)； 能够处理数据、信息的不确定性(如数据的模糊性，事件的随机性)。四.智能优化算法的产生与发展（1）四.智能优化算法的产生与发展（1）1975年holland提出遗传算法 (Genetic Algorithm) 1977年Glouer提出禁忌搜索算法 (Tabn Search) 四.智能优化算法的产生与发展（2）四.智能优化算法的产生与发展（2）1982年Kirkpatrick提出模拟退火算法 (Simulated Annealing) 人工神经元网络 1995年Dorigo提出蚁群算法 (Ant Colony Optimization)四.智能优化算法的产生与发展（3）四.智能优化算法的产生与发展（3）1995年Kennedy & Eherhart提出粒子群优化 (Particle Swarm Optimization) 其它 文化算法(Cultural Algorithm) 人工生命算法(Artificial-Life Algorithm)四.智能优化算法的产生与发展（4）四.智能优化算法的产生与发展（4）我们统称以上算法为人工生命计算 (Artificial Life Computation) 人工生命计算 + 模糊逻辑 (Fuzzy Logic)= 软计算(Soft Computation) 人工生命计算 + 进化编程 = 进化算法 (Evolutionary computation)五.应用前景局限性和研究方向、注意事项（1）五.应用前景局限性和研究方向、注意事项（1）应用前景十分广阔——国民经济的各个领域 局限性——不能保证最优解，理论上不完备五.应用前景局限性和研究方向、注意事项（2）五.应用前景局限性和研究方向、注意事项（2）研究方向及注意事项 以应用为主，扩大面向新问题的应用；不要刻意做理论研究，若碰上也不拒绝; 算法改进表现在以下几个方面：问题的描述、编码方法、算法构造及可行性修复策略; 要进行大量的上机计算；五.应用前景局限性和研究方向、注意事项（3）五.应用前景局限性和研究方向、注意事项（3）算例的选取，以下算例的说服力降序排列：网上的测试用例、文献中的例子、实际例子、随机产生的例子、自己编的例子; 如何检验算法的好坏：比较计算速度、可解规模、 (从不同的随机种子出发)达优率。第二章 伪随机数的产生第二章 伪随机数的产生第二章 伪随机数的产生第二章 伪随机数的产生一.伪随机数产生的意义 二.产生U(0,1)的乘同余法 三.正态分布N(0,1)的产生 四.逆变法与其它分布随机数的产生一.伪随机数产生的意义一.伪随机数产生的意义在GA,SA,TS中都要用到； 在计算机中的固有伪随机数发生器只有U(0,1) 且可重复性不好，没有其他分布； 自己设计的发生器，可控型好、可重复性好，便于仿真比较。 二.产生U(0,1)的乘同余法（1）二.产生U(0,1)的乘同余法（1）乘同余法的计算公式 可产生随机数序列。 问题：怎样设定 和 可以使随机数序列最长？ 二.产生U(0,1)的乘同余法（2）二.产生U(0,1)的乘同余法（2）乘同余法的方法： 若 的整数，当 {x}满足以下条件时，可以达到最大周期 (序列长度) 为3(Mod8)或5 (Mod8)的数 ； 为奇数，一般取为1。二.产生U(0,1)的乘同余法（3）二.产生U(0,1)的乘同余法（3）乘同余法举例说明： = =16 = 3 =1,3,9,11,1,3,9,11 = 5 =1,5,9,13,1,5,9,13 = 3 =2,6,2,6… 可得整数序列 ，要想获得U(0,1)，见下面二.产生U(0,1)的乘同余法（4）二.产生U(0,1)的乘同余法（4） 产生U(0,1)步骤： ； 令 。 二.产生U(0,1)的乘同余法（5）二.产生U(0,1)的乘同余法（5） 产生U(0,1)举例说明： = =16 =3，x0=1 =1/16, 3/16, 9/16, 11/16, 1/16, 3/16, 9/16, 11/16 … =3，x0=2 =2/16, 6/16, 2/16, 6/16… 二.产生U(0,1)的乘同余法（6）二.产生U(0,1)的乘同余法（6） 优秀编程举例： IF(NR·(T·0)) NR=NR+M(M对应于计算机中最大整数) 三.正态分布N(0,1)的产生（1）三.正态分布N(0,1)的产生（1） 正态分布可以用多个U(0,1)来近似，若 是独立同分布， 较大，则 近 似正态分布，且满足 及 则 三.正态分布N(0,1)的产生（2）三.正态分布N(0,1)的产生（2）令： 一般n取12则： 其中： （详见下页）三.正态分布N(0,1)的产生（3）三.正态分布N(0,1)的产生（3）注： 四.逆变法与其它分布随机数的产生（1）四.逆变法与其它分布随机数的产生（1）逆变法四.逆变法与其它分布随机数的产生（2）四.逆变法与其它分布随机数的产生（2） 是分布函数， ，如何产生 ？ 设 ， 是随机变量 产生 ， 是 分布函数 逆变法的目的：产生 分布的随机数四.逆变法与其它分布随机数的产生（3）四.逆变法与其它分布随机数的产生（3）逆变法的步骤： 已知 ，或由 求 即 ，令 推导 产生 用 得到四.逆变法与其它分布随机数的产生（4）四.逆变法与其它分布随机数的产生（4）负指数分布的产生 负指数函数的密度函数：四.逆变法与其它分布随机数的产生（5）四.逆变法与其它分布随机数的产生（5）负指数函数的分布函数的产生过程： ① 令 ② ③ 产生 则 ④ 即四.逆变法与其它分布随机数的产生（6）四.逆变法与其它分布随机数的产生（6）产生 是负指数分布的。第三章 遗传算法第三章 遗传算法第三章 遗传算法 第三章 遗传算法 一.导言 二.Holland的基本GA 三.计算举例 四.Holland的结构理论 五.GA的各种变形 六.应用 七.学习GA的几点体会一.导言（1）一.导言（1）遗传算法(GA)的产生 1975年，Holland提出GA 著名的 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf ： Adaptation in Natural and Artificial Systems (中文名称：自然与人工系统的自适应性) 后来，DeJong和Goldberg做了大量工作，使GA更加完善。一.导言（2）一.导言（2）遗传算法(GA)的来源： 生物的进化：自然选择、适者生存 生物的遗传和变异 (GA)缺点：无人的主动性 ； 解决方法有以下三个： 定向培育 随机算法 网格法一.导言（3）一.导言（3）定向培育 过程如下： 第一：一个种群，大量的生物个体； 第二：选择具有需要特性的若干个体； 第三：进行繁殖； 第四：重复第二，直到满意为止。 一.导言（4）一.导言（4）随机算法：在解空间随机产生多个解，选择最好的 网格法：根据最好解的几何分布，来不断的缩小搜索范围。一.导言（5）一.导言（5）遗传算法的基本 思想 教师资格思想品德鉴定表下载浅论红楼梦的主题思想员工思想动态调查问卷论语教育思想学生思想教育讲话稿 根据问题的目标函数构造适值函数(Fitness Function)； 产生一个初始种群(100-1000)； 根据适值函数的好坏，不断选择繁殖； 若干代后得到适值函数最好的个体即最优解。一.导言（6）一.导言（6）遗传算法的构成要素 种群(Population), 种群大小(Pop-size) 基因表达法——编码方法 (Encoding Scheme; Gene Representation)一.导言（7）一.导言（7）遗传算子(Genetic Operator)： 交叉(Crossover)，变异(Mutation) 选择策略:一般为正比选择 停止准则(Stopping Rule/Criterion): 一般是指定最大代数二.Holland的基本GA（1）二.Holland的基本GA（1）算法框架与步骤 见下页 二.Holland的基本GA（2）二.Holland的基本GA（2）二.Holland的基本GA（3）二.Holland的基本GA（3）解空间与编码空间的转换 遗传运算是对编码空间操作的，所以要进行 两个空间的转换。 见下页示意图 二.Holland的基本GA（4）二.Holland的基本GA（4）二.Holland的基本GA（5）二.Holland的基本GA（5）各个步骤的实现 初始种群的产生 编码方法 适值函数 遗传运算 选择策略 停止准则 二.Holland的基本GA（6）二.Holland的基本GA（6）初始种群的产生 随机产生(依赖于编码方法)；种群的大小(依赖于计算机的计算能力和计算复杂度)。 例：0,1编码 产生 ， >0.5， =1； <0.5， =0 二.Holland的基本GA（7）二.Holland的基本GA（7）编码方法——二进制编码 二进制编码，用0，1字符串表达。 例：0110010，适用以下三种情况 背包问题： 1，背；0，不背 二.Holland的基本GA（8）二.Holland的基本GA（8）实优化： 精度高时编码长，一般不采用此法而用实值函数。 指派问题 二进制编码缺点：编码长不利于计算； 二进制编码优点：便于位值计算，包括的实数范围大 二.Holland的基本GA（9）二.Holland的基本GA（9）适值函数——根据目标函数设计 用适值函数 标定(Scaling)目标函数 采用方法 或 。 遗传运算(遗传算法的精髓)——交叉和变异 下面我们就介绍一下交叉和变异 二.Holland的基本GA（10）二.Holland的基本GA（10）交叉(Crossover) 单切点交叉 随机产生一个断点(Cutting Point)［1，n-1］ 例： 二.Holland的基本GA（11）二.Holland的基本GA（11）双切点交叉(交换中间段) 例： 不是所有点都交叉，设定一个交叉概率 ，一 般为0.9二.Holland的基本GA（12）二.Holland的基本GA（12）变异(Mutation) 初始种群中没有需要的基因，在种群中按变异 概率 任选若干位基因改变位值0→1或1→0， 有意想不到的结果， 一般设定得比较小，在 5%以下。 二.Holland的基本GA（13）二.Holland的基本GA（13）选择策略 最常用的正比选择(Proportional Selection) 对于个体 ，适值 ，选择概率如下式可计算 NP—Number of Population 二.Holland的基本GA（14）二.Holland的基本GA（14）得到选择概率后，我们采用旋轮法(Roulette Wheel) 令 ， 随机产生 当 ，选择个体 二.Holland的基本GA（15）二.Holland的基本GA（15）如下图所示: 注： 优良种得到较多的繁殖机会，后代很 像 ； 而很可能失去繁殖的机会。 二.Holland的基本GA（16）二.Holland的基本GA（16）停止准则 指定最大代数(NG—Number of Max Generation) 很少用 ，麻烦三.计算举例（1）三.计算举例（1）例1： ， ，NP=5 简单分析： 编码为五位的0，1编码，推导如下 设编码长度L，取决于 ，即编码精度 若要求编码精度为1，则由C<=1可推得L>=5三.计算举例（2）三.计算举例（2）② ，最大值 ，最小值三.计算举例（3）三.计算举例（3）步骤： 产生初始种群NG=10,t=0 判断停止准则 计算适值 用旋轮法正比选择 三.计算举例（4）三.计算举例（4）计算生成的列表： 表1 表2三.计算举例（5）三.计算举例（5）观察结果 ⑴ 整个种群在改善 ：2325 2992 ⑵ 模板 0٭٭٭٭较好，而 1 ٭٭٭٭较差 ⑶ “好坏”数量的变化 ：2 3 ； ：3 2三.计算举例（6）三.计算举例（6）结果(3)数量变化可由表1中的数据推导出： 同理： =0.9 =0.02三.计算举例（7）三.计算举例（7）双亲的选择方法： 随机选： 产生 ， 比例选: 产生 ，当 ，选择个体 父亲优选，母亲随机选： 选 ， 四.Holland的结构理论（1）四.Holland的结构理论（1）又称概形理论(Schema Theory) 1.模板的概念： 若干位确定，若干位不确定的一类个体的总称，用 表示，如0٭٭٭٭和1 ٭٭٭٭。四.Holland的结构理论（2）四.Holland的结构理论（2）模板的长度 ： 模板第一个确定位与最后一个确定位之间的长度。 模板的阶数 ： 模板中确定位的个数。 例如： —— ٭1٭1٭0 ٭ ٭， =4， =3四.Holland的结构理论（3）四.Holland的结构理论（3）常识： n位编码总长n-1; 阶数为 的概型， 中的个体总数为 ; 对于一个n位二进制表达，染色体长度为n 模板度>个体数( > ) ， 即分类方法数>个体总数。 因模板因子、个体因子分别为(0，1， ٭ )、 (0，1) 。四.Holland的结构理论（4）四.Holland的结构理论（4）模板理论 引理1：在正比选择下，模板在第 代的期望 个体数为： 其中 是 第 代 模板中所有个体的适值均值与种群中所 有个体的适值均值的比， 是第 代 的个 体数。 如例1中： 0٭٭٭٭ ， =1.4858， =2， =3四.Holland的结构理论（5）四.Holland的结构理论（5）证明：四.Holland的结构理论（6）四.Holland的结构理论（6）注释: 种群的适值和为： ， 则选择概率为： 为 中的个体总数，且 下标随遗传的进行而变化；四.Holland的结构理论（7）四.Holland的结构理论（7） 为 模板中所有个体的适值均值; 为种群的适值均值 只要均值 >1，则好的种群的个体会越来越多。 问题：以上证明没有考虑交叉变异，那么交叉变异会不会破坏种群模板 ？概率有多大？ 四.Holland的结构理论（8）四.Holland的结构理论（8）引理2：第 代以概率 做交叉，对长度为 的概型 ，则在第 代中个体数为概型 的概 率下界为： 其中 为第 代个体为 的概率。四.Holland的结构理论（9）四.Holland的结构理论（9）引理2的证明 证明：交叉破坏 的条件 做了交叉： 交叉点在 内: 配偶 不在 中： 则不被破坏的概率：四.Holland的结构理论（10）四.Holland的结构理论（10）思考：若 不属于概型 ，是否能产生后代为概型 ？ 答案：可以 四.Holland的结构理论（11）四.Holland的结构理论（11）引理3：若第 代以 做变异，对于一个阶数为 的模板 ,则在第 代仍为 的概率的下界 为： 证明： 对于 ，当 =1，不破坏的概率为 当 >1，不破坏的概率为 取其泰勒展开式的第一项：四.Holland的结构理论（12）四.Holland的结构理论（12）主定理(概型定理)： 第 代以概率 和 做交叉和变异时，长度 为 ，阶数为 ，适值均值比为 的概 型 在第 代的期望个体数的下界为： 当 时， 随代数的增加而增加。五.GA的各种变形（1）五.GA的各种变形（1）其它编码方法 顺序编码：用1到N的自然数的不同顺序来 编码，此种编码不允许重复，即 且 ，又称自然数编码。 该法适应范围很广：指派、旅行商问题，单机调度。 合法性问题：是否符合采用的编码规则的问题五.GA的各种变形（2）五.GA的各种变形（2）实数编码 特征：方便运算简单，但反映不出基因的特征 整数编码 应用于新产品投入，时间优化，伙伴挑选 例：3212345 对顺序编码来说是不合法的，而 对整数编码来说是合法的；010200不合法的01 编码；练 习（1）练 习（1）对于编码长度为7的0－1编码，判断以下编码的合法性 (1) [ 1 0 2 0 1 1 0 ], (2) [ 1 0 1 1 0 0 ], (3) [ 0 1 1 0 0 1 0 ], (4) [ 0 0 0 0 0 0 0 ], (5) [ 2 1 3 4 5 7 6 ]. 练 习（2）练 习（2）对于编码长度为7的顺序编码，判断以下编码的合法性 (1) [ 7 1 2 0 4 3 5 ], (2) [ 1 3 6 2 4 7 ], (3) [ 2 1 3 5 4 7 6 ], (4) [ 8 1 4 3 2 5 7 ], (5) [ 2 1 3 2 5 7 6 ]. 练 习（3）练 习（3）对于编码长度为7的实数编码，判断以下编码的合法性 (1) [ 3.5 1.9 2 7 1.8 1.7 0 ], (2) [ 89.05 4.78 2 1 4.3 6.9 ], (3) [ 0 1 1 0 0 1 0 ], (4) [ 0 0 0 0 0 0 0 ], (5) [ 2 1 3 4 5 7 6 ]. 五.GA的各种变形（3）五.GA的各种变形（3）遗传运算中的问题 在顺序编码遗传运算的过程中会遇见不合法 的编码，应战的策略有二:拒绝或修复。 例如：经交叉后，后代编码不合法 21 ¦ 345 ¦ 67 21 ¦ 125 ¦ 67 43 ¦ 125 ¦ 76 43 ¦ 345 ¦ 76 我们采用下面的修复策略使以上的编码合法。五.GA的各种变形（4）五.GA的各种变形（4）顺序编码的合法性修复： 交叉修复策略 它分为以下几种 部分映射交叉 顺序交叉 循环交叉五.GA的各种变形（5）五.GA的各种变形（5）部分映射交叉(PMX) ( Partially Mapped Crossover) PMX步骤： ⑴选切点X,Y； ⑵交换中间部分； ⑶确定映射关系； ⑷将未换部分按映射关系恢复合法性。五.GA的各种变形（6）五.GA的各种变形（6）PMX例题：五.GA的各种变形（7）五.GA的各种变形（7）顺序交叉( OX )Order Crossover OX步骤： ⑴ 选切点X,Y； ⑵ 交换中间部分； ⑶ 从切点Y后第一个基因起列出原序，去掉已有基因； ⑷ Y后第一个位置起填入。五.GA的各种变形（8）五.GA的各种变形（8）OX例题： 五.GA的各种变形（9）五.GA的各种变形（9）OX的特点： 较好的保留了相邻关系、先后关系满足了TSP 问题的需要，但不保留位值特征。 五.GA的各种变形（10）五.GA的各种变形（10）循环交叉(CX) Cycle Crossover 基本思想：子串位置上的值必须与父母的相同 位置上的位值相等。 CX步骤： ⑴ 选 的第一个元素作为 的第一位， 选 的第一个元素作为 的第一位；五.GA的各种变形（11）五.GA的各种变形（11）⑵ 到 中找 的第一个元素赋给 的相对位置…，重复此过程，直到 上得到 的第一个元素为止，称为一个循环； ⑶ 对最前的基因按 、 基因轮替原则重复以上过程； ⑷ 重复以上过程，直到所有位都完成。五.GA的各种变形（12）五.GA的各种变形（12）CX 例题：五.GA的各种变形（13）五.GA的各种变形（13）CX的特点： 与OX的特点不同的是， CX较好的保留了位值 特征，适合指派问题；而OX较好的保留了相邻 关系、先后关系满足了TSP问题的需要。练 习练 习P1：［ 6 1 2 8 ｜9 5 4 7｜ 10 3 ］ P2：［ 10 7 4 1 ｜3 6 2 8｜ 5 9 ］ PMX： C1： C2： OX： C1： C2: 练 习（2）练 习（2）P1：［ 6 1 2 8 9 5 4 7 10 3 ］ P2：［10 7 4 1 3 6 2 8 5 9 ］ CX： C1： C2：五.GA的各种变形（14）五.GA的各种变形（14）变异的修复策略 换位变异(最常用) 例： 4 3 1 2 5 6 7 4 5 1 2 3 6 7 移位变异：任选一位移到最前 例： 4 3 1 2 5 6 7 5 4 3 1 2 6 7五.GA的各种变形（15）五.GA的各种变形（15）实数编码的合法性修复 交叉 单切点交叉 五.GA的各种变形（16）五.GA的各种变形（16）双切点交叉(与单切点交叉类似) 该方法最大的问题：如何在实优化中保持 可行性。五.GA的各种变形（17）五.GA的各种变形（17）凸组合交叉 约束是个凸集，可行性可以保持，问题是分散 性太差，向中间汇集的问题需要解决。五.GA的各种变形（18）五.GA的各种变形（18）变异 位值变异： 任选一位加Δ， 例： 五.GA的各种变形（19）五.GA的各种变形（19）向梯度方向变异 缺点：只能用于目标函数可微的问题 例: 五.GA的各种变形（20）五.GA的各种变形（20）适值函数的标定(Scaling) 五.GA的各种变形（21）五.GA的各种变形（21）标定的目的： 使适值函数不会太大，有一定差别 选择压力的概念： 选择压力是种群好、坏个体被选中的概率 之差，差大称为选择压力大。五.GA的各种变形（22）五.GA的各种变形（22）局部搜索、广域搜索与选择压力的关系 局部搜索与广域搜索是GA中的一对矛盾， 好的算法要将以上二者综合考虑。算法开始重 广域搜索，选择压力小；随迭代进行，逐步偏 重于局部搜索，选择压力大。五.GA的各种变形（23）五.GA的各种变形（23）适值的标定方法 线性标定： 函数表达式 , 为目标函数， 为适值函数五.GA的各种变形（24）五.GA的各种变形（24）对 ， =1， = ， 函数表达式 ： +ξ， 对 ， =-1， = , 函数表达式： +ξ，五.GA的各种变形（25）五.GA的各种变形（25）动态线性标定(最常用) 优点：计算容易不占用时间 函数表达式： ， 为迭代指标 最常用极大化： =1 , 函数表达式：五.GA的各种变形（26）五.GA的各种变形（26）加入的意义： 加入使最坏个体仍有繁殖的可能， 随 而减小 的取值： ， ， ， 调节 和 ，从而来调节五.GA的各种变形（27）五.GA的各种变形（27）引入目标的目的： 调节选择压力，即好坏个体选择概率的 差，使广域搜索范围宽保持种群的多样性，而 局域搜索细保持收敛性。如下图表示： 开始：希望选择压力小 后来：希望选择压力大五.GA的各种变形（28）五.GA的各种变形（28）幂律标定： 函数表达式： 的取值， >1时选择压力加大 <1时选择压力减小 对数标定： 函数表达式： 对数标定的作用：缩小差别五.GA的各种变形（29）五.GA的各种变形（29）指数标定： 函数表达式： 指数标定的作用：扩大差别 窗口技术： 函数表达式： 为前W代中的最小目标值，它考虑了各代 的波动，这样 具有记忆性五.GA的各种变形（30）五.GA的各种变形（30）正规化技术： 函数表达式： 正规化技术的作用： 将 映射到(0,1)区间，抑制超级染色体 正规化技术的实质：特殊的动态标定 即 其中：五.GA的各种变形（31）五.GA的各种变形（31）选择策略 传统的GA选择和遗传是一起进行的，即使 后代不如父代，却无法纠正。下面介绍的选择 策略都是先遗传后选择。这样，样本空间扩大 了，可供选择的个体增多了。五.GA的各种变形（32）五.GA的各种变形（32）截断选择： 选择最好的前T个个体，让每一个有1/T的选择概率，平均得到NP/T个繁殖机会。 例：NP=100,T=50 即100名学生，成绩前50名的选出。每人的选择概率为1／50，有平均2个机会。 这种方法计算量在排序上。五.GA的各种变形（33）五.GA的各种变形（33）顺序选择： 步骤： ⑴ 从好到坏排序所有个体 ⑵ 定义最好个体的选择概率为 ,则第 个个体的选择概率为：五.GA的各种变形（34）五.GA的各种变形（34）⑶ 由于 有限时要归一化，则有下面的两个公式： 顺序选择的缺点： 把选择概率固化了，选择压力不可调五.GA的各种变形（35）五.GA的各种变形（35）举例: 且： 采用旋轮法，随机产生 当 ，选择个体五.GA的各种变形（36）五.GA的各种变形（36）正比选择： 令： ， 用动态标定来调节选择压力，采用旋轮法来共 同完成种群的选择。 五.GA的各种变形（37）五.GA的各种变形（37）停止准则 指定最大代数 检查种群中适值的一致性，保持历史上最好的个体。计算公式： 或 第二种方法因很难实现，所以很少使用。六.应用（1）六.应用（1）背包问题 个物品，对物品 ，价值为 ，重量为 ， 背包容量是 。如何选取物品装入背包，使背 包中的价值最大。 六.应用（2）六.应用（2）模型: ，装入物品 ，不装入物品 六.应用（3）六.应用（3）如何处理约束来保持可行性 拒绝策略： 可行解不易达到时，很难达到一个初始种群 修复策略： 将不可行解修复为可行的，但将失去多样性。六.应用（4）六.应用（4）惩罚策略： 设计惩罚函数，但设计不好会掩盖目标函 数的优化。 下面，我们将分别采用惩罚策略及优先适 合启发式来处理上面的背包问题。 六.应用（5）六.应用（5）罚函数法 令适值函数 ，其中 是目标函数 令 ，其中 注： 与 是 的两个端点 六.应用（6）六.应用（6）函数式的意义： ⑴ 的作用是使 ，保证 ⑵ 可行也罚，只有当 不罚。 ⑶ 罚函数法目的：把解拉向边界，尽量装满。六.应用（7）六.应用（7）解码法——First Fit Heuristic(优先适合启 发式)解码法是修复程序(修复可行性的方法) ⑴步骤： 将选上物品按 降序排列； 选前 个物品，使 ； ⑵解码法的关键：如何在GA中解决可行性问题 ⑶编码方法：采用顺序编码 六.应用（8）六.应用（8）例： =7 用顺序( 3 2 5 1 4 6 7 )表示选择物品的顺序 用优先适合启发式保留前K位，使解可行 即： =3， ( 3 2 5 ) 问题：编码长度是可变的，如何做交叉和变异 六.应用（9）六.应用（9）⑷变长顺序编码的遗传算法插入式交叉算法 在 上选一个随机的断点； 在 上随机选一个基因片断插入 的断点处； 去掉 上的重复基因； 按优先适合启发式得到可行解 见下页例题六.应用（10）六.应用（10）例题： 六.应用（11）六.应用（11）最小生成树问题(Minimum Spanning Tree) 问题的提出 难点：对于下面的红色的图形，如何设计 一个合适的编码方法？ 六.应用（12）六.应用（12） 传统的编码方法： 节点表示法： 无法避免回路，很难做遗传运算，如： {(1,2),(2,3),(2,5),(2,6),(4,6)} 六.应用（13）六.应用（13） 边编码法： 无法保证是树无法保证可行性 {1,2,4,5,10} 缺点：麻烦，无法做遗传运算，无法保持合法性 六.应用（14）六.应用（14） 为解决以上问题，人们提出了最小生成树 的(Prűfer数)的编码方法。 最小生成树的定义： 用n-2位自然数唯一的表达出一棵n个节点的 生成树，而且交叉变异仍是一棵生成树。六.应用（15）六.应用（15）叶子：树中度数为1的节点 例如：1，3，4，5 最小生成树应用条件： 覆盖所有顶点 连通的 没有回路 六.应用（16）六.应用（16） 编码步骤 设节点i是标号最小的叶子 令j是编码中的第一个数字，若i与j相连 删去边(i , j) 转Ⅰ,直到剩下一条边为止 六.应用（17）六.应用（17）图解：i=1,( i , j )=(1,2),j=2 ; i=3,( i , j )=(3,2) , j=2 i=4,( i , j )=(4,6),j=6 ; i=5,( i , j )=(5,2), j=2 编码：（2 2 6 2） 六.应用（18）六.应用（18）解码步骤 令Prűfer数中的节点集为 ,不包含在 中的节点集为 ； 若i为 中最小标号的节点，j为 上最左边数字连接边(i , j)，并从 中去掉i，从 中去掉j，若j不再在 中，将j加入 中。 六.应用（19）六.应用（19）重复Ⅱ，直到 中没有节点(即为空)， 中剩下(s,r) 连接(s,r) 图解过程见下页 六.应用（20）六.应用（20）例： = [2，2，6，2]， = [1，3，4，5] (1,2) = [2，6，2]， = [3，4，5] (3,2) = [6，2]， = [4，5] (4,6) = [2]， = [5，6] (5,2) = [Ф]， = [2，6] 六.应用（21）六.应用（21）最小生成树的的优点： 对于一个 个节点的Prűfer数的个数为 ，生成树的个数也是 。 最小生成树实现了解空间和编码空间的一一对应，交叉变异不破坏合法性。 一个好的编码方法对遗传算法至关重要。 null1765234[ 2 3 2 4 4 ]练习:null175[ 6 3 2 4 4 ]P=[ 1 5 7 ]4236练习:六.应用（22）六.应用（22）二次指派问题——机器布置问题(QAP) 机器布置问题 Facility Layout —Quadratic Assignment Problem 六.应用（23）六.应用（23）问题的提出： 台机器，要布置在 个地方，机器i与k之 间的物流量为 ，位置j与L之间的距离为 ， 如何布置使费用最小。 设： 表示机器i布置在位置j； 其它。 同理对 。 六.应用（24）六.应用（24）数学模型： 二次0-1规划 六.应用（25）六.应用（25）用GA求解 编码——顺序编码 表示机器 放在位置 i ， 是1到n中的数 如：[ 4 , 3 , 1 , 2 , 5 ] 机器4放在位置1； 机器3放在位置2； 机器1放在位置3； … ； 六.应用（26）六.应用（26）该编码的优点：没有重复，保证了编码的合法性 六.应用（27）六.应用（27）函数表达式变为： 优点：使其更加简洁，便于计算。 缺点：变量出现在下标，任何数学规划不可用 解决方法：遗传算法(GA) 六.应用（28）六.应用（28）用GA求解的设定 编码方法：顺序编码 适值公式： 动态线性标定： 其它：用CX做交叉；换位变异；正比选择，就可以解决该问题。 七.学习GA的几点体会（1）七.学习GA的几点体会（1）编码是成功的关键(如最小树问题) 最好能使编码空间与解空间一一对应 减少编码冗余，编码应尽可能短 便于遗传运算——有利于保持合法性、可行性实在没有办法保持，要设计合理的修复程序，尽可能保持父辈的特征。七.学习GA的几点体会（2）七.学习GA的几点体会（2）遗传算子的设计有最大的创新空间 选择压力的调整使多样性和收敛性得到合适的分配。开始时多样性重要，重广域搜索；刚要结束时收敛性重要，重局域搜索。 调整方法：适值函数的构造；合适的标定方法七.学习GA的几点体会（3）七.学习GA的几点体会（3）在GA的研究中我们要做一些什么 扩大GA的应用, GA应用面广，适应性最好 算法改进方向的研究 理论研究 算法开发中的几个技术(见下页)七.学习GA的几点体会（4）七.学习GA的几点体会（4）参数整定：经验加反复试验(Tuning) 如： ， ，NG，NP几种参数的选定 判断好坏算法的办法： ⑴ 快 ⑵ 能解的问题大 ⑶ 达优率高，大问题50%的达优率七.学习GA的几点体会（5）七.学习GA的几点体会（5）算例的选择： ⑴ 自己编的——没有说服力，但可以解释算法 ⑵ 随机产生的——适合没有前例的例子 ⑶ 文献的例子——面较大 ⑷ 网上的例子——典型问题QAP,TSP智能优化方法 AI-Based Optimization Methods智能优化方法 AI-Based Optimization MethodsBy Professor Dingwei Wang Northeastern University China 2004第四章 禁忌搜索第四章 禁忌搜索第四章 禁忌搜索（ Tabu Search ）第四章 禁忌搜索（ Tabu Search ）一.导言 二.TS的基本原理及步骤 三.TS的算法步骤 四.TS可以克服局优的分析 五.TS举例 六.TS的中、长期表的使用 七.TS表的应用举例 八.学习TS的几点体会一.导言（1）一.导言（1）TS的提出 1977年F.Glover提出TS ，90年代初得到广 泛重视 一.导言（2）一.导言（2）TS的基本思想——避免在搜索过程中的循环 只进不退的原则——用Tabu表锁住退路 不以局部最优作为停止准则 邻域选优的规则模拟了人类的记忆功能——找过的地方都记下来，不再找第二次一.导言（3）一.导言（3）TS的要素构成 禁忌表(Tabu List) 渴望水平函数(Aspiration Level Function) 移动规则——邻域选优 选优规则——保持历史上的最优解 停止准则——与GA相似二. TS的基本原理及步骤（1）二. TS的基本原理及步骤（1）问题的描述及邻域的概念 TS仅用于离散优化，排斥实优化 二. TS的基本原理及步骤（2）二. TS的基本原理及步骤（2） 二. TS的基本原理及步骤（3）二. TS的基本原理及步骤（3）邻域举例： X=[0,1,0,0,1,0,0] u=1, d=[0,0,1,0,0,0,0] 注意：移动的意义是灵活的，目的是便于搜索。如： 排序问题中一次换位可称为一次移动，还可以定义为 选一个切点，两部分作交叉运算。练 习练 习定义邻域移动为位值加1或减1, 对整数编码[ 2 2 3 5 3 ]，以下染色体是否在其邻域内： [ 2 3 3 5 3 ]， [ 2 3 2 5 3 ]， [ 2 2 3 5 5 ]， [ 2 2 3 4 3 ]， [ 2 2 2 5 3 ]， [ 2 2 3 4 4 ]， 是否是否否是练 习（2）练 习（2）定义邻域移动为两两换位, 对顺序编码[ 4 2 3 5 1 ]，以下染色体是否在其邻域内： [ 4 3 2 5 1 ]， [ 4 3 5 1 2 ]， [ 4 3 3 5 1 ]， [ 5 2 3 4 1 ]， [1 2 3 5 4 ]， [ 3 4 2 5 1 ]， 是否是否否是二. TS的基本原理及步骤（4）二. TS的基本原理及步骤（4）禁忌表的概念 禁忌表的作用：防止搜索出现循环 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 前若干步走过的点、方向或目标值，禁止返回 表是动态更新的——把最新的解记入，最老的解从表中释放(解禁)。 表的长度称为Tabu-Size，一般取5、 7 、11，表长越大分散性越好。二. TS的基本原理及步骤（5）二. TS的基本原理及步骤（5）邻域搜索规则 每一步移动到不在T表中的邻域中的最优解，即 若 ， 则令 则本次移动到最优解 邻域搜索规则的作用：保证TS的优良局部搜索 功能二. TS的基本原理及步骤（6）二. TS的基本原理及步骤（6）渴望水平函数 是一个取决于 和 的值，若有 则 是不受T表限制。即使 ，仍可取 渴望水平，一般为历史上曾经达到的最好 目标值。三. TS的算法步骤（1）三. TS的算法步骤（1）步骤： 选一个初始点 ， ，令 ， ，迭代指标 ； 若 停止，否则令 ，若 (其中NG为最大迭代数)停止； 注： 表示非正常终止，造成的原因：邻域小，T表长。正常设置为(T表长度<邻域大小)。步骤②的作用是设置循环体出口。三.TS的算法步骤（2）三.TS的算法步骤（2）若 ， 令 ,更新 ( 当前邻域最优目标函数值) ； 注：步骤③的作用邻域选优 若 ， 且 ，令 ,更新 C(x)； 注：步骤④的作用破禁检查三.TS的算法步骤（3）三.TS的算法步骤（3）若 ，令 ， 注：步骤⑤的作用选优并记录历史最好点,更新渴望水平) 更新T表，转步2( 存入T表中的第一个位置 )null四.TS可以克服局优的分析（1）四.TS可以克服局优的分析（1）从邻域搜索的方法看 移向 中最好的解，但不与当前解比较 是 中的最优点，但 可能劣于四.TS可以克服局优的分析（2）四.TS可以克服局优的分析（2）选优规则看 始终保持历史上的最优解，不以当前解为最优 从停止规则上看 不以最优判据为停止规则，而是指定最大迭代 步数为停止条件，这样不能保证最优性。五.TS举例（1）五.TS举例（1）问题的提出 由7层不同的绝缘材料构成的一种绝缘体，应如 何排列顺序，可获得最好的绝缘性能。五.TS举例（2）五.TS举例（2） 编码方式：顺序编码 初始编码：2-5-7-3-4-6-1 目标值：极大化目标值。 邻域定义：两两交换是一个邻域移动 邻域大小： Tabu Size：3 NG：5五.TS举例（3）五.TS举例（3）初始表 初始编码：2-5-7-3-4-6-1 结论：交换4和5五.TS举例（4）五.TS举例（4）迭代1 编码：2-4-7-3-5-6-1 = =16 结论：交换1和3五.TS举例（5）五.TS举例（5）迭代2 编码：2-4-7-1-5-6-3 = =18 结论：因交换1和3已在禁忌表中，故只能交换2和4若选择这项 =16，渴 望水平不能发生作用五.TS举例（6）五.TS举例（6）迭代3 编码：4-2-7-1-5-6-3 =14， =18 结论：因渴望水平发挥作用，交换在破禁表中的4,5因 =20大于渴望水平 =18 此时渴望水平发生作用，破禁。交换 4和5。 五.TS举例（7）五.TS举例（7）迭代4 编码：5-2-7-1-4-6-3 = =20 结论：交换7和1五.TS举例（8）五.TS举例（8）迭代5 编码：5-2-1-7-4-6-3 = =20 结论： 迭代已到5次，得到最优解 5-2-7-1-4-6-3和5-2-1-7-4-6-3 = =20 六.TS的中、长期表的使用（1）六.TS的中、长期表的使