人工智能---遗传算法37

第4章遗传算法4.1基本概念4.2选择算子4.3交叉算子4.4变异算子4.5基本遗传算法4.6基本实现技术4.7遗传算法应用第4章遗传算法生物进化自然法则优胜劣汰适者生存有性繁殖基因通过有性繁殖不断进行混合和重组遗传算法从生物界按照自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计的一种优化搜索算法第4章遗传算法应用函数优化组合优化：旅行商、图形化分…生产调度：车间调度、生产规划…自动控制：控制器、参数辨识…机器人智能控制：机器人路径规划、运动轨迹规划…图像处理与模式识别：特征提取、图像分割…人工生命：进化模型、学习模型、行为模型…遗传程序设计机器学习4.1基本概念个体个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼一个个体也就是搜索空间中的一个点种群种群(population)就是模拟生物种群而由若干个体组成的群体它一般是整个搜索空间的一个很小的子集通过对种群实施遗传操作，使其不断更新换代而实现对整个论域空间的搜索4.1基本概念适应度(fitness)借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度适应度函数(fitnessfunction)问题中的全体个体与其适应度之间的一个对应关系一般是一个实值函数该函数就是遗传算法中指导搜索的评价函数4.1基本概念染色体(chromosome)染色体是由若干基因组成的位串（生物学）个体对象由若干字符串组成来表示（遗传算法）遗传算法(geneticalgorithm)染色体就是问题中个体的某种字符串形式的编码表示染色体以字符串来表示基因是字符串中的一个个字符个体染色体9----1001（2，5，6）----0101011104.1基本概念遗传算子(geneticoperator)选择(selection)交叉(crossover)变异(mutation)4.2选择算子选择算子模拟生物界优胜劣汰的自然选择法则的一种染色体运算从种群中选择适应度较高的染色体进行复制，以生成下一代种群算法：个体适应度计算在被选集中每个个体具有一个选择概率选择概率取决于种群中个体的适应度及其分布个体适应度计算，即个体选择概率计算个体选择方法按照适应度进行父代个体的选择4.2选择算子个体适应度计算按比例的适应度计算(proportionalfitnessassignment)基于排序的适应度计算(rank-basedfitnessassignment)个体选择方法轮盘赌选择(roulettewheelselection)随机遍历抽样(stochasticuniversalsampling)局部选择(localselection)截断选择(truncationselection)锦标赛选择(tournamentselection)4.2.1按比例的适应度计算算法：对一个规模为N的种群S，按每个染色体xiS的选择概率P(xi)所决定的选中机会，分N次从S中随机选择N个染色体，并进行复制其中：f为适应度函数f(xi)为xi的适应度1()()()iiNjjfxPxfx优胜劣汰1.概率越高，随机选中概率越大2.概率越高，选中次数越多3.适应度高的染色体后代越多4.2.3轮盘赌选择原理：做一个单位圆，然后按各个染色体的选择概率将圆面划分为相应的扇形区域转动轮盘，轮盘静止时指针指向某一扇区，即为选中扇区，相应的个体/染色体即被选中4.2.3轮盘赌选择算法：在[0,1]区间，产生一个均匀分布的伪随机数r若rq1，则染色体1被选中若qk-1rqk(2kN)，则染色体k被选中其中qi为染色体xi(i=1,2,…,n)的累积概率一个染色体xi被选中的次数，可由期望值e(xi)来确定为种群S中全体染色体的平均适应度1()iiijqPx11()()()()()()()/iiiiiNNiijjexPxNfxfxfxNffxfxNf4.3交叉算子交叉算子交换、交配、杂交互换两个染色体某些位上的基因随机化算子，生成新个体4.3交叉算子一点杂交产生一个在1到L－1之间的随机数I配对的两个串相互对应的交换从i＋1到L的位段4.3交叉算子例3.1设染色体s1=1011011100染色体s2=0001110011交换其后2位基因s1:1011011100s1’：1011011111s2：0001110011s2’：0001110000单点交叉4.4变异算子变异算子突变改变染色体某个/些位上的基因随机化算子，生成新个体次要算子，但在恢复群体中失去的多样性方面具有潜在的作用4.4变异算子例4.1设染色体s=1011011100s1:1011011100s1’：1011011000二进制变异4.5基本遗传算法遗传算法对种群中的染色体反复做三种遗传操作使其朝着适应度增高的方向不断更新换代，直至出现了适应度满足目标条件的染色体为止算法拓展遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用基本遗传算法是Holland提出的一种统一的最基本的遗传算法，简称SGA（SimpleGeneticAlgorithm)、CGA（CanonicalGeneticAlgorithm）其它的“GA类”算法称为GAs(GeneticAlgorithms）,可以把GA看作是GAs的一种特例4.5基本遗传算法参数种群规模种群的大小，用染色体个数表示最大换代数种群更新换代的上限，也是算法终止一个条件交叉率Pc参加交叉运算的染色体个数占全体染色体总数的比例取值范围：0.4-0.99变异率Pm发生变异的基因位数占全体染色体的基因总位数的比例取值范围：0.0001-0.1染色体编码长度L4.5基本遗传算法算法步1：在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc，变异率Pm，代数Gen步2：随机产生U中的N个染色体s1,s2…sN,组成初始种群S={s1,s2…sN}，置代数t=1步3：若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束步4：计算S中每个染色体的适应度f()步5：按选择概率p(si)所决定的选中机会，每次从S中随机选中1个染色体并将其复制，共做N次，然后将复制得到的N染色体组成群体S1步6：按Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的染色体代替原染色体，组成群体S2步7：按Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，组成群体S3步8：将群体S3作为新种群，即用S3代替S，Gen=Gen+1，转步34.5流程图开始Gen=0编码随机产生N个初始个体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子j=0j=0j=0根据适应度选择复制个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制将复制的个体添入新群体中将交叉后的两个新个体添入新群体中将变异后的个体添入新群体中j=j+1j=j+2j=j+1j=N?j=c?j=m?Gen=Gen+1输出结果终止YNYYYNNNpcpm4.6基本实现技术编码方法二进制编码格雷编码编码规则应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案4.6基本实现技术适应值函数适应值函数必须是正数出现负数时应进行变换，常用变换方式有三种：线性比例法：g(x)=a*f(x)+b(b0)指数比例法：g(x)=exp(af(x))(a0)幂指数比例法：g(x)=(f(x))a(a为偶数)4.7算法举例例7.1利用遗传算法求解区间[0,31]上的二次函数y=x2的最大值分析原问题转化为[0,31]中寻找能使y取最大值的点x区间[0,31]为论域空间/解空间x为个体对象函数f(x)=x2可作为适应度函数4.7算法举例解：定义适应度函数，编码染色体适应度函数取f(x)=x2用5位二进制数作为个体x的基因型编码/染色体设定种群规模，产生初始种群种群规模N=4初始种群S={s1=01101(13),s2=11000(24)，s3=01000(8)，s4=10011(19)}4.7算法举例计算各代种群中各染色体的适应度，并进行遗传操作选择设从区间[0,1]产生4个随机数r1=0.45,r2=0.11,r3=0.57,r4=0.98按轮盘赌选择法，染色体s1,s2，s3，s4依次选中次数为1，2，0，1选择产生种群S1={s1=11000(24),s2=01101(13)，s3=11000(24)，s4=10011(19)}染色体适应度选择概率累积概率估计选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.0014.7算法举例交叉设交叉率Pc=100%,即S1全部染色体参与交叉将s1与s2配对，s3与s4配对，交换后两位基因新种群S2={s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)}变异设变异率Pm=0.001种群变异基因位数：Pm*L*N=0.001*5*4=0.020.02不足1，本轮不做变异--------------第一代遗传操作完成----------------第二代种群S={s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)}4.7算法举例选择设从区间[0,1]产生4个随机数r1=0.25,r2=0.41,r3=0.77,r4=0.98按轮盘赌选择法，染色体s1,s2，s3，s4依次选中次数为1，1，1，1选择产生种群S1={s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)}染色体适应度选择概率累积概率估计选中次数s1=110016250.360.361s2=011001440.080.441s3=110117290.410.851s4=100002560.151.0014.7算法举例交叉将s1与s2配对，s3与s4配对，交换后三位基因新种群S2={s1=11100(28),s2=01001(9)，s3=11000(24)，s4=10011(19)}变异种群变异基因位数：Pm*L*N=0.001*5*4=0.020.02不足1，本轮不做变异--------------第二代遗传操作完成----------------第三代种群S={s1=11100(28),s2=01001(9)，s3=11000(24)，s4=10011(19)}4.7算法举例选择设从区间[0,1]产生4个随机数r1=0.25,r2=0.41,r3=0.77,r4=0.98按轮盘赌选择法，染色体s1,s2，s3，s4依次选中次数为2，0，1，1选择产生种群S1={s1=11100(28),s2=11100(28)，s3=11000(24)，s4=10011(19)}染色体适应度选择概率累积概率估计选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.0014.7算法举例交叉将s1与s4配对，s2与s3配对，交换后两位基因新种群S2={s1=11111(31),s2=11100(28)，s3=11000(24)，s4=10000(16)}变异种群变异基因位数：Pm*L*N=0.001*5*4=0.020.02不足1，本轮不