浅谈遗传算法

浅谈遗传算法姓名：杨金霄学号：14721487指导老师：张宪霞1、算法作用主要内容2、基本概念3、组成部分4、简单案例1、算法作用问：遗传算法是用来干啥的？答：遗传算法的目的，是寻找最优解，比如求函数的最大值，优化问题都可以用遗传算法。寻找最优解2、基本概念遗传算法(GeneticAlgorithms,GA)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法的概念最早是由BagleyJ.D于1967年提出的。遗传算法是对达尔文生物进化理论的简单模拟，其遵循“适者生存”、“优胜劣汰”的原理。遗传算法模拟一个人工种群的进化过程，并且通过选择、杂交以及变异等机制，种群经过若干代以后，总是达到最优（或近最优）的状态，即满足某种收敛条件。3、组成部分1、编码（解码）2、适应度函数3、遗传算子（选择、交叉、变异）4、运行参数问1：啥叫编码？答：遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码。参数个体解空间编码空间编码解码3.1编码（解码）答：由于遗传算法不能直接处理问题空间的数据，所以我们必须将问题空间的数据映射成遗传空间的基因型串结构数据。而且通过编码建立初始种群，是遗传算法运行的前提。问2：为啥要编码？12031032（基因型串结构数据）广东北京新疆上海举例编码解码（1）二进制编码(最常用)基本遗传算法使用固定长度的二进制符号来表示群体中的个体（对应实际问题的解），如：x1=1000110100010101基因串（2）互换编码如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。3.1.1常见的编码方式：（3）值编码在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。3.2适应度函数问1：啥叫适应度？答：进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。问2：啥叫适应度函数？答：遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。总而言之，适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。3.3遗传算子（操作）选择交叉变异选择问1：啥叫选择？答：选择操作是把当前群体中适应度较高的个体按某种规则遗传到下一代群体中。问2：为啥要选择？答：选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。最简单也是最常用的选择方法。基本思想：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，其中个体i的适应度为fi，则i被选择的概率pi为：轮盘赌选择法图例个体适应度越大，其被选择的概率就越高。轮盘赌交叉问1：啥叫交叉？答：交叉是指把两个父代个体依据交叉概率按某种方式相互交换其部分结构而生成新个体的操作。问2：为啥要交叉？答：GA中的交叉运算是产生新个体的主要方法，它决定了GA的全局搜索能力，同时保持种群的多样性。交叉运算在遗传算法中起关键作用，是产生新个体的主要方法。1、单交叉点法（最常用）选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。0000|0111000000001100|000001111110父代子代0000|0000011111101100|011100000000常用的交叉方法：图解2、双交叉点法选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因。0001|0010|11001011|0111|0101父代子代0111|0010|01101101|0111|11003、基于“与/或”交叉法选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因。0001001010110111父代子代0001001010110111变异问1：啥叫变异？答：变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。问2：为啥要变异？答：GA中的变异运算是产生新个体的辅助方法，它决定了GA的局部搜索能力，同时保持种群的多样性。基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。011100000000变异前基本位变异变异后0111000100003.4运行参数交叉率变异率种群规模终止进化代数说明：GA运行时选择的参数应该视解决的具体问题而定，到目前为止，还没有一个适用于GA所有应用领域的关于算法参数的理论。下面给出一些推荐的常用的参数。交叉率推荐使用80％-95％。变异率推荐使用0.5％-1％。种群规模推荐使用0-30。终止进化代数当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。附算法流程随机产生初始群体计算个体适应度产生新一代群体是否满足停止准则？轮盘赌选择交叉运算变异运算否是输出结果并结束4、简单案例求下列二元函数的最大值：X1={1,2,3,4,5,6,7}X2={1,2,3,4,5,6,7}（1）编码分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个解。例如，基因型X＝101110所对应的表现型是：x＝[5，6]（2）初始群体的产生遗传算法是对群体进行的进化操作，需要给其准备一些表示起始搜索点的初始群体数据。本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。如：011101，101011，011100，111001p(0)(3)适应度汁算遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度。(4)选择运算本例中，我们采用轮盘赌选择法来确定各个个体复制到下一代群体中的数量。01123424%24%17%35%个体编号初始群体p(0)X1X2适配值占总数的百分比选择次数123401110110101101110011100135533471343425500.240.240.170.351102总和1431选择结果011101111011101011111001(5)交叉运算本例采用单点交叉的方法，其具体操作过程是：•先对群体进行随机配对；•其次随机设置交叉点位置；•最后再相互交换配对染色体之间的部分基因。个体编号选择结果配对情况交叉点位置交叉结果12340111011110011010111110011--23--40110011111011010011110111--2：23--4：4(6)变异运算本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：•首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，其中的数字表示变异点设置在该基因座处；•然后依照某一概率将变异点的原有基因值取反。个体编号交叉结果变异点位置变异结果（子代群体P（1））12340110011111011010011110110111011111111110011110104526对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体P(t+1)。个体编号子代群体p(1)X1X2适配值占总数的百分比123401110111111111100111101035777172349850530.140.420.210.23总和2351从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体“111111”。