论文部分内容阅读
蚁群算法是一种新型仿生类优化算法，是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法。蚁群算法由意大利学者M. Dorigo等人首先提出，并成功地应用于求解一系列NP完全的组合优化问题，如：旅行商问题、二次分配问题、车辆寻路问题和图着色问题等等。蚁群算法从提出到现在，短短十余年的时间，以其在离散型组合优化问题中的突出表现，吸引了人们的极大关注。论文针对基本蚁群算法收敛速度较慢和算法容易出现停滞现象的缺点，对蚁群算法进行研究，提出了两种改进的蚁群优化算法，并分别应用于TSP问题和多维0-1背包问题。论文的研究工作主要包括以下两个方面：1．改进的蚁群算法应用于TSP问题的研究。提出一种求解TSP问题的具有分段和变异特性的蚁群算法SMAS。该算法融合了分段的分而治之思想和遗传算法中的变异，有利于保持群体多样性的特性，是在采用轮盘赌方式的最大最小蚁群算法陷入局部最优解的情况下，引入随机分段和遗传算法的变异操作来优化当前最优解，改善解的质量，有效地改善了蚁群算法易于过早地收敛于非最优解的缺陷。2．改进的蚁群算法应用于多维0-1背包问题的研究(MKPACA)。0-1背包问题是典型的NP完全问题，且蚁群算法已成功地解决了许多组合优化的难题。因此，论文提出一种求解多维0-1背包问题的蚁群算法——MKPACA，当物品数较大时，也取得了较好的求解质量。在MKPACA中，引入受益量密度的概念，改变概率计算的时机，并采用“轮盘赌”方式根据概率p_j选择下一个物资，这样既兼顾了概率大小，又增加了搜索的随机性，兼顾解空间的多种情况，有效改善了蚁群算法搜索速度慢且易于过早地收敛于非最优解的缺陷。