人工智能教学资料 遗传算法关联规则.pdfVIP

基于遗传算法的关联规则挖掘 Outline ?遗传算法 ?基于遗传算法的关联规则 遗传算法 ? 遗传算法是根据生物进化思想而启发得出的一种全局优化算法。 简称GA，在本质上是一种不依赖具体问题的直接有哪些信誉好的足球投注网站方法。在 人工智能研究中，现在人们认为“遗传算法，自适应系统，细胞 自动机，混沌理论与人工智能一样，都是对今后十年的计算机技 术有重大影响的关键技术”。 ? 在遗传算法中，数据编码、初始群体的设定、适应度函数的设计、 控制参数的选取的遗传操作的设计构成了它的核心内容。 ? 生物进化的进化过程主要是通过染色体之间的交叉和染色体的变 异来完成。遗传算法中最优解的有哪些信誉好的足球投注网站过程也模仿生物的这个进化 过程，使用所谓的遗传算子作用于群体中，进行下述遗传操作， 从而得到新一代群体： ? 选择：根据各个个体的适应度，按照一定的规则或方法从上一代 群体中选择出一些优良的个体遗传到下一代群体中。 ? 交叉：将群体内的各个个体随机搭配成对，对每一个个体以某个 概率交换他们之间的部分染色体。 ? 变异：对群体中的每一个个体，以某一个概率或某些基因改变其 基因上的基因值。 遗传算法的构成要素 ? 染色体编码方法 一般使用固定长度的二进制符号串来表示群体中的个体，其等位 基因是由二值符号集{0，1}所组成，初始群体可以用均匀分布的随 机数来生成。 ? 个体适应度评价 遗传算法按与个体适应度成正比的概率来决定当前群体中每个个 体遗传到下一代群体中的机会多少。 ? 遗传算子 比例选择算子、单点交叉算子、变异运算算子 ? 运行参数 M：群体大小 T：迭代次数 Pc：交叉概率 Pm：变异概率 遗传算法的基本运算过程 ? 编码：二进制编码、实数编码、整数编码 ? 初始化：最大迭代数T、计数器t、随机生成M个初始群体P(0) ? 个体评价：计算各个个体的适应度 ? 选择运算：将选择算子作用于群体 ? 交叉运算：将交叉算子作用于群体 ? 变异运算：将变异算子作用于群体 （群体p(t)经过选择、交叉、变异运算后得到下一代群体p(t+1)） ? 终止条件判断：若t=T,则t-t+1;若tT，则把进化过程中得到的 最大适应度的个体作为最优解输出，终止运算。 GA中常用技术 ?编码 ?适应度函数 ?遗传算子 ?关键参数确定 编码 ? 三个原则 1.完备性：编码应该可以表示问题空间中所有点 2.健全性：GA编码空间的染色体位串必须对应问题中某一潜在解 3.非冗余性：染色体和潜在解必须一一对应 ? 二进制编码 每个染色体可以表示为： 例如： X=(0110010) 1 2(x , x , , x ) x {0,1}n iX ? ? ? 顺序编码 例如： X=（2 3 1 5 4 7 6）不允许重复 若 X=（ 2 1 3 1 2 4 5） 在TSP问题中这不是一个合法的编码，需要修复。主要的修复办 法：部分映射交叉、顺序交叉、循环交叉等。但在整数编码中这是 合法的。 ? 大字符集编码 ? 树编码 适应度函数 ? 适应度函数的设计主要满足以下条件 1.单值、连续、非负、最大化 2.合理，一致性:要求其反应对应解的优劣程度 3.计算量小 4.通用性强 ? 几种常见的适应度函数 1.直接以待求解的目标函数转化为适应函数 若目标函数为最大化问题 fitness(f(x)) = f(x) 若目标函数为最小化问题 fitness(f(x)) = -f(x) (可能不满足轮盘赌选择中的概率非负的要求) 2.若函数为最小问题： 为f(x)的最大估计 若函数为最大问题： 为f(x)的最小估计 max max(x), f(x) c (f(x)) 0,other c f fitness ? ?? ? ? ? maxc min min(x) c , f(x) c (f(x)) 0,other f fitness ? ?? ? ? ? minc 遗传因子 ? 选择因子 1.适应度比例方法 各个个体被选中的概率与其适应度成正比，适应度越高的个体 被选中的概率越大。(由于随机操作，选择误差比较大) 2.最佳个体保存方法 随机性可能会破坏优良个体，所以我们保存每次进化的最佳个 体，让群体中适应度最高的个体不进行配对交叉直接复制到下一代 3.排序选择方法 根据适应度进行排序，然后根据事先设计好的概率表按序分配 给个体，作为其选择概率。 交叉算子 1.离散实值重组 2.二进制交叉 2.1单点交叉 父个体1 0 1 1 1 0 0 1 1 0 1 0 父个体2 1 0 1 0 1 1 0 0 1 0 1 随机选择一个交叉点：5，交叉产生两个子个体： 子个体1 0 1 1 1 0 1 0 0 1 0 1 子个体2 1 0 1 0 1 0 1 1 0 1 0 2.2多点交叉 2.3 均匀交叉 变异算子 ?