第三章搜索技术

第三章搜索技术内容摘要：

搜索技术 第二节 启发式搜索 十二、遗传算法 基本思想 • 变异 (mutation):对群体 P(t)中的每一个个体，以某一概率 (称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它的等位基因。 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 特点 • 以决策变量的编码作为运算对象 • 以目标函数值作为搜索信息 • 同时进行解空间的多点搜索 • 使用概率搜索技术 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 算法实现关键 • 染色体编码 • 群体的初始化 • 适应值评价 • 选择种群（轮盘赌） • 种群交配 • 种群变异 • 算法流程 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 基本遗传算法（ Simple Geic Algorithms,简称 SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑴ 基本遗传算法的构成要素 • ① 染色体编码方法。 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集 {0， 1}所组成的。 初始群体中各个个体的基因值可用均匀分布的随机数来生成。 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑴ 基本遗传算法的构成要素 • ② 个体适应度评价。 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。 为正确计算这个概率 ， 这里要求所有个体的适应度必须为正数或零。 • ③遗传算子。 基本遗传算法使用下述三种遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子或均匀变异算子。 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑴ 基本遗传算法的构成要素 ④基本遗传算法的运行参数。 基本遗传算法有下述 4个运行参数需要提前设定：群体大小 M，即群体中所含个体数目，一般取为 20~100；遗传运算的终止进化代数 T，一般取为 100~500； 交叉概率 Pc，一般取为 ~； 变异概率 Pm，一般取为 ~。 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑵ 基本遗传算法的实现 ① 个体适应度评价 • 在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。 个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。 基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。 为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑵ 基本遗传算法的实现 ②比例选择算子 • 比例选择实际上是一种有退还随机选择 ,也叫做赌盘 (Roulette Wheel)选择 ,因为这种选择方式与赌博中的赌盘操作原理非常相似。 • 比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即 0到 1之间的随机数）来确定各个个体被选中的次数。 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑵ 基本遗传算法的实现 ③单点交叉算子 • 单点交叉算子是最常用和最基本的交叉操作算子。 单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率 在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。 cp第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑵ 基本遗传算法的实现 ④ 基本位变异算子 • 基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率 指定其为变异点；对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。 mp第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑶ 遗传算法的应用步骤 遗传算法提供了一种求解复杂系统优化问题的通用框架。 对于具体问题 ， 可按下述步骤来构造： • ①确定决策变量及其各种约束条件，即确定出个体的表现型 X和问题的解空间； • ②建立优化模型，即描述出目标函数的类型及其数学描述形式或量化方法； 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑶ 遗传算法的应用步骤 • ③ 确定表示可行解的染色体编码方法 ， 即确定出个体的基因型 X及遗传算法的搜索空间； • ④ 确定解码方法 ， 即确定出由个体基因型 X到个体表现型 X的对应关系或转换方法； • ⑤确定个体适应度的量化评价方法，即确定出由目标函数值 到个体适应度的转换规则； )(Xf第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 基本遗传算法 ⑶ 遗传算法的应用步骤 • ⑥ 设计遗传算子 ， 即确定出选择运算 、 交叉运算 、 变异运算等遗传算子的具体操作方法； • ⑦确定遗传算法的有关运行参数。 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 应用 • 组合优化 • 生产调度问题 • 自动控制 • 机器人学 • 图象处理 第三章 搜索技术 第二节 启发式搜索 十二、遗传算法 免疫遗传算法 基于免疫的改进遗传算法，是免疫原理与传统遗传算法的结合。 算法的核心在于免疫算子的构造，而免疫算子又是通过接种疫苗和免疫选择两个步骤完成的。 在理论上，免疫算法是概率 1收敛的。 第三章 搜索技术 第二节 启发式搜索 十三、免疫算法 免疫算法流程图 初始抗体生成 抗原识别 抗体促进和抑制 满足终止条件。 群体更新 结束 亲和力计算 记忆细胞分化 Y N 第三章 搜索技术 第二节 启发式搜索 十三、免疫算法 免疫算法七要素 • 识别抗原 – 将目标函数和约束作为抗原 • 生成初始化的抗体 – 随机生成 N个抗体 • 计算亲和度 – 抗体和抗原的亲和度 – 抗体和抗体的亲和度 第三章 搜索技术 第二节 启发式搜索 十三、免疫算法 免疫算法七要素 • 记忆细胞分化 – 与抗原有最大亲和度的抗体加入记忆细胞 • 抗体促进和抑制 – 促进高亲和度的个体 ,消除低期望值的抗体 • 产生新的抗体 – 选择两个抗体做变异和交叉 ,得到新的抗体 • 结束条件 第三章 搜索技术 第二节 启发式搜索 十三、免疫算法 常用免疫算法 • 负选择算法 – 依靠 T细胞表面的受体，识别非自体，并消灭非自体（注：受体与所有的自体均不匹配） • 克隆选择算法 – 只关注抗原和抗体的亲和度对 B细胞的复制的影响，而不考虑抗体之间的亲和度 免疫系统 免疫算法 抗原 要解决的问题 抗体 最佳解向量 抗原识别 问题识别 从记忆细胞产生抗体 联想过去的成功 淋巴细胞分化 优良解 (记忆 )的保持 细胞抑制 剩余候选解的消除 抗体增加 (细胞克隆 ) 利用遗传算子产生新抗体 免疫系统与一般免疫算法之间的比较 第三章 搜索技术 第二节 启发式搜索 十四、模拟退火算法 (Simulated Annealing) 基本思想 (1)是基于 Monte Carlo迭代求解策略的一种随机寻优算法，源于物理退火原理；类似物理退火让固体粒子收敛到一个能量最低状态的过程，实现算法最终收敛到最优解的目的。 (2)结合爬山法和随机行走 第三章 搜索技术 第二节 启发式搜索 十四、模拟退火算法 (Simulated Annealing) 基本思想 (3) 结合概率突跳特性在解空间中随机寻找目标函数的全局最优解。 (4)首先生成一个随机解 ,然后对其进行扰动 (在同一温度下进行多次扰动 ),对扰动后得到的解进行评估与替换 ,温度逐渐下将形成多代。 第三章 搜索技术 第二节 启发式搜索 十四、模拟退火算法 (。