遗传算法

kenan88 发表于 2006-5-1 21:33:18

遗传算法(GeneticAlgorithm，简称GA)是一种基于进化论优胜劣汰、适者生存的物种遗传思想的搜索算法。本世纪50年代初，由于一些生物学家尝试用计算机模拟生物系统，从而产生了GA的基本思想。美国密执根大学的霍勒德（J.H.Holland）于70年代初提出并创立了遗传算法。遗传算法作为一种解决复杂问题的崭新的有效优化方法，近年来得到了广泛的实际应用，同时也渗透到人工智能、机器学习、模式识别、图像处理、软件技术等计算机学科领域。GA在机器学习领域中的一个典型应用就是利用GA技术作为规则发现方法应用于分类系统。 　　遗传算法将个体的集合──群体作为处理对象，利用遗传操作──交换和突变，使群体不断"进化"，直到成为满足要求的最优解。 　　在霍勒德的GA算法中采用二进制串来表示个体。考虑到物种的进化或淘汰取决于它们在自然界中的适应程度，GA算法为每一个体计算一个适应值或评价值，以反映其好坏程度。因而，个体的适应值越高，就有更大的可能生存和再生，即它的表示特征有更大的可能出现在下一代中。遗传操作"交换"旨在通过交换两个个体的子串来实现进化；遗传操作"突变"则随偶地改变串中的某一（些）位的值，以期产生新的遗传物质或再现已在进化过程中失去的遗传物质。 　　霍勒德提出的遗传算法也称为简单遗传算法（simplegeneticalgorithm,SGA），是一种基本的遗传算法。SGA的处理过程如下： 　　　　begin 　　　　　　　1.选择适当表示，生成初始群体； 　　　　　 2.评估群体； 　　　　　　　3.While未达到要求的目标do 　　　　　　　　　　begin 　　　　　　　　　　 1.选择作为下一代群体的各个体； 　　　　　　　　　　 2.执行交换和突变操作； 　　　　　　　　　　 3.评估群体； 　　　　　　　　　　end 　　　　end 　　因此，对于一个SGA算法来说主要涉及以下内容： 　　　·编码和初始群体生成； 　　　·群体的评价； 　　　·个体的选择； 　　　·交换； 　　　·突变；

kenan88 发表于 2006-5-1 21:34:19

1.编码和初始群体的生成 　　GA的工作基础是选择适当的方法表示个体和问题的解（作为进化的个体）。SGA要求个体均以0、1组成的串来表示，且所有个体串都是等长的。实际上，可以任意指定有限元素组成的串来表示个体，而不影响GA的基本算法。 　　对于同一问题，可以有不同的编码表示方法。由于遗传操作直接作用于所表示的串上，因而不同的表示方法对SGA的效率和结果都会有影响。从原理上讲，任何取值为整数（或其它有限可枚举的值）的变量，均可用有限长度的0、1串来表示，而任何取值为连续实数的变量也均可用有限长度的0、1串来近似表示。因此，对任何一个变量，均可在一定程度上用0、1串来表示（编码），而当问题的解涉及多个变量时，则可用各变量对应串的拼接（形成一个长串）来表示相应解。 　　SGA处理的起始点并非一个个体，而是由一组个体所组成的群体。一般可用随机方法来产生初始群体，当然最好能考虑各个体的代表性和分布概率。

kenan88 发表于 2006-5-1 21:39:30

2. 群体的评价
　　对群体中各个体的适应性评价常需直接利用待优化问题的目标函数。这一目标函数也可称为适应函数，个体选择（或再生）过程正是基于这一函数来评价当前群体中各个体的再生概率。

kenan88 发表于 2006-5-1 22:02:57

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采用称为旋转盘（roulettewheel）的方法来产生各个体的再生数。方法是： 　　每一个体均对应于旋转盘中的一个以园点为中心的扇形区域，区域角度为2π*fi/∑fi，因而，各个体的区域角度之和等于2π。然后随机产生一个0到2π的值，根据该值所对应的区域，再生一个对应个体，直到产生的个体个数达到所需的数目，从而生成下一代的原始群体。这个群体还需进一步应用交换和突变操作。

kenan88 发表于 2006-5-1 22:37:45

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的位，只有通过突变。

kenan88 发表于 2006-5-1 22:43:05

遗传算法进化循环的一个例子 设每一串的长度为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的灵活性。 　　尽管遗传算法在实际优化问题中取得了很好的效果,目前对该算法尚无一个清楚完整的理论解释。霍勒德的图式理论(schematheory)和戈尔伯格（Goldberg，1989）的积木块假设仅在一定程度上解释了GA的工作原理。

343381794 发表于 2006-5-4 19:17:48

这个可以用在评分原则上么

徐耀辉 发表于 2006-5-12 08:37:24

页: [1]

数模论坛's Archiver

遗传算法