共查询到20条相似文献,搜索用时 15 毫秒
1.
多维背包问题的一个蚁群优化算法 总被引:6,自引:0,他引:6
蚁群优化(ACO)是一种通用的启发式方法,已被用来求解很多离散优化问题.近年来,已提出几个ACO算法求解多维背包问题(MKP).这些算法虽然能获得较好的解但也耗用太多的CPU时间.为了降低用ACO求解MKP的复杂性,文章基于一种已提出但未实现过的MKP的信息素表示定义了新的选择概率的规则和相应的基于背包项的一种序的启发式信息,从而提出了一种计算复杂性较低、求解性能较好的改进型蚁群算法.实验结果表明,无论串行执行还是虚拟并行执行,在计算相同任务时,新算法耗用时间少且解的价值更高.不仅如此,在实验中,文中的新算法获得了ORLIB中测试算例5.250-22的两个"新"解. 相似文献
2.
系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种求解多维0-1背包问题的算法——多维0-1背包问题蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验取得了较好的结果。 相似文献
3.
基于蚁群系统的多选择背包问题优化算法 总被引:7,自引:0,他引:7
提出了一种用蚁群系统求解多选择背包问题的优化算法。该方法利用蚂蚁算法所具有的正反馈特性,再结合变异参数,使算法既有较快的求解速度又有较高的求解精度。实验结果表明,采用此算法能快速有效地解决背包问题。 相似文献
4.
关于求解难组合优化问题的蚁群优化算法 总被引:10,自引:1,他引:10
1.引言组合优化问题在规划、调度、资源分配、决策等工程问题中有着非常广泛的应用。在问题规模较小时,可以使用分支定界法或动态规划方法等来求解。当问题规模增大时,解的数目虽然有限,但呈指数增长,要在合理时间内求得准确的最优解实际上已不可能。为此,人们设计了各种启发式算法。近年来,最重要和最有希望的一个研究领域是构造“师法自然“的启发式。它们类比社会系统、物理系统、生物系统等的运行机制,设计算法在问题的解空间中进行非确定性搜索。典型的有遗传算法(GA)、模拟退火(SA)、人工神经网络(ANN)。这些算法由于其自适应性,对难组合优化问题的求解取得了好的结果,被广泛应用于工程优化和控制中。本文将要介绍的蚁群优化算法,由于其较强的自适应性和对问题状态的学习能力,正逐步成为一种新的有潜力的优化算法。 相似文献
5.
针对基本蚁群算法在求解旅行商问题时表现的停滞和早熟现象,提出一种带遗忘因子的蚁群优化算法。通过在人工蚂蚁中加入遗忘因子,建立新的状态转移公式,修改信息素更新策略,蚂蚁按照基本蚁群算法的搜索方式工作,结合当前解的最优值误差率,对状态转移方程进行调整,新公式可用于降低最优值误差、提高最优值跟踪能力、修正路径评价模型、计算每条路径到当前最优解的概率。对TSP实例的仿真结果表明,改进算法耗时更短,路径寻优结果更优。 相似文献
6.
基于信息熵调整的自适应蚁群算法 总被引:1,自引:2,他引:1
针对基本蚁群算法在求解大规模旅行商问题进易导致搜索时间过长或陷入停滞的问题,提出一种基于信息熵调整的自适应蚁群算法.该算法通过优化过程中种群的信息熵来衡量演化的程度,自适应地调整路径选择策略和信息素更新策略.信息熵的计算以某条路径边上的信息素占总信息素量的比例为基础.对大规模城市数旅行商问题进行实验,实验结果表明,提出的基于信息熵调整的自适应蚁群算法能获得比基本蚁群算法更好的解,并且增加了算法的稳定性. 相似文献
7.
蚁群优化算法及其应用 总被引:17,自引:2,他引:15
蚂蚁算法是由意大利学者M.Dorigo等人提出的一种新型的模拟进化算法。该算法首先应用于旅行商问题并获得了极大的成功,其后,又被用于求解指派问题、Job—shop调度问题、图着色问题和网络路由问题等。实践证明,蚂蚁算法是一种鲁棒性强、收敛性好、实用性广的优化算法,但同时也存在一些不足,如收敛速度慢和容易出现停滞现象等。 相似文献
8.
9.
10.
Tian-MingBu Song-NianYu Hui-WeiGuan 《计算机科学技术学报》2004,19(C00):17-17
蚁群优化算法(ACO)是一种解组合优化问题的“元启发式”算法,也是一种结合了正反馈和贪婪搜索的基于种群的新方法。其思想及其应用产生于上个世纪90年代,而“蚁群优化(Ant Colony Optimization)”的确切提出则只有5年左右的时间。作为一种全新的启发式搜索算法,它在TSP,二次分配(Quadratic Assignment)和网络路由上所获得的结果完全可以与其他最优的启发式算法相媲美,甚至超越它们,并已成为当前最成功的群体智能系统之一。 相似文献
11.
随着社会的不断进步,配送车辆最短路径优化问题已广泛应用于交通运输、网络购物、物流配送等与生产生活息息相关的问题,然而配送车辆路径优化的计算比较复杂.文中建立在带约束条件的多车辆物流配送问题模型的基础上,运用改进的蚁群算法解决物流配送过程中的路径选择问题.通过对信息索的全局和局部更新规则进行改进,和传统的最值蚁群算法进行比较,算法的收敛速度和全局搜索能力得到提高.文中最后成功将改进后的蚁群算法应用于多车辆物流调度路径优化问题.结果表明该优化算法性能受优. 相似文献
12.
在项目决策与规划、资源分配、货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了许多算法。本文推广了文献[7]中求解单维0-1背包问题的蚁群算法,并从结合2-opt等局部优化的蚁群算法求解旅行商问题中得到启示:通过交换策略可以加快算法的收敛速度和获取更高质量的解,因此提出了基于交换策略的蚁群算法。再把这种算法与AIAACA算法进行比较,实验结果显示该算法与AIAACA算法效果相当,用时更少,是求解多雏0-1背包问题的有效算法。 相似文献
13.
14.
15.
群体智能的研究为分布式控制和优化提供了更好的方法, 以蚁群算法为代表的群体智能已经得到了大量的研究, 并广泛应用于组合优化领域.但是在求解组合优化问题特别是在求解规模较大的问题时, 收敛速度慢、易于停滞等现象仍然制约算法的广泛应用.为此, 提出了DEAHACO算法, 该算法提出动态挥发率机制, 用以更好地平衡求解效率和求解质量之间的矛盾, 避免算法陷入局部最优;同时, 为了加快算法的收敛速度, 对启发式信息进行了重新定义, 以指导算法快速收敛;最后, 引入了边界对称变异策略对迭代结果进行对称变异, 既提高了变异效率, 也改进了变异质量.实验表明, 该算法与其他算法相比, 其收敛速度提高了20%以上, 同时算法在其他一些经典的TSP问题上也表现出很好的性能. 相似文献
16.
针对物流配送路径优化问题的特点,提出利用蚁群算法建立数学模型,并对蚁群算法进行了改进。通过局部优化的处理,加快了改进后算法的收敛速度,并提高了全局搜索能力;对信息素的更新方式加以改进,进而提高了蚁群算法的自适应性,使得算法在执行过程中可以根据收敛和进展情况,相应地调整信息残留程度,从而进一步提高收敛速度或全局搜索能力。通过实例计算验证,使用改进后的蚁群算法优化物流配送路径,能够快速并有效地求得问题的最优解。 相似文献
17.
基于变异和动态信息素更新的蚁群优化算法 总被引:65,自引:0,他引:65
尽管蚁群优化算法在优化计算中已得到了很多应用,但在进行大规模优化时,其收敛时间过长仍是应用该算法的一个瓶颈.为此,提出了一种高速收敛算法.该算法采用一种新颖的动态信息素更新策略,以保证在每次搜索中,每只蚂蚁都对搜索做出贡献;同时,还采取了一种独特的变异策略,以对每次搜索的结果进行优化.计算机实验结果表明,该算法与最新的改进蚁群优化算法相比,其收敛速度提高了数十倍乃至数百倍以上. 相似文献
18.
为对城市动态车辆路径进行优化,设计一种具有贪婪转移准则的改进多目标蚁群算法。对蚂蚁执行多目标迭代局部搜索,在多个邻域上优化解或产生新的帕累托解。使用SUMO和NS2仿真软件,并用TraNS软件进行交互,对西安市区500组不同出发点和终点数据进行测试。结果表明,与两种传统优化算法相比,计算复杂度略有增加,但求解旅行时间明显缩短(平均少10%左右);与三种最新优化算法对比,在不同迭代次数和不同车辆数量条件下,虽然收敛速度不全都最快,但求解旅行时间均为最短(平均少5%左右)。该算法能更好满足行车时间硬要求,规避交通拥堵,能较好应用于动态车辆路径优化问题。 相似文献
19.
针对蚁群优化算法在进行全局最优解搜索时容易陷入局部最优解和收敛速度缓慢等缺陷,提出了一种有效求解全局最优解搜索问题的重叠蚁群优化算法。该算法通过设置多个重叠的蚁群系统,并对每一个蚁群初始化不同的参数,之后在蚁群之间进行信息素的动态学习,增强了不同蚁群对最优解的开采能力,避免了算法出现早熟现象。仿真实验结果表明,重叠蚁群优化算法在避免陷入局部最优解方面具有良好的效果,是一种提高蚁群算法性能的有效的改进算法。 相似文献