遗传算法简单实例-文档资料

1、1遗传算法(GA)的肇始“ 活的有机体是解决问题的专家。它们所表现出来的各种才能足以使最好的计算机程序自惭形秽。这种现象尤其令计算机科学家们感到痛楚。计算机科学家们为了某种算法可能花费数月乃至数年的脑力劳动，而有机体则能通过进化和自然选择这样一种显然并非定向进行的机制获得这种能力。” - John Holland2遗传算法的思想 Darwin的进化论 - “自然选择、适者生存” 特定环境的考验 种群中个体的选择选择 种群中的交叉交叉繁殖 种群中个体的变异变异 上述操作反复执行，个体逐渐优化3 为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各为更好地理解遗传算法的运算过程，

2、下面用手工计算来简单地模拟遗传算法的各 个主要执行步骤。个主要执行步骤。 例：求下述二元函数的最大值：例：求下述二元函数的最大值： max f(x1,x2)=x12+x22 s.t. x1 1,2,3,4,5,6,7 x2 1,2,3,4,5,6,7 遗传算法的运算对象是表示个体的符号串，所以必须把变量遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种编码为一种 符号串。符号串。本题中，用无符号二进制整数来表示。本题中，用无符号二进制整数来表示。 因因 x1, x2 为为 0 7之间的整数，所以分别用之间的整数，所以分别用3位无符号二进制整数来表示，将它位无符号二进

3、制整数来表示，将它 们连接在一起所组成的们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可位无符号二进制数就形成了个体的基因型，表示一个可 行解。行解。 例如，基因型例如，基因型 X101110 所对应的表现型是：所对应的表现型是：x 5，6 。 个体的表现型个体的表现型x和基因型和基因型X之间可通过编码和解码程序相互转换。之间可通过编码和解码程序相互转换。4 遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始 群体数据。群体数据。 本例中，群体规模的大小取为本例中，群体规模的大小取为4，

4、即群体由，即群体由4个个体组成，每个个体可通过随机个个体组成，每个个体可通过随机 方法产生。方法产生。 如：如：011101，101011，011100，111001 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传 机会的大小。机会的大小。 本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接 利用目标函数值作为个体的适应度。利用目标函数值作为个体的适应度。 选择运算选择运算(或称为复制运算或称为复制运算)把当前群体中适应

5、度较高的个体按某种规则或模型把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代 群体中。群体中。 5 本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中 的数量。其具体操作过程是：的数量。其具体操作过程是： 先计算出群体中所有个体的适应度的总和先计算出群体中所有个体的适应度的总和 fi ( i=1.2,M ); 其次计算出每个个体的相对适应度的大小其次计算出每个个体的相对适应度

6、的大小 fi / fi ，它即为每个个体被遗传，它即为每个个体被遗传 到下一代群体中的概率，到下一代群体中的概率， 每个概率值组成一个区域，全部概率值之和为每个概率值组成一个区域，全部概率值之和为1； 最后再产生一个最后再产生一个0到到1之间的随机数，依据该随机数出现在上述哪一个概率区之间的随机数，依据该随机数出现在上述哪一个概率区 域内来确定各个个体被选中的次数。域内来确定各个个体被选中的次数。0124%24%17%35%1#2#3#4#个体编号个体编号初始群体初始群体p(0)适值适值占总数的百分比占总数的百分比总和总和123401110110101101110011100134342550

7、0.240.240.170.351431选择次数选择次数选择结果选择结果1102011101111001101011111001 x1 x2 3 5 5 3 3 4 7 16 交叉运算是遗传算法中交叉运算是遗传算法中产生新个体产生新个体的主要操作过程，它以某一概率相互交换某的主要操作过程，它以某一概率相互交换某 两个个体之间的部分染色体。两个个体之间的部分染色体。 本例采用单点交叉的方法，其具体操作过程是：本例采用单点交叉的方法，其具体操作过程是： 先对群体进行随机配对；先对群体进行随机配对； 其次随机设置交叉点位置；其次随机设置交叉点位置； 最后再相互交换配对染色体之间的部分基因。最后再相互

8、交换配对染色体之间的部分基因。选择结果选择结果01 110111 10011010 111110 01配对情况配对情况交叉点位置交叉点位置个体编号个体编号12341-23-41-2：23-4：4交叉结果交叉结果011001 111101101001111011 可以看出，其中新产生的个体可以看出，其中新产生的个体“111101”、“111011”的适应度较原来两个个的适应度较原来两个个体体 的适应度都要高。的适应度都要高。7 变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进 行改变，它行改变，它也是产生新个体也

