蚁群优化算法的若干研究

《蚁群优化算法的若干研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、蚁群优化算法的若干研究ＳｏｍｅＲｅｓｅａｒｃｈｅｓｏｎＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ作者姓名；冷煌专业名称：计算机系统结构指导教师；刘淑芬教授学位类别；工学博±‘论文答辩＇日期：２０１６年１２月０２日授予学位日期：年月日论文评阅人：答辩委员会组成：姓名职務工作单位巧名职称工作单位盲审专家正高级哈尔滨工业大学主席许进教授北京大学盲审专家副高级浙江大学委员孔俊教授东北师范大学盲审专家正高级重庆大学黄尉教授吉林大学王生生教

2、授吉林大学杨永健教授吉林大学胡亮教授吉林大学未经本论文作者的书面授权，依法收存和保管本论文书面版本、电子版本的任何单位和个人，均不得对本论文的全部或部分内容进行任何形式的复制、修改、发行、出租、改编等有碍作者著作奴的商业性使用（但纯学术性使用不在此限）。否则，应承担侵权的法律责任。吉林大学博±学位论文原创性声明本人郑重声明：所呈交的博±学位论文，是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中己经注明引用的内容夕ｈ，本论文不包含任何其他个人或集体已经发表或撰写过的作

3、品成果。对本文的研究做出重要贡献的个人和集体，均己在文中Ｗ明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名；＞４；＾日期：２〇１６年／Ｚ月令日摘要摘要蚁群优化算法的若干研究蚁群优化算法，作为一种自然启发的群智能算法，属于元启发式算法的范畴。它源于对自然界中蚁群觅食行为的模拟。蚂蚁在觅食时，会在经过的路径上分泌一种化学激素——信息素，并同时根据附近信息素浓度的高低来判断前进方向。蚁群中的个体行为模式较为简单，其交互行为仅仅通过一个标量的信息素浓度来间接进行。但是多个个体的独立并行行为，却使

4、整个种群表现出了复杂的智能行为。蚁群系统天然具有的分布式、自学习、自组织、鲁棒性和简单性，使得蚁群优化算法在解决最优化问题时，具有较传统数学方法更为强大的求解能力，在生产生活的各个领域都得到了广泛关注和应用。蚁群优化算法的关键是一个参数化的概率模型，称为信息素模型。每次迭代，系统根据信息素模型来生成种群，然后又将生成的种群信息反映在信息素模型中，以影响下一代种群。也就是说，上下代种群是通过信息素模型来进行间接通信的。信息素模型既是引导种群进化方向的先验知识，同时也是保存历史种群信息的后验知识。所以信息素模型的选取直接决定了整个蚁群

5、优化算法的性能优劣。本文致力于探索更好的信息素模型来提升蚁群优化算法的性能。文章从表达能力的角度对信息素模型进行研究，进而讨论了不同问题下的信息素模型描述能力。一个理想的信息素模型应该能够蕴含种群的全部信息。但是实际应用中，对于不同约束强度的组合优化问题，传统信息素模型的表达能力有不同程度的缺失。虽然信息素模型的这种不足可以通过算法的构造机制来进行弥补，但是算法对信息素模型的额外补充并不能彻底弥补信息的丢失。随着问题规模的增大，信息素模型的表达能力会严重制约蚁群优化算法的性能。针对传统信息素模型表达能力的局限性，文本首先推导出了关

6、于问题决策变量的全概率分布模型，并据此提出了一种无信息丢失的全信息素模型。在全信息素模型下，信息素模型能够记录所有的信息，其描述能力达到顶点。然而，全信息素模型虽然能得到理想的结果，却是以超多项式级的空间为代价的。相比之下，实际采用的标准信息素模型在空间上有了极大的简化。但是，这种简I吉林大学博士学位论文化是以牺牲信息量为代价的。信息素模型描述能力的下降，作用到搜索过程中会引起搜索偏向，从而影响整个算法的性能。针对标准信息素模型描述能力的不足和全信息素模型空间代价大的缺点，本文提出了g阶信息素模型。该模型将全信息素模型和传统标准信

7、息素模型（即1阶信息素模型）统一在一个信息素模型框架之下。根据实际需要，g阶信息素模型可以在空间花费和描述能力间做出平衡，既能避免过度的空间花费，同时又可以提供必要的描述能力。文章对这种g阶信息素模型进行了分析和实验，说明了g阶信息素模型较传统标准信息素模型的优势，分析了g阶信息素模型是如何在标准信息素模型的基础上进一步提高蚁群优化算法的性能。在蚁群优化算法中，种群中个体间的竞争是算法向前演化的推动力量。通过对g阶信息素模型的比较分析，本文发现：相较于1阶信息素模型中个体间的独占式竞争，在更高阶信息素模型中，个体间的竞争是相容的。

8、这种相容式竞争很好地弥补了传统1阶信息素模型下蚁群优化算法的全局搜索能力和种群多样性方面的不足，进而增强算法的求解能力。为了更好的描述蚁群优化算法的动态行为，本文从统计学角度提出了采样点和相似度系数方法来分析算法的行为。蚁群优化算法可以看作为一种概