人工智能_遗传算法

《人工智能_遗传算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章遗传算法4.1基本概念4.2选择算子4.3交叉算子4.4变异算子4.5基本遗传算法4.6基本实现技术4.7遗传算法应用第4章遗传算法生物进化自然法则优胜劣汰适者生存有性繁殖基因通过有性繁殖不断进行混合和重组遗传算法从生物界按照自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计的一种优化搜索算法第4章遗传算法应用函数优化组合优化：旅行商、图形化分…生产调度：车间调度、生产规划…自动控制：控制器、参数辨识…机器人智能控制：机器人路径规划、运动轨迹规划…图像处理与模式识别：特征提取、图像分割…人工生命：进化

2、模型、学习模型、行为模型…遗传程序设计机器学习4.1基本概念个体个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼一个个体也就是搜索空间中的一个点种群种群(population)就是模拟生物种群而由若干个体组成的群体它一般是整个搜索空间的一个很小的子集通过对种群实施遗传操作，使其不断更新换代而实现对整个论域空间的搜索4.1基本概念适应度(fitness)借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度适应度函数(fitnessfunction)问题中的全体个体与其适应度之

3、间的一个对应关系一般是一个实值函数该函数就是遗传算法中指导搜索的评价函数4.1基本概念染色体(chromosome)染色体是由若干基因组成的位串（生物学）个体对象由若干字符串组成来表示（遗传算法）遗传算法(geneticalgorithm)染色体就是问题中个体的某种字符串形式的编码表示染色体以字符串来表示基因是字符串中的一个个字符个体染色体9----1001（2，5，6）----0101011104.1基本概念遗传算子(geneticoperator)选择(selection)交叉(crossover)变异(muta

4、tion)4.2选择算子选择算子模拟生物界优胜劣汰的自然选择法则的一种染色体运算从种群中选择适应度较高的染色体进行复制，以生成下一代种群算法：个体适应度计算在被选集中每个个体具有一个选择概率选择概率取决于种群中个体的适应度及其分布个体适应度计算，即个体选择概率计算个体选择方法按照适应度进行父代个体的选择4.2选择算子个体适应度计算按比例的适应度计算(proportionalfitnessassignment)基于排序的适应度计算(rank-basedfitnessassignment)个体选择方法轮盘赌选择(roul

5、ettewheelselection)随机遍历抽样(stochasticuniversalsampling)局部选择(localselection)截断选择(truncationselection)锦标赛选择(tournamentselection)4.2.1按比例的适应度计算算法：对一个规模为N的种群S，按每个染色体xiS的选择概率P(xi)所决定的选中机会，分N次从S中随机选择N个染色体，并进行复制其中：f为适应度函数f(xi)为xi的适应度优胜劣汰概率越高，随机选中概率越大概率越高，选中次数越多适应度高的染色

6、体后代越多4.2.3轮盘赌选择原理：做一个单位圆，然后按各个染色体的选择概率将圆面划分为相应的扇形区域转动轮盘，轮盘静止时指针指向某一扇区，即为选中扇区，相应的个体/染色体即被选中4.2.3轮盘赌选择算法：在[0,1]区间，产生一个均匀分布的伪随机数r若rq1，则染色体1被选中若qk-1

7、某些位上的基因随机化算子，生成新个体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=1

8、011011100s1:1011011100s1’：1011011000二进制变异4.5基本遗传算法遗传算法对种群中的染色体反复做三种遗传操作使其朝着适应度增高的方向不断更新换代，直至出现了适应度满足目标条件的染色体为止算法拓展遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用基本遗传算法是Holland提出的一种统一的最基本的遗传算