对一类带聚类特征TSP问题的蚁群算法求解

蚁群算法是近几年提出的一种新型的模拟进化算法,初步的研究表明该算法具有极强的鲁棒性和发现较好解的能力,但同时也存在收敛速度慢的缺点。针对带聚类特征的TSP问题,提出了一种新型的蚁群算法。该算法利用TSP问题本身所具有的聚类特征,从数据域上将其分解成多个子问题,对每个子问题分别采用蚁群算法并行求解,最后将所有子问题的解按一定规则合并成问题的解。对带聚类特征TSP问题的仿真实验表明该算法的收敛速度得到了极大的提高。     

一种改进的粗粒度并行蚁群算法

蚁群算法是一种模拟进化算法,具有很强的全局搜索能力。提出了一种基于粗粒度模型的并行蚁群算法,该算法采用了一个新的信息素更新策略———Ant-proportion,这种新的更新策略是综合考虑全局和局部信息,依据蚂蚁在搜索过程中所得到的路径的优劣程度和路径中各路段对其贡献的大小来分配信息素增量;另一方面,该算法采用的粗粒度模型充分利用了蚁群算法内在的并行性,使得算法具有更快的收敛速度和更好的优化质量。最后,选用了CHN144问题对该算法进行了检验,算法求得的最优路径优于已知的最优结果。     

基于信息素递减的蚁群算法

通过对蚂蚁巡游路径的分析,发现经典蚁群算法在解决旅行商问题(TravelingSalesmanProblem,TSP)时的缺陷,在此基础上给出了新的信息素更新公式,提出了基于信息素递减的蚁群算法。新算法避免了蚂蚁在寻找最优解的过程中,由于禁忌表元素的逐渐增加而限制蚂蚁巡游路径选择的缺点,减少了巡游后期信息素对于后继蚂蚁的影响,提高了后继蚂蚁的巡游质量。通过具体的算例分析,表明此算法比传统的蚁群优化算法(AntColonyOptimization,ACO)算法有更快的收敛速度和非常好的稳定性。     

基于K-means算法的改进蚁群聚类算法及其应用

基于化学识别的蚁群聚类算法无需给定聚类数目就能自动实现数据集的聚集,但大量采用随机策略使得蚂蚁达到平衡的运行时间长,效率不高。为此提出了一种用K-means算法做初次聚类、蚁群聚类算法再次聚类的新算法,结果表明该算法具有较高的正确率。最后将该算法应用于系统应用协同中,得到了较好的分析结果。     

基于混沌社会演化算法的文本聚类新方法

用K均值算法进行文本聚类通常只能以局部最优结束,很难找到全局最优.文章提出了一种基于混沌社会演化算法的文本聚类新方法.在该方法中提出了认知主体在聚类中对范式继承的方式,在认知主体对范式的背叛中提出一种混沌变异算子.实验证明该方法不但能有效地提高文本聚类的效率而且能有效地提高文本聚类的精度.     

动态需求下考虑订单聚类的外卖配送路径优化

外卖配送路径优化包括骑手间订单分配和骑手配送路径规划两部分。针对其中订单动态产生和骑手位置不断变化的问题,基于预优化后动态调整的思想建立以最小化超时订单比例、单均配送时间和单均行驶距离为目标的两阶段优化模型。在预优化阶段,设计改进变邻域搜索算法获得初始配送方案;在动态调整阶段,采用周期性优化策略,将不断变换的骑手位置转化为虚拟配送中心车辆问题进行求解;在每一阶段采用不同的聚类方法对订单进行聚类,优化初始解的质量以更快求解。结果验证了本文策略和算法在求解动态外卖配送路径问题时的有效性和可行性。研究成果不仅深化拓展了PDVRP(pickup and delivery vehicle routing problem with time window)相关理论研究,也为外卖平台提供一种科学的优化方案。     

基于Spark的并行图聚类算法研究

对并行图聚类算法进行了研究。基于Spark 提出了一个新的并行图聚类算法;由于Spark 中的top 操作需要耗费大量的内存,提出了一个新算法来替代top 操作,有效减少了所消耗的内存;通过对自底向上的层次聚类算法进行改进提高了聚类的速度;基于图数据的特征提出了一种图数据过滤的方法来减少算法运行的时间以及所占用的空间并对其有效性进行了说明。仿真结果表明,运行效果优于进行比较的其他并行化图聚类算法。     

基于蚁群算法的并行测试任务调度

并行测试的任务优化调度是并行测试技术的核心问题.提出了一种用于解决并行测试任务调度问题的改进蚁群算法,通过该算法可以获得测试时间最短的任务调度序列.给出了并行测试任务调度问题的数学模型,设计了启发式函数和状态转移概率的计算公式.采用动态标注方法在搜索过程中加大可行解间的信息素差别,避免算法早熟.给出了应用实例,实际应用表明该算法是有效的,能很好地解决此类多维动态组合优化问题.     

