群体智能之集群智能
目录
5.集群智能-蚁群优化算法（ACO: Ant Colony Optimization ），适用于离散问题最优解
5.2 ACO: Ant Colony Optimization
6.粒子群优化算法 PSO: Particle Swarm Optimization 求解连续解空间的优化问题
1.写在前面
人工智能的发展史上，大概分为三大学派：
（1）符号主义：符号逻辑，专家系统；规则驱动的确定性智能
（2）联结主义：神经网络、深度学习；数据驱动不确定性智能
（3）行为主义：强化学习、涌现智能.；交互驱动的涌现智能
2.群体智能
- 群体智能指的是无智能或者仅具有相对简单智能的 主体通过合作涌现出更高智能行为的特性 。其中的个体并非绝对的无智能或只具有简单智能，而是 相对于群体表现出来的智能而言是简单的。
- 单个复杂个体可以实现的功能，同样可以由大量简 单的个体通过群体合作实现，后者的优势在于它更 健壮、灵活和经济。
- 群体智能利用群体优势，在没有中心控制的条件下， 寻找解决复杂问题的新思路
3.群体智能分类
- 集群智能 ： 众多无智能的个体，通过相互之间的简单合作所表现出 来的智能行为（个体智能比较低）
- 博弈 ：具备一定智能的理性个体，按照某种机制行动，在群体 层面体现出的智能（理性、自私，优化个人目标，达到社会最优）
- 众包 ： 设计合适的机制，激励个体参与，从而实现单个个体不 具备的社会智能（激励个人（真实的人））
4.集群智能
- 集群智能是分布式、自组织的（自然/人造）系统 表现出的一种群体智能
- 集群智能系统一般由一群简单的智能体构成，智 能体按照简单的规则彼此进行局部交互，智能体 也可以环境交互
- 灵感通常来自生物系统 蚁群、鸟群、兽群 、粒子群
4.1 集群智能的特点
- 分布式：无中心控制
- 随机性：非确定性
- 自适应：个体根据环境进行策略调整
- 正反馈：个体好的尝试会对个体产生正反馈
- 自发涌现：会在群体层面涌现出一种智能
4.2 集群智能代表性方法
- 蚁群优化算法
- 粒子群优化算法
5.集群智能-蚁群优化算法（ACO: Ant Colony Optimization ），适用于离散问题最优解
我们思考一个问题，蚂蚁寻找食物的过程。当两个路径等长的时候，让足够多的蚂蚁去自主选择，可能选择走两条路径的蚂蚁数目是比较接近的。如果上面的路径短，再重复试验，上面的蚂蚁会明显多余下面路径上的蚂蚁，我们说这个是一个集群智能中的蚁群问题。
假设路径不等长的情况下，我们得到下面这个图，上面路径为下面路径的一半：
- 蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。上面的路径长度是下面路径长度的一半
- 假设初始时每条路线分配一只蚂蚁，每个时间单位行走一步，上图为经过9个时间单位时的情形
- 走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。
经过18个时间单位时的情形： 走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚 好走到D点。
5.1 蚁群寻食过程分析
- 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单 位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物， 此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路 线往返了一趟，每一处的信息素为2个单位，其比值为2：1。
- 寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增 派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个 时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。
- 若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只）， 而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上 的信息素单位积累为24和6，比值为4：1。
- 若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线， 而都选择ABD路线。
5.2 ACO: Ant Colony Optimization
- 一种解空间搜索方法
- 适用于在图上寻找最优路径
5.3 形式化
- 每个蚂蚁对应一个计算智能体
- 蚂蚁依概率选择候选位置进行移动
- 在经过的路径上留下“信息素”（Pheromone）
- “信息素”随时间挥发
- “信息素”浓度大的路径在后续的选择中会以更高 的概率被选取
5.4 旅行商问题的蚁群优化求解
整个算法实现图示：
蚁群大小 ： 一般情况下，蚁群中的蚂蚁个数不超过TSP图中节点的个数
终止条件：（1）设定迭代轮数 （2） 设定最优解连续保持不变的迭代轮数
思想： （1）局部随机搜索+自增强 （2） 鲁迅：“世界本无路，走的人多了也就有了路”
缺点 ：（1） 收敛速度慢 （2） 易于陷入局部最优 （3） 对于解空间为连续的优化问题不适用
6.粒子群优化算法 PSO: Particle Swarm Optimization 求解连续解空间的优化问题
是一种随机优化方法 ，通过粒子群在解空间中进行搜索，寻找最优解（适应度 最大的解），在整个集合上随机选取几个点，值小的点会看到值大的点，如果要是求最大值，值比较小的点就会向值大的点移动（向优秀的同学学习）。
6.1 粒子群优化算法构成要素
6.2 粒子群优化算法算法过程描述
6.3 粒子群优化算法粒子位置和速度更新示例
6.4 粒子群优化算法粒子速度更新公式解读
6.5 粒子群优化算法算法终止条件
- 迭代的轮数
- 最佳位置连续未更新的轮数
- 适应度函数的值到达预期要求
6.6 粒子群优化算法速度更新参数分析
6.7 粒子群优化算法改进
6.8 粒子群优化算法和遗传算法相比
- 遗传算法强调“适者生存”，不好的个体在竞争中被淘 汰；PSO强调“协同合作”，不好的个体通过学习向 好的方向转变。
- 遗传算法中最好的个体通过产生更多的后代来传播基因； PSO中的最好个体通过吸引其它个体向它靠近来施加 影响。
- 遗传算法的选择概率只与上一代群体相关，而与历史无 关，群体的信息变化过程是一个Markov链过程；而 PSO中的个体除了有位置和速度外，还有着过去的历 史信息（pBest、gBest）
6.9粒子群优化算法优缺点
优点：
- 易于实现；
- 可调参数较少；
- 所需种群或微粒群规模较小；
- 计算效率高，收敛速度快
缺点：
- 和其它演化计算算法类似，不保证收敛到全局最优解
6.10 粒子群优化算法小结
- 一种随机优化算法
- 适用于求解连续解空间的优化问题
7.课后作业
代码参考：https://github.com/guofei9987/scikit-opt