目录
蚁群优化
欺诈检测系统
进化算法等于搜索算法
模拟退火 禁忌搜索 用以避免局部最优
基于领域的启发式搜索
问题特征
- 问题足够困难 难以写代码来解决
- 人不知道如何解决这个问题
- 问题是不断变化
- 搜索每个解是不可行
- 可以接受”足够好”的解
基本术语
- 种群 候选解集合 可以有变异和交叉这样的遗传操作应用于他们
- 候选解: 给定问题的一个可能的解 染色体
- 基因: 组成染色体的不可分割的构建块 经典的基因包含0 1
- 染色体： 一串基因 定义了一个特定的候选解 01101011
- 变异: 一个过程 候选解中的基因被随机改变 以创建新的性状
- 交叉: 染色体被组合以创建新的候选解决方案的方法
- 选择: 选择的候选解 繁殖下一代解的技术
- 适应度: 一个评分 衡量候选解适合给定问题的程度
遗传算法: 发现可行的 接近最佳的解
两个不错的解可以进行组合 形成更适应的后代
遗传算法中的变异算子搜索特定候选解的近邻 变异算子也起到了一定的逃离局部最优的作用
基本遗传算法的实现的参数
变异率
特定基因变异的概率 过高导致延长找到一个可接受的解 过低在搜索空间中移动的过于缓慢 所以要设置以恶值 允许足够的多样性 防止算法停滞不前
种群规模
较大规模 可以在搜索空间中取样更多 较小规模 则取样较少4
交叉率
高交叉率在交叉阶段会产生新的 潜在优越的解 较低的交叉率有助于保持较适应个体的基因信息在下一代不受破坏
基因表示
2进制 对象 整数 浮点数 树的表示
停止
- 达到世代的最大数目
- 超过分配给它的时间
- 发现一个满足所需条件的解
- 该算法已经达到一个稳定阶段
实现遗传算法
使用遗传算法之前 先不妨考虑是否有更好的启发式搜索算法 同时需要考虑采用的弱方法的类型
锦标赛
通过适应度去进行竞争
规模大: 选择会丧失遗传多样性
规模小: 减慢算法的进展
单点交叉比较受欢迎,因为它有优越的遗传特性(保持连续的基因)
项目
排课
约束
- 硬约束(必须遵守)
- 教授在任何时间只能上一门课
- 教室要足够大 容纳该班的学生
- 教室在任何给定的时间只能上一门课
- 教室必须包含所有需要的设备
- 软约束(尽量满足)
- 教室的容量是适合班级的规模
- 教室喜欢的教室
- 教授喜欢的上课时间
优化
自适应
自适应遗传算法能够自动调整交叉率 突变率这些参数 在算法运行的过程中 会调整这些参数
评估个体表现 和整个种群作为一个整体的表现并依此更新变异率的算法公式
pm = (f max - fi) / (f max - f avg) * m f i > f avg
p m = m, f i <= f avg
- f max : 种群中适应度最佳的个体
- f i : 当前个体适应度
- f avg: 种群平均适应度
多次启发
- 模拟退火: 仿照冶金退火的搜索启发方法 简单说是一种爬山方法 旨在逐步减少较差解的接受率 在遗传算法上下文中 模拟退火将随时间降低变异率 和 交叉率
- 禁忌搜索: 保持一个”禁忌”解的列表 防止算法回到搜索空间中以前访问过的 已经是差的区域 有助于避免算法反复考虑它以前发现的 ，已经是差的解
优化适应度函数
- 并行计算
- 适应度值散列 缓存的概念
- 改进基因编码方法
