动态自适应蚁群算法在二次分配问题中的应用

采用一种新算法动态自适应蚁群算法解决二次分配问题,并引入3-opt方法对问题求解进行局部优化,通过对二次分配问题的不同实例进行实验,结果表明,该算法在求解二次分配问题上具有较好的能力,可以很好地解决较大规模的二次分配问题,而以往的算法只适合于处理较小规模的二次分配问题.

求解二次分配问题的离散粒子群优化算法

提出了一种求解二次分配问题的离散粒子群优化算法.根据二次分配问题及离散量的特点,重新定义了粒子的位置、速度等量及其运算规则,为抑制早熟停滞现象,为粒子和粒子群分别定义了个体多样性和平均多样性.算法中定义了排斥算子来保持粒子群的多样性,使用局部搜索算子来提高算法的局部求精能力,使算法在空间勘探和局部求精间取得了较好的平衡.在QAPLIB的实例上的仿真结果表明,离散粒子群优化算法具有良好的性能.

模拟退火蚁群算法求解二次分配问题

提出了一种求解二次分配问题的模拟退火蚁群算法。将模拟退火机制引入蚁群算法,在算法中设定随迭代变化的温度,将蚁群根据信息素矩阵搜索得到的解集作为候选集,根据当前温度按照模拟退火机制由候选集生成更新集,利用更新集更新信息素矩阵,并利用当前最优解对信息素矩阵进行强化。当算法出现停滞对信息素矩阵进行重置。实验表明,该算法有着高的稳定性与收敛速度。

二次分配问题的粒子群算法求解

文章采用了一种新的算法,即粒子群算法(PSO)去解决二次分配问题(QAP),构造了该问题的粒子表达方法,建立了此问题的粒子群算法模型,并对不同的二次分配问题算例进行了实验,结果表明:粒子群算法可以快速、有效地求得二次分配问题的优化解,是求解二次分配问题的一个较好方案。PSO算法在很多连续优化问题中已经得到较成功的应用,而在离散域上的研究和应用还很少。文章应用PSO算法解决QAP问题是一种崭新的尝试,它对于将PSO算法应用于离散问题,特别是组合优化问题无疑具有启发性,并为进一步深入研究奠定了基础。

基于二次分配问题的混合蚁群算法

二次分配问题是组合优化领域中经典的NP-hard问题之一,应用广泛。在对二次分配问题进行分析的基础上,提出了一种求解该问题的混合蚁群算法。该算法通过在蚁群算法中引入遗传算法的2-交换变异算子,增强了算法的局部搜索能力,提高了解的质量。实验结果表明,该算法在求解二次分配问题时优于蚁群算法和遗传算法。

二次分配问题的大洪水算法求解

大洪水算法是一种求解组合优化问题的独特方法,该方法通过模拟洪水上涨的过程来达到求解一些组合优化难题的目的。本文运用该方法求解二次分配问题(QAP),设计了相应的算法程序,并对QAPLIB(二次分配基准问题库)中的算例进行了实验测试,结果表明,大洪水算法可以快速有效地求得二次分配问题的优化解,是求解二次分配问题的一个新的较好方案。

几种基于匈牙利算法求解二次分配问题的方法及其分析比较

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题。二次分配问题的线性化模型和下界计算方法,是求解二次分配问题的重要途径。本文以二次分配问题的线性化模型为基础,根据现有QAP对偶上升下界计算方法中的具体操作,提出几种可行的QAP对偶上升计算新方法。最后,通过求解QA-PLIB中的部分实例,深入分析其运行结果,详细讨论了基于匈牙利算法求解二次分配问题的对偶方法中哪些操作可较大程度地提高目标函数最优解的下界增长速度,这为基于匈牙利算法求解二次分配问题的方法的改进奠定了基础。

解决二次分配问题的改进蚁群算法

现有的解决二次分配问题的蚁群算法大都与局部搜索过程相结合,文章对其中的局部搜索过程做了修改:一方面结合利用包含全局信息的信息素来指导局部搜索,避免了快速陷入局部最优;另一方面加入了一个二次机会策略,充分搜索解邻域,增强了算法的搜索能力。运用该文给出的算法,针对QAPLIB(二次分配基准问题库)中的问题进行了计算,并将结果与原有蚁群算法进行了比较。实验结果表明该文提出的算法具有更优的性能。

求解二次分配问题的改进禁忌搜索算法

针对二次分配问题,提出了一种改进禁忌搜索算法ITS。ITS基于"集中和分散"策略,由局部搜索和精英重组两个步骤经过多次迭代完成。局部搜索采用RTS(Robust Tabu Search)。在精英重组步骤,对局部优化解中的优良个体采用MPX交叉操作,得到新的可行解。在QAPLIB典型实例上的实验结果表明,与RTS相比,改进后的禁忌搜索算法具有更优的性能。

一种求解物流设施二次分配问题的混合分布估计算法

为了求解物流设施二次分配问题,提出了一种混合分布估计算法(HEDA)。首先,根据QAP的距离和物流量矩阵信息,提出了一种基于假设物流中心启发式规则的种群初始化方法,用于提高初始种群的质量和算法的搜索效率;其次,针对HEDA的概率模型,提出了一种概率矩阵初始构型生成机制和扰动操作,用于提高算法的全局探索能力;最后,在分析QAP的结构性质的基础上,设计了一种基于快速评价的局部搜索策略,用于提高算法的局部开发能力。仿真计算实验和算法比较验证了HEDA的优化性能。