9、是产生新个体的一种操作方法。的一种操作方法。 本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是： 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置， 其中的数字表示变异点设置在该基因座处；其中的数字表示变异点设置在该基因座处； 然后依照某一概率将变异点的原有基因值取反。然后依照某一概率将变异点的原有基因值取反。对群体对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体进行一轮选择、交叉、变异运算之后可得到新一代的群体p(

10、t+1)。个体编号个体编号1234交叉结果交叉结果011001 111101101001111011变异结果变异结果变异点变异点4526011101 111111111001111010子代群体子代群体p(1)011101 1111111110011110108 从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得 到了明显的改进。事实上，这里已经找到了最佳个体到了明显的改进。事实上，这里已经找到了最佳个体“111111”。 需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，需要说明的是，表中

11、有些栏的数据是随机产生的。这里为了更好地说明问题， 我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中 有可能需要一定的循环次数才能达到这个最优结果。有可能需要一定的循环次数才能达到这个最优结果。个体编号个体编号子群体子群体p(1)适值适值占总数的百分比占总数的百分比总和总和1234011101 111111111001111010349850530.140.420.210.232351 x1 x2 3 5 7 7 7 1 7 29个体编号个体编号初始群体初始群体p(0) 适值适值fi(x1,x2)占总数

12、的百分比占总数的百分比fi / f1234011101101011011100111001343425500.240.240.170.35 x1 x2 3 5 5 3 3 4 7 1 fi=143fmax=50f=35.75选择结果选择结果011101111001101011111001配对情况配对情况交叉点位置交叉点位置1-23-41-2：23-4：4交叉结果交叉结果011001 111101101001111011选择次数选择次数1102变异结果变异结果变异点变异点4526011101 111111111001111010子代群体子代群体p(1) 适值适值fi(x1,x2)占总数的百分比占

