群智能算法是一种新型的仿生类进化算法,主要包括蚁群优化算法和粒子群算法.群智能算法具有较强的鲁棒性,采用分布式计算机制,并且易于实现,已在众多领域得到了广泛的应用.本文主要围绕蚁群优化算法和微粒群算法的理论及其应用,就如何求解大规模旅行商(Traveling Salesman Problem, TSP)问题、连续性优化问题、约束优化问题、无线传感器网络路由优化问题进行了研究.本文的主要工作概括如下:
1.针对大规模TSP问题,提出了一种基于模块度分簇的改进蚁群算法.该算法首先借鉴网络中的分簇原理,基于模块度的分簇算法将TSP问题中的城市划分为若干个簇,降低了问题的维数,并提出模块度的概念来度量所得到的簇结构和实际TSP问题网络匹配的程度;其次,基于信息素扩散的改进蚁群算法求解簇间的连接顺序,即求解分簇得到的小规模TSP问题的最优解,在基于信息素扩散的改进蚁群算法中,从多方面模拟真实蚂蚁的行为,定义了新的信息素扩散挥发规则,增强了蚂蚁之间的合作,使其快速找到最优解,同时增加扰动因子避免其陷入局部最优解,并且分析了其全局收敛性,实例测试结果表明了算法的有效性;然后,构造了求解簇内最短路径的基于信息素扩散的改进蚁群算法;最后,将所有簇内和簇间的解按照一定的规则组成了原TSP问题的解.仿真实验结果表明该算法适合求解大规模TSP问题,与已有算法相比,解的质量和收敛速度均有了较明显的提高.
2.针对蚁群算法在连续空间函数优化中应用的瓶颈,提出了一种蚁群混合算法求解连续空间问题,定义了新的蚁群信息素更新规则、蚁群在解空间的寻优方式和蚁群行进策略.为了克服蚁群算法搜索时间过长,易陷于局部最优等缺点,在搜索过程中嵌入了改进的Alopex算法,该算法具有快速搜索和摆脱局部最优解的能力,实验结果表明了蚁群混合算法的有效性.
3.针对标准微粒群算法不能保证全局收敛性问题,提出了一种随机混合微粒群算法.在随机微粒群算法中,将惯性权重设置为零,减少了关键参数对算法性能的影响,提高了算法的通用性;在保证算法全局收敛性的同时,结合Alopex算法重新生成停止进化粒子的位置,有效地避免了算法因单一搜索机制引起地停滞现象.将该算法应用于复杂多维函数,取得了较好的效果,为解决较复杂的函数优化问题提供了一种可行的方法.
4.针对约束优化问题,提出了一种基于协同进化的微粒群算法.该算法在标准微粒群算法的基础上,采用“保留最优,调节部分”的确定型选择策略,利用进化中个体之间的差异,提出协同算子公式,引导进化方向,使个体之间相互利用信息,更新微粒的位置进化方程;同时,提出基于不可行度的约束处理方法,根据不可行度和不可行度阀值提出新的竞争选择准则,并由此给出新的适应值函数引导群体加强对约束边界的搜索.基于典型的约束优化问题的实验结果表明:该算法可行有效,尤其对解决复杂问题表现出较优的性能.
5.研究了蚁群算法在无线传感器网络路由协议中的应用.无线传感器网络路由协议的一个重要目标就是要合理高效地使用网络中各传感器节点的能量,延长网络寿命.文中提出了一种基于蚁群算法的无线传感器网络分簇路由协议.该方法首先利用网络自身拓扑结构,基于模块度的分簇算法得到一个稳定的簇结构,无需每轮循环都构造簇,从而节省了构造簇的开销;其次,根据每个簇内节点的剩余能量以及簇内节点的分布情况,给出了新的簇头选择函数;然后,提出基于蚁群算法的簇间多跳路由算法,该算法以如何均衡传输路径上消耗的能量和簇头节点的剩余能量为出发点,制定了新的蚂蚁转移概率和信息素更新规则,通过实验仿真,并与已有较好算法相比较,验证了算法的有效性.