基于蚁群算法的一类扩展型TSP研究

旅行售货问题（TSP）是经典的组合优化难题，本文研究它的一种推广模型，蚁群算法是近年来发展起来的一种新型的启发式随机优化搜索算法，本文在蚁群算法中采用了优势个体指导机制，实验模拟结果显示算法的有效性。     

具有不同到达时间的差异工件批调度问题的蚁群聚类算法

研究具有不同到达时间的差异工件在单机环境下的批调度问题.通过引入工件单元的概念并对分批约束进行松弛,提出了该问题的一个新的下界,证明了该下界的有效性.将蚁群算法和聚类算法相结合,提出了一种基于多阶段聚类的蚁群聚类算法ACC(Ant colony clustering).算法首先利用K-均值聚类将工件分簇,在簇内部通过蚁群算法搜索分批,最后提出一个全局优化算法对局部分批结果进行合成和优化.克服了蚁群算法随着工件规模增大求解时间过长的问题,适合于求解大规模算例.实验结果表明:与现有的启发式规则LPTBFF(Longest processing time batchfirst fit)和HGA(Hybrid Genetic algorithm)算法相比,该算法求解效果更好.     

基于蚁群并行算法的电气接线路径优化及仿真

继电控制系统中元件的连接关系可以使用网络拓扑图描述，元件间的接线路径优化类似于旅行商(TSP)问题，属于NP完备的组合优化问题。本文将ACS蚁群算法引入接线路径优化，建立了适用于继电系统接线路径优化的计算模型，并在MPI(消息传递界面)的基础上实现了算法的并行化。通过对算法初始参数进行仿真分析，确定了各参数的最佳取值范围，实验结果证明，在参数选择适当的情况下，ACS蚁群算法具有很好的全局搜索能力和较快的收敛速度。     

Solving Job-shop Scheduling Problem with an Ant Colony Optimization Algorithm Based on Mutation and Dynamic Pheromone Updating

The validity of the ant colony algorithm has been demonstrated as a powerful tool solving the optimization. An ant colony optimization algorithm based on mutation and dynamic pheromone updating in this paper was applied to settle job shop scheduling problem. Result of computer simulation shows that this method is effective.     

基于蚁群算法的Job-Shop多资源约束车间作业调度

针对多资源约束的车间调度问题,考虑资源种类变化的情况及资源在可用时间上的约束影响,建立了该类问题的通用调度模型。提出了一种基于蚁群算法的作业优化调度算法,在Job-Shop问题图形化定义的基础上,设计了状态转移规则、轨迹强度更新规则以及工序时间的决策规则,借鉴精英策略的思路,对多资源约束车间的具体调度进行了分析与实现。实例仿真表明,该方法对多资源的车间调度问题是可行的。     

基于Matlab的分布式并行优化计算环境

在对并行计算环境进行深入讨论的基础上，提出了基于Matlab的分布式并行优化计算环境的层次结构，并设计了初始化函数、发送接收任务函数、进行任务函数和回送并综合结果函数四大类的基本并行函数，这些函数都具有大粒度的特点。利用这些基础函数，实现了并行SQP。为伪代码的分析中表明，利用四类基本函数实现分布式并行计算是简单而有效的。     

基于Voronoi图和蚁群优化算法的无人作战飞机航路规划

无人作战飞机(UCVA)航路规划是一类复杂优化问题.在众多航路规划算法中,Voronoi图是一种根据战场多威胁源分布情况获取可行航路的图形算法,而蚁群优化(ACO)算法是受到蚂蚁觅食行为启发而形成的一种启发式仿生算法.根据已知威胁源生成Voronoi加权图,其中每条Voronoi边的总代价可以由威胁代价和燃油代价计算得出;然后给出了在Voronoi图条件下,用于航路规划的改进ACO算法模型和具体实现方法;最后,将Voronoi图与ACO算法相结合,并针对某UCAV多种空战态势下的航路规划问题进行了系列仿真实验.实验结果验证了所提方法在解决UCAV航路规划问题时的可行性和有效性.     

基于蚁群算法的动态联盟伙伴选择研究

提出“小生境蚁群算法”（MACO），在利用正反馈的同时，引入时变参数来利用经验信息和启发信息，并在局部寻优时结合了小生境信息盖的思想，从而有效地防止遗传算法中出现的“早熟”问题和蚂蚁算法中发生的“停滞”状态。把制造企业动态联盟合作伙伴的选择抽象为多目标优化的问题，并建立了优化选择目标函数。运用MACO解算选择合作伙伴的多目标问题，获得最优解。