计算智能主要算法研究

　　(2) 组合优化.对较大规模的组合问题，目前在计算机上用枚举法很难或甚至不可能求出其精确最优解，而遗传算法则较为方便的求得其满意解.实践证明，遗传算法对于组合优化中的NP完全问题非常有效.

　　(3) 生产调度问题.遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面都有有效的应用.

　　(4) 图像处理.图像处理是计算机视觉中的一个重要研究领域.遗传算法在图像处理的优化计算如模式识别、图像恢复、图像边缘特征提取等方面都有很好的应用.

　　2.4 蚁群算法

　　2.4.1  蚁群算法的生物学基础

　　其原理可大致描述如下：蚂蚁属于群居昆虫，个体行为极其简单，而群体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找到最优路径。人们通过大量的研究发现，蚂蚁个体之间是通过在其所经过的路上留下一种可称之为“信息素”（pheromone）的物质来进行信息传递的。随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。同时，该物质随着时间的推移会逐渐挥发掉，于是路径的长短及该路径上通过的蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象。蚂蚁个体之间就是通过这种信息交流达到最快捷搜索到食物源的目的。

　　2.4.2  蚁群算法描述

　　蚁群算法就是模拟蚂蚁搜索食物的过程,该算法的思想是:用蚂蚁的行走路线表示待求解问题的可行解,每只蚂蚁在解空间中独立地搜索可行解,解的质量越高,在“行走路线”上留下的信息素也就越多,随着算法的推进,代表较好解的路线上的信息素逐渐增多,选择它的蚂蚁也逐渐增多,最终整个蚁群在正反馈的作用下集中到代表最优解的路线上,也就找到了最优解。

　　蚁群算法的核心有三条。第一，选择机制：信息素越多的路径，被选中的概率越大；第二，信息素更新机制：路径越短，迹增加越快；第三，协作机制：个体之间通过信息素进行交流。

　　蚁群算法的特点是不仅能够智能搜索、全局优化，而且具有稳健性（鲁棒性）、正反馈、分布式计算、易与其它算法结合等特点[4]。利用正反馈原理，可以加快进化过程；分布式计算使该算法易于并行实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合，可改善算法的性能；由于鲁棒性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题。但是，蚁群算法还不像其它的启发式算法那样已形成系统的分析方法和具有坚实的数学基础。参数的选择更多的是依靠实验和经验，没有定理来确定，而且它的计算时间偏长。

　　2.4.3  基于蚁群算法的优化设计

　　蚁群算法主要用于求解不同的组合优化问题，一类应用于静态组合优化问题，另一类用于动态组合优化问题。静态问题指一次性给出问题的特征,在解决问题过程中,问题的特征不再改变。动态问题被定义为一些量的函数,这些量的值由隐含系统动态设置。

　　基于蚁群算法优化设计在静态组合中的优化应用包括[5]：旅行商问题(TSP)、二次分配问题(QAP)、车间任务调度问题(JSP)、车辆路线问题(VRP)、图着色问题(GCP)、有序排列问题(SOP)。在动态组合中的优化应用包括：大规模集成电路中的综合布线以及电信网络中的路由等方面。同时，蚁群算法在其他领域上的组合问题上都取得比较理想的效果，如管线敷设问题、机构同构判定问题、开关盒布线问题、学习模糊规则问题等

  【中安网原创稿件声明】转载中安网文章时应遵循以下三个规则：1、保持原创文章中图表、图片、音视频的完整性；2、完整标注文章作者［文章前后有说明］；3、转载中安网原创中部分内容也要完整标注来源"中安网"，违者本网将依法追究。