Mechanical assembly planning using ant colony optimization

In mechanical assembly planning research, many intelligent methods have already been reported over the past two decades. However, those methods mainly focus on the optimal assembly solution search while another important problem, the generation of solution space, has received little attention. This paper proposes a new methodology for the assembly planning problem. On the basis of a disassembly information model which has been developed to represent all theoretical assembly/disassembly sequences, two decoupled problems, generating the solution space and searching for the best result, are integrated into one computation framework. In this framework, using an ant colony optimization algorithm, the solution space of disassembly plans can be generated synchronously during the search process for best solutions. Finally, the new method’s validity is verified by a case study.     

Solving software project scheduling problems with ant colony optimization

Software project scheduling problem (SPSP) is one of the important and challenging problems faced by the software project managers in the highly competitive software industry. As the problem is becoming an NP-hard problem with the increasing numbers of employees and tasks, only a few algorithms exist and the performance is still not satisfying. To design an effective algorithm for SPSP, this paper proposes an ant colony optimization (ACO) approach which is called ACS-SPSP algorithm. Since a task in software projects involves several employees, in this paper, by splitting tasks and distributing dedications of employees to task nodes we get the construction graph for ACO. Six domain-based heuristics are designed to consider the factors of task efforts, allocated dedications of employees and task importance. Among these heuristic strategies, the heuristic of allocated dedications of employees to other tasks performs well. ACS-SPSP is compared with a genetic algorithm to solve the SPSP on 30 random instances. Experimental results show that the proposed algorithm is promising and can obtain higher hit rates with more accuracy compared to the previous genetic algorithm solution.     

An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed

This paper deals with the scheduling problem of minimizing the makespan in a permutational flowshop environment with the possibility of outsourcing certain jobs. It addresses this problem by means of the development of an ant colony optimization-based algorithm. This new algorithm, here named as flowshop ant colony optimization is composed of two combined ACO heuristics. The results show that this new approach can be used to solve the problem efficiently and in a short computational time.     

基于免疫蚂蚁算法的Job-shop调度问题

描述了作业调度问题，借鉴生物免疫机理提出了求解车间调度问题的免疫蚁群算法，该方法在蚂蚁搜索程中，运用免疫机理提取疫苗，并对进化种群进行免疫操作，从而有效地抑制了蚁群算法的“早熟”和搜索效率低下的问题，显著地提高了蚁群算法对全局最优解的搜索能力和收敛速度，给出了免疫蚁群算法的具体步骤，并对算法进行了实例验证。     

On solving permutation scheduling problems with ant colony optimization

A new approach for solving permutation scheduling problems with ant colony optimization (ACO) is proposed in this paper. The approach assumes that no precedence constraints between the jobs have to be fulfilled. It is tested with an ACO algorithm for the single-machine total weighted deviation problem. In the new approach the ants allocate the places in the schedule not sequentially, as in the standard approach, but in random order. This leads to a better utilization of the pheromone information. It is shown by experiments that adequate combinations between the standard approach which can profit from list scheduling heuristics and the new approach perform particularly well.     

一种求解Job-Shop调度问题的新型蚁群算法

Job-Shop调度问题是一类具有很高理论研究和工程应用价值的问题。针对使用蚁群算法求解Job-Shop调度问题时较难设置合适参数的问题,提出一种动态设置参数的新型蚁群求解算法。分析了蚁群算法中参数对求解结果的影响,给出了算法求解Job-Shop调度问题的关键技术和实现过程。最后对五个基本测试问题进行了仿真实验,并与遗传算法、模拟退火算法、基本蚁群算法进行了比较。结果表明,该算法能得到较优的结果,具有一定的应用价值。     

Multi-satellite control resource scheduling based on ant colony optimization

