当前位置:文档下载 > 所有分类 > 自然科学 > 基本遗传算法及应用举例
免费下载此文档

基本遗传算法及应用举例

基本遗传算法及应用举例

基本遗传算法及应用举例

遗传算法(Genetic Algorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。遗传算法是多学科相互结合与渗透的产物。目前它已发展成一种自组织、自适应的多学科技术。

针对各种不同类型的问题,借鉴自然界中生物遗传与进化的机理,学者们设计了不同的编码方法来表示问题的可行解,开发出了许多不同环境下的生物遗传特征。这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。但这些遗传算法有共同的特点,即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。基于此共同点,人们总结出了最基本的遗传算法——基本遗传算法。基本遗传算法只使用选择、交叉、变异三种基本遗传操作。遗传操作的过程也比较简单、容易理解。同时,基本遗传算法也是其他一些遗传算法的基础与雏形。 1.1.1 编码方法

用遗传算法求解问题时,不是对所求解问题的实际决策变量直接进行操作,而是对表示可行解的个体编码的操作,不断搜索出适应度较高的个体,并在群体中增加其数量,最终寻找到问题的最优解或近似最优解。因此,必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中,把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之,个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。

编码是应用遗传算法是需要解决的首要问题,也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集{0,1},也就是说,把问题空间的参数表示为基于字符集{0,1}构成的染色体位串。每个个体的染色体中所包含的数字的个数L称为染色体的长度或称为符号串的长度。一般染色体的长度L为一固定的数,如

X=10011100100011010100

表示一个个体,该个体的染色体长度L=20。

二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a,b],我们用长度为L的二进制编码符号串来表示该参数,总共能产生2种不同的编码,若参数与编码的对应关系为

00000000000 00000000=0 →a

00000000000 00000001=1 →a+δ

111111111111 11111111=2-1→b 则二进制编码的编码精度

L

L

b a

L

2 1

假设某一个个体的编码是xk ak1ak2 akl,则对应的解码公式为

b aL

xk a L( akj2L j)

2 1j 1

例如,对于x [0,1023],若用长度为10的二进制编码来表示该参数的话,则下述符号串:

第1页

免费下载Word文档免费下载:基本遗传算法及应用举例

(下载1-5页,共5页)

我要评论

返回顶部