《二进制蚁群算法的研究及其应用》由会员分享，可在线阅读，更多相关《二进制蚁群算法的研究及其应用（76页珍藏版）》请在金锄头文库上搜索。
1、宁波大学硕士学位论文二进制蚁群算法的研究及其应用姓名：王柳毅申请学位级别：硕士专业：计算机应用技术指导教师：熊伟清宁波大学硕士学位论文 I作者:作者: 王柳毅 申请级别:硕士 题目: 王柳毅 申请级别:硕士 题目: 二进制蚁群算法的研究及其应用 导师:导师: 学校:宁波大学 学校:宁波大学 二进制蚁群算法的研究及其应用 摘 要 摘 要 蚁群算法是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法，该算法采用了正反馈并行自催化机制，具有较强的鲁棒性，优良的分布式计算机制，易于与其他方法结合等优点，在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜力，近几年吸引了国内外许多学者
2、对其进行了多方面的研究工作。 本文中，首先阐述了几种真实蚁群的觅食行为，介绍了蚁群算法的思想起源，随后，以组合优化问题（TSP）问题入手，对传统蚁群算法进行了概括的介绍，并对现有的改进算法进行了叙述，针对目前蚁群算法中所存在的问题，结合遗传算法的编码方式对传统蚁群算法进行了适当的改进，引入了随机二元链式结构，提出了二进制蚁群算法，给出了二进制蚁群算法的算法模型，并对其收敛性进行了论证。随后又对新的改进算法在几个领域中进行了应用。 首先是在函数优化中，加入了并行化策略，对几个典型的多峰函数进行优化，实验结果显示，算法性能较好。 随后，又在数据挖掘中进行了新算法的应用，首先对传统的Ant-Mine
3、r进行了简要的介绍，随后，针对传统的Ant-Miner的缺陷，将二进制蚁群算法引入到Ant-Miner中，并且加入新的算子变异算子同灾变算子，同时也引入了新的有效值的计算公式。对两个数据集进行了测试，实验结果证明，算法性能较之Ant-Miner有所提高。 接着，又在神经网络中加入了二进制蚁群算法，提出了一个新的二层模型，对传统的BP算法进行了改进，并且引入了拥堵策略。对两个函数进行了逼近，实验证明，同传统的BP算法相比，新的算法的精度得到了一定的提高。 最后，给出了一些研究中发现的问题，也是我们准备进一步深入研究的方向。 宁波大学硕士学位论文 II关键词：蚁群算法， 二进制， 函数优化， 数据
4、挖掘， 神经网络 关键词：蚁群算法， 二进制， 函数优化， 数据挖掘， 神经网络 宁波大学硕士学位论文 IIIResearch on the Theory and Applications of Binary Ant Colony Algorithm Abstract Ant colony optimization algorithm (ACO) is a bionic optimization algorithm recently developed, and it simulates the foraging behavior of ant colony in the insect kin
5、gdom. It adopts positive feedback, parallel and autocatalysis mechanism, and the algorithm has the advantages of strong robustness, fine distributive computation mechanism and easy to combine with other algorithms and so on. In solving many complex optimization problems, ACO shows excellent performa
6、nce and great developing potential, and attracts lots of researchers attention. In the paper, we present several foraging behavior of real ant, and introduce the source of the ant colony algorithm. Start with the combination optimization (TSP) problem, the general ACO and some modified ones are summ
7、arized generally. Aiming at the defect of the general ACO, we combine the coding method of general Genetic Algorithm with the ACO, and introduce the stochastic binary chain structure. Adopting this structure, a new ant colony algorithm model is present, also a new ACO is introduced, which is called
8、binary ant colony optimization algorithm (BACO). Later, the convergence of the new algorithm is demonstrated. Then, the new algorithm is applied in several fields. First of all, BACO is adopted in the multi-peak function optimization problems, in order to get all the optimal solutions, parallel mech
9、anism is added. The modified BACO is applied to solve several functions, and the result show that the performance is good. Secondly, we adopt the new algorithm in the data mining field. We first introduce the general Ant-Miner, then, aiming at the defect of the general Ant-Miner, BACO is adopted int
10、o the Ant- Miner, and some new operators are added such as mutation operator and disaster operator. After analyzing the virtual value computing formula, some shortage is found and a new formula is proposed. After applying in two testing data set, the result improved a lot compared to Ant-Miner. Then
11、, we add BACO into the traditional artificial network, and propose a new model of two- layer, which purpose is to modify the general Back-Propagation (BP) algorithm, and a new strategy called traffic flow control. After using the new algorithm to approach two nonlinear functions, compared with the g
12、eneral BP algorithm, the precision of the new one has improved much. At last, some problems found in the research are present, which point out directions of next steps.Key Words：Ant Colony Algorithm, Binary, Function Optimization, Data Mining, Artificial Networks宁波大学硕士学位论文 - 1 - 引 言 引 言 许多实际工程问题可以抽象
13、为相应的组合优化问题。采用常规问题对于大规模组合优化问题的有效解决往往存在着许多障碍。近年来，人们对于将自然界的许多有益特性应用于工程实际。目前已经有很多启发式算法用于解决复杂的系统优化问题，如电信网络路由，网络导航等问题。与传统算法相比较，启发式算法的优点在于其有较好的全局搜索能力，避免过早收敛于局部最优解。 蚁群算法是借鉴自然界中群居性昆虫通过自组织的合作能力所产生的群集智能解决组合优化问题的典型例子，它是继模拟退火算法，遗传算法，禁忌搜索算法，人工神经网络算法等元启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。 目前对蚁群算法的缺陷也是很显而易见的，由于传统蚁群算法的编码特
14、性，使得它在处理连续性问题上的表现不像离散域中那么优越，而目前的改进一般还是局限在蚁群之间传递信息的媒介信息素的设置和更新策略，但是对蚁群算法的编码规则的改进却相对比较少，也是极具有潜力的发展领域。 二进制表示法作为最有效和最经济的数据表示法，在遗传算法中得到了很好的应用。因此，遗传算法的二进制编码方式给了蚁群算法一个新的发展方向，本文的目的就是将二进制编码方式应用到蚁群算法中，给出一个改进的蚁群算法，并在多个领域中进行了应用。 宁波大学硕士学位论文 - 2 - 1 绪论绪论 1.1 问题的引出问题的引出 数以百万计的蚂蚁如何组成一个群落？在蚁群中，单只蚂蚁的能力和智力如此简单，不论工蚁还是蚁
15、后都不可能有足够的能力来完成筑巢，觅食，迁徙，清扫蚁穴等复杂行为，那么，它们是如何相互协调，分工，合作来完成这些任务呢？像蚁穴这样复杂结构的信息又是如何存储在这群蚂蚁当中呢？这些一直是困扰生物学家的问题。又如，我们经常能够看到成群的鸟，鱼或者浮游生物。这些生物的聚集行为有利于它们觅食和逃避捕食者，它们的群落规模动辄以十百，千，万计，并且经常不存在一个统一的指挥者。他们是如何完成聚集，移动这些功能呢？生态学家对这个问题一直十分感兴趣。另外，当今出于全球化进程的社会中，各个厂商都是为了自己的最大利益生产，销售产品。没有任何单个厂商有足够的能力把握全局，但各大城市的物品却很少出现匮乏，总能达到供需平
16、衡，厂商是在什么力量的支配下完成这些配给任务的？经济学家一直在思考这个问题。 其实，这些看似毫不相关的问题都具有相同的特征，即相对简单的个体在没有一个集中控制的情况下，通过相互作用产生复杂的群体行为，它们都属于复杂系统研究的范围，各个领域的专家已经对这些问题有了长期，深入的研究，提出了一些解释并建立了一些模型。 例如对于动物群体的聚集行为有两种数学的描述方法：第一种方法是在考虑到相同物种的相互吸引与排斥的同时，基于每个个体的随机移动利用欧拉连续方程（偏微分方程）进行描述，从而描述整个群体的密度；另外一种方法是基于个体的轨迹，利用拉格朗日方程对于个体的移动，速度等进行描述。 1.2 基于主体的仿真基于主体的仿真 随着计算能力的普及，我们可以不利用方程，而通过对个体行为准则的模拟，仿真进行建模，这种建模方式被称作基于主体的仿真（Agent Based Simulation）。这种建模方式强调群体中每个个体的特性，更强调个体之间的相互交互作用，这是许多传统建模方式所缺少的，它
