张砦-遗传算法在多目标优化中的应用.ppt

遗传算法在多目标优化中的应用
张砦
目录
遗传算法概述
二、多目标优化问题
、实例1—— Rosenbrock函数最值问题
四、实例2——智能组卷问题
遗传算法概述



(SGA)




1遗传算法的生物学基础
生物在自然界中的生存繁衍,显示出了其对自然环境的自
适应能力。受其启发,人们致力于对生物各种生存特性的机理
研究和行为模拟,为人工自适应系统的设计和开发提供了广阔
的前景
遗传算法( Genetic Algorithms,简称GAs)所借鉴的生物学
基础是生物的遗传和进化
1)生物的所有遗传信息都包含在其染色体中,染色体决定了
生物的性状;
(2)染色体是由基因及其有规律的排列所构成的,遗传和进
化过程发生在染色体上
(3)生物的繁殖过程是由其基因的复制过程来完成的;
4)通过同源染色体之间的交叉或染色体的变异会产生新的
物种,使生物呈现新的性状,
5)对环境适应性好的基因或染色体经常比适应性差的基因
或染色体有更多的机会遗传到下一代
2遗传算法搜索机制
遗传算法模拟自然选择和自然遗传过程中发生的繁
殖、交叉和基因突变现象(染色体的变化),将实际问
题的解答描述成染色体的形式,进行类似生物进化现象
的操作以求解。对每次迭代中保留的候选解,按某种指
标从解群中选取较优的个体,利用遗传算子(选择、交叉
和变异)对这些个体进行组合,产生新一代的候选解群
重复此过程,直到满足某种收敛指标为止,

(1)萌芽期(50年代后期至70年代初期)
50年代后期,一些生物学家着手采用电子计算机模拟生物
的遗传系统,尽管这些工作纯粹是研究生物现象,但其中已使用
现代遗传算法的一些标识方式
1965年,德国的L. Rechenberg等人正式提出进化策略的方法
当时的进化策略只有一个个体,而且进化操作也只有变异一种
1965年,美国的L. j. Fogel正式提出进化规划,在计算中采
用多个个体组成的群体,而且只运用变异操作
60年代期间,. Holland在研究自适应系统时,提出
系统本身与外部环境相互协调的遗传算法。1968年,
. Holland教授叉提出模式理论,它成为遗传算法的主要理论
基础
·1967年, Bagley发表了关于遗传算法应用的论文,在其论文
中首次使用“遗传算法( Genetic Algorithm)”一词
(2)成长期(70年代中期至80年代末期)
1975年,《 Adaptation in Natural
and Artificial System》正式出版,全面地介绍了遗传算法,人
们常常把这一事件视作遗传算法问世的标志,Ho1land也被视作
遗传算法的创始人
1975年,
纯数值函数优化计算实验,树立了遗传算法的工作框架,得到了
一些重要且具有指导意义的结论
1987年,美国D. Lawrence总结人们长期从事遗传算法的经验,
公开出版《 Genetic Algorithm and Simulated Annealing》一书
以论文集形式用大量实例介绍遗传算法。
1985年,作为Ho1and的学生,. Goldberg博士出版专著
《 Genetic Algorithms—— .in search,0
ptimization and
Machine Learning》,全面、系统地介绍遗传算法,使这一技术
得到普及与推广。该书被人们视为遗传算法的教科书
1985年,在美国举行第一届遗传算法国际学术会议
(International Conference on Genetic Algorithms, 1**
ICGA),与会者交流运用遗传算法的经验。随后,每2年左右都举
(3)发展期(90年代以后)
90年代,遗传算法不断地向广度和深度发展
1991年,D. Lawrence出版《 Handbook of Genetic
Algorithms》一书,详尽地介绍遗传算法的工作细节
1996年Z. Michalewicz的专著《遗传算法+数据结构=进
化程序》深入讨论了遗传算法的各种专门问题。同年, T Back的
专著《进化算法的理论与实践:进化策略、进化规划、遗传算法
深入阐明进化算