蚁群算法求解复杂集装箱装载问题

针对复杂集装箱装载问题(CLP),应用启发式信息与蚁群算法求解了最优装载方案。首先,建立了复杂集装箱装载问题的数学模型,利用蚁群算法对解空间的强搜索能力、潜在并行性及可扩充性,结合三空间分解策略将布局空间依次分割;然后,装入满足约束条件的最优货物块,完成不同大小三维矩形货物的装载布局。在此基础上,设计了基于空间划分策略的蚁群算法。最后以700件货物装入40尺(12.025m)高柜箱进行计算,结果表明该方法能提高集装箱的空间利用率,同时兼顾了多个装载约束条件,可应用性好。     

基于装箱树算法求解集装箱装载问题的研究

研究了把同种货物装入一个集装箱内，使箱子内的空间利用率为最大的集装箱装载问题．首先，运用启发式算法,充分考虑了箱子和货物的方位、剩余空间等问题．然后，通过主空间装填、空间分层、剩余空间优化等建立一个装箱树．最后，用Java程序完成装箱树算法，并实现集装箱装载问题的求解．用实例验证了算法的可行性，能够投入实际应用．     

集装箱装入问题的研究

集装箱装载问题是一种有广泛应用背景的组合优化问题,它属于NP-hard问题。禁忌搜索算法(TS)是求解组合问题的一种主要方法,有很强的全局搜索能力。集装箱装入属于有多种约束的空间资源优化问题。约束条件多,求解困难。根据同类型货物一次性装载的思想,提出了一种新的基于空间划分的启发式算法。     

求解强异类集装箱装载问题的混合蚁群算法

针对强异类集装箱装载问题,设计了一种混合蚁群算法。算法中搜索空间分为货物摆放的优先序列和货物摆放的状态两部分;引入体积大的货物优先放入的启发式规则;将蚂蚁搜索得到的序列与历史最优序列进行交叉,取三者最优序列作为该蚂蚁的搜索路径;在更新信息素时,采取两种挥发系数更新信息素以避免信息素过快饱和,同时分析了算法的复杂度。通过三个强异类实例的测试,表明算法得到的装载方案有较高的空间利用率。     

同类货物集装箱装载问题的启发式算法

提出了求解同类货物集装箱装载问题的一种启发式算法.算法中采用了层的思想,集装箱的每个面都可用来构建层.通过对二维布局、层高组合和用来构建层的集装箱面的选择等三个方面的优化求解,得到了具有较高装载率的集装箱装载方案.实例结果表明,该算法是求解同类货物集装箱装载问题的一种行之有效的方法.     

基于混合遗传算法的多约束集装箱装载问题研究

在考虑集装箱装载货物底置等级、侧放方式、堆码层数等一些实际应用的约束条件下,根据同类型货物一次性装载的思想,提出了一种新的基于空间划分的启发式算法,并以此为基础构造了一种混合遗传算法。     

求解三维装箱问题的混合遗传模拟退火算法

集装箱装载是货物运输过程中重要的一步,其属于NP-hard问题。为了提高效率,降低成本,提出了以集装箱体积利用率最大化为目标建立三维装载模型,同时考虑体积约束、重量约束、重心约束、方向约束。利用混合遗传、模拟退火与三空间分割启发式装载算法求解模型,算法中融入局部最优解保存策略来避免局部较好解在后续的算法过程中出现适应度降低的情况。通过强异类算例与弱异类算例对算法进行性能测试,并结合具体的货物装载数据,得出三维装载图与目标函数值。结果表明,该算法应用于集装箱装载有着较好的效果。     

集装箱装载的一种启发式算法

多约束条件下的三维装箱问题是一个复杂的组合优化问题,属于NP-HARD问题，其求解是很 困难的．所以在实际应用中,往往采用一些启发式算法来求解．本文在考虑一些实际应用中 的约束条件下，提出了一种三维集装箱装载的启发式算法．此算法采用了三空间分割、平均 高度装载、货物合并、空间合并等策略，考虑了方向、重量、优先顺序、货物的配置位置等 约束条件．通过逐步淘汰差的装载方案，最后达到满意的装载．实例仿真说明了该算法的有 效性和实用性，能够直接用于实际应用中．     

