智能优化方法

“本教材主要介绍近年来产生发展的多种智能优化算法。包括为人熟知的遗传算法、禁忌搜索算法、模拟退火算法和蚁群优化算法；近年来已成为研究热点的粒子群优化算法；还有尚待普及的捕食搜索算法和动态环境下的进化计算。书中讨论这些算法的产生和发展、算法的基本思想和理论、基本构成、计算步骤和主要的变形以及数值例子和实际应用。为了方便读者学习，各章之后还附有精选的习题、思考题及相关的参考文献。本教材是为“智能优化方法”这门研究生课程编写的

智能优化方法

• 遗传算法及其应用研究
  • 遗传算法及其应用研究
    • 多峰问题
      • 局部极值
    • GA
      • 《遗传算法原理及应用》
        • 周明，孙树栋
    • PSO
      • 雷秀娟老师的书
    • ACO
      • 段海滨
        • 15年出版
    • ABC
      • 蜂群算法
    • BFO
      • 细菌觅食算法
    • 萤火虫
    • 布谷鸟
    • 蛙跳
    • 鱼群
      • 李晓磊博士论文提出
    • 烟花
      • 谭营
    • 头脑风暴
      • 史玉回
    • …
  • 遗传算法的生物学基础
    • 遗传算法
      • Holland教授提出
      • 染色体-DNA-基因-交叉、复制-新个体
      • 适者生存
      • 生物进化过程需要四个基本条件
        • 存在由多个生物个体组成的种群
        • 生物个体之间存在着差异
        • 生物能够自我繁殖
        • 不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱
      • 生物群体的进化机制包括三种基本形式
        • 自然选择
          • 控制生物群体的行为发展方向，使适应能力强的个体在种群中数量不断增加，且使其具有的染色体形状特征得以保留
        • 杂交
        • 突变
          • 不可逆过程
          • 具有突发性
          • 间断性
          • 不可预测性
          • 对于保证群体的多样性具有不可替代的作用
      • 生物进化是一个开放的过程，自然界对进化中的生物群体提供及时的反馈信息，或称外界对生物的评价
        • 评价反映了生物的生存价值和机会
      • 生物的遗传方式
        • 复制
          • Reproduction
        • 交叉
          • Crossover
        • 变异
          • Mutatioan
      • 遗传算法主要借鉴了生物进化的一些特征
        • 进化发生在解的编码上。这些编码按生物学的术语称为染色体。
          • 由于进行了编码，优化问题的一切性质都通过编码来研究。
          • 编码和解码是遗传算法的一个主题
        • 自然选择规律决定哪些染色体产生超过平均数的后代
          • 遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代
        • 当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征
        • 当染色体结合时，随机的变异会造成子代与父代的不同
  • 遗传算法简介
    • 遗传算法是模拟生物中自然环境下的遗传和进化过程中而形成的一种自适应全局优化搜索方法
    • 由密歇根大学Holland提出
    • 遗传算法概要
      • 数学模式
        • max f(x)
        • s,t，X属于R
        • R包含于U
      • 最优解
        • 枚举
        • 启发
      • n维决策向量
    • 遗传算法运算过程
      • 子主题 1
    • 手工模拟计算示例
    • 遗传算法的应用
      • 函数优化
      • 子主题 2
      • 生产调度
      • 自动控制
      • 机器人学
      • 图像处理
      • 人工生命
      • 子主题 8
