博客

230320 智能优化方法上课粒子群算法

2023/3/20 粒子群（PSO）算法

老师又没来，这说明助教比老师强，男助教能讲算法，女助教讲论文怎么写，说明男助教强

大作业相关

  • 下周起开始汇报，下周一
  • 按照题目第一关键字，顺序号第二关键字
  • 讲 15 分钟，问答 5 分钟
  • 下周一、三讲的组只需要把算法设计讲出来即可

上课内容

The Particle Swarm Optimization Algorithm（粒子群）

  • Origins：1986 年，有人描述这个过程用 3 个简单的行为。
    • Separation
      • 避免人群过于拥挤
    • Alignment
      • 朝领头的个体对齐
    • Cohesion（内聚）
      • 个体会朝着中间个体走，开始向中间集合
  • 结合了自身经验和群体（原文为 social）经验
  • Concept：
    • 用大量粒子探索解空间，找到最优解
    • 对于每一个粒子，通过邻居做调整
    • 邻居是固定的

伪代码（注意是伪代码）

void PSO() {
    P = Particle_init(); // 预处理粒子点位置
    for(int i=0;i<iteration_max;i++) {
        for(auto p : P) {
            fp = f(p);
            if(fp > f(pBest[id(p)])) pBest[id(p)] = p;
        }
        gBest = best gBest, p in P;
        for(auto& p : P) {
            v[id(p)] = v[id(p)] + c1 * rand() * (pBest[id(p)] - p) + c2 * rand() * (gBest - p);
            p = p + v[id(p)];
        }
    }
}
  • 伪代码中的参数
    • pBest[i]: 对于 \(i\) 号粒子，他自己历史最佳的位置
    • gBest: 所有粒子中最佳位置
    • c1: 局部信息的权重
    • c2: 全局信息的权重
    • p: 粒子位置
    • v: 路径方向
    • id(p): 指 p 的下标
  • 参数的一些注意事项
    • 粒子数量属于 [10, 50]
    • 通常 \(C_1 + C_2 = 4\)
    • \(C_1\) 是个人最佳价值的重要性
    • \(C_2\) 是邻居最佳价值的重要性
    • rand() 是 [0,1] 区间的随机数
    • 速度要适中
  • 算法
    1. 创建一些粒子
    2. 用目标函数评估粒子位置
    3. 用粒子当前位置更新当前粒子的历史最优位置 pBest
    4. 更新整个粒子群中历史最优位置 gBest
    5. 更新粒子速度 \(v_i^{t+1} = v_t^t + c_1 U_1^t (pb_i^t – p_i^t) + c_2 U_2^t (gb^t – p_i^t)\)
    6. 把粒子移动到新位置上 \(p_i^{t+1} = p_i^t + v_i^{t+1}\)
    7. 跳到第二步直到终止
  • 特点
    1. Intensification：由于有 pbest，因此可以在自己的附近区域内做搜索。
    2. Diversification：可以让 gbest，让粒子从自己的位置到 gbest 位置路径区域上找最优解。
  • 优点
    • 参数少
    • 实现简单
    • 可以并行
    • 有效的全局搜索算法
  • 缺点
    • 网络权重的编码而且遗传算子的选择有时比较麻烦。
    • 对于离散的优化问题处理不佳，容易陷入局部最优解，因此一般需要使用期改进方法避免陷入局部最优解

今天还讲了粒子群做二位装箱、模拟退火做 TSP，但是我都没听，反正我不做这俩

Tags: