研究生课程：高级人工智能-第13讲 群体智能

《高级人工智能》课程笔记：第13讲 群体智能

第13讲 群体智能

群体智能

• 群体智能指的是无智能或者仅具有相对简单智能的主体通过合作涌现出更高智能行为的特性
  • 其中的个体并非绝对的无智能或只具有简单智能，而是相对于群体表现出来的智能而言是简单的。
• 单个复杂个体可以实现的功能，同样可以由大量简单的个体通过群体合作实现，后者的优势在于它更健壮、灵活和经济。
• 群体智能利用群体优势，在没有中心控制的条件下，寻找解决复杂问题的新思路

集群智能：众多无智能的个体，通过相互之间的简单合作所表现出来的智能行为

博弈：具备一定智能的理性个体，按照某种机制行动，在群体层面体现出的智能

众包：设计合适的机制，激励个体参与，从而实现单个个体不具备的社会智能

集群智能

分布式 、 自组织的（自然/人造）系统表现出的一种群体智能

集群智能系统一般由一群简单的智能体构成，智能体按照简单的规则彼此进行局部交互，智能体也可以环境交互

灵感通常来自生物系统（蚁群、鸟群、兽群、粒子群）

特点：

• 分布式：无中心控制
• 随机性：非确定性
• 自适应：个体根据环境进行策略调整
• 正反馈：个体好的尝试会对个体产生正反馈
• 自发涌现：会在群体层面涌现出一种智能

蚁群优化算法

一种解空间搜索方法，适用于在图上寻找最优路径

算法形式化：

• 每个蚂蚁对应一个计算智能体
• 蚂蚁依概率选择候选位置进行移动
• 在经过的路径上留下“信息素”
• “信息素”随时间挥发
• “信息素”浓度大的路径在后续的选择中会以更高的概率被选取

TSP问题蚁群算法流程

蚁群大小：一般情况下，蚁群中的蚂蚁个数不超过TSP图中节点的个数

终止条件：

• 设定迭代轮数
• 设定最优解连续保持不变的迭代轮数

思想：局部随机搜索+自增强

缺点：

• 收敛速度慢
• 易于陷入局部最优
• 对于解空间为连续的优化问题不适用

粒子群优化算法

• 粒子群优化算法是一种基于种群寻优的启发式搜索算法 。在 1995年由Kennedy和Eberhart首先提出来的。
• 它的主要启发来源于对鸟群群体运动行为的研究。我们经常可以观察到鸟群表现出来的同步性，虽然每只鸟的运动行为都是互相独立的，但是在整个鸟群的飞行过程中却表现出了高度一致性的复杂行为，并且可以自适应的调整飞行的状态和轨迹。
• 鸟群具有这样的复杂飞行行为的原因，可能是因为每只鸟在飞行过程中都遵循了一定的行为规则，并能够掌握邻域内其它鸟的飞行信息。
• 粒子群优化算法借鉴了这样的思想，每个粒子代表待求解问题搜索解空间中的一个潜在解，它相当于一只鸟，“飞行信息”包括粒子当前的位置和速度两个状态量。
• 每个粒子都可以获得其邻域内其它个体的信息，对所经过的位置进行评价，并根据这些信息和位置速度更新规则，改变自身的两个状态量，在“飞行”过程中传递信息和互相学习，去更好地适应环境。
• 随着这一过程的不断进行，粒子群最终能够找到问题的近似最优解。

是一种随机优化方法，通过粒子群在解空间中进行搜索，寻找最优解（适应度最大的解）

构成要素

• 粒子群：
  • 每个粒子对应所求解问题的一个可行解
  • 粒子通过其位置和速度表示
    • 粒子在第轮的位置：
    • 粒子在第轮的速度：
• 记录：
  • ：粒子的历史最好位置
  • ：全局历史最好位置
• 计算适应度的函数-适应度：

算法过程描述

• 初始化
  • 初始化粒子群：每个粒子的位置和速度，即和
  • 和