满足货物承载能力约束的集装箱装载问题研究

本文采用基于矩阵的货物空间约束表达形式和货物承载能力约束表达形式以及简单块生成策略,对基于Beam Search算法的集装箱装载算法进行了改进,以使其能够有效进行满足货物承载能力约束的集装箱装载问题的优化计算,实验结果表明了该算法的有效性。     

求解多车辆装载问题的启发式改进蚁群算法设计

针对启发式优化算法不能较理想地对多车辆大规模装载问题进行优化的局限性,文章设计了一种启发式改进蚁群算法,该算法将单车辆的启发式装载与多车辆装载时的蚁群优化算法有机结合,较好地解决了多车辆大规模装载问题。经过实例验证,该算法具有较高的计算效率和较好的收敛特性。     

An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times

This study introduces the problem of minimizing average relative percentage of imbalance (ARPI) with sequence-dependent setup times in a parallel-machine environment. A mathematical model that minimizes ARPI is proposed. Some heuristics, and two metaheuristics, an ant colony optimization algorithm and a genetic algorithm are developed and tested on various random data. The proposed ant colony optimization method outperforms heuristics and genetic algorithm. On the other hand, heuristics using the cumulative processing time obtain better results than heuristics using setup avoidance and a hybrid rule in assignment.     

置换流水车间调度的蚁群优化算法

提出了一种求解置换流水车间调度的蚁群优化算法。该算法的要点是结合了NEH启发式算法和蚁群优化方法。理论论证和对置换流水车间调度问题的基准测试表明了该算法的有效性。     

一种进化型蚁群算法及其在TSP问题中的检验

蚁群算法是通过模拟蚂蚁觅食而发展出的一种新的启发算法，其收敛速度一直是人们关心的问题。针对蚁群算法的一些不足，提出基于最小生成树的进化型蚁群算法。它利用了最小生成树与最优路径之间的关系限制了蚂蚁在每一个城市的搜寻范围，进化了寻优策略，节省了在不可能构成最优路径的路段上的计算时间，提高了运算速度，克服了以往蚁群算法的计算时间长、精度低的缺点，使得蚁群算法有了显著的提高。计算机仿真结果表明，该文算法改进了标准蚂蚁群算法的效率和计算结果的质量。     

Guidance-solution based ant colony optimization for satellite control resource scheduling problem

An ant colony optimization (ACO) approach for the satellite control resource scheduling problem is presented. Based on the observation that the solution space of the problem is sparse, this ACO approach is combined with a guidance solution based pheromone updating method to avoid trapping in local optima. The basic idea of this method is to change the distribution of pheromone trails by updating them with a guidance solution once the algorithm stagnates. We compare the proposed algorithm with several other heuristics. The experimental results demonstrate that our approach possesses strong competitive advantage in exploring global best solutions.     

求解QAP问题的近似骨架导向快速蚁群算法

QAP(quadratic assignment problem)问题是经典的组合优化问题之一,广泛应用于许多领域中.针对QAP问题,提出了一种新的蚁群算法--近似骨架导向的快速蚁群算法(ABFANT).该算法的基本原理是通过对局部最优解的简单相交操作得到QAP问题实例的近似骨架(approximate-backbone),利用这些近似骨架可以极大地缩小QAP问题的搜索空间,而同时不降低搜索的性能,最后对这个缩小后的搜索空间,直接用当前求解QAP问题最好的启发式算法之一-快速蚁群算法(FANT)求解得到问题的解.在QAPLIB中的典型实例上的实验结果表明,近似骨架导向的快速蚁群算法明显优于快速蚁群算法.此外,指出基于近似骨架的算法思想可以很容易地被移植到其他求解QAP问题的启发式算法中.     

