最大-最小蚂蚁系统及K-TSP问题的求解

蚂蚁算法目前已得到广泛的运用。为克服基本蚂蚁算法容易出现停滞现象等缺陷,许多学者提出了改进的蚂蚁算法。最大—最小蚂蚁系统是其中性能最优良的蚂蚁算法。在简述基本蚂蚁算法及最大—最小蚂蚁系统对其改进的基础上,实现了用最大-最小蚂蚁系统求解K-TSP问题的算法,列出了求解结果,并与文献[7]中的结果进行了对比,指出最大最小蚂蚁系统是求解K-TSP问题的有效算法。

具有Back-time约束的k-TSP问题(英文)

本文讨论了具有Back-time约束的k-TSP问题,给出了求解该问题的近似算法,以及在最坏情况下由该算法产生的近似解的估计.

K-TSP问题的近似算法

利用△TSP问题的Christofides算法及其在K TSP问题上的扩展 ,通过权函数变换c′ij=cij-ui-vj 使c′ij>0 ,c′ik+c′kj≥c′ij,给出了求解K TSP问题的有效途径 ,得到了目标函数的更好的界值估计 ,C(Ha)≤λ(n)C(H ) -(λ(n) -1 ) {(k-1 )c11+∑ni=1 cii}.

卷烟零售终端走访路径规划算法集成与应用

为解决卷烟零售终端走访业务领域中的多点路径规划问题,对现有路径规划算法进行归纳和总结。提出了一种Top-K群体算法集成方法将多种路径规划算法进行组合优化及集成应用,以克服单个算法存在的固有缺陷,获得更优的规划结果。以沈阳市卷烟零售终端为研究对象进行15.6万次模拟实验。结果表明:Top-K比6种原算法获得的路径平均缩短约9.82%,算法优化提升效果显著,能够获得更好的路径规划结果,具有更好的可靠性和通用性。基于Top-K开发了一种适用于烟草零售客户走访的路径规划微服务,并在沈阳烟草进行实际应用。过去1年时间里,该服务使用频次超过1.7万次,路径规划总长度超过15.6万公里,具有良好的实用性和通用性。

多物流配送中心选址及求解

经典蚁群算法不能直接用于求解多配送中心选址问题(MDLP),据此,将MDLP映射为扩展K-TSP过程并设计了改进的蚁群算法.改变了经典蚁群算法禁忌表的设置方式,算法运行时,给蚁群建立一个共享禁忌表,里面存放所有蚂蚁访问过的客户点,任何蚂蚁只能选择共享禁忌表未曾记录的客户点,从而增强蚂蚁间的信息交流,促进它们的分工与协作,使蚂蚁无遗漏无重复地遍历各配送点并找出问题的最优解.为提高算法的求解性能,在蚂蚁的选择规则里加入了代价引导函数,使用2-opt策略优化可行解并优化了信息素的更新方式.仿真算例及算法对比表明,模型和算法可以有效地表达和求解MDLP.

多点配送中心选址及求解蚁群算法

将多点配送中心选址问题(multi-distribution center location problem,MDLP)映射为扩展K-TSP过程并设计了改进的蚁群算法。为提高算法的求解性能,在蚂蚁的选择规则里加入了代价引导函数,使用2-opt策略优化可行解并优化了信息素的更新方式。仿真算例及算法对比表明,模型和算法可以有效地表达和求解MDLP。

一种新的免疫协同多Agent模型及其仿真分析

提出了一个具有高效问题求解能力的多Agent系统模型。基于生物免疫系统的自适应识别机制,将基因库进化与亲和度成熟、元动力学等要素相结合,设计具有自适应性和强大搜索能力的单Agent结构,多个Agent基于形态空间模型协同演化并涌现出智能求解能力。模型采用基于群体的多点随机搜索以及多Agent完全并行的执行方式,是一种新型协同演化模型。仿真实验结果证明了模型的有效性。

城市垃圾分类收运中的数学模型化方法

研究厨余垃圾的处理与清运问题,为大、小型处理设备的数量选择、选址及垃圾收运路线的设计分别建立了最优化模型。模型中将城市道路网抽象成无向赋权图,考虑了在交通拥堵和环境影响下的运输成本、设备处理量的均衡性和对环境的影响程度,构成多目标优化问题,进而运用改进的粒子群算法确定大型设备的位置,并给出了设置小型设备的基本原则;通过分析大、小型设备在不同处理能力下总成本的差异,确定了适合城市实际情况的最优设备处理能力。垃圾收运路线设计中以运输成本与环保成本作为优化指标,建立了基于K-TSP的运输车辆清运路线模型,并运用蚁群算法进行路网优化。最后对深圳市南山区的厨余垃圾收运问题进行了仿真,仿真结果表明,上述模型和算法能有效地解决城市垃圾分类收运问题。

一种求解旅行商问题的高效混合遗传算法

旅行商问题(TravellingSalesmanProblemTSP)是一个典型的组合优化难题,论文提出一种求解旅行商问题的高效混合遗传算法。该算法结合遗传算法和2-opt邻域搜索优化技术,并针对旅行商问题的特点,提出K近邻点集以缩减搜索空间从而加快求解速度。基于典型实例的仿真结果表明,此算法的求解效率比较高。

