《算法合集之《遗传算法的特点及其应用》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《遗传算法的特点及其应用》.ppt（21页珍藏版）》请在金锄头文库上搜索。
1、遗遗传传算算法法的的特特点点及及其其应应用用 省、市：省、市：上海市上海市学学校：校：复旦附中复旦附中姓姓名：名：张张宁宁 IOI2002集训队集训队论文论文目目 录录 |遗传算法的基本概念遗传算法的基本概念|简单的遗传算法简单的遗传算法选择、交换、变异选择、交换、变异|遗传算法应用举例遗传算法应用举例子集和问题子集和问题TSP(旅行商旅行商)问题问题|结束语结束语遗遗传传算算法法的的基基本本概概念念|遗遗传传算算法法（Genetic Algorithms，简简称称GA）根根据据适适者者生生存存，优优胜胜劣劣汰汰等等自自然然进进化规则来进行搜索计算和问题求解。化规则来进行搜索计算和问题求解。
2、对许多用传统数学难以解决或明显失效的对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，复杂问题，特别是优化问题，GA提供了提供了一个行之有效的新途径。一个行之有效的新途径。简简单单的的遗遗传传算算法法|GAGA把把每每一一个个可可能能的的解解编编码码为为一一个个向向量量，称称为为一一个个染染色色体体，向向量量的的每每一一个个元元素素称称为为基基因因。所所有有染染色色体体组组成成群群体体。并并按按预预定定的的目目标标函函数数对对每每个个染染色色提提进进行行评评价价，根根据据其其结结果果给给出出一一个适应度的值。个适应度的值。|算算法法开开始始时时先先随随机机地地产产生生一一些些染染色
3、色体体，计计算算其其适适应应度度，根根据据适适应应度度对对诸诸染染色色体体进进行行选选择择、交交换换、变变异异等等遗遗传传操操作作，剔剔除除适适应应度度低低的的染染色体，留下适应度高的染色体。色体，留下适应度高的染色体。|由于新群体的成员是上一代群体的优秀者，由于新群体的成员是上一代群体的优秀者，因而在总体上优于上一代。因而在总体上优于上一代。GAGA就这样反复迭就这样反复迭代，直至满足某种预定的优化指标。上述代，直至满足某种预定的优化指标。上述GAGA的工作过程可用的工作过程可用图图1 1简要描述。简要描述。 选选 择择 选选择择运运算算使使用用比比较较普普遍遍的的一一种种是是适适应应度度比
4、比例例法法。其其实实就就是是将将适适应应度度值值视视为为其其权权值值，权权值值大大的的被被选选中中的的概概率率也也大大。它它与与各各染染色色体体适适应应度度成成比比例例。某一染色体被选中的概率为某一染色体被选中的概率为 式式中中x xi i为为种种群群中中第第i i个个染染色色体体对对应应的的数数字字串串，f f( (x xi i) )是是第第i i个个染染色色体体的的适适应应度度值值， 是是种种群群中中所所有有染染色色体体的的适适应应度度值值之之和和。显显然然，此此法法要求染色体的适应度应为正值。要求染色体的适应度应为正值。 交交 换换 复制操作虽然能够从旧种群中选择出优秀复制操作虽然能够从
5、旧种群中选择出优秀者，但不能创造新的染色体，因此，遗传者，但不能创造新的染色体，因此，遗传算法的开创者提出了交换操作。即：在匹算法的开创者提出了交换操作。即：在匹配集中任选两个染色体，随机选择一点或配集中任选两个染色体，随机选择一点或多点交换点位置，交换双亲染色体交换点多点交换点位置，交换双亲染色体交换点右边的部分，即可得到两个新的染色体数右边的部分，即可得到两个新的染色体数字串。字串。变变 异异 变异运算用来模拟生物在自然界的遗传变异运算用来模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变，环境中由于各种偶然因素引起的基因突变，它以很小概率随机地改变遗传基因的值。它以很小概率随机地
6、改变遗传基因的值。在染色体以二进制编码的系统中，它随机在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由地将染色体的某一个基因由1 1变成变成0 0，或由，或由0 0变成变成1 1。通过变异操作，可以使搜索能在。通过变异操作，可以使搜索能在尽可能大的空间中进行，获得质量较高的尽可能大的空间中进行，获得质量较高的优化解答。优化解答。 遗遗传传算算法法应应用用举举例例|子集和问题子集和问题|TSP(旅行商旅行商)问题问题子子集集和和问问题题GAGA在子集和问题上的应用在子集和问题上的应用|子子集集和和问问题题SUBSET_SUMSUBSET_SUM：给给定定正正整整数数集集合合S S和和
7、一一个个整整数数t t，判判定定是是否否存存在在S S的的一一个个子子集使得集使得S S中整数的和为中整数的和为t t。|我我们们已已知知道道该该问问题题是是一一个个NP-NP-完完全全问问题题。在在实实际际应应用用中中，我我们们常常遇遇到到的的是是最最优优化化子子集集和和问问题题。在在这这种种情情况况下下，我我们们要要找找出出S S的的一一个个子子集集S S，使使得得其其和和不不超超过过t t，但但又又尽可能接近于尽可能接近于t t。子子集集和和问问题题|下面用遗传算法来解决：下面用遗传算法来解决：|我我们们可可以以用用n n位位二二进进制制数数来来表表示示每每个个染染色色体体。每每一一位位
8、，用用0 0、1 1表示是否属于子集表示是否属于子集。 我我们们将将染染色色体体所所表表示示的的子子集集的的元元素素和和与与所所给给t t的的差差异异记记为为适适应应度度，即即令令染染色色体体x x的的每每一一位位为为x xi i，所所表表示示元元素的值为素的值为S Si i则则 但但是是经经过过实实践践后后发发现现由由于于适适应应度度相相对对差差异异较较小小，使使得得适适应应度度非非常常接接近近，难难以以区区分分染染色色体体的的优优劣劣，使使得得遗遗传传进进化化变变得得非非常常缓缓慢慢，且且f(x)f(x)可可能能为为负负值值，因因此此还还需需对对适适应应度度函函数数做做一一下下变变换换，才
9、才可可以以适适合合本本题题的的要求。要求。 令令f(k)f(k)为当前群体中所有染色体适应度的最大值为当前群体中所有染色体适应度的最大值 f f(x)=|f(k)-f(x)|(x)=|f(k)-f(x)| 所以适应度为所以适应度为f f (x)(x)。 子子集集和和问问题题|选选择择时时可可以以用用前前面面所所介介绍绍的的适适应应度度比比例例法法，但但可可能能会会因因为为偶偶然然情情况况使使得得优优秀秀的的染染色色体体没没有有子子孙孙。因因此此，我我在在这这里里采采用用确确定定性性选选择择法法，先先计计算算群群体体中中每每个个串串的的生生存存概概率率 ，1=1=j=nj=n，然然后后计计算算期
10、期望望复复制制数数e ei i=P=Ps s*n*n，式式中中：n n为为群群体体中中染染色色体体的的数数目目。根据根据e ei i的值给每个染色体串分配一个复制数的值给每个染色体串分配一个复制数。|交交换换运运算算与与前前述述相相同同，不不过过若若进进行行单单点点交交换换有有可可能能使使得得两两个个染染色色体体在在交交换换时时产产生生的的差差异异过过大大，使使得得遗遗传传变变得得不不稳稳定定，优优秀秀的的染染色色体体不不能能遗遗传传到到下下一一代代。因此可以采用因此可以采用多点交换多点交换。|变变异异运运算算时时，只只需需注注意意变变异异概概率率的的取取值值，至至于于具具体体算法如前面所述。
11、算法如前面所述。子子集集和和问问题题|在本题中的一些数值不妨取值如下：在本题中的一些数值不妨取值如下：|种群长度（染色体个数）：种群长度（染色体个数）：2020|选择概率：选择概率：0.90.9|变异概率：变异概率：0.10.1|结结束束条条件件：当当前前最最优优解解在在100100代代遗遗传传后后仍仍未改变，或已取到最优解未改变，或已取到最优解TSP(旅旅行行商商)问问题题GA在在TSP（旅行商）问题求解中的应用旅行商）问题求解中的应用|设设存存在在N个个城城市市，Dij表表示示城城i与与城城j之之间间的的距距离离，Dij=Dji，现现在在要要求求一一条条遍遍历历所所有有N个个城城市市，且且
12、不不走重复路的最短路径（最短哈密尔顿圈）。走重复路的最短路径（最短哈密尔顿圈）。|这这是是一一个个典典型型NP-完完全全问问题题。传传统统解解法法对对此此都都并并不不太太奏奏效效下下面面我我们们试试着着用用遗遗传传算算法法来来解解决决这这道道题目。题目。TSP(旅旅行行商商)问问题题|我我们们先先采采用用十十进进制制编编码码，每每个个染染色色体体由由按按一一定定顺顺序序排排列列的的N N个个城城市市的的序序号号组组成成，表表示示一一条条可可能能的的旅旅行行路路径径。适适应应度度为为一一条条旅旅行行路路径径对对应应的的距距离离，路路径径越越短短的的染染色色体体适适应应度越高。例如，取度越高。例如
13、，取N=10N=10，城市代号为城市代号为1 1至至1010。 例如例如种群中的染色体：种群中的染色体：2 8 4 10 5 1 7 3 6 92 8 4 10 5 1 7 3 6 9 表表 示示 一一 条条 旅旅 行行 路路 径径 2 28 84 410105 51 17 73 36 69 92 2 其总路径长其总路径长 我我们们可可以以采采用用非非负负变变换换，把把最最小小化化优优化化目目标标函函数数变变换换为为以最大值为目标的适应度函数，可以如下定义：以最大值为目标的适应度函数，可以如下定义： 其其中中c cmaxmax为为可可以以取取为为进进化化过过程程中中路路径径长长度度的的最最大大
14、值值，或或者者为了保证为了保证f(x)f(x)为正而预先设定为一个与种群无关的常数。为正而预先设定为一个与种群无关的常数。TSP(旅旅行行商商)问问题题|关于选择运算，关于选择运算，可以考虑可以考虑前面介绍的确定性前面介绍的确定性选择法。选择法。|此此处处的的交交换换运运算算不不同同于于前前，因因为为两两个个染染色色体体，若若进进行行简简单单的的交交换换运运算算，可可能能会会使使得得染染色色体体所所表表示示路路径径中中会会重重复复经经过过同同一一城城市市，即即同同一一染染色色体体中中的的两两个个基基因因有有着着相相同同的的城城市市编编号号。因因此此须须改改进进交交换换运运算算。我我们们可可以以
15、采采用用部部分分匹匹配交换运算（配交换运算（PMXPMX）。 当当然然也也可可以以不不进进行行交交换换运运算算，而而直直接接进进行行变变异异运运算算，因为因为本例中的本例中的变异运算本就隐含了交换的含义。变异运算本就隐含了交换的含义。|变变异异操操作作与与二二进进制制编编码码时时不不同同，从从群群体体中中随随机机抽抽取取一一个个染染色色体体，随随机机抽抽取取两两个个基基因因，将将两两者者交交换换，即即颠颠倒倒城城市市次序。次序。|算算法法的的主主要要部部分分已已经经讨讨论论完完了了，但但是是还还有有一一点点值值得得提提出出的的，由由于于遗遗传传算算法法是是一一种种不不断断优优化化的的搜搜索索算
16、算法法，因因此此，我们可以用贪心算法构造初始群。我们可以用贪心算法构造初始群。 TSP(旅旅行行商商)问问题题|题目中的一些数值不妨取值如下：题目中的一些数值不妨取值如下：|种群长度（染色体个数）：种群长度（染色体个数）：2020|变异概率：变异概率：0.10.1|结结束束条条件件：当当前前最最优优解解在在100100代代遗遗传传后后仍仍未未改改变。变。遗遗传传算算法法应应用用举举例例|通通过过两两道道例例题题，我我们们在在遗遗传传算算法法原原有有简简单单定定义义上上，加加以以扩扩充充，介介绍绍了了若若干干高高级级遗遗传传算算法法在在具具体体实实例例中中的的应应用用，旨旨在在打打开开思思想想的
17、的局局限限性性，不不仅仅仅仅在在原原有有简简单单定定义义下下做做文文章章，而而是是充充分分发发挥挥想想象象，对对于于不不同同问问题题，采采取取不不同同对对策策，在在遗遗传传算算法法的的框框架架下下，安安排排使使用用合合理理的的算算法法，改改进进原原有有算算法法，或或与与原原有有算算法法相相结结合合。这这样样，才才能能充充分发挥遗传算法的长处解决问题。分发挥遗传算法的长处解决问题。 结结束束语语|遗遗传传算算法法的的原原理理是是简简单单的的，但但是是如如何何熟熟练练运运用用遗遗传传算算法法却却并并不不是是一一个个简简单单的的问问题题，理理论论要要切切合合实实际际，对对于于不不同同问问题题，遗遗传
18、传算算法法要要稍稍加加变变化化，就就如如同同画画龙龙点点睛睛一一般般，切切忌忌不不可可生生搬搬硬硬套套。我我认认为为遗遗传传算算法法应应当当与与现现有有优优化化算算法法结结合合，可可产产生生比比单单独独使使用用遗遗传传算算法法或或现现有有优优化化算算法法更更好好，更实用的算法。更实用的算法。|本本文文的的主主要要目目的的还还是是让让大大家家对对遗遗传传算算法法能能够够有有一一个个初初步步的的了了解解，这这样样对对大大家家进进行行深深入入的的实实践践是是有有帮帮助助的的。希希望望大大家家通通过过本本文文的的指指导导，能能够够将遗传算法熟练应用在各个方面。将遗传算法熟练应用在各个方面。 图 一 Y
19、问题的初始（侯选）解种群满足预定指标编码为染色体（向量）种群P（t）计算各染色体适应度通过遗传运算存优去劣种群P（t+1）复制交换变异种群P（t）种群P（t+1）解码染色体问题解答空间N图1 遗传算法工作原理示意图多多点点交交换换|不不过过在在本本例例中中使使用用多多点点交交换换，只只需需进进行行两两点点交交换换即即可可，其实两点交换与单点交换是类似的。其实两点交换与单点交换是类似的。|设有两个父辈染色体设有两个父辈染色体A A和和B B： A A：1010010010111010100100101110 B B：0100111011000101001110110001 设两个交换点选择如下：
20、设两个交换点选择如下： A A：10100|10010|111010100|10010|1110 B B：01001|11011|000101001|11011|0001 则则两两点点交交换换运运算算就就是是交交换换染染色色体体A A和和染染色色体体B B，两两个个交交换点之间的部分，则交换结果如下：换点之间的部分，则交换结果如下： A A：1010011011111010100110111110 B B：0100110010000101001100100001部部分分匹匹配配交交换换运运算算|部部分分匹匹配配交交换换运运算算先先在在两两父父染染色色体体串串中中各各产产生生两两个个交交换换点点
21、，把把这这两两点点之之间间的的区区域域定定义义为为匹匹配配区区域域，再再对对两两个个匹匹配配区区域域中中的的基基因因通通过过对对应应匹匹配配置置换换。例如，两父染色体串为：例如，两父染色体串为： A A： 2 8 4 10 * 5 1 7 3 * 6 9 2 8 4 10 * 5 1 7 3 * 6 9 B B： 5 6 7 1 * 10 2 8 3 * 9 4 5 6 7 1 * 10 2 8 3 * 9 4 符号符号“* *”表示交换点。表示交换点。 以以染染色色体体A A为为例例，其其匹匹配配区区域域中中有有四四个个元元素素5 5，1 1，7 7，3 3，与与染染色色体体串串B B中中的的四四个个元元素素1010，2 2，8 8，3 3，逐逐一一匹匹配配，即即通通过过在在染染色色体体串串A A内内进进行行元元素素间间的的置置换换，使使得得匹匹配配区区域域内内这这四四个个元元素素换换为为1010，2 2，8 8，3 3。为为此此，染染色色体体串串A A中中的的元元素素。作作如如下下置置换换：A： 2 8 4 10 * 5 1 7 3 * 6 9A： 1 7 4 5 * 10 2 8 3 * 6 9
