遗传算法及其MATLAB程序实现.doc

遗传算法及其MATLAB实现
主要参考书:
MATLAB 辅助优化计算与设计飞思科技产品研发中心编著
电子工业出版社
遗传算法及其应用陈国良等编著
人民邮电出版社
主要内容:
遗传算法简介
遗传算法的MATLAB实现
应用举例
在工业工程中,许多最优化问题性质十分复杂,很难用
,人们对求解这类难
、被称为“
进化算法(evolutionary algorithm)”的随机优化技术在解这
类优化难题中显示了优于传统优化算法的性能。目前,进化
算法主要包括三个研究领域:遗传算法、进化规划和进化
策略。其中遗传算法是迄今为止进化算法中应用最多、比较
成熟、广为人知的算法。
一、遗传算法简介
遗传算法(ic Algorithm, GA)最先是由美国Mic-
hgan大学的John Holland于1975年提出的。遗传算法是
模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算
模型。它的思想源于生物遗传学和适者生存的自然规律,
是具有“生存+检测”的迭代过程的搜索算法。遗传算法
以一种群体中的所有个体为对象,并利用随机化技术指
导对一个被编码的参数空间进行高效搜索。其中,选择、
交叉和变异构成了遗传算法的遗传操作;参数编码、初始
群体的设定、适应度函数的设计、遗传操作设计、控制参
数设定等5个要素组成了遗传算法的核心内容。
遗传算法的基本步骤:
遗传算法是一种基于生物自然选择与遗传机理的随机
搜索算法,与传统搜索算法不同,遗传算法从一组随机产
生的称为“种群(Population)”的初始解开始搜索过程。种
群中的每个个体是问题的一个解,称为“染色体(chromos
ome)”。染色体是一串符号,比如一个二进制字符串。这
些染色体在后续迭代中不断进化,称为遗传。在每一代中
用“适值(fitness)”来测量染色体的好坏,生成的下一代染
色体称为后代(offspring)。后代是由前一代染色体通过交
叉(crossover)或者变异(mutation)运算形成的。
在新一代形成过程中,根据适度的大小选择部分后代,淘
汰部分后代。从而保持种群大小是常数。适值高的染色体
被选中的概率较高,这样经过若干代之后,算法收敛于最
好的染色体,它很可能就是问题的最优解或次优解。
主要步骤如下所示:
(1)编码:GA在进行搜索之前先将解空间的解数据表示成
遗传空间的基因型串结构数据,这些串结构数据的不同组
合便构成了不同的点。
(2)初始群体的生成:随机产生N个初始串结构数据,每个
串结构数据称为一个个体,N个个体构成了—个群体。
GA以这N个串结构数据作为初始点开始迭代。
(3)适应性值评估检测:适应性函数表明个体或解的优劣性。
对于不同的问题,适应性函数的定义方式也不同。
(4)选择:选择的目的是为了从当前群体个选出优良的个体
,使它们有机会作为父代为下一代繁殖子孙。遗传算法通
过选择过程体现这一思想,进行选择的原则是适应性强的
个体为下一代贡献一个或多个后代的概率大。选择实现了
达尔文的适者生存原则。
(5)交叉:交叉操作是遗传算法中最主要