求解旅行商问题的高效自适应混合蚂蚁算法

在目前求解TSP问题效果最好的混合算法——最大最小蚂蚁算法和3-opt局部搜索算法的基础上,提出了一种改进的混合蚂蚁算法。算法前期使用局部搜索的解初始化信息素矩阵,加快收敛速度,后期依Metropolis接受准则概率接受局部优化解,有效地避免陷入局部最优,自适应的信息素调节机制使算法更加灵活,而K近邻候选集则使之适应大规模问题求解,理论分析和TSPLIB中部分实例仿真结果表明,此算法能比其他改进蚁群算法具有更多优越性。

TST技术在岩溶地区隧道超前预报中的应用

顶效隧道位于岩溶发育地区,地质构造复杂,岩体破碎,对超前预报技术的要求高,风险较大。目前国内外应用的隧道超前预报技术多数都存在着技术缺陷,不能区分不同方向的地震回波,不能准确地确定掌子面前方围岩的波速,不能正确地进行纵横波分离等问题,影响到预报的可靠性和准确性。为了确保施工安全,减少和避免地质灾害发生,顶效隧道超前预报中采用了TST技术。应用结果表明,TST技术采用空间阵列系统和速度扫描技术有效地解决了掌子面前方围岩速度分布问题,提高了构造定位精度;应用二维方向滤波技术有效地消除了上下、左右的侧向回波和面波干扰,成功提取了前方回波用于超前预报,避免了虚报误报,解决了复杂地质条件下的超前预报问题。

基于K均值的改进遗传算法求解TSP

提出一种基于K均值聚类方法的改进遗传算法,该算法通过聚类方法把大规模TSP转换为多个小型TSP,利用改进的遗传算法针对每一个类分别优化,求解得到多个闭合回路,再利用节约的思想将多段回路连接构成单一回路。其中遗传算法引入距离因子,结合TSP回路中边的长度进行交叉和变异,实验证明,基于K均值的改进遗传算法在求解结果方面提高30%以上。

基于K-means聚类的煤炭港区TSP浓度变化及影响因素分析

为分析煤炭港区大气中的总悬浮颗粒(TSP)浓度的变化特征和影响因素,利用典型煤炭港区2020年度监测数据,基于K-means聚类方法,分析了港区TSP浓度的变化特征;结合港区气象环境特征参数,解析了TSP污染物浓度变化与湿度、风速的相关性。结果表明:港区TSP质量浓度整体上与湿度、风速分别呈正相关和负相关关系,浓度日变化趋势呈“单峰单谷”形式,分别在5:00—7:00和17:00—18:00取得峰值和谷值,在夏、冬季易出现异常波动情况,且表现出6种不同的小时变化规律聚类特征。研究结果可为煤炭港区颗粒物污染防治提供理论支撑。

基于K-means信息挥发速率动态调整的改进蚁群算法

针对蚁群算法在求解TSP问题时,存在容易陷入局部最优,收敛速度慢,且求解时间较长的问题,提出了一种基于K-means与信息挥发速率动态调整策略的改进蚁群算法,利用K-means聚类算法将大规模TSP问题分解为数个子问题。在城市选择上,加入轮盘赌规则,对信息素更新规则进行了改进,每轮迭代时动态调整信息挥发速率。实验表明,相比蚁群算法,改进算法避免了求解陷入局部最优解,加快了算法的收敛。

改进的分布式并行遗传算法求解大规模TSP问题

TSP问题的应用十分广泛,而传统的遗传算法在求解TSP问题时存在求解精度低和时间长等不足。针对该问题提出了一种改进的分布式并行遗传算法用来求解大规模TSP问题。改进遗传算法使父代染色体进行顺序交叉、就近变异和局部最优选择,将大规模TSP问题用k-均值聚类算法进行分组,使用分布式并行算法将子问题分配到不同的计算节点上用改进的遗传算法求解。求解得到的子问题用Delaunay三角剖分算法进行合并,从而得到整个问题的解。通过TSPlib数据库进行实验,结果显示提出的算法在求解时间和求解精度上均有所提高。

一种基于K-means聚类及分组策略的TSP问题启发式算法

提出了一种基于分组策略的TSP启发式算法。采用二分k均值聚类方法对顶点进行递归分组,当组内顶点数降到给定阈值之下时进行精确求解,对求解结果合并从而得到原问题的解。实验结果及分析表明,求解结果和精确解/当前最优解差距很小,可以作为精确解的近似。该方法具有O(n^(2))的复杂度,并可以进一步简化到O(nlog n)。

基于路径选择的自适应蚁群算法研究

本文提出样本空间经过K-均值聚类算法聚类加工处理后,算法通过动态地调整选择路径概率,优化TSP求解过程中解的分布均衡性,可以在加速收敛和防止早熟、停滞现象之间取得很好的平衡。这种新的算法提供了在样本空间预处理情况下,动态自适应地解决TSP问题最优解的新方法。比起普通蚁群算法,此算法对大规模数据的最优解的求解更有显著效果。