智能信息处理读书笔记.doc

智能信息处理读书笔记

在上了李兴明老师的通信网络中的智能信息处理这门课后，作为课程补充，我初略的阅读了清华大学出版社，孙红编写《智能信息处理导论》一书。这本书从智能信息处理产生的背景和发展历史、基本理论和方法、应用以及研究现状和发展趋势等方面，介绍了模糊理论及其应用、神经网络信息处理及其应用、云信息处理及其应用、可拓信息处理及其应用、粗集信息处理及其应用，遗传算法、免疫算法、蚁群算法优化处理、量子智能信息处理、多元信息融合和信息融合技术及其应用。
从一开始的概述中我了解到，智能信息处理是一种模拟人与自然界其他生物处理信息的行为，建立处理复杂系统信息的理论、算法和系统的方法和技术，面对不确定性系统和不确定性现象的现象处理问题。智能信息处理在复杂系统建模、系统分析、系统决策、系统控制、系统优化和系统设计等领域具有广大的应用前景。对于这样一个有着发展前景的学科，我对这本书进行了进一步阅读。由于时间有限，我仅选取几章内容进行精读。下面我就遗传算法与蚁群算法来做一个读书笔记，谈一些我在读书时的感受与理解。
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。
下面我根据自己的理解来写一下遗传算法的基本运算过程：
第一步：初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
第二步：个体评价：计算群体P(t)中各个个体的适应度。
第三步：选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
第四步：交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。
第五步：变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
第六步：终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
在了解了遗传算法后，我对遗传算法的有别于传统算法的特点谈一些自己的理解。
首先遗传算法是从问题解的串集开始搜索，而不是从单个解开始。我认为这是遗传算法与传统优化算法的最大区别所在。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。
其次遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。而且遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。我认为这一特点使得遗传算法的应用范围大大扩展。
最后遗传算法具有自组织、自适应和自学习性的特点。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。
在对遗传算法做了进一步的了解后，可以看出遗传算法也存在一些明显的缺点，比如由于算法本身是在模拟生物界的一个遗传进化过程，那么这样的方式就会让算法在后期由于空间较大，搜索速度会很慢，而且我觉得这样的算法对一开始的种群选择要求比较高，而且存在很大的不确定性，稳定性不佳。对此书中有提到的是可以将遗传算法与一些启发式算法相结合，来解决这些问题。那么由于蚁群算法也是一种启发式算法，所以我下面先阅读蚁群算法。
蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。这个算法的原理就是蚂蚁在运动过程中，会留下一种称为信息素的东西，并且会随着移动的距离，播散的信息素越来越少，所以往往在家或者食物的周围，信息素的浓度是最强的，而蚂蚁自身会根据信息素去选择方向，当然信息素越浓，被选择的概率也就越大，并且信息素本身具有一定的挥发作用。 蚂蚁的运动的一个规则可以简单归纳如下：
1、当周围没有信息素指引时，蚂蚁的运动具有一定的惯性，并有一定的概率选择其他方向
2、当周围有信息素的指引时，按照信息素的浓度强度概率性的选择运动方向
3、找食物时，蚂蚁留下家相关的A信息素，找家时，蚂蚁留下食物相关的B信息素，并随着移动距离的增加，洒播的信息素越来越少
4、随着时间推移，信息素会自行挥发
下面我对这样一个算法根据自己的理解构建一个简单的例子，如果现在有两条通往食物的路径，一条较长路径A,一条较短路径B,虽然刚开始A,B路径上都有蚂蚁，又因为B比A短，蚂蚁通过B花费的时间较短，随着时间的推移和信息素的挥发，逐渐的B上的信息素浓度会强于A，这时候因为B的浓度比A强，越来越多多蚂蚁会选择B，而这时候B上的浓度只会越来越强。如果蚂蚁一开始只在A上呢，由于蚂蚁的移动具有一定小概率的随机性，所以当一部分蚂蚁找到B时，随着时间的推移，蚂蚁会收敛到B上。
对于蚁群算法这样一个元启发式的算法，我也从书中对其特点做一个归纳：
1、采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解。
2、每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯。
3、搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率。
4、启发式的概率搜索方式不容易陷入局部最优，易于寻找到全局最优解。
但是同样的，蚁群算法自然也有着自己的不足之处，比如蚁群很明显在一开始的信息素是不足的，这样子算法的收敛是比较慢的，而且开销也相对比较大。同时我们也可以想象要是蚂蚁一直去一个食物很多的地方，那么这个路径上的信息素浓度就会很高，这样子就算旁边新出现了一个更好的食物源，那么蚂蚁也可以不会去，这样子对应在算法上就会出现局部最优的情况。与之前的遗传算法对比一下我发现两者在搜索速度上是互补的，遗传算法是一开始快，后面慢，而蚁群算法是反过来的，所以这应该就是之前书中提到的提出按双方可以与启发式算法结合的原因。所以我下面又找了一篇关于遗传算法与蚁群算法融合的论文，来对这两个算法的应用做一个更深的了解。
遗传算法具有快速全局搜索能力，但是对于系统的反馈信息却没有利用，往往导致大量无为的冗余迭代，求精确解效率低。蚁群算法具有并行，分布，全局收敛能力，但是搜索初期信息素匮乏，导致搜索初期信息素积累时间较长，求解速度慢。为了克服这两种算法各自的缺陷，形成优势互补，我所研读的两篇文献所采用的方法并没有太大的区别。都是首先利用遗传算法的随机搜索、快速、全局收敛性产生有关问题的初始解，并将其转化为蚁群算法的初始信息素分布，然后利用蚁群算法的并行性、正反馈机制以及求解效率高等特征寻求最优解。在遗传算法运行过程中动态确定遗传算法与蚁群算法的融合时机，避免由于遗传算法过早或过晚结束而影响算法的整体性能。通过这样的方式让两种算法得到一定程度的优势互补，在时间效率和求解效率上面得到比较好的结果。
对于蚁群与遗传算法具体的融合方式，两篇论文采用的方式存在着些许的不同，在此我仅对赵义武、牛庆银所写的遗传算法与蚁群算法的融合研究这篇论文做一个关于其融合算法思想做一个简单的说明。这个算法里面融入了遗传算法中的交叉算子与变异算子。算法的关键在于找到这样两条曲线，分别是蚁群与遗传算法的效率曲线，并从中找到遗传算法效率显著降低的点与蚁群算法后期效率显著提升的点，然后在合适的位置从遗传算法进入蚁群算法之中。
通过这段时间的学习，我对智能信息处理多了许多了解，一方面了解了这个学科的历史与发展现状，另一方面也了解了很多不同人工智能算法，并对算法的一些基本思想与优缺点做了一些了解。我认为有理由相信在可以遇见的未来，智能信息处理的地位将进一步提高。

读书笔记阅读书目
1、 《智能信息处理导论》 孙红
2、遗传算法与蚁群算法的融合研究 赵义武、牛庆银
3、融入遗传算法的混合蚁群算法 刘立东 蔡淮