The multi-satellite control resource scheduling problem (MSCRSP) is a kind of large-scale combinatorial optimization problem. As the solution space of the problem is sparse, the optimization process is very complicated. Ant colony optimization as one of heuristic method is wildly used by other researchers to solve many practical problems. An algorithm of multi-satellite control resource scheduling problem based on ant colony optimization (MSCRSP–ACO) is presented in this paper. The main idea of MSCRSP–ACO is that pheromone trail update by two stages to avoid algorithm trapping into local optima. The main procedures of this algorithm contain three processes. Firstly, the data get by satellite control center should be preprocessed according to visible arcs. Secondly, aiming to minimize the working burden as optimization objective, the optimization model of MSCRSP, called complex independent set model (CISM), is developed based on visible arcs and working periods. Ant colony algorithm can be used directly to solve CISM. Lastly, a novel ant colony algorithm, called MSCRSP–ACO, is applied to CISM. From the definition of pheromone and heuristic information to the updating strategy of pheromone is described detailed. The effect of parameters on the algorithm performance is also studied by experimental method. The experiment results demonstrate that the global exploration ability and solution quality of the MSCRSP–ACO is superior to existed algorithms such as genetic algorithm, iterative repair algorithm and max–min ant system.     

基于移动机器人路径规划的鼠群算法

研究静态环境下机器人路径规划问题,并根据老鼠觅食行为提出一种鼠群算法.该算法引入环境因子和经验因子,每次搜索后对路径进行经验因子更新,通过迭代的方式寻找静态环境下机器人最佳路径.同时提出一种禁忌策略,有效地避免了路径死锁问题.理论分析和实验结果表明,该算法能使机器人在有较多障碍的环境下迅速找到一条优化路径,而且安全避碰,与同类算法相比具有一定的优越性.     

An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups

In many real-world production systems, it requires an explicit consideration of sequence-dependent setup times when scheduling jobs. As for the scheduling criterion, the weighted tardiness is always regarded as one of the most important criteria in practical systems. While the importance of the weighted tardiness problem with sequence-dependent setup times has been recognized, the problem has received little attention in the scheduling literature. In this paper, we present an ant colony optimization (ACO) algorithm for such a problem in a single-machine environment. The proposed ACO algorithm has several features, including introducing a new parameter for the initial pheromone trail and adjusting the timing of applying local search, among others. The proposed algorithm is experimented on the benchmark problem instances and shows its advantage over existing algorithms. As a further investigation, the algorithm is applied to the unweighted version of the problem. Experimental results show that it is very competitive with the existing best-performing algorithms.     

整合Petri网和蚁群优化算法用于柔性制造系统调度优化研究

以Petri网与蚁群优化算法相结合，求解柔性制造系统的调度问题，取得了明显的优化效果。以一个典型算例的调度优化为例，证明了算法的有效性。     

Scalable platforms using ant colony optimization

Mass customization necessitates increased product variety at the customers’ end but comparatively lesser part variety at the manufacturer’s end. Product platform concepts have been successful to achieve this goal at large. One of the popular methods for product platform formation is to scale one or more design variables called the scaling variables. Effective optimization methods are needed to identify proper values of the scaling variables. This paper presents a graph-based optimization method called the scalable platforms using ant colony optimization (SPACO) method for identifying appropriate values of the scaling variables. In the graph-based representation, each node signifies a sub-range of values for a design variable. This application includes the concept of multiplicity in node selection because there are multiple nodes corresponding to the discretized values of a given design variable. In the SPACO method, the overall decision is a result of the cumulative decisions, made by simple computing agents called the ants, over a number of iterations. The space search technique initially starts as a random search technique over the entire search space and progressively turns into an autocatalytic (positive feedback) probabilistic search technique as the solution matures. We use a family of universal electric motors, widely cited in the literature, to test the effectiveness of the proposed method. Our simulation results, when compared to the results reported in the literature, prove that SPACO method is a viable optimization method for determining the values of design variables for scalable platforms.     

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

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

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

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

Inducing decision trees with an ant colony optimization algorithm

