人工智能导论笔记 |
您所在的位置:网站首页 › 人工智能导论第四章课后答案大全解析 › 人工智能导论笔记 |
遗传算法:
基本思想:在求解问题时从多个解开始,然后通过一定的法则进行逐步迭代以产生新的解 遗传算法的基本要素: 编码 生成初始种群 适应度函数 个体选择概率 个体选择方法 交叉操作 变异
编码: 位串编码: 将问题空间的参数用一维数组表示 (1)二进制编码:用若干二进制数表示一个个体,将原问题的解空间映射到位串空间B={0,1}上,然后在位串空间上进行遗传操作 优点:类似生物染色体的组成,算法易于用生物遗传理论解释,遗传操作如交叉、变异等易实现;算法处理的模式数最多 缺点:相邻整数的二进制编码可能具有较大的Hamming距离,降低了遗传算子的搜索效率;要先给出求解精度 (2)Gray编码:将二进制编码通过一个变换进行转换得到的编码 实数编码: 采用实数表达不必进行数制转换,可直接在解的表现型上进行遗传操作 多参数映射编码的基本思想:把每个参数先进行二进制编码得到子串,再把这些子串连成一个完整的染色体 多参数映射编码中的每个子串对应各自的编码参数,所以,可以有不同的串长度和参数的取值范围
适应度函数的尺度变换: 欺骗问题:在遗传算法中,将所有妨碍适应度值高的个体产生,从而影响遗传算法正常工作的问题统称欺骗问题 过早收敛:缩小这些个体的适应度,以减低这些超级个体的竞争力 停滞现象:改变原始适应值的比例关系,以提高个体之间的竞争力 适应度函数的尺度变换或者定标:对适应度函数值域的某种映射变换
(1)线性变换: f'=af+b;满足f'avg=favg,f'max=Cmult*favg (2)幂函数变换: f'=f^k (3)指数变换: f'=e^-af
选择: (1)适应度比例法: 各个个体被选择的概率和其适应度值成比例 个体i被选择的概率:
(2)排序方法: 线性排序:
非线性排序:
交叉: 一般的交叉方法: (1)一点交叉: 在个体串中随机设定一个交叉点,实行交叉时,该点前或后的两个个体的部分结构进行交换,并生成两个新的个体 (2)两点交叉: 随机设置两交叉点,将两个交叉点之间的码串相互交换 修正的交叉方法: (1)部分匹配交叉PMX: A=9 8 4 | 5 6 7 | 1 3 2 B=8 7 1 | 2 3 9 | 5 4 6 先交换匹配区中的内容 A' = 9 8 4 | 2 3 9 | 1 3 2 B' = 8 7 1 | 5 6 7 | 5 4 6 将A'和B'中匹配区域外出现的重复项,按照匹配区内对应关系交换 A'' = 7 8 4 | 2 3 9 | 1 6 5 B'' = 8 9 1 | 5 6 7 | 2 4 3 (2)顺序交叉OX: 将匹配区外与另一基因匹配区内相同的值置为H A' = H 8 4 | 5 6 7 | 1 H H B' = 8 H 1 | 2 3 9 | H 4 H 将匹配区移动到起点位置,H移动到中间位置,其余值按顺序补在后面 A'' = 5 6 7 | H H H | 1 8 4 B'' = 2 3 9 | H H H | 4 8 1 将A,B的匹配区交换,放入预留区H的位置,即得到两个子代 A''' = 5 6 7 | 2 3 9 | 1 8 4 B''' = 2 3 9 | 5 6 7 | 4 8 1 (3)循环交叉CX: A=1 2 3 4 5 6 7 8 9 B=5 4 6 9 2 3 7 8 1 得到从A第一位开始的循环基因:1-5-2-4-9-1 可用循环的基因A',顺序与A相同 A=1 2 3 4 5 6 7 8 9 A'=1 2 x 4 5 x x x 9 剩余部分填入B对应的基因 A'=1 2 6 4 5 3 7 8 9
变异: (1)位点变异: 群体中的个体码串,随机挑选一个或多个基因,并对这些基因的基因值以变异概率作变动 (2)逆转变异: 在个体码串中随机选择两点,然后将两点之间的基因值以逆向排序插入到原位置 (3)插入变异: 在个体码串中随机选择一个码,然后将此码插入随机选择的插入点中间 (4)互换变异: 随机选取染色体的两个基因进行简单互换 (5)移动变异: 随机选择一个基因,向左或向右移动一个随机位数
遗传算法的一般步骤:
遗传算法的特定: 遗传算法是一种全局优化概率算法 遗传算法对所求解的优化问题没有太多的数学要求,由于进化特性,搜索过程中不需要问题的内在性质,不论是线性还是非线性的,离散还是连续的都可以处理,可直接对结构对象进行操作 利用随机技术指导对一个被编码的参数空间进行高效搜索 采用群体搜索策略,易于并行化 仅用适应度函数值来评估个体,并在此基础上进行遗传操作,使种群中个体之间进行信息交换 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |