群体智能
知识点：
- 演化计算：蚁群优化算法、粒子群优化算法
- 博弈论
- 课程复习使用
一. 群体智能
群体智能：Social/Colletive Intelligence, “无智能”或者仅具有相对简单智能的个体通过合作表现出更高智能行为的特性。其中的“无智能”/简单智能并不是绝对意义上的智能，而是相对于群体表现出来的相对智能。（众人拾材火焰高）
集群智能：Swarm Intelligence, 众多无智能的个体，通过相互之间的简单合作，所表现出来的智能行为。
特点：
- 分布式，无中心控制
- 随机性，非确定性
- 自适应，个体根据环境进行策略调整
- 正反馈，个体好的尝试会对个体产生正反馈
- 自发涌现，会在群体层面涌现出一种智能
博弈： Game Theory, 具备一定智能的理性个体，按照某种机制行动，群体层面表现出的智能。
众包：Crowdsourcing, 设计合适的机制，激励个体参与，从而实现单个个体不具备的社会智能。
二. 演化计算
2.1 蚁群优化算法
Ant Colony Optimization, AOC. 在图上寻找最优路径问题。
形式化：蚂蚁(智能体) 依据一定的概率选择位置进行移动，途中会留下信息素，信息素会随时间挥发，且信息素浓度与该位置被选择的概率成正相关。
用蚁群优化算法求解TSP问题：
- TSP问题描述：给定n个城市及每对城市之间的距离，求解访问每个城市一次、并回到起点的最短回路。
- 符号表示：n个城市的有向图$G = (V,E)$，其中 $V={1,2,\dots,n}$,$E={(i,j)|i,j\in V}$,$d_{ij}$为节点之间的距离
- 目标函数：$min f(w)=\sum_{l=1}^{n} d_{i_{l}i_{l+1}}$,其中，$s=(i_{1},\dots,i_{n})$
- 根据信息素来选择下一个城市的概率计算为：
$$
p_{i j}^{k}(t)=\left{\begin{array}{ll}
\frac{\left(\tau_{i j}(t)\right)^{\alpha}\left(\eta_{i j}(t)\right)^{\beta}}{\sum_{k \in \text { allowed }}\left(\tau_{i k}(t)\right)^{\alpha}\left(\eta_{i k}(t)\right)^{\beta}} & j \in \text { allowed } \
0, & \text { otherwise }
\end{array}\right.
$$
其中，i为当前城市,j为下一城市，$\tau_{i j}(t)$为边$(i,j)$上的信息素浓度, $\eta_{i j}(t)=1/d_{i j}$是根据距离定义的启发式函数，$\alpha$，$\beta$反映了信息素与启发信息的相对重要性。
- 信息素更新
$$\begin{array}{l}\Delta \tau_{i j}^{k}=f(x)=\left{\begin{array}{cc}\frac{Q}{L_{k}}, & (i, j) \in w_{k} \0, & \text { otherwise }\end{array}\right. \\tau_{i j}(t+1)=\rho \cdot \tau_{i j}(t+1)+\Delta \tau_{i j} \\Delta \tau_{i j}=\sum_{k=1}^{m} \Delta \tau_{i j}^{k}\end{array}$$
其中：$Q$ 为常数，$w_k$ 表示第 $k$ 只蚂蚁在本轮迭代中走过的路径，$L_k$ 为路径长度，$\rho$ 为小于 1 的常数，反映信息素挥发速度。即路径越长，信息素越小。
- 算法流程
1 | 1. 初始化 随机放置蚂蚁 |
- 缺点：收敛速度慢（与m,n取值相关），容易陷入局部最优解(探索与开发的平衡)，不适于求解连续空间的优化问题。
1.2 粒子群优化算法
Particle Swarm Optimization, PSO. 求解连续解空间的优化问题，主要启发来源于对⻦群群体运动行为的研究。
- 形式化：每一只鸟(称为粒子，代表一个可行解解) 都有自己的状态信息：位置与速度，同时可以获得领域内其它鸟的信息，根据这些信息不断的改变自己的状态，去更好的适应环境，最终能找到最近最优解。
- 算法流程
其中，$x_{n}^{(i)}$为粒子i 在第 n 轮的位置，$v_{n}^{(i)}$为粒子i 在第 n 轮的速度，$p_{best}^{(i)}$为粒子i 的历史最好位置,$g_{best}^{(i)}$全局最好的历史位置。
速度更新公式包含三项，第一项为惯性项（保持原速度不变的倾向），第二项为记忆项（回到历史最好位置的倾向），第三项为社会项（走向粒子群全局最好位置的倾向）。
-
算法终止条件：迭代次数，最佳位置连续为更新的次数，适应度函数的值达到预期要求。
-
优化：对惯性项加上一个权重
-
优点：收敛速度快，所需微粒群规模较小
-
缺点：不保证收敛到全局最优解
蚁群算法和粒子群算法的相同点：都基于自然界的生物行为；都使用多个个体（蚂蚁或粒子）组成的群体来寻找全局最优解；都可用于解决各种优化问题；都是不确定算法。
三. 博弈
-
局中人：在博弈中有权决定自己行动方案的博弈参加者。重要假设：局中人是自私的理性人。
-
策略：博弈中可供局中人选择的行动方案。
-
策略集合：局中人可以选择的策略的集合。
-
局势：所有局中人选择的策略形成的策略组。
-
博弈类型
静态博弈（同时选择策略） vs 动态博弈（按顺序选择策略）
竞争博弈（炒股） vs 合作博弈（结盟）
完全信息博弈（每个局中人对所有局中人的策略及效用充分了解） vs 不完全信息博弈
-
效用函数，payoff，通常用$U$来表示，是局势、时间（动态博弈中）的函数。每个局中人都有自己的效用函数。希望效用函数越大越好。
-
最佳应对：对局中人1，若 $U_1(s,t) \ge U_1(s’,t)$ ，其中 s’ 是局中人除 s 外的其它策略，t 为局中人2的策略，$U_{1}(s,t)$为局中人1 从这组决策中获得的收益，则称策略 𝑠 是局中人1对局中人2的策略 t 的最佳应对。
-
最优策略：如果一个局中人的某个策略对其它局中人的任何策略都是最佳应对，那么这个策略就是该局中人的占优策略。
-
纳什均衡：如果一个局势下，每个局中人的策略都是相对其他局中人当前策略的最佳应对，则称该局势是一个纳什均衡。也就是博弈进入了僵局。不存在纯策略的纳什均衡。
- 混合策略：每个局中人以某个概率分布在其策略集合中选择策略。
- 混合策略纳什均衡：给定其他局中人的策略选择概率分布的情况下， 当前局中人选择任意一个(纯)策略获得的期望效用相等。
- 纳什定理：任何有限博弈都至少存在一个纳什均衡。但寻找博弈的纳什均衡是困难的。
- 帕累托最优：对于一组策略选择(局势)，若不存在其他策略选择 使所有参与者得到至少和目前一样高的回报，且至少一个参与者会得到严格较高的回报，则这组策略选择为帕累托最优。
- 社会最优：使参与者的回报之和最大的策略选择(局势)。社会最优的结果一定也是帕累托最优的结果，但帕累托最优不一定是社会最优。
-
机制设计：设计一个博弈，使其达到预期结果，如实现社会最优。
-
maxmin策略，以我为主，最小化损失，抑制风险
-
minmax策略，抑制对手
-
匹配市场
匹配定理：对于左右两部节点数相同的二部图，如果其不存在完全匹配（刚好一一对应），那么该二部图一定包含一个受限集。
匹配的效用：成功匹配的估价之和，称为匹配的效用。
最优匹配：效用最大的匹配。最优匹配对于个体而言不一定是最优的，甚至是最差的。
市场结清：每个卖方和买方都成交了。市场结清价格总是存在，且使得买卖双方总效用最优。
-
中介市场
买方和卖方通过中介交易。竞争不充分的地方，中介垄断价格。竞争充分的地方，中介的收益趋近于0。
-
议价权
问题描述：给定一个网络，每个节点代表一个人，达成议价约定的两个人可以分配价值为1的东西。
不稳定边：对于结局中未参与配对的边，如果边的两个端点获得的收益之和小于1，则称这条边为不稳定边。
稳定结局：不存在不稳定边。
有备选项的议价：A、B两人议价，确定分配比例。A的备选项收益为x ，B的备选项为y 。要求 $x+y\le 1$，否则A和B达不成交易。则定义剩余价值为$s=1-x-y$。
纳什议价解：A的收益 $x+\frac{s}{2}=\frac{1+x-y}{2}$, B的收益 $y+\frac{s}{2}=\frac{1-x+y}{2}$。
均衡结局：结局中的任意一个参与配对的边都满足纳什议价解的条件。
四. 参考资料
中国科学院大学 计院高级人工智能课程课件