蚁群优化算法学习笔记

数学建模 

本人阅读《蚁群优化算法》-马良等过程中的笔记
前五章的目录

  1. 引论
    1. 组合优化与计算复杂性
    2. 来自自然界的几类优化方法
  2. 蚁群算法原理
    1. 基本思想
    2. 研究概况
  3. 标准的TSP的蚁群算法
    1. TSP概述
    2. 经典方法
    3. 遗传算法与模拟退火
    4. 蚁群算法
    5. 元胞蚁群算法及其收敛性
  4. 扩展旅行商问题的蚁群算法
    1. 瓶颈TSP及其求解
    2. 最小比率TSP及其求解
    3. 时间约束TSP及其求解
    4. 多目标TSP及其求解
  5. 车辆路径问题的蚁群算法
    1. VRP概述
    2. CVRP及其求解
    3. 多目标VRP及其求解
    4. VRPTW及其求解
    5. VRPSTW及其求解
    6. FVRP及其求解
      看完目录前五章，首先有好多英文缩写看不明白，接着看

第一章 引论

1.1 组合优化与计算复杂性
最优化分连续变量与离散变量，离散变量的问题往往称为组合优化
局部搜索法是基于贪婪思想，利用领域函数进行搜索的，局部搜索法可能落入局部最优点，或由于步长和初始点选择不好而错过最优点。
依据一定概率，对于步长问题，可以采用变步长方法，在接近最优点附近，采取某种策略改变步长
对于初始点问题，可以采用随机生成的一些初始点，从每个初始点出发进行搜索，找到各自的最优解，再从这些最优解中选择一个最好的结果

典型组合优化难题
1. 旅行商问题（TSP）：所有可能的路线最多有（n-1）!/2 条
2. 图着色问题（GCP）：记图的最大顶点读书为\(\Delta\) ，则图的最小着色数以\(\Delta + 1\)为上界
3. 工件排序问题（JSP）：NP难题（NP-hard）
4. 二次分配问题（QAP）：目标函数非线性
5. 度约束最小树问题（DCMSTP）：最小生成树问题（不懂）
上述典型问题及等价问题，普遍认为没有多项式算法求解

1.2 来自自然界的几类优化方法
计算智能系统是在神经网络、模糊系统、进化计算

  1. 遗传算法的基本步骤（GA）：
    1. 问题的染色体表示
    2. 初始解组（种群）的生成
    3. 计算解组中各个解的适值函数（代价函数）
    4. 从解组中随机抽取两个解作为父母代
    5. 对父母代实施遗传操作（交叉、变异等）以产生一个后代解
    6. 按某种规则，用该后代解替换原解组中的某个解
    7. 按当前解组符合停机条件则算法终止，否则，转步骤1
      结果的好坏主要依赖于遗传代数和解组规模
  2. 模拟退火算法基本步骤（SA）：
    物体内部服从Boltzman分布
    1. 选择初始状态H（初始解）、初始温度、降温次数等
    2. 生成H的领域状态H‘，并计算两种状态下的目标函数f(H')-f(H)
    3. 按接受概率置换H为H‘
    4. 重复步骤2和步骤3直至停机条件满足
  3. 禁忌搜索法（TS）在搜索过程中使用记忆功能
  4. 人工神经网络
  5. 蚁群系统：信息激素，轨迹，自催化行为，增强型学习系统
  6. 微粒群算法（PSO）：
    1. 依照初始化过程，对微粒群的随机位置和速度进行初始设定
    2. 计算每个微粒的适应值
    3. 对每个微粒，将其适应值与所经历过的最好位置进行比较，若较好，则将其作为当前的最好位置
    4. 对每个微粒，将其适应值与全局所经历的最好位置的适应值进行比较，若较好，则将其作为当前的的全局最好位置
    5. 对微粒的速度和位置进行进化
    6. 若未到达结束条件（通常为足够好的适应值或最大代数），则返回步骤2

本文由 CubeTian 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2019-09-10T20:21:15+08:00