这三章讨论的是蚁群算法在实际问题中，如旅行商问题（TSP），路径规划中的应用。
蚁群算法（ACO）是解决离散组合优化问题（即每一种组合对应一个值，要寻找最小的那个值对应的组合。而问题的组合数目常常随着问题规模的增加而成指数型增加，所以枚举法根本无能为力）的一种智能算法。和其他花费巨大时间求最优解的方法不同，它能够在短时间内求得一个离最优解很近的解（有的教材上称为次优解）。这种思想在近代数值计算中经常被提到，即牺牲一定的精度来换取时间上的巨大优势。蚁群算法最早被用于解决经典的旅行商问题（TSP），取得了很好的结果，以后被陆续扩展到解决路径规划等问题，同样取得很好的结果。
总结几点：
1. 从当前点选择下一个点时，采用轮盘赌法根据概率进行选择，这样能有效地避免陷入局部最优解，而概率则由信息素（经过该点的蚂蚁越多，则信息素越大）和启发值（一种简单的情况是，从局部观点来看，一步走的距离越小，启发值就越大）组成。
2. 蚁群算法的一个关键点在于信息素的更新。在解决TSP问题中，信息素的更新只是在所有蚂蚁遍历完路径之后再对最短路径上的信息素进行增加更新，而在解决路径规划时，涉及到两种更新方式--局部更新和全局更新。全局更新的方式和在解决TSP中的信息素更新方式一致，而局部更新是指当蚂蚁经过该点时，该点的信息素就减少，它的目的是增加蚂蚁搜索未经过点的概率，避免陷入局部最优解，达到全局搜索的目的。它在程序的实现中是很关键的，如果将这部分从程序中删除，变成解决TSP时的更新方式的话，则发现最后的结果出现错误。至于背后的原因，暂时还没有想明白。
3. 解决TSP和二维路径规划问题时，针对相应的弧设定信息素值，即从某一点i到另外一点j的值；而在解决三维路径规划问题时，针对相应的节点设定信息素值。不同于前者，现在某点的信息素值在其他各点来看都是相同的。之所以这样，我想原因大概和以下因素有关。首先，三维规划问题中，定义了一个可视搜索空间，选择的空间变小，而前向的步长又相等，每次前进一个步长，所以在可视空间中，不同选择对应的弧长的差距就不明显了。这自然引发了一个问题，既如此，为什么不将可视搜索空间变大到整个的解空间呢，然后在采用弧长信息素的设置方式？此消彼长，虽然可以达到预期的目的，但是后者的计算量急剧膨胀，而对最后计算的结果改善却很小，得不偿失。
4. 前面已经说过，蚁群算法是解决离散组合优化问题的。而直观上来看，路径规划问题和离散组合优化问题不搭边。对于三维路径规划，采用meshgrid的方法将空间离散为一个个具体的点，转化为离散问题；而对于二维路径规划，采用MAKLINK图论理论，把问题转化为初始路径规划的无向网络图，其中图中的节点是线段的中点。然后，先使用Dijkstra算法找出一条初始路径，然后将各个线段分成若干段，要求蚂蚁只能经过线段的分点处，就把问题也转化成离散组合优化问题了。这种方法和有限元的方法有些类似，都是将连续问题离散化，然后再进行求解。
5. 在解决路径规划问题时，关于启发值的设定都采用了一个技巧。因为目标点已知，所以从当前点按照距离的远近和信息素的大小来选择下一个点时，相当于局部的策略，还应该和全局目标尽量保持一致，针对二维问题而言，要求当前步的局部走向和起点终点的大体走向保持一致，而对三维问题而言，要求下一个点尽量接近目标点。当然，也可以综合这两者来进行计算和选择。
6. 蚁群算法的几个特点中提到，正反馈机制；每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯；搜索过程采用分布式计算方式。（对这一点存疑，因为从程序的实现来看，并不是多个个体同时并行计算，而是一个一个蚂蚁串行计算）
7. 蚁群算法不仅可以解决无约束优化问题，也可以解决有约束优化问题，后者将其对应的信息素的值设定为0即可。
8. 书中给出的代码的终止规则都是采用的是迭代到最大迭代次数为止，只有这一个循环终止的条件。
《MATLAB智能算法30个案例分析》Chapter22--Chapter24 读书笔记
原文：http://www.cnblogs.com/liuyc/p/3540324.html