实用标准文案
基本遗传算法及应用举例
遗传算法(Genetic Algorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。遗传算法是多学科相互结合与渗透的产物。目前它已发展成一种自组织、自适应的多学科技术。
针对各种不同类型的问题，借鉴自然界中生物遗传与进化的机理，学者们设计了不同的编码方法来表示问题的可行解，开发出了许多不同环境下的生物遗传特征。这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。但这些遗传算法有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。基于此共同点，人们总结出了最基本的遗传算法——基本遗传算法。基本遗传算法只使用选择、交叉、变异三种基本遗传操作。遗传操作的过程也比较简单、容易理解。同时，基本遗传算法也是其他一些遗传算法的基础与雏形。 1．1．1 编码方法
用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。
编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L称为染色体的长度或称为符号串的长度。一
精彩文档
实用标准文案
般染色体的长度L为一固定的数，如
X=10011100100011010100
表示一个个体，该个体的染色体长度L=20。
二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[a，b]，我们用长度为L的二进制编码符号串来表示该参数，总共能产生2L种不同的编码，若参数与编码的对应关系为
00000000000……00000000=0 →a
00000000000……00000001=1 →a+δ ?
? ?
111111111111……11111111=2L-1→b 则二进制编码的编码精度??b?a L2?1 假设某一个个体的编码是xk?ak1ak2?akl，则对应的解码公式为
b?aL(?akj2L?j) xk?a?L2?1j?1例如，对于x?[0,1023],若用长度为10的二进制编码来表示该参数的话，则下述符号串： x=0010101111
就表示一个个体，它对应的参数值是x=175.此时的编码精度为1.
二进制编码方法相对于其它编码方法的优点，首先是编码、解码操作简单易行；其次是交叉遗传操作便于实现；另外便于对算法进行理论分析。
2. 个体适应度函数
在遗传算法中，根据个体适应度的大小来确定该个体在选择操作中被选定的概率。个
精彩文档
实用标准文案
体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择操作方法来确定群体中各个个体是否有可能遗传到下一代群体中。为了正确计算不同情况下各个个体的选择概率，要求所有个体的适应度必须为正数或为零，不能是负数。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好目标函数值为负数时的处理方法。
设所求解的问题为：maxf(x)， x?D.
对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的问题，即minf(x)?max(?f(x)). 当优化问题是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度函数值F(x)就等于相应的目标函数值f(x)，即F(x)?f(x).
但实际目标优化问题中的目标函数有正也有负，优化目标有求函数最大值，也有求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个要求，必须寻求出一种通用且有效的由目标函数值到适应度之间的转换关系，有它来保证个体适应度总取非负值。
为满足适应度取负值的要求,基本遗传算法一般采用下面方法将目标函数值f(x)变换为个体的适应度F(x).
对于求目标函数最大值的优化方法问题，变换方法为 f(x)?Cmin, f(x)?Cmin?0时，
F(x)?
0 f(x)?Cmin?0时，
式中，Cmin为一个适当的相对比较小的数，它可以是预先指定的一个较小的数，或进
精彩文档
基本遗传算法及的应用举例