Decision trees have been widely used in data mining and machine learning as a comprehensible knowledge representation. While ant colony optimization (ACO) algorithms have been successfully applied to extract classification rules, decision tree induction with ACO algorithms remains an almost unexplored research area. In this paper we propose a novel ACO algorithm to induce decision trees, combining commonly used strategies from both traditional decision tree induction algorithms and ACO. The proposed algorithm is compared against three decision tree induction algorithms, namely C4.5, CART and cACDT, in 22 publicly available data sets. The results show that the predictive accuracy of the proposed algorithm is statistically significantly higher than the accuracy of both C4.5 and CART, which are well-known conventional algorithms for decision tree induction, and the accuracy of the ACO-based cACDT decision tree algorithm.     

Job-Shop调度问题的量子蚁群算法求解*

针对最小化最大完工时间的作业车间调度问题,提出了一种量子蚁群调度算法.该算法结合了量子计算中量子旋转门的量子信息和蚁群寻优的特点,通过作业车间调度问题的析取图表示,将原问题转换为求解析取图的关动路径,并利用量子蚁群算法进行求解.采用该算法对作业车间调度问题的基准数据进行测试,仿真结果表明了该算法的可行性和有效性.     

改进蚁群算法水面无人艇平滑路径规划

针对水面无人艇的路径规划,首先用仿生学算法对环境障碍物做开运算,提出改进的蚁群算法搜索可行路径得到航路点序列,优化合并没有障碍物的相邻航路点并顺序连接,得到可行且无碰撞风险的全局路径;其次,使用Dubins曲线算法对连接点进行平滑处理,分析其几何特性并找出其不足之处;最后,引入贝塞尔三阶曲线理论对于已经优化过的折线段进行平滑处理,使其在满足最小旋转半径的同时,也满足USV动力学特性,最终得到一条优化可行的路径.仿真结果证明本算法设计的光滑路径在计算复杂度、路径优化等方面都有了较大的提高.     

变异蚁群优化算法在流水作业排序中的应用

在采用蚁群算法求解流水作业排序中,针对蚁群算法存在的时间过长及过早收敛问题,使用解锁素及信息素挥发率作为启发式信息并引入局部优化,对蚁群系统加以改进。计算机仿真结果表明,改进后的蚁群系统对流水作业优化调度有较好的效果。     

一种改进的机器人路径规划的蚁群算法

针对具有复杂回旋地形结构的机器人路径规划问题, 提出了一种改进的蚁群算法. 该算法引入自适应迁移概率函数实现蚁群具有正、反向运动的能力, 改善了算法的曲折迂回能力; 能见度信息中引入距离启发因素和障碍相交检测机制, 完成路径搜索与避障过程有机结合, 提高算法的搜索效率; 引入贪婪信息素更新策略和节点信息素分布, 降低了数据存储量, 改善了路径规划的效果和算法的收敛速度. 基于不同算法的比较仿真实验, 数值结果证实了该算法的有效性.     

Decomposition-based classified ant colony optimization algorithm for scheduling semiconductor wafer fabrication system

Due to its typical features, such as large-scale, multiple re-entrant flows, and hybrid machine types, the semiconductor wafer fabrication system (SWFS) is extremely difficult to schedule. In order to cope with this difficulty, the decomposition-based classified ant colony optimization (D-CACO) method is proposed and analyzed in this paper. The D-CACO method comprises decomposition procedure and classified ant colony optimization algorithm. In the decomposition procedure, a large and complicate scheduling problem is decomposed into several subproblems and these subproblems are scheduled in sequence. The classified ACO algorithm then groups all of the operations of the subproblems and schedules them according to machine type. To test the effect of the method, a set of simulations are conducted on a virtual fab simulation platform. The test results show that the proposed D-CACO algorithm works efficiently in scheduling SWFS.     

Diversity control in ant colony optimization

Optimization inspired by cooperative food retrieval in ants has been unexpectedly successful and has been known as ant colony optimization (ACO) in recent years. One of the most important factors to improve the performance of the ACO algorithms is the complex trade-off between intensification and diversification. This article investigates the effects of controlling the diversity by adopting a simple mechanism for random selection in ACO. The results of computer experiments have shown that it can generate better solutions stably for the traveling salesmen problem than AS_rank which is known as one of the newest and best ACO algorithms by utilizing two types of diversity.