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

遗传算法遗传算法1.1基本概念1.2选择算子1.3交叉算子1.4变异算子1.5基本遗传算法1.6基本实现技术1.7遗传算法应用遗传算法生物进化自然法则优胜劣汰适者生存有性繁殖基因通过有性繁殖不断进行混合和重组遗传算法从生物界按照自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计的一种优化搜索算法遗传算法应用函数优化组合优化：旅行商、图形化分…生产调度：车间调度、生产规划…自动控制：控制器、参数辨识…机器人智能控制：机器人路径规划、运动轨迹规划…图像处理与模式识别：特征提取、图像分割…人工生命：进化模型、学习模型、行为模型…遗传程序设计机器学习个体个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼一个个体也就是搜索空间中的一个点种群种群(population)就是模拟生物种群而由若干个体组成的群体它一般是整个搜索空间的一个很小的子集通过对种群实施遗传操作，使其不断更新换代而实现对整个论域空间的搜索遗传算法1.1基本概念适应度(fitness)借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度适应度函数(fitnessfunction)问题中的全体个体与其适应度之间的一个对应关系一般是一个实值函数该函数就是遗传算法中指导搜索的评价函数1.1基本概念染色体(chromosome)染色体是由若干基因组成的位串（生物学）个体对象由若干字符串组成来表示（遗传算法）遗传算法(geneticalgorithm)染色体就是问题中个体的某种字符串形式的编码表示染色体以字符串来表示基因是字符串中的一个个字符个体染色体9----1001（2，5，6）----0101011101.1基本概念遗传算子(geneticoperator)选择(selection)交叉(crossover)变异(mutation)1.2选择算子选择算子模拟生物界优胜劣汰的自然选择法则的一种染色体运算从种群中选择适应度较高的染色体进行复制，以生成下一代种群算法：个体适应度计算在被选集中每个个体具有一个选择概率选择概率取决于种群中个体的适应度及其分布个体适应度计算，即个体选择概率计算个体选择方法按照适应度进行父代个体的选择1.2选择算子个体适应度计算按比例的适应度计算(proportionalfitnessassignment)基于排序的适应度计算(rank-basedfitnessassignment)个体选择方法轮盘赌选择(roulettewheelselection)随机遍历抽样(stochasticuniversalsampling)局部选择(localselection)截断选择(truncationselection)锦标赛选择(tournamentselection)1.2.1按比例的适应度计算算法：对一个规模为N的种群S，按每个染色体xiS的选择概率P(xi)所决定的选中机会，分N次从S中随机选择N个染色体，并进行复制其中：f为适应度函数f(xi)为xi的适应度1()()()iiNjjfxPxfx优胜劣汰1.概率越高，随机选中概率越大2.概率越高，选中次数越多3.适应度高的染色体后代越多1.2.2算法过程其具体操作过程是：•先计算出群体中所有个体的适应度的总和fi(i=1.2,…,M);•其次计算出每个个体的相对适应度的大小fi/fi，它即为每个个体被遗传到下一代群体中的概率，•每个概率值组成一个区域，全部概率值之和为1；•最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。1.3交叉算子交叉算子交换、交配、杂交互换两个染色体某些位上的基因随机化算子，生成新个体1.3交叉算子一点杂交产生一个在1到L－1之间的随机数I配对的两个串相互对应的交换从i＋1到L的位段1.3交叉算子例3.1设染色体s1=1011011100染色体s2=0001110011交换其后2位基因s1:1011011100s1’：1011011111s2：0001110011s2’：0001110000单点交叉1.4变异算子变异算子突变改变染色体某个/些位上的基因随机化算子，生成新个体次要算子，但在恢复群体中失去的多样性方面具有潜在的作用1.4变异算子例4.1设染色体s=1011011100s1:1011011100s1’：1011011000二进制变异1.5基本遗传算法遗传算法对种群中的染色体反复做三种遗传操作使其朝着适应度增高的方向不断更新换代，直至出现了适应度满足目标条件的染色体为止算法拓展遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用基本遗传算法是Holland提出的一种统一的最基本的遗传算法，简称SGA（SimpleGeneticAlgorithm)、CGA（CanonicalGeneticAlgorithm）其它的“GA类”算法称为GAs(GeneticAlgorithms）,可以把GA看作是GAs的一种特例1.5基本遗传算法参数种群规模种群的大小，用染色体个数表示最大换代数种群更新换代的上限，也是算法终止一个条件交叉率Pc参加交叉运算的染色体个数占全体染色体总数的比例取值范围：0.4-0.99变异率Pm发生变异的基因位数占全体染色体的基因总位数的比例取值范围：0.0001-0.1染色体编码长度L1.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，转步31.5流程图开始Gen=0编码随机产生N个初始个体满足终止条件?计算群体中各个体适应度从左至右依次执行遗传算子j=0j=0j=0根据适应度选择复制个体选择两个交叉个体选择个体变异点执行变异执行交叉执行复制将复制的个体添入新群体中将交叉后的两个新个体添入新群体中将变异后的个体添入新群体中j=j+1j=j+2j=j+1j=N?j=c?j=m?Gen=Gen+1输出结果终止YNYYYNNNpcpm1.6基本实现技术编码方法二进制编码格雷编码编码规则应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案1.6基本实现技术适应值函数适应值函数必须是正数出现负数时应进行变换，常用变换方式有三种：线性比例法：g(x)=a*f(x)+b(b0)指数比例法：g(x)=exp(af(x))(a0)幂指数比例法：g(x)=(f(x))a(a为偶数)1.7算法举例例7.1利用遗传算法求解区间[0,31]上的二次函数y=x2的最大值分析原问题转化为[0,31]中寻找能使y取最大值的点x区间[0,31]为论域空间/解空间x为个体对象函数f(x)=x2可作为适应度函数1.7算法举例解：定义适应度函数，编码染色体适应度函数取f(x)=x2用5位二进制数作为个体x的基因型编码/染色体设定种群规模，产生初始种群种群规模N=4初始种群S={s1=01101(13),s2=11000(24)，s3=01000(8)，s4=10011(19)}1.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.0011.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)}1.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.0011.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)}1.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.0011.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，本轮不做变异--------------第三代遗传操作完成----------------第四代种群S={s1=11111(31),s2=11100(28)，s3=11000(24)，s4=10000(16)}1.7算法举例在这一代种群中已经出现了适应度最高的染色体s1=11111。遗传操