《武汉大学选修课系统工程概论ap8优化技术的前沿》由会员分享，可在线阅读，更多相关《武汉大学选修课系统工程概论ap8优化技术的前沿（31页珍藏版）》请在金锄头文库上搜索。
1、优化决策技术的前沿优化决策技术的前沿 遗传算法 神经网络 模糊决策 混沌 协同学 耗散结构 优化决策技术的前沿遗传算法 产生与发展 John Holland与其同事和学生在20世纪60年代末 到70年代初期的开创性工作。 1975年他的专著Adaptation in Natural and Artificial System的出版标志着GAs的诞生。 “Genetic Algorithms”一词首先出现在J.D.Bagleg 的博士论文中，他研究了遗传算法在博弈论中的 参数搜索，这是遗传算法的最早的应用。优化决策技术的前沿关键人物 J. H. Holland J. D. Bagley（遗传算法
2、的第一篇应用论文，自适应遗传 算法） K. A. De Jong（数值计算，参数设置，测试函数，在线指 标，离线指标） D. J. Goldberg（搜索、优化和机器学习中的遗传算法， 1989，系统总结主要研究成果） L. Davis （遗传算法手册，1991，大量应用实例） J. R. Koza（1992， 应用于计算机程序的优化设计与自动 生成，提出遗传编程的概念）优化决策技术的前沿遗传算法 遗传算法的发展高潮始于20世纪80年代末，并一直 延续至今。 人们对遗传算法的兴趣日益增长有两个背景： 其一是工程领域，特别是人工智能与控制领域，不 断地涌现超大规模的、复杂的非线性系统，在这些 系
3、统的研究中存在着大量经典优化方法所不能有效 求解的优化问题。 其二是遗传算法能独立的或与其他方法相结合的形 式用于智能机器的学习系统的设计中，而不依赖于 问题的种类优化决策技术的前沿六峰值驼背函数 Six-hump camel back function 该函数有6个局部极小点， 其中全局最小点 (-0.0898, 0.7126)T (0.0898, -0.7126) T 全局最小值：-1.031628遗传算法LINGO优化决策技术的前沿遗传算法 遗传算法（Genetic Algorithms，简称GAs） 的生物学背景： Darwin的进化论和Mendel的遗传学说 适者生存，劣质淘汰 即优
4、胜劣汰优化决策技术的前沿遗传算法的基本思想 GAs是将问题的求解表示成“染色体”，从而构成 一群染色体。 将它们置于问题的“环境”中，根据适者生存的原 则，从中选择出适应环境的染色体进行复制，即 再生（Reproduction，也称Selection），通过交 叉（Crossover）、变异（Mutation）两种基因操 作产生出新的一代更适应环境的染色体群。 这样一代代的不断进化，最后收敛到一个最适合 环境的个体上，求得问题的最优解。 优化决策技术的前沿自然进化与GAs的对应关系基因串 （染色体）问题的 可行解基因型表现型适应度解码编码目标函数解码不同环境解的 评价值优化决策技术的前沿GAs
5、的流程图实际问题参数集确定表示问题解答的染色体（串）生成初始染色体串群计算每个个体的适应度是否收敛选择高适应值的串进行复制交叉变异输出最优解是否优化决策技术的前沿遗传算法的基本概念 个体和个体空间 适应度函数（F ( t )） 遗传算子:选择、交叉和变异算子 控制参数:种群规模 M、交叉概率Pc 、变异概率Pm 、进化代数T优化决策技术的前沿基本遗传算法的构成要素 （1）染色体编码方法 采用固定长度的二进制符号串来表示群体 的个体，其等位基因是0,1组成。如 X100111001000101101 该个体的染色体长度是n18优化决策技术的前沿基本遗传算法的构成要素 （2）个体适应度评价 基本遗
6、传算法按与个体适应度成正比的概 率来决定当前群体中每个个体遗传到下一 代的机会的多少。 必须预先确定好由目标函数值到个体适应 度之间的转换规则。优化决策技术的前沿个体适应度评价优化决策技术的前沿基本遗传算法的构成要素 （3）遗传算子 基本遗传算法使用三种遗传算子： 选择算子（比例选择算子） 交叉运算（单点交叉算子） 变异算子（基本位变异或均匀变异算子）优化决策技术的前沿比例选择算子 也称赌盘选择，个体被选中并遗传到下一 代群体中的概率与该个体的适应度大小成 正比。金银铜铁10203040优化决策技术的前沿单点交叉算子 （1）对群体中的个体进行两两随机配对 （2）对每一对相互配对的个体，随机设置
7、某一 基因座之后的位置为交叉点 （3）对每一对相互配对的个体，依设定的交叉 概率与其交叉点相互交换两个个体的部分染色体 ，从而产生两个新的个体。 A:1 0 1 1 0 1 1 1 0 0 单点交叉A: 1 0 1 1 0 1 1 1 1 1 B:0 0 0 1 1 1 0 0 1 1 B: 0 0 0 1 1 1 0 0 0 0优化决策技术的前沿基本位变异算子 （1）对个体的每一个基因座，依变异概率指定 其为变异点； （2）对每一个指定的变异点，对其等位基因值 作取反运算或用其他等位基因来代替，从而产生 一个新的个体。 A:1 0 1 1 0 1 1 1 0 0 A: 1 0 1 1 1 1
8、 1 1 0 0基本位变异变异点优化决策技术的前沿基本遗传算法的构成要素 （4）运行参数 群体大小M，即种群中所含个体的数量； 一般取20100 终止进化代数T： 交叉概率Pc ：一般取0.40.99 变异概率Pm：一般取0.00010.1优化决策技术的前沿遗传算法的数学基础 模式定理：在遗传算子选择、交叉和变异的作用下，具有 低阶、短定义距以及平均适应度高于群体平均适应度的模 式在子代中将得以指数级增长。 积木块假设：低阶、距短、高平均适应度的模式（积木 块）在遗传算子作用下，相互结合，能生成高阶、长距、 高平均适应度的模式，可最终生成全局最优解。 隐含并行性：遗传算法有效处理的模式个数为
9、收敛性分析与证明：基本遗传算法收敛于最优解的概率小 于1；使用最佳保留策略的遗传算法能收敛于最优解的概 率为1 优化决策技术的前沿遗传算法的特点 （1）良好的并行性 （2）很强的通用性 （3）良好的全局优化性能和稳健性 （4）良好的可操作性与简单性优化决策技术的前沿函数优化的实例 （1）个体编码，把编码为一种符号串。 本例中x1，x2可分别用3位无符号二进制整数表 示，把它们连接在一起组成的6位无符号二进 制整数就形成个体的基因型，表示一个可行解 。优化决策技术的前沿函数优化的实例 基因型 X101110 表现型 X5,6T 个体的表现型和基因型之间可通过编码和 解码相互转换。优化决策技术的前
10、沿函数优化的实例 （2）初始种群的产生 群体规模的大小取4 每个个体随机产生 （3）适应度计算 直接以目标函数值作为个体的适应度优化决策技术的前沿函数优化的实例 （4）选择运算 先计算出群体中个体的适应度之和 其次计算每个个体的相对适应度的大小 最后产生一个01之间的随机数，依据该 随机数出现在上述哪一个概率区间来确定 各个个体被选中的次数。优化决策技术的前沿函数优化的实例 （5）交叉计算 先对群体进行随机配对 其次随机设置交叉位置 最后在相互交换配对染色体之间的部分基 因优化决策技术的前沿函数优化的实例 （6）变异操作 首先确定各个个体的基因变异位置； 然后依据某一概率将变异点的原有基因值
11、取反。优化决策技术的前沿函数优化的实例个体 编号初始群 体P(0)x1x2f i(x1，x2)f i/ f i101110 135340.24210101 153340.24301110 034250.17411100 171500.35 f i143fmax50faver=35.75优化决策技术的前沿函数优化的实例选择 次数选择 结果配对 情况交叉点 位置交叉结 果变异 点变异结 果101110 11212：2011001401110 1 111100 1111101511111 1 010101 13434：4101001211100 1 211100 1111011611101 0优化决策技术的前沿轮盘赌规则00.240.480.65优化决策技术的前沿函数优化的实例子代群 体P(1)x1x2f i(x1，x2)f i/ f i01110 135340.1411111 177980.4211100 171500.2111101 072530.23 f i235fmax98faver=58.75优化决策技术的前沿考试方式 开卷考试 题目形式： 名词解释 简答 计算建模题
