论文部分内容阅读
蚁群优化(ant colony optimization, ACO)是受自然界蚁群觅食行为的启发而产生的一种群体智能优化算法。ACO算法采用了求解离散问题的优化机制,解决了科学和工程领域的大量难题:比如各种经典的组合优化问题和数字图像处理问题等。尽管蚁群算法拥有信息素更新策略的正反馈性和贪婪启发式搜索机制,保证了算法能够更快地发现较好的解,但是当蚁群算法的搜索过程进行到后期,所有蚂蚁探索的解完全一致,不能对解空间进行进一步的开发。由于蚁群算法具有较强的耦合性,易于与其他与启发式算法以及仿生优化算法相结合,本文选取蛙跳算法(shuffled frog leaping algorithm, SFLA)与蚁群算法相融合,使算法在运行的后期跳出局部最优解,增大算法的求解精度。基于以上研究,本文的主要工作有以下几点:首先,提出二阶蚁群算法(double phase ant colony optimization, DPACO)。在蚁群算法的信息素更新阶段引入顺序更新规则,分两个阶段对蚂蚁走过路径上的信息素进行更新,提出了两种信息素更新阶段的划分策略:硬划分策略和软划分策略,并把每段路径上的信息素的值限定在一个整数区间中;对经典旅行商问题的实验结果表明,二阶蚁群算法能够跳出局部最优解,算法的搜索能力明显增强。考虑到蚁群算法有较强的耦合性,研究了二阶蚁群算法与蛙跳算法的融合。一是将二阶蚁群算法的概率选择规则中加入了经验反馈算子,使得蚂蚁在路径构建中能够考虑所选取解元素对整个路径的长期影响;二是设计了双态蚁群搜索模式,把蚂蚁分成常规蚂蚁和寻优蚂蚁两种状态,避免了蚂蚁选取较长的路径;三是使用改进的交叉算子和变异算子来改进混合蛙跳算法的局部搜索过程,使得蛙跳算法最大程度的避免了不成熟的收敛。最后,在二阶蚁群算法的每一步迭代过程中引入蛙跳算法的局部搜索与全局更新过程。实验表明,本文算法在求解旅行商问题精度上有很大提高。