13、总数的百分比fi / f011101 111111111001111010349850530.140.420.210.23 x1 x2 3 5 7 7 7 1 7 2 fi=253fmax=98f=58.7510遗传算法的一个实例 求解方程：将方程求解问题转化为生存问题：解一定在0,10之间，将区间0,10划分成若干个小区间，设想每个小区间为一个生物个体，使下列表达式最小的个体有 最好的生存能力，该个体即为解。10010 xex)0( x|100|10 xex11遗传算法的一个实例 如何找到这个最优个体？ 可通过 Darwin 的进化论由初始个体经过代代演化，逐渐进化出来。 如何将生物进化的操

14、作转化为计算机可以执行的操作？ 通过编码表征生物个体，则生物之间的演化转化为编码的变化。12步骤一：初始化 个体编码：(假定要求小数点后两位) 将0,10划分为1024个小区间 个体 1 0000000000 个体 2 0000000001 个体 3 0000000010 个体 1024 1111111111 种群初始化： 随机生成m个10位二进制串102421001013 定义适应度函数： 选择（适应度较大的个体） 步骤二：选择|100|110 xexf为何取倒数？0.10.30.20.40.10.10.30.40.20.60.41.0ABCD随机产生0,1之间的数 RN，选择个体 RN个体

15、ABCD1 . 00 RN4 . 01 . 0 RN6 . 04 . 0 RN16 . 0 RN14 选中的优势个体进行交叉 - 由父个体生成子个体步骤三：交叉相同的两个父个体生成相同的两个子个体15 变异操作 在个体中随机选择一位，改变该位的值步骤四：变异交叉和变异操作均以一定概率进行16 反复执行步骤二、三、四并记录最优个体（适应度最大的个体） 程序结束时，最优个体即为所求解 程序结束的判定 根据循环次数 根据最大适应度 根据种群中相同个体数与总个体数的比值步骤五17遗传算法各步骤的评价 选择 - 优胜劣汰 选择操作为种群提供了演进的方向 交叉 - 优优组合 交叉操作的作用在于汇集散布于不

16、同 个体间的局部优势模式 变异 - 寻找新模式 变异操作是种群向外扩展的触角(随机) 好的变异将保留，坏的淘汰18遗传算法的总体评价 优点 解决问题的方法具有普适性 全局收敛性（依概率收敛） 能解决的问题范围很广 不足 求得的解为近似的数值解 对于经典数学可以解决的问题，效率较低19遗传算法的适应度函数求函数的全局极小值取 的初始区间，例如：-10,10将此区间分为1024个小区间，然后编码若求全局极大值(且为正)，可直接取函数值为其适应度值，据此作概率选择；若求全局极小值(且为正)，可取函数值的倒数为其适应度值，据此作概率选择。若不全为负，可统一加上一个正数，使为正。)(41)(10sin(

17、)80sin(sin()sin(70sin()60sin()50exp(sin(22yxyxyxexyyx,20TSP问题的遗传算法求解 步骤一：个体编码及种群初始化 步骤二：适应度选择 步骤三：交叉操作 步骤四：变异操作 步骤五：重复二、三、四步，直至结束 令城市(点)数目为 N21 个体编码 取长度为N的数字串，串中数字互不重复，取值范围为1,N之间的整数。则每一个数字串代表一个个体，个体中数字出现的位置表征路径中城市出现的顺序。 初始种群 令种群中有 M 个个体，可随机产生 M 个数字 串构成初始种群。例如： 将数字串 1234N 上的数字进行随机的交换步骤一：初始化22 适应度的计算步

18、骤二：适应度选择123451l2l3l4l5lNiijlf11对于个体 ，适应度为：j被选中作为父个体的概率：Mjjjjffp11jp选择选择 M 次次重新生成种群重新生成种群23 TSP中交叉算子的特点 要保证生成的解为有效解 从一个父个体中随机选取一段子串A，在另一个父个体中将A中出现的数字去掉形成串B，AB为一个子串步骤三：交叉操作此外还有多种交叉算子24 常用的变异操作： 随机选取两个相邻位置的数字，交换其顺序。 51243(5) 51234(5)步骤四：变异操作1234512345交换3,4此外还有多种变异算子25 反复执行步骤二、三、四 结束判定 循环执行 G 次 (例如 G=50

19、0) 后 当最优个体的总路径长度小于预期时步骤五：26中国各省会城市的运行结果2712345 缺陷：相同父个体生成不同的子个体 以下是相同个体： 12345(1) 54321(5) 反射操作 12345(1) 34512(3) 旋转操作交叉算子的进一步研究用群论描述 所有路径的集合形成一个二面体群 A 等价解构成一个正规子群 B A 中陪集的数目为 2N2812345(1) 32154(3) 相同父个体交叉34215(3) 15234(1) 不同子个体，且和父个体不同12345123451234529 简单实例简单实例产生初始种群产生初始种群1.计算适应度计算适应度 0001100000 01

20、01111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8） （5） （2） （10） （7）（12） （5） （19） （10） （14）30 简单实例简单实例选择选择 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率100011000008201011110015300000001012410011101001051010101010761110010110127100101101158110000000119910011101001010

21、00010100111488521071251910140.08695758521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.15217431 简单实例简单实例选择选择 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.

22、0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.00000032 简单实例简单实例选择选择在在01之间产生一个之间产生一个3.随机数：随机数： 个体个体染色体染色体适应度适应度选择概率选择概率累积概率累积概率10001100000820101111001530000000101241001110100105101010101076111001

23、01101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰

24、！淘汰！淘汰！淘汰！330001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011 简单实例简单实例4.交叉交叉 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 000101001100011110100000010110111100001011010110111100001001110100

25、0001100111010011000000011010101000101001001134 简单实例简单实例5.变异变异 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 000101001100011110100000010110111100001011010110111100001001010100000110011101001100000001101010100010100100110001100000 1110010110 11000000

26、01 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011000111101000000101101111000010110101101111000010011101000001100111010011000000011010101000101001001135 问题的提出问题的提出 一元函数求最大值：一元函数求最大值： 2 , 1 0 . 2)10sin()(xxxxf36 问题的提出问题的提出 用微分法求取用微分法求取f(x)的最大值：的最大值： 解有无穷多个：解有无穷多个： xxxxxxf1

27、0)10tan( 0)10cos(10)10sin()( 即的实数递减序列。一接近于是及，0), 2, 1, 2 , 1( , 2, 1 ,2012 0 , 2 , 1 ,20120iiiixxiixiiiii37 问题的提出问题的提出 当当i为奇数时为奇数时xi对应局部极大值点，对应局部极大值点，i为偶数时为偶数时xi对应对应局部极小值。局部极小值。x19即为区间即为区间-1,2内的最大值点：内的最大值点： 此时，函数最大值此时，函数最大值f(x19)比比f(1.85)=3.85稍大。稍大。 19191985. 12037x38 编码编码 表现型：表现型：x 基因型：二进制编码（串长取决于求解精度）基因型：二进制编码（串长取决于求解精度） 串长与精度之间的关系串长与精度之间的关系： 若要求求解精度到若要求求解精度到6位小数，区间长度为位小数，区间长度为2-(-1)3，即需将区间分为即需将区间分为3/0.000001=3106等份。等份。 所以编码的二进制串长应为所以编码的二进制串长应为22位。位。 41943042300000022097152222139 产生初始种群产生初始种群 产生的方式：随机产生的方式：随机 产生的结果：长度为产生的结果：长度为22的二进制串的二进制串