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