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