黑白二次分配问题

二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑色设备的距离不超过预定阈值.文章将之定义为黑白二次分配问题BWQAP(Black and White QAP).文章首先分析了它的计算复杂性,指出该问题是NP-难解问题,不存在ε-近似度的多项式时间近似算法(ε>0).同时证明了其可行解的存在性与黑白图上的支配集问题等价,也属于NP-难解问题.为了能在可接受的时间内得到大规模实例质量可接受的近似解,提出了一种求解BWQAP的启发式算法GFO.该算法利用QAP现有算法得到初始解,然后利用局部搜索策略完成解的可行化和优化.大量实验表明,该启发式算法能够有效地求解BWQAP问题的实例.

一种求解二次分配问题的新方法

二次分配问题(QAP)是一种易于表述却难于求解的组合优化难题。将二次分配问题目标函数中的二次项线性化得到与原问题等价的(混合)整数线性化模型,是求解二次分配问题的重要途径,但二次分配问题线性化模型中庞大的变量和约束数,致使利用其求解较大规模的实例仍具有很大困难。通过松弛原有二次分配问题线性化模型中的约束,得到3个求解规模较小且较松弛的模型,提出了一种求解二次分配问题的新方法,并不仅从理论上证明了该方法的正确性,也从实验的角度说明了该方法较以往方法的优越性。

利用混合粒子群优化算法求解二次分配问题

提出一种求解二次分配问题的混合粒子群优化算法。新算法将遗传算法的交叉策略引入PSO算法中,同时采用禁忌搜索算法作为局部搜索算法。在QAPLIB实例上的实验结果表明,混合算法具有良好的性能。

二次型0-1分配问题的遗传算法求解

文章针对数学中一类计算非常困难的二次型０－１分配问题，提出遗传算法的求解思想，并根据问题的具体特点对算法进行改进，将复杂的约束条件包含在适应值函数中，构造非线性变化的动态适应值来求解该类问题。最后成功地运用于一个分散决策问题实例，与常规遗传算法相比该搜索算法具有明显的优越性。

禁忌搜索算法与蚁群算法的混合策略在二次分配问题上的应用

二次分配问题是一个NP-hard问题,它在线路板设计、布局问题以及打字机键盘的设计等现实生活中有许多的应用。使用基本蚁群算法进行搜索时,其全局优化性能的优劣在很大程度上与蒸发系数的选择有关,若选择不合适,易使算法陷入局部最优。为此,本文提出一种新的算法,即将基本蚁群算法与禁忌搜索策略相结合来求解二次分配问题,设计出具体的算法模型,并对标准问题库中的具体实例进行测试,实验结果证实新方法的有效性。

一类特殊二次分配问题及其求解

二次分配问题(quadratic assignment problem,QAP)是应用于诸多领域的组合优化NP-难题,许多从实际问题中抽象出来的二次分配问题,其流矩阵与距离矩阵中存在大量零元素,如果在该类二次分配问题的求解中,能够充分利用这些零元素的信息,将大大缩减问题的规模,节省大量运算时间。本文以二次分配问题的线性松弛模型为基础,分别从理论和实验的角度对这类二次分配问题的求解进行了研究,说明了二次分配问题求解中,先行利用零元素信息减小问题规模的可行性和重要性。

二次分配问题及其研究进展(Ⅰ)

二次分配问题(QAP)是应用于诸多领域的经典组合优化难题之一。本文简要回顾了目前QAP问题的模型和求解方法的研究进展,最后讨论了求解QAP的发展趋势。

求解二次分配问题的预处理快速蚂蚁系统

分析了快速蚂蚁系统(FANT)跳出迭代最优解的策略,指出算法易发生停滞现象的原因,并通过改进算法解的构建步,引入一个变动的参数,提出了求解二次分配问题的一种新算法———预处理快速蚂蚁系统(PFANT).新算法改进了FANT算法易发生停滞的现象,拓宽了迭代最优解邻域的搜索范围,提高了二次分配问题解的质量.

改进蚁群算法在二次分配问题中的应用

为了解决基本蚁群算法在求解大规模二次分配问题时暴露出的缺陷,本文提出一种改进的蚁群算法。在基本蚂蚁算法中,采用全局信息素更新策略,使用距离及流量作为启发式信息并引入局部优化策略,对每代的最优解进行改进,进一步加快算法的收敛速度。通过对于二次分配问题的3种不同类型的问题进行实验,将改进的蚁群算法与基本蚂蚁算法及混合遗传算法进行比较,结果表明该改进算法具有更优的性能。

变参数的快速蚂蚁系统求解二次分配问题

二次分配问题(QAP)是经典的组合优化问题之一,广泛应用于许多领域中。通过分析快速蚂蚁系统(FANT)的信息素更新机制,引入一个变动的参数,提出了一种新的蚁群算法—变参数的快速蚂蚁系统(VPFANT)。该算法改进了FANT易发生停滞现象等缺点,拓宽了快速蚁群系统解的搜索范围,提高解的寻优能力。