人工智能遗传算法2

第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，按每个染色体xiS的选择概率P(xi)所决定的选中机会，分N次从S中随机选择N个染色体，并进行复制

其中：f为适应度函数

f(xi)为xi的适应度优胜劣汰概率越高，随机选中概率越大概率越高，选中次数越多适应度高的染色体后代越多轮盘赌赌选择择原理：：做一个个单位位圆，，然后后按各各个染染色体体的选选择概概率将将圆面面划分分为相相应的的扇形形区域域转动轮轮盘，，轮盘盘静止止时指指针指指向某某一扇扇区，，即为为选中中扇区区，相相应的的个体体/染色体体即被被选中中轮盘赌赌选择择算法：：在[0,1]区间，，产生生一个个均匀匀分布布的伪伪随机机数r若rq1，则染染色体体1被选中中若qk-1<rqk(2kN)，则染染色体体k被选中中其中qi为染色色体xi(i=1,2,……,n)的累积积概率率一个染染色体体xi被选中中的次次数，，可由由期望望值e(xi)来确定定为种群群S中全体体染色色体的的平均均适应应度4.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参加交交叉运运算的的染色色体个个数占占全体体染色色体总总数的的比例例取值范范围：：变异率率Pm发生变变异的的基因因位数数占全全体染染色体体的基基因总总位数数的比比例取值范范围：：染色体体编码码长度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+1

j=N?

j=c?

j=m?Gen=Gen+1输出结果终止YNYYYNNNpcpm4.6基本本实实现现技技术术编码码方方法法二进进制制编编码码格雷雷编编码码编码码规规则则应使使用用能能易易于于产产生生与与所所求求问问题题相相关关的的且且具具有有低低阶阶、、短短定定义义长长度度模模式式的的编编码码方方案案应使使用用能能使使问问题题得得到到自自然然表表示示或或描描述述的的具具有有最最小小编编码码字字符符集集的的编编码码方方案案4.6基本本实实现现技技术术适应应值值函函数数适应应值值函函数数必必须须是是正正数数出现现负负数数时时应应进进行行变变换换，，常常用用变变换换方方式式有有三三种种：：线性性比比例例法法：：g(x)=a*f(x)+b(b>0)指数数比比例例法法：：g(x)=exp(af(x))(a0)幂指指数数比比例例法法：：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={s1=11000(24),s2=01101(13)，s3=11000(24)，s4=10011(19)}染色体适应度选择概率累积概率估计选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.0014.7算法举例例交叉设交叉率率Pc=100%,即S1全部染色色体参与与交叉将s1与s2配对，s3与s4配对，交交换后两两位基因因新种群S2={s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)}变异设变异率率Pm=0.001种群变异异基因位位数：Pm*L*N=0.001*5*4=0.020.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={s1=11001(25),s2=01100(12)，s3=11011(27)，s4=10000(16)}染色体适应度选择概率累积概率估计选中次数s1=110016250.360.361s2=011001440.080.441s3=110117290.410.851s4=100002560.151.0014.7算法举例例交叉将s1与s2配对，s3与s4配对，交交换后三三位基因因新种群群S2={s1=11100(28),s2=01001(9)，s3=11000(24)，s4=10011(19)}变异种群变变异基基因位位数：：Pm*L*N=0.001*5*4=0.020.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={s1=11100(28),s2=11100(28)，s3=11000(24)，s4=10011(19)}染色体适应度选择概率累积概率估计选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.0014.7算法举举例交叉将s1与s4配对，，s2与s3配对，，交换换后两两位基基因新种群群S2={s1=11111(31),s2=11100(28)，s3=11000(24)，s4=10000(16)}变异种群变变异基基因位位数：：Pm*L*N=0.001*5*4=0.020.02不足1，本轮轮不做做变异异--------------第三代代遗传传操作作完成成----------------第四代代种群群S={s1=11111(31),s2=11100(28)，s3=11000(24)，s4=10000(16)}4.7算法举举例在这一一代种种群中中已经经出现现了适适应度度最高高的染染色体体s1=11111。遗传操操作终终止，，将染色体体“11111”作为最最终结结果输输出。。将染色色体“11111”解码为为表现现型，，得所所求最最优解解：31将31代入函函数y=x2中，即即得原原问题题的解解，即即函数数y=x2的最大大值为为9614.7算法举举例YYy=x2

8131924

X第