阅读文章--机电之家
遗传算法(Genetic Algorithm，简称GA)简介
[ 来源：'d' | 类别：技术 | 时间：2008-6-24 14:21:02 ] [字体：]
遗传算法的定义
遗传算法通常实现为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进 制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中 随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。
遗传算法的机理
在遗传算法里，优化问题的解被称为个体，它表示为一个参数列表，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，不过也有其他的表示方法 适用。一开始，算法随机生成一定数量的个体，有时候操作者也可以对这个随机产生过程进行干预，播下已经部分优化的种子。在每一代中，每一个个体都被评价， 并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序，适应度高的在前面。这里的“高”是相对于初始的种群的低适应度来说的。
下一步是产生下一代个体并组成种群。这个过程是通过选择和繁殖完成的，其中繁殖包括杂交和突变。选择则是根据新个体的适应度进行的，适应度越高，被选择的 机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。之后，被选择的个体进入杂交过程。一般的遗传算法 都有一个杂交率的参数，范围一般是0.6~1，这个杂交率反映两个被选中的个体进行杂交的概率。例如，杂交率为0.8，则80%的“夫妻”会生育后代。每 两个个体通过杂交产生两个新个体，代替原来的“老”个体，而不杂交的个体则保持不变。杂交父母的染色体相互交错，从而产生两个新的染色体，第一个个体前半 段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段不是真正的一半，这个位置叫做杂交点，也是随机产生的，可以是染色体的任意位 置。再下一步是突变，通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变常数，通常是0.01或者更小，这代表突变发生的概率。根据这个概率， 新个体的染色体随机的突变，通常就是改变染色体的一个字节（0变到1，或者1变到0）。
经过这一系列的过程（选择、杂交和突变），产生的新一代个体不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去 产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体杂交，然后突变，产生第三代。周而复始，直到 终止条件满足为止。一般终止条件有以下几种：
遗传算法(Genetic Algorithm，简称GA)是一种基于进化论优胜劣汰、适者生存的物种遗传思想的搜索算法。本世纪50年代初，由于一些生物学家尝试用计算机模拟生物系统，从而产生了GA的基本思想。美国密执根大学的霍勒德（J.H.Holland）于70年代初提出并创立了遗传算法。遗传算法作为一种解决复杂问题的崭新的有效优化方法，近年来得到了广泛的实际应用，同时也渗透到人工智能、机器学习、模式识别、图像处理、软件技术等计算机学科领域。GA在机器学习领域中的一个典型应用就是利用GA技术作为规则发现方法应用于分类系统。
遗传算法将个体的集合──群体作为处理对象，利用遗传操作──交换和突变，使群体不断"进化"，直到成为满足要求的最优解。
在霍勒德的GA算法中采用二进制串来表示个体。考虑到物种的进化或淘汰取决于它们在自然界中的适应程度，GA算法为每一个体计算一个适应值或评价值，以反映其好坏程度。因而，个体的适应值越高，就有更大的可能生存和再生，即它的表示特征有更大的可能出现在下一代中。遗传操作"交换"旨在通过交换两个个体的子串来实现进化；遗传操作"突变"则随偶地改变串中的某一（些）位的值，以期产生新的遗传物质或再现已在进化过程中失去的遗传物质。
霍勒德提出的遗传算法也称为简单遗传算法（simple genetic algorithm,SGA），是一种基本的遗传算法。SGA的处理过程如下：
begin
1. 选择适当表示，生成初始群体；
2. 评估群体；
3. While 未达到要求的目标 do
begin
1. 选择作为下一代群体的各个体；
2. 执行交换和突变操作；
3. 评估群体；
end
end
因此，对于一个SGA算法来说主要涉及以下内容：
·编码和初始群体生成；
·群体的评价；
·个体的选择；
·交换；
·突变；
1. 编码和初始群体的生成
GA的工作基础是选择适当的方法表示个体和问题的解（作为进化的个体）。SGA要求个体均以0、1组成的串来表示，且所有个体串都是等长的。实际上，可以任意指定有限元素组成的串来表示个体，而不影响GA的基本算法。
对于同一问题，可以有不同的编码表示方法。由于遗传操作直接作用于所表示的串上，因而不同的表示方法对SGA的效率和结果都会有影响。从原理上讲，任何取值为整数（或其它有限可枚举的值）的变量，均可用有限长度的0、1串来表示，而任何取值为连续实数的变量也均可用有限长度的0、1串来近似表示。因此，对任何一个变量，均可在一定程度上用0、1串来表示（编码），而当问题的解涉及多个变量时，则可用各变量对应串的拼接（形成一个长串）来表示相应解。
SGA处理的起始点并非一个个体，而是由一组个体所组成的群体。一般可用随机方法来产生初始群体，当然最好能考虑各个体的代表性和分布概率。
2. 群体的评价
对群体中各个体的适应性评价常需直接利用待优化问题的目标函数。这一目标函数也可称为适应函数，个体选择（或再生）过程正是基于这一函数来评价当前群体中各个体的再生概率。
3. 个体的选择
选择操作是对自然界"适者生存"的模拟。评价值（目标函数值）较大的个体有较高的概率生存，即在下一代群体中再次出现。
一种常用的选择方法是按比例选择，即若个体i的适应值（目标函数值）是fi，则个体i在下一代群体中复制（再生）的子代个数在群体中的比例将为：
fi/∑fi 。
其中，∑fi示指所有个体适应值之和。
若当前群体与下一代群体的个数均维持在n，则每一个体i在下一代群体中出现的个数将是：
n*fi/∑fi=fi/f ,
其中f=∑fi/n是群体评价的平均值。fi /f的值不一定是一个整数。为了确定个体在下一代中的确切个数，可将fi/f的小数部分视为产生个体的概率。如，若fi/f为2.7，则个体i有70％的可能再生2+1=3个，而有30％的可能只再生2个。
SGA采用称为旋转盘（roulette wheel）的方法来产生各个体的再生数。方法是：
每一个体均对应于旋转盘中的一个以园点为中心的扇形区域，区域角度为2π*fi/∑fi，因而，各个体的区域角度之和等于2π。然后随机产生一个0到2π的值，根据该值所对应的区域，再生一个对应个体，直到产生的个体个数达到所需的数目，从而生成下一代的原始群体。这个群体还需进一步应用交换和突变操作。
4. 交换
交换是GA中最主要的遗传操作，其工作于选择过程结束后产生的下一代群体。交换操作应用于从这一群体中随机选择的一系列个体对（串对）。
SGA采用的是单点交换。设串长为L，交换操作将随机选择一个交换点（对应于从1到L-1的某个位置序号），紧接着两串交换点右边的子串互换，从而产生了两个新串。
例如，设Ａ1，Ａ2为要交换的串，交换点被随机选择为7（串长为10）。
Ａ1＝1000011111
Ａ2＝1111111011
交换得新串Ａ1'，Ａ2'：
Ａ1'＝1000011011
Ａ2'＝1111111111
当然，并非所有选中的串对都会发生交换。这些串对发生交换的概率是Pc。Pc为事先指定的0－1之间的值，称为交换率。
5. 突变
另一种遗传操作是突变，它一般在交换后进行。突变操作的对象是个体（即串），旨在改变串中的某些位的值，即由0变为1，或由1变为0。并非所有位都能发生变化，每一位发生变化的概率是Pm。Pm为事先指定的0－1之间的某个值，称为突变率。串中每一位的突变是独立的，即某一位是否发生突变并不影响其它位的变化。突变的作用是引进新的遗传物质或恢复已失去的遗传物质。例如，若群体的各串中每一位的值均为0，此时无论如何交换都不能产生有1的位，只有通过突变。
遗传算法进化循环的一个例子
设每一串的长度为10，共有4个串组成第一代群体（POP1），目标函数（适应函数）为各位值之和，因而函数值为0－10。POP1中四个串的适应值分别为：3，6，6，9，所以再生的比例个数为：0.5，1，1，1.5。若最后实际的再生个数为0，1，1，2，则产生选择后的群体POP2。下一步对POP2中各串配对，随机选择串1和串4为一对，串2和串3为另一对。
群体POP1
串 适应值
0000011100 3
1000011111 6
0110101011 6
1111111011 9
群体POP2（选择后）
串 适应值
1000011111 6
0110101011 6
1111111011 9
1111111011 9
群体POP3（交换后）
串 适应值
1000011011 5
0110101011 6
1111111011 9
1111111111 10
群体POP4（突变后）
串 适应值
1000011011 5
0110111011 7
1111111011 9
0111111111 9
设交换率为0.5，即只有一对串发生交换，如串1和串4。若交换点随机选在位置7，因而交换后产生群体POP3。设突变率为0.05，即在POP3的40个位中，共有2个位发生突变，不妨设突变发生在串2的第6位和串4的第1位，从而产生群体POP4。注意，仅群体POP4代表新一代的群体（上一代为POP1），POP2和POP3只是一些进化中的中间群体。
在SGA算法中，一般采用的群体大小为30到200，交换率为0.5到1，突变率为0.001到0.05。这些参数：群体大小、交换率、突变率，统称为GA的控制参数，应在算法运行前事先设定。当然，已有人研究了控制参数在算法运行中的自适应调整，以提高GA的灵活性。
尽管遗传算法在实际优化问题中取得了很好的效果,目前对该算法尚无一个清楚完整的理论解释。霍勒德的图式理论(schema theory)和戈尔伯格（Goldberg，1989）的积木块假设仅在一定程度上解释了GA的工作原理。
·上篇文章：粒子群算法
·下篇文章：遗传算法的研究方向阅读：1407人次 【 我也要发表机电论文 】 【 】
相关文章
·基于DSP和FPGA的机器人声控系统设计与实现 2011-3-5 11:23:16
·新手入门：电子元器件常识 2011-3-5 11:19:44
·如何为机器视觉系统选择采集卡 2011-3-5 11:16:07
·ARM的开发步骤 2011-3-5 11:11:31
·光电编码器的原理与应用 2011-3-5 11:10:01
特别声明：机电之家(http://www.jdzj.com)所共享的机电类资料，机电论文、机电类文章、机电企业类管理制度、机电类软件都来自网上收集，其版权归作者本人所有，如果有任何侵犯您权益的地方，请联系我们，我们将马上进行处理。购买的论文都出自原创，保证作者的原创的版权的转让，任何纠纷由法律解决。
相关评论0篇,当前显示最新的5篇
主办：浙江-杭州-机电之家网络运营部浙ICP备05041018号