• 循环执行如下三步直至满足结束条件
  • 计算每个粒子的适应度：
  • 更新每个粒子历史最好适应度及其相应的位置，更新当前全局最好适应度及其相应的位置
  • 更新每个粒子的速度和位置
    • 
    • 

粒子速度更新公式：

1. 惯性项：保持原速度不变的倾向
2. 记忆项：回到历史最好位置的倾向
3. 社会项：走向粒子群全局最好位置的倾向
4. 权重参数：一般取值为2
5. 随机参数：0和1之间的随机数

算法终止条件：

• 迭代的轮数
• 最佳位置连续未更新的轮数
• 适应度函数的值到达预期要求

速度更新参数：又称加速度参数，用来控制粒子当前最优位置和粒子群当前最优位置对粒子飞行速度的影响

• ：每个微粒执行局部搜索；
• ：微粒群转化为一个随机爬山法
• ：微粒逐渐移向和的加权均值
• ：算法比较适合于单峰优化问题
• ：算法比较适合于多峰优化问题

惯性权重：速度冲量导致微粒按照先前速度方向继续移动。提出一个惯性权重来控制先前微粒速度的影响

粒子群优化算法和遗传算法相比

• 遗传算法强调“适者生存”，不好的个体在竞争中被淘汰； PSO 强调“协同合作”，不好的个体通过学习向好的方向转变。
• 遗传算法中最好的个体通过产生更多的后代来传播基因；PSO 中的最好个体通过吸引其它个体向它靠近来施加影响。
• 遗传算法的选择概率只与上一代群体相关，而与历史无关，群体的信息变化过程是一个Markov链过程；而PSO中的个体除了有位置和速度外，还有着过去的历史信息（pBest, gBest）。

优点：

• 易于实现
• 可调参数较少
• 所需种群或微粒群规模较小
• 计算效率高，收敛速度快

缺点：和其它演化计算算法类似，不保证收敛到全局最优解

粒子群优化算法代码

import numpy as np

def cal(x):
    return x*x*x-5*x*x-2*x+3

x_min = -2
x_max = 5

p_num = 1000

g_best_max = 1
g_best_max_i = 0

g_best_min = 1
g_best_min_i = 0

x_MAX = (x_max - x_min) * np.random.random_sample((p_num,)) + x_min
v_MAX = (x_max - x_min) * np.random.random_sample((p_num,)) + x_min

x_MIN = (x_max - x_min) * np.random.random_sample((p_num,)) + x_min
v_MIN = (x_max - x_min) * np.random.random_sample((p_num,)) + x_min

p_best_max = np.ones_like(x_MAX)
p_best_min = np.ones_like(x_MAX)

for i in range(1,10000):

    f_max = cal(x_MAX)
    f_min = cal(x_MIN)

    t_max = cal(p_best_max)
    t_min = cal(p_best_min)

    p_best_max = np.where(t_max > f_max, p_best_max, x_MAX)
    p_best_min = np.where(t_min < f_min, p_best_min, x_MIN)


    if np.max(f_max) > g_best_max:
        g_best_max = np.max(f_max)
        g_best_max_i = x_MAX[np.argmax(f_max)]

    if np.min(f_min) < g_best_min:
        g_best_min = np.min(f_min)
        g_best_min_i = x_MIN[np.argmin(f_min)]

    v_MAX = v_MAX + (p_best_max - x_MAX) + (g_best_max - x_MAX)
    x_MAX = x_MAX + v_MAX

    x_MAX = np.where(x_MAX > x_max,x_max,x_MAX)
    x_MAX = np.where(x_MAX < x_min,x_min,x_MAX)

    v_MIN = v_MIN + (p_best_min - x_MIN) + (g_best_min - x_MIN)
    x_MIN = x_MIN + v_MIN

    x_MIN = np.where(x_MIN > x_max,x_max,x_MIN)
    x_MIN = np.where(x_MIN < x_min,x_min,x_MIN)

print(g_best_max_i)
print(g_best_min_i)