浅谈遗传算法.pptxVIP

浅谈遗传算法 姓名：杨金霄 学号导老师：张宪霞主要内容1、算法作用2、基本概念3、组成部分4、简单案例1、算法作用问：遗传算法是用来干啥的？答：遗传算法的目的，是寻找最优解 ，比如求函数的最大值，优化问题都可以用遗传算法。寻找最优解2、基本概念遗传算法(Genetic Algorithms, GA)是一类借鉴生物界自然选择和自然遗传机制的随机化有哪些信誉好的足球投注网站算法。遗传算法的概念最早是由Bagley J.D 于1967年提出的。遗传算法是对达尔文生物进化理论的简单模拟，其遵循“适者生存”、“优胜劣汰”的原理。遗传算法模拟一个人工种群的进化过程，并且通过选择、杂交以及变异等机制，种群经过若干代以后，总是达到最优（或近最优）的状态，即满足某种收敛条件。3、组成部分1、编码（解码）2、适应度函数3、遗传算子（选择、交叉、变异）4、运行参数 3.1 编码（解码）问1：啥叫编码？答：遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码。解码参数个体编码解空间编码空间问2：为啥要编码？答：由于遗传算法不能直接处理问题空间的数据，所以我们必须将问题空间的数据映射成遗传空间的基因型串结构数据。而且 通过编码建立初始种群，是遗传算法运行的前提。举例3021032（基因型串结构数据）广东北京新疆上海编码解码13.1.1常见的编码方式： （1）二进制编码(最常用) 基本遗传算法使用固定长度的二进制符号来表示群体中的个体（对应实际问题的解），如： x1=1000 1101 0001 0101基因串 （2）?互换编码 如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。 （3）值编码 在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。 3.2 适应度函数问1：啥叫适应度？答：进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。问2：啥叫适应度函数？答：遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。 总而言之，适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。 3.3 遗传算子（操作）选择交叉变异选择问1：啥叫选择？答： ?选择操作是把当前群体中适应度较高的个体按某种规则遗传到下一代群体中。问2：为啥要选择？答：选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。轮盘赌选择法 最简单也是最常用的选择方法。基本思想：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，其中个体 i的适应度为f i，则i 被选择的概率 pi为： 图例轮盘赌个体适应度越大，其被选择的概率就越高。交叉问1：啥叫交叉？答：交叉是指把两个父代个体依据交叉概率按某种方式相互交换其部分结构而生成新个体的操作。问2：为啥要交叉？答： GA中的交叉运算是产生新个体的主要方法，它决定了GA的全局有哪些信誉好的足球投注网站能力，同时保持种群的多样性。交叉运算在遗传算法中起关键作用，是产生新个体的主要方法。常用的交叉方法： 1、单交叉点法（最常用）选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。0000 | 0111 0000 | 0000 0111 1110父代0000 | 0000 0111 | 0111 0000 0000子代图解 2、双交叉点法选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因。0001 | 0010 || 0111 | | 0010 || 0111 | 1100父代子代3、基于“ 与/或 ”交叉法选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因。00010111 父代0001 0111子代变异问1：啥叫变异？答：变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。问2：为啥要变异？答： GA中的变异运算是产生新个体的辅助方法，它决定了GA的局部有哪些信誉好的足球投注网站能力，同时保持种群的多样性。基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变