进化算法设计原则

进化算法：基于自然选择和自然遗传等生物进化机制的一种搜索算法，主要通过选择、重组和变异这三种操作实现优化问题的求解
进化算法原则：

  • 适用性原则
  • 可靠性原则
  • 收敛性原则
  • 稳定性原则
  • 生物类比原则

遗传算法

染色体编码

  • 二进制编码
    • 优点：类似于生物染色体组成，遗传操作易实现
    • 缺点：有较大hamming距离，降低搜索效率
  • Gray编码：将二进制编码通过一个变换进行转换得到的编码

  • 实数编码

    群体初始化

    随机数初始化方法

    适应值评价

    用于评估各个染色体的适应值，进而区分优劣，规定适应值越大的染色体越优
    适应函数的尺度变换（定标）：对适应度函数值域的某种映射变换。

  • 欺骗问题：妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题

  • 过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。

  • 停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。

    选择/复制

    从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。个体适应度越高，其被选择的机会就越多。

  • 适应度比例方法或蒙特卡罗法 —— 各个个体被选择的概率和其适应度值成比例

  • 排序方法—— 各个个体被选择的概率和其适应度值成比例
  • 轮盘赌方法
  • 锦标赛选择方法：随机选择个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。
  • 最佳个体保存方法：把群体中适应度最高的个体不进行交叉而直接复制到下一代中
  • 随机竞争方法：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。

    交配

    对于每个染色体，如果Random(0, 1)小于Pc（自定） 则表示该染色体可进行交配操作（其中Random(0, 1) 为 [0, 1] 间均匀分布的随机数），否则染色体不参与交配直接复制到新种群中。
    交配时：随机产生一个有效的交配位置，染色体交换位于该交配位置后的所有基因。

    变异

    对于交配后新种群中染色体的每一位基因，根据变异概率Pm判断该基因是否进行变异。如果Random(0, 1)小于Pm，则改变该基因的取值（其中Random(0, 1)为[0, 1]间均匀分布的随机数）。否则该基因不发生变异，保持不变。

    处理流程

    image.png

    例子

    ch6-智能计算及其应用 (1).pdf

群智能算法

受动物群体智能启发的算法称为群智能算法（swarm algorithms，SI） 。由简单个体组成的群落与环境以及个体之间的互动行为称为“群智能”。

和进化算法的区别

  • 相同点
    • 都是研究个体和群体的关系
    • 存在个体与群体的信息传递
    • 为了解决实际问题
    • 属于随机搜索算法
  • 不同点
    • 群智能模拟的是个体之间的协同作用，而进化算法主要模拟的是适者生存的自然选择机制。

粒子群算法

image.png
第一部分为前一时刻速度对下一时刻的影响，第二部分为个体认知分量，第三部分为群体分量

  • φ1 > 0，φ2 > 0，则称该算法为 PSO全模型
  • φ1 > 0，φ2 = 0，则称该算法为 PSO认知模型
  • φ1 = 0，φ2 > 0，则称该算法为 PSO社会模型
  • φ1 > 0，φ2 > 0且g≠i，则称该算法为 PSO无私模型

算法流程

  1. 初始化每个粒子，即在允许范围内随机设置每个粒子的初始位置和速度。 初始化，设置初始位置和速度
  2. 评价每个粒子的适应度 适应度
  3. 设置每个粒子的 Pi。对每个粒子，将其适应度与其经历过的最好位置 Pi 进行比较，如果优于 Pi，则更新 Pi。 更新pi
  4. 设置全局最优值 Pg。对每个粒子，将其适应度与群体经历过的最好位置 Pg 进行比较，如果优于 Pg ，则更新 Pg。
  5. 依据公式更新粒子的速度和位置。 更新位置
  6. 检查终止条件。如果未达到设定条件（预设误差或者迭代的次数），则返回第（2）步。