High speed ant colony optimization CMOS chip

Ant colony optimization (ACO) is an optimization computation inspired by the study of the ant colonies’ behavior. This paper presents design and CMOS implementation of the ant colony optimization based algorithm for solving the TSP problem. In order to implement ant colony optimization algorithm in CMOS, we will present a new algorithm. This algorithm is based on the original ant colony optimization but it can be implemented in CMOS. Briefly, pheromone matrix is transformed on the chip area and ants move up-down through the pheromone matrix and they make their decisions. Finally ants select a global path. In previous researches only pheromone values is used, but select the next city in this paper is based on heuristics value and pheromone value. In definition of problem, we use heuristics value as a matrix. Previous researches could not be used for wide type of optimization problem but our chip gives heuristics value initially and we can change initial value of heuristics value according to the optimization problem so this capability increases the flexibility of ACO chip. Simple circuit is used in blocks of our chip to increase the speed of convergence of ACO chip. We use Linear Feedback Shift Register (LSFR) circuit for random number generator in ACO chip. ACO chip has capability of solving the big TSP problem. ACO chip is simulated by HSPICE software and simulation results show the good performance of final chip.     

网格资源分配算法的研究

资源分配是网格计算研究领域中的一个要点问题,目前已研究的若干计算智能方法大多是单一的用于解决网格资源分配问题,对于在混合的前提下提高资源分配性能方面还缺乏深入的研究。为此,针对网格资源分配问题提出了一个启发式混合搜索算法,通过带有启发式的遗传算法在资源中进行搜索,在生成的解中再利用蚁群算法做进一步的探索。仿真实验结果表明,该算法在满足用户需求的前提下,有效地提高了网格资源利用率。     

混合蚁群优化算法求解卫星数传调度问题

为了求解卫星数传调度问题,提出了混合蚁群优化算法。算法设计了基于任务数传操作的解构造图,提出了基于解构造图的任务调度序列和资源分配序列概率决策模型,采用基于随机加权的混合策略综合利用问题的启发式信息。算法通过基于混沌变异的列信息素向量更新策略增强解构造的多样性,通过具有补偿机制的全局信息素更新策略来保证算法的收敛性。利用STK工具设计了五个调度场景,并利用计算机生成各场景的数传任务。仿真实验结果表明,该算法是可行、有效的,收敛性和解多样性较好。     

生长森林的蚁群优化算法在Steiner树问题上的应用

Steiner树问题是一个经典的优化问题.已被证明是NP-complete问题.对于此问题已经有了很多经典的求解方法,然而在这些方法中一些算法的时间复杂度太高,另一些算法则得不到较好的解.因此,本文提出一种生长森林的蚁群优化算法求解Steiner树问题.在此算法中,蚂蚁行动过程中形成的是森林,每只蚂蚁走出的每一步都只是使当前的森林进一步生长,蚂蚁行动的目标就是使森林中的所有的树连接成一棵树且这棵树包含了所有的目标节点.仿真实验结果表明,算法在寻优能力、收敛速度方面都有良好的表现.     

垃圾分类收运路径问题的新型混合蚁群算法求解

针对垃圾分类收运路径问题,考虑车辆装载容量约束、硬时间窗约束、装载率对成本的影响等条件下,以最小化运输成本和车辆固定成本为目标建立了数学模型。将考虑时间吻合度因子和车容量利用率因子的改进蚁群算法与混沌电磁场优化算法进行动态融合,并结合2-opt和两点交换的局部搜索方法,提出一种以改进蚁群算法为外部框架,混沌电磁场优化算法为内部模块的新型混合蚁群算法对城市生活垃圾分类收运问题进行求解。根据算法间优势互补的思想,利用两种算法的优点来弥补单个算法的缺陷,使其成功应用于该问题。最后,用车辆路径问题标准测试集和上海市杨浦区的数据作为实例进行测试与对比,验证了模型的正确性以及算法的有效性与优化能力。