《张砦遗传算法在多目标优化中的应用汇编》由会员分享，可在线阅读，更多相关《张砦遗传算法在多目标优化中的应用汇编（45页珍藏版）》请在金锄头文库上搜索。
1、遗传算法在多目标优化中的应用 张砦 目 录 一、遗传算法概述 二、多目标优化问题 三、实例1Rosenbrock函数最值问题 四、实例2智能组卷问题 一、遗传算法概述 1.1 遗传算法的生物学基础 1.2 遗传算法搜索机制 1.3 遗传算法的发展 1.4 基本遗传算法（SGA） 1.5 遗传算法的特点 1.6 遗传算法的收敛性分析 1.7 遗传算法研究的主要问题 1.8 遗传算法的应用 1.1 遗传算法的生物学基础 生物在自然界中的生存繁衍，显示出了其对自然环境的自 适应能力。受其启发，人们致力于对生物各种生存特性的机理 研究和行为模拟，为人工自适应系统的设计和开发提供了广阔 的前景。 遗传算
2、法(Genetic Algorithms，简称GAs)所借鉴的生物学 基础是生物的遗传和进化。 (1) 生物的所有遗传信息都包含在其染色体中，染色体决定了 生物的性状； (2) 染色体是由基因及其有规律的排列所构成的，遗传和进 化过程发生在染色体上； (3) 生物的繁殖过程是由其基因的复制过程来完成的； (4) 通过同源染色体之间的交叉或染色体的变异会产生新的 物种，使生物呈现新的性状。 (5) 对环境适应性好的基因或染色体经常比适应性差的基因 或染色体有更多的机会遗传到下一代。 1.2 遗传算法搜索机制 遗传算法模拟自然选择和自然遗传过程中发生的繁 殖、交叉和基因突变现象（染色体的变化），将
3、实际问 题的解答描述成染色体的形式，进行类似生物进化现象 的操作以求解。对每次迭代中保留的候选解，按某种指 标从解群中选取较优的个体，利用遗传算子(选择、交叉 和变异)对这些个体进行组合，产生新一代的候选解群， 重复此过程，直到满足某种收敛指标为止。 1.3 遗传算法的发展 (1) (1) 萌芽期萌芽期 (50(50年代后期至 年代后期至7070年代初期年代初期) ) 50年代后期，一些生物学家着手采用电子计算机模拟生物 的遗传系统，尽管这些工作纯粹是研究生物现象，但其中已使用 现代遗传算法的一些标识方式。 1965年，德国的L.Rechenberg等人正式提出进化策略的方法 ，当时的进化策略
4、只有一个个体，而且进化操作也只有变异一种 。 1965年，美国的L.j.Fogel正式提出进化规划，在计算中采 用多个个体组成的群体，而且只运用变异操作。 60年代期间，美国J.H.Holland在研究自适应系统时，提出 系统本身与外部环境相互协调的遗传算法。1968年， J.H.Holland教授又提出模式理论，它成为遗传算法的主要理论 基础。 1967年，Bagley发表了关于遗传算法应用的论文，在其论文 中首次使用“遗传算法（ Genetic Algorithm）”一词。 (2) (2) 成长期成长期 (70(70年代中期至 年代中期至8080年代末期年代末期) ) 1975年，J.H.
5、Holland教授的专著Adaptation in Natural and Artificial System正式出版，全面地介绍了遗传算法，人 们常常把这一事件视作遗传算法问世的标志， Holland也被视作 遗传算法的创始人。 1975年，De.Jong在其博士论文中结合模式定理进行了大量的 纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了 一些重要且具有指导意义的结论。 1987年，美国D.Lawrence总结人们长期从事遗传算法的经验 ，公开出版Genetic Algorithm and Simulated Annealing一 书，以论文集形式用大量实例介绍遗传算法。 198
6、5年，作为Holland的学生，D.E.Goldberg博士出版专著 Genetic Algorithmsin Search，Optimization and Machine Learning，全面、系统地介绍遗传算法，使这一技术 得到普及与推广。该书被人们视为遗传算法的教科书。 1985年，在美国举行第一届遗传算法国际学术会议 (International Conference on Genetic Algorithms，简称ICGA ），与会者交流运用遗传算法的经验。随后，每2年左右都举行一 次这种会议。 (3) (3) 发展期发展期(90(90年代以后年代以后) 90年代，遗传算法不断地
7、向广度和深度发展。 1991年，D.Lawrence出版Handbook of Genetic Algorithms一书，详尽地介绍遗传算法的工作细节。 1996年 Z.Michalewicz的专著遗传算法 + 数据结构 = 进 化程序深入讨论了遗传算法的各种专门问题。同年，T.Back的 专著进化算法的理论与实践：进化策略、进化规划、遗传算法 深入阐明进化算法的许多理论问题。 1992年，Koza出版专著Genetic Programming:on the Programming of Computer by Means of Natural Selection ，该书全面介绍了遗传规划的原
8、理及应用实例，表明遗传规划己 成为进化算法的一个重要分支。 1994年，Koza又出版第二部专著Genetic Programming :Automatic Discovery of Reusable Programs，提出自动 定义函数的新概念，在遗传规划中引入子程序的新技术。同年， K.E.Kinnear主编Advances in Genetic Programming，汇集 许多研究工作者有关应用遗传规划的经验和技术。 1.4 基本遗传算法（SGA） 1.4.1 基本遗传算法的构成要素 (1) (1) 染色体编码方法染色体编码方法 基本遗传算法使用固定长度的二进制符号串固定长度的二进制符
9、号串来表示群体 中的个体，其等位基因由二值符号集0，1组成。初始群体 中各个个体的基因值用均匀分布的随机数来生成。如： 100111001000101101，就可表示一个个体，该个体的染色体 长度是18。 (2) (2) 个体适应度评价个体适应度评价 基本遗传算法按与个体适应度成正比的概率来决定当前按与个体适应度成正比的概率来决定当前 群体中每个个体遗传到下一代群体中的机会多少。群体中每个个体遗传到下一代群体中的机会多少。为正确计 算这个概率，这里要求所有个体的适应度必须为正数或零。 这样，根据不同种类的问题，必须预先确定好由目标函数值 到个体适应度之间的转换规则，特别是要预先确定好当目标 函
10、数值为负数时的处理方法。 (3) (3) 遗传算子遗传算子 基本遗传算法使用下述三种遗传算子： 选择运算：使用比例选择算子比例选择算子； 交叉运算：使用单点交叉算子单点交叉算子； 变异运算：使用基本位变异算子基本位变异算子。 (4) (4) 基本遗传算法的运行参数基本遗传算法的运行参数 基本遗传算法有下述4个运行参数需要提前设定： M M：群体大小，即群体中所含个体的数量，一般取20-100。 T T：遗传运算的终止进化代数，一般取100 - 500 p p c c ：交叉概率，一般取0.4 - 0.99 p p m m ：变异概率，一般取 0.0001 - 0.1 说明说明: :这4个运行参
11、数对遗传算法的求解结果和求解效率都有一定 的影响，但目前尚无合理选择它们的理论依据。在遗传算法的 实际应用中，往往需要经过多次试算后才能确定出这些参数合 理的取值大小或取值范围。 1.4.2 基本遗传算法的形式化定义 基本遗传算法可定义为一个7元组： GAGA (M, F, s, c, m, p(M, F, s, c, m, p c c , p, p m m ) ) M群体大小； F个体适应度评价函数； s选择操作算子； c交叉操作算子： m变异操作算子； pc交叉概率； pm变异概率； 1.4.3 基本遗传算法的实现 （1 1） 编码与解码编码与解码 假设某一参数的取值范围是umin , u
12、max，我们用长度 为的二进制编码符号串来表示该参数，则它总共能够产生 2种不同的编码，参数编码时的对应关系如下： 00000000000000000 umin 00000000000000011 umin + 00000000000000102 umin + 2 1111111111111111=21 umax 其中， 为二进制编码的编码精度，其公式为： = umax umin 2 1 x = umin + ( bi 2i-1 ) 1 i=l Umax umin 2l 1 假设某一个体的编码是： x： bl bl-1 bl-2b2b1 则对应的解码公式为： 例 设 -3.0 x 12.1 ,
13、 精度要求 =1/10000，由公式 ： Umax umin 2l =+ 1 1/10000 12.1 + 3.0 + 1= = 151001 即： 217 151001 218 x需要18位 0/1 符号表示。 如：010001001011010000 解码： x = umin + ( bi 2i-1) 1 i=l Umax umin 2l 1 = - 0.3 + 70352(12.1+3)/(218-1) = 1.052426 = Umax umin 2l 1 得： （2 2） 个体适应度评价个体适应度评价 (1) 当优化目标是求函数最大值，并且目标函数总取正值 时，可以直接设定个体的适应
14、度F(X)就等于相应的目标函数 值f(X)，即： F(X)f(X) (2) (2) 对于求目标函数最小值的优化问题对于求目标函数最小值的优化问题，理论上只需简单 地对其增加一个负号就可将其转化为求目标函数最大值的优 化问题，即：min f(X)max (-f(X) 但实际优化问题中的目标函数值有正也有负，优化目标 有求函数最大值，也有求函数最小值，显然上面两式保证不 了所有情况下个体的适应度都是非负数这个要求。 （3 3） 选择算子选择算子 作用：作用：从当前代群体中选择出一些比较优良的个体，并将其复 制到下一代群体中。 比例选择算子：比例选择算子：指个体被选中并遗传到下一代群体中的概率 与该
15、个体的适应度大小成正比。 轮盘选择：轮盘选择：轮盘法的基本精神 是：个体被选中的概率取决于 个体的相对适应度，显然，个 体适应度愈高，被选中的概率 愈大。但是，适应度小的个体 也有可能被选中，以便增加下 一代群体的多样性。 （4 4） 交叉算子交叉算子 作用： 通过交叉，子代的基因值不同于父代。交换是遗传 算法产生新个体的主要手段。正是有了交换操作，群体的性 态才多种多样。 单点交叉算子单点交叉算子的具体计算过程如下：的具体计算过程如下： . 对群体中的个体进行两两随机配对。 . 每一对相互配对的个体，随机设置某一基因座之后的位 置为交叉点。 . 对每一对相互配对的个体，依设定的交叉概率pc在其交 叉点处相互交换两个个体的部分染色体，从而产生出两个新 的个体。 单点交叉A；10110111 00 A：10110111 11 B：00011100 11 B：00011100 00 （5 5）变异算子）变异算子 基本位变异算子：最简单和最基本的变异操作算子。 对于基本遗传算法中用二进制编码符号串所表示的个体 ，若需要进行变异操作的某一基因座上的原有基因值为0，则 变异操作将该基因值变为1，反之，若原有基因值为1，则变 异操作将其变为0。 具体执行过程： .对个体的每一个基因座，依变异概率pm指定其为变异点。 .对每一个指定的变异点，