• 基本遗传算法
  • 描述
    • 共同特点
      • 即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程
    • 基本遗传算法只选择算子、交叉算子和变异算子
      • 遗传操作过程简单，容易理解
    • 构成要素
      • 染色体编码方法
      • 个体适应度评价
      • 遗传算子
      • 基本遗传算法的运行参数
    • 形式化定义
      • GA=（C, E, P0, M,
        • 八元组
        • Ｃ－个体的编码方法
        • Ｅ－个体适应度评价函数
        • P0-初始群体
        • M
          • 群体大小
        • 子主题 6
          • 选择算子
        • 子主题 7
          • 交叉算子
        • 子主题 9
          • 变异算子
        • T
          • 遗传运算终止条件
    • 大致流程
      • 伪代码
  • 实现
    • 编码与解码
      • 常见编码方法
        • 二进制编码
        • 大字符集编码
        • 序列编码
        • 实数编码
        • 树编码
        • 自适应编码
        • 乱序编码
        • 二倍体和显性规律
      • 编码
      • 解码
      • 例题
      • 注意
    • 群体的设置
      • 初始群体的设定
        • 按一定分布随机产生
          • 子主题 1
          • 子主题 2
      • 群体规模的设定
    • 个体适应度评价
      • 仅用目标函数即适应度函数为依据
      • 当优化目标求函数最大值
        • F(X)=f(X)
          • 个体适应度F(X)
      • 求目标函数最小值的优化问题
        • min f(X)= max(-f(X))
    • 比例选择算子
      • 是最常用的比例选择算子
        • 执行比例选择的手段是
          • 轮盘选择
      • 定义
        • 指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成比例
      • 为防止选择误差
        • 精英选择
          • 代沟
        • 稳态选择
      • 轮盘选择
    • 单点交叉算子
      • 交叉算子的作用
        • 通过交叉，子代的基因值不同于父代。交换是遗传算法产生新个体的主要手段。正式有了交换操作，群体的性态才多种多样
      • 最基本最常用
        • 单点交叉算子
          • 具体计算
            • 两两随机配对
            • 设置某一基因座之后的位置为交叉点
            • 在交叉点相互交换部分染色体
    • 基本位变异算子
      • 是最简单最基本的变异操作算子
        • 具体执行
          • 对指定的变异点，对其基因值做取反运算，或用其他等位基因值来代替
    • 算法流程图
  • 应用举例
    • 例：Rosenbrock函数的全局最大值计算
      • 1 确定决策变量及其约束条件
      • 2 建立优化模型
      • 3 确定编码方法
      • 4 确定解码方法
      • 5 确定个体评价方法
      • 6 设计遗传算法
      • 7 确定遗传算法的运行参数
  • 性能评估
    • 适应性函数计算次数
    • 在线和离线性能函数
    • 最优解搜索性能
  • 模式理论
    • 基本概念
      • Holland教授提出
      • 问题的引出
        • 子主题 1
      • 模式、模式阶、模式定义长度
        • 模式Schema
          • *
        • 模式阶 Schema Order
          • 模式中已有明确字符的个数
        • 模式定义的长度Schema Defining Length
          • 指模式中第一个和最后一个具有明确字符之间的距离
          • 模式长度越短，在遗传操作中被破坏的可能性越小
            • 长度为0的模式最难被破坏
      • 编码字符串的
    • 模式定理
    • 建筑块（积木块）假说
      • 子主题 1
    • 隐含并行性（内在并行性）
  • 编码
    • 二进制与格雷码
    • 浮点数编码
      • 方法
        • 个体的每个基因值都用浮点数表示
      • 交叉运算必须在基因界
    • 符号编码
      • 符号集可以是字母表
      • 无数值含义，只有代码含义的符号集
    • 连续函数离散化
  • 适应度函数
    • 度量个体适应度的函数
    • 目标函数
      • 遗传算法的一个特点是它使用所求问题的目标函数就可以得到下一步的有关搜索信息
      • 一类
        • 求目标函数的全局最大值
    • 适应度尺度变换
      • 多样性降低
        • 局部最优点
          • 早熟现象
      • 保证群体多样性
      • 变换方法
        • 线性尺度变换
          • 条件1：全部新个体的新适应度平均值等于原来的适应度平均值
          • 条件2：新的最大适应度要等于原来的倍数
          • 最小适应度为负时的处理
            • 将最小适应度值映射为0
        • 乘幂尺度变换
          • 新适应度平均值为原平均值的幂次
        • 指数尺度变换
      • 约束条件的处理方法
        • 搜索空间限定法
        • 罚函数法
          • 无对应可行解时使用罚函数降低个体适应度
          • 最简单的罚函数为平方法
          • 松紧法：前期松，后期紧
        • 可行解变换法
  • 选择算子
    • 比例选择
    • 分级选择
      • 排序选择
        • 采用线性分级
    • 竞技选择法
      • 每次选择k个个体中的最大
    • 最优保存策略
      • 适应度最高的个体不参与分叉变换，替代最低适应度
      • 全局搜索能力差
    • 确定式采样选择
  • 交叉算子
    • 单点交叉
    • 双点交叉与多点交叉
      • 多点交叉又称为广义交叉
        • 一般不大使用多点交叉
    • 均分交叉
      • 属于多点交叉的范围
    • 算术交叉
      • 最容易破坏群体多样性
      • 一般操作浮点数编码的个体
  • 变异算子
    • 随机变异
    • 均匀变异
    • 边界变异
    • 高斯变异
  • 终止条件
    • 规定最大迭代次数丅200～500
    • 规定最小的偏差，
    • 观察适应度的变换趋势
• 布谷鸟算法
  • 研究背景
    • 2008年提出
    • 群智能优化算法之一
  • 定义
    • 基于布谷鸟巢寄生繁殖行为，莱维飞行寻找寄生鸟巢
  • 优点
    • 实现简单
    • 自组织性
    • 鲁棒性强
    • 适用性广
    • 司扩展性
  • 应用
    • 优化问题
    • 图像处理
    • 路径规划
    • TSP
  • 仿生行为
    • 巢寄生方式孵育幼鸟
      • 杜鹃雏鸟孵化后把巢内其他卵推出鸟巢
    • 莱维飞行寻找寄生鸟巢
      • 一系列连续随机导向直线运动组成，频繁出现的较短距离的直线运动和偶尔出现的较长移动相间出现，甚至不时出现更长距离的移动
      • 莱维分布
  • 研究切入点
  • 研究现状
    • 改进算法
  • 每一个样本只能属于一个类别，
    • 每一个样本只能属于一个类别，
  • 融合粒子群算法的布谷鸟优化聚类算法PSOCS
    • 收敛速度慢
• 细菌觅食优化
  • 仿生随机搜索算法
  • 大肠杆菌觅食
    • 游动和旋转
    • 寻找食物能力较差的个体会被淘汰
    • 迁徙操作
      • 群体到环境比较好的地方
  • BFO
    • 算法参数
      • 种群大小
      • 游动步长
  • BFO与GA联系
    • 相似
    • 区别
      • 函数
      • 复制
      • 变异
• 蚁群算法
  • 研究现状
    • AS
      • 最早
        • 蚁密算法
        • 蚁量算法
      • 为解决TSP问题
• 粒子群
  • PSO
  • 基于迭代的优化方法
  • 基于群智能的随机优化算法
  • 源于对鸟群捕食行为的研究
  • 应用
    • 飞机离场
      • 模型
        • 先到先服务
    • 移动机器人路径规划
      • 路径规划常用算法
        • 人工势场法
        • 骨架式的方法
        • 单元分解的方法
      • 问题描述
        • 路径规划定义
        • 最优的标准
          • 路径最短
          • 子主题
          • 时间最小
          • 最安全或所需动能最小
        • 需要考虑的因素
          • 始于初始点
            • 止于目标点
• 人工蜂群算法
  • 丁海军
    • ABC改进 适合组合优化
      • 应用于TSP
    • 基于觅食机制
      • 2005 karaboga
        • 提出并归纳综述其他人的应用
  • 人工蜂群在多序列比对中的应用
• 果蝇优化算法
  • 步长改进FOA
    • 随机步长
  • 混沌FOA
  • 优点：FOA算法结构比较简单，相对于其他智能优化方法运行效率高
  • 缺点：易陷入局部最优解
  • 应用
• 萤火虫优化算法
  • 萤火虫发光
    • 亮度决定移动方向，吸引度决定移动大小
  • 假定条件
    • 不分雌雄
• 软件
  • Visio
    • 算法流程图
  • Matlab
    • 矩阵运算
    • 图像处理
    • 可拓展性强
• 作业
  • 期中汇报
    • 与老师讲的相关
    • 中外文文献
  • 期末
    • 大作业：算法优化
      • 应用
        • 函数优化
        • TSP组合优化
          • 背包
        • 调度
        • 图像领域
          • 分割
          • 压缩
          • 增强
          • …
        • 应画出适应度曲线
    • 汇报
  • 作业1
    • 书后遗传算法练习
  • 作业2
    • 遗传算法解决旅行商问题如何编码
      • 中文文献
    • 蚁群和粒子群的编码
    • 练习：Rosenbrock函数的全局最大值计算
      • 1 确定决策变量及其约束条件
      • 2 建立优化模型
      • 3 确定编码方法
      • 4 确定解码方法
      • 5 确定个体评价方法
      • 6 设计遗传算法
      • 7 确定遗传算法的运行参数
  • 作业3
    • 基于繁殖类的蜂群算法