多车场车辆路径问题的新型聚类蚁群算法

在对多车场带时间窗的车辆路径问题进行详细阐述的基础上,以车辆运输总费用最少为目标函数,建立了问题的数学模型。提出了先采用聚类蚁群算法将多车场带时间窗的车辆路径问题分解为若干个单车场车辆路径问题,然后对各单车场问题应用改进蚁群算法进行优化的求解思路。最后通过一个实例将这种新型聚类蚁群算法与就近分配禁忌搜索算法和K-均值算法的优化能力进行了对比。试验结果表明,该算法对优化多车场带时间窗的车辆路径问题的求解结果是相当令人满意的。     

多车场车辆路径问题的新型聚类蚁群算法

在对多车场带时间窗的车辆路径问题进行详细阐述的基础上,以车辆运输总费用最少为目标函数,建立了问题的数学模型.提出了先采用聚类蚁群算法将多车场带时间窗的车辆路径问题分解为若干个单车场车辆路径问题,然后对各单车场问题应用改进蚁群算法进行优化的求解思路.最后通过一个实例将这种新型聚类蚁群算法与就近分配禁忌搜索算法和K-均值算法的优化能力进行了对比.试验结果表明,该算法对优化多车场带时间窗的车辆路径问题的求解结果是相当令人满意的.     

LED芯片图像的势函数标记分水岭分割

全自动LED芯片测试分拣系统通过视觉图像处理精确定位LED芯片,其图像特征信息的提取建立在良好的图像分割基础上。为了精确提取图像特征,针对LED芯片图像的特点,改进了分水岭分割算法,采用直方图势函数提取标记,并在标记基础上对梯度图进行分水岭变换,实现了LED芯片图像的良好分割。实验结果表明,该方法有效地抑制了过分割现象,具有较好的抗噪性,对LED芯片图像感兴趣区域提取准确度高、鲁棒性强,分割效果较好。     

融合改进蚁群和DWA的移动机器人路径规划

针对传统蚁群算法搜索时间长、易陷入局部最优且动态规划能力弱等缺陷,提出一种融合改进蚁群和动态窗口算法（DWA,Dynamic Window Approach）的路径规划方法,解决移动机器人全局路径优化以及局部动态避障路径规划问题。在分析传统蚁群算法路径规划原理及优缺点的基础上,通过引入初始栅格转移规则、改变信息素更新方式、删除冗余节点、圆切障碍顶点等方法,提高蚁群算法的收敛速度、规划路径的平滑度以及安全可靠度;进一步在改进蚁群算法中引入DWA进行局部路径规划,实现机器人的动态避障。对比仿真结果表明,所提改进算法在路径长度、迭代次数、收敛时间以及路径平滑度、安全可靠度等性能指标上较传统算法均有所提高。     

改进蚁群算法在焊接机器人路径规划中的应用

路径规划是机器人研究的核心内容之一。为了解决针对于白车身生产线焊接机器人路径规划效率低下的问题,提出了一种改进的焊接机器人路径规划的方法,分析了焊接机器人路径规划问题的构成。并针对基础蚁群算法在解决焊接机器人路径规划时,容易出现搜索时间过长、效率低、容易陷入局部最优等问题,引用了粒子群算法。利用粒子群算法对蚁群算法随机产生的若干组较优解进行交叉和变异操作,得到了更有效的解。最后在MATLAB中利用优化后的蚁群算法计算最佳焊接路径,并与基础蚁群算法的结果对比。对比情况表明:优化的蚁群算法在解决焊接机器人路径规划问题上能得到更优的焊接路径和稳定性。     

改进蚁群算法下激光切割加工工艺优化研究

针对传统算法下激光切割加工工艺速度慢的问题,提出改进蚁群算法下激光切割加工工艺优化设计,根据激光切割加工工艺原理,选择激光切割加工工艺参数,在此基础上对穿孔点进行确定,并引用蚁群算法,确定激光切割加工路径,选择出最短路径,以此实现对激光切割加工工艺的优化。为保证此次设计的优化方法具有一定的实际应用意义,与改进前的加工工艺进行了对比,结果表明,该优化方法能减少激光器在每个加工轮廓之间移动所需要的时间,并且通过蚁群算法能够更快得到最优加工路径。     

单模单冲数控冲床加工路径优化方法研究

金属板上各孔冲裁顺序直接影响数控冲床冲裁加工时的生产效率。针对目前传统数控冲床加工路径算法单一、加工时间长及路径长度偏大等问题,提出一种基于有选择的最近邻算法和改进蚁群算法的加工路径优化方法。该方法对常见的矩形高密度冲孔板采用最近邻算法,对非矩形阵列分布的孔形采用改进的蚁群算法。实验结果表明,优化后的加工路径在长度及计算时间上取得了较好的效果,提高了冲床加工的效率。     

基于改进蚁群算法的立体仓库三维空间路径优化

拣货作业作为在制造企业仓储系统中重要环节,其工作效率直接影响整个仓储系统的运行速度和工作成本.首先基于现有蚁群搜索算法,研究了将原有的二维平面搜索路线空间扩展到三维空间的改进蚁群算法;其次对改进蚁群算法进行仓储三维空间路径优化研究,针对现有仓库货架模型,将蚁群算法中两点间的直线路径转化成水平与垂直的折线路径将概率模型与禁忌表方法加入到改进蚁群算法,避免局部最优解的情况;最后将改进蚁群算法与其他代表性优化算法比较.实例验证结果表明,改进蚁群算法方法能有效地提高在仓储系统三维空间内路径规划的效率与速度.     

基于改进蚁群算法的激光切割加工路径优化研究

针对激光切割加工全局路径优化采用传统蚁群系统算法时,存在收敛速度慢、易陷入局部最优的问题,对蚁群系统算法进行了改进研究。利用激光加工图元的起点和终点信息,建立了图元等价TSP问题的数学模型,提出了通过最邻近插入算法对蚁群系统算法路径规划结果进行了再优化的改进算法;详细阐述了改进蚁群系统算法的实现步骤,分析了传统蚁群系统算法和改进蚁群系统算法的迭代次数和优化效果。研究结果表明:该改进蚁群系统算法加快了收敛速度,迭代次数减少了约30%,缩短了激光加工所走路径的总长度,并成功应用到自主开发的高速激光切割加工系统中。     

孔群分类加工路径的优化算法

柔性钣金加工中心采用钻削或攻丝加工孔群时,为缩短刀具空走行程并提高孔群加工效率,针对孔群中圆孔需分类使用不同刀具加工问题,提出蚁群算法与贪心算法相结合的混合算法对孔群加工路径进行优化。该混合算法对同一种类孔群中的孔采用蚁群算法优化路径,不同种类孔群间的过渡应用贪心算法优化。通过在自主开发钣金刻铣加工CAD/CAM软件中,将所提出的混合算法与X向路径法、Y向路径法、贪心算法、蚁群算法进行实验对比。对分布无序的3类41个圆孔的孔群加工实验,结果表明:混合算法优化后路径长度比X向路径法优化后缩短42.84%,比Y向路径法优化后缩短48.93%,比贪心算法优化后缩短11.10%,比蚁群算法优化后缩短6.19%。由此可见,本文所提出的混合算法能够更有效缩短分类孔群加工路径,提高加工效率。     

一种新型蚁群随机树的机器人路径规划算法

为提高复杂环境下机器人的路径规划效率,提出了一种用蚁群算法来优化随机树算法的新的全局路径规划算法。该算法有效地结合了蚁群和随机树算法的优点,利用随机树算法的高效性快速收敛到一条可行路径,将该路径转换为蚁群的初始信息素分布,可以减少蚁群算法初期迭代; 然后利用蚁群算法的反馈性优化路径,求得最优路径。仿真实验表明,该蚁群随机树算法可以提高机器人路径规划的速度,并且在任何复杂环境下迅速规划出最优路径。     

Ant colony optimization algorithm for stochastic project crashing problem in PERT networks using MC simulation

This paper describes a new approach based on ant colony optimization (ACO) metaheuristic and Monte Carlo (MC) simulation technique, for project crashing problem (PCP) under uncertainties. To our knowledge, this is the first application of ACO technique for the stochastic project crashing problem (SPCP), in the published literature. A confidence-level-based approach has been proposed for SPCP in program evaluation and review technique (PERT) type networks, where activities are subjected to discrete cost functions and assumed to be exponentially distributed. The objective of the proposed model is to optimally improve the project completion probability in a prespecified due date based on a predefined probability. In order to solve the constructed model, we apply the ACO algorithm and path criticality index, together. The proposed approach applies the path criticality concept in order to select the most critical path by using MC simulation technique. Then, the developed ACO is used to solve a nonlinear integer mathematical programming for selected path. In order to demonstrate the model effectiveness, a large scale illustrative example has been presented and several computational experiments are conducted to determine the appropriate levels of ACO parameters, which lead to the accurate results with reasonable computational time. Finally, a comparative study has been conducted to validate the ACO approach, using several randomly generated problems.     

VIRTUAL PROCESSING OF LASER SURFACE HARDENING ON AUTOBODY DIES

A new method of collision-free path plan integrated in virtual processing is developed to improve the efficiency of laser surface hardening on dies. The path plan is based on the premise of no collision and the optimization object is the shortest path. The optimization model of collision-free path is built from traveling salesman problem (TSP). Collision-free path between two machining points is calculated in configuration space (C-Space). Ant colony optimization (ACO) algorithm is applied to TSP of all the machining points to fmd the shortest path, which is simulated in virtual environment set up by IGRIP software. Virtual machining time, no-collision report, etc, are put out after the simulation. An example on autobody die is processed in the virtual platform, the simulation results display that ACO has perfect optimization effect, and the method of virtual processing with integration of collision-free optimal path is practical.     

Rolling element bearing fault detection using support vector machine with improved ant colony optimization

In support vector machine (SVM), it is quite necessary to optimize the parameters which are the key factors impacting the classification performance. Improved ant colony optimization (IACO) algorithm is proposed to determine the parameters, and then the IACO-SVM algorithm is applied on the rolling element bearing fault detection. Both the optimal and the worst solutions found by the ants are allowed to update the pheromone trail density, and the mesh is applied in the ACO to adjust the range of optimized parameters. The experimental data of rolling bearing vibration signal is used to illustrate the performance of IACO-SVM algorithm by comparing with the parameters in SVM optimized by genetic algorithm (GA), cross-validation and standard ACO methods. The experimental results show that the proposed algorithm of IACO-SVM can give higher recognition accuracy.     

基于改进蚁群算法的机器人末端路径排序优化

建立了针对机器人加工时的末端运动路径排序优化问题的数学模型,将该模型转化为广义旅行商问题并用蚁群算法求解。同时对经典的蚁群算法进行了改进,即采用多阶段搜索策略、邻域搜索策略及多蚁种搜索策略,使改进后的蚁群算法能为机器人求取一条更优的末端运动路径。计算机仿真与机器人加工实验结果表明,改进蚁群算法所得的末端运动路径比基本蚁群算法所得结果缩短了3%以上。     

基于矩阵算式和蚁群算法的元功能链设计方案优化方法*

为解决矩阵算式求解元功能链设计方案过程中缺乏优化工具的问题,提出了一种矩阵算式结合蚁群算法的优化方法。分析了相似性理论,用相似度和广义距离表征两个相邻元件的兼容性;定义了相似度矩阵,并使之与设计方案矩阵关联计算,获得了蕴含元件相似度信息的设计方案矩阵;定义了设计方案的评价模型和基于蚁群算法的优化模型,给出了评价参数、权重以及评价值的计算方法;以元件的评价得分作为信息素,以广义距离作为相邻节点路径的长度,构建了信息素矩阵和概率矩阵;将方案求解问题转化为组合优化的最优路径问题,用蚁群算法直接优化蕴含在设计方案矩阵中的方案,得到了同时满足结构需求、功能需求、评价需求的设计方案。通过某三轴伺服传送机构设计方案优化的实例,验证了方法的有效性。     

Industrial applications of the ant colony optimization algorithm

The ant colony optimization (ACO) algorithm is a fast suboptimal meta-heuristic based on the behavior of a set of ants that communicate through the deposit of pheromone. It involves a node choice probability which is a function of pheromone strength and inter-node distance to construct a path through a node-arc graph. The algorithm allows fast near optimal solutions to be found and is useful in industrial environments where computational resources and time are limited. A hybridization using iterated local search (ILS) is made in this work to the existing heuristic to refine the optimality of the solution. Applications of the ACO algorithm also involve numerous traveling salesperson problem (TSP) instances and benchmark job shop scheduling problems (JSSPs), where the latter employs a simplified ant graph-construction model to minimize the number of edges for which pheromone update should occur, so as to reduce the spatial complexity in problem computation.     

An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs

The problem of scheduling in flowshops with sequence-dependent setup times of jobs is considered and solved by making use of ant colony optimization (ACO) algorithms. ACO is an algorithmic approach, inspired by the foraging behavior of real ants, that can be applied to the solution of combinatorial optimization problems. A new ant colony algorithm has been developed in this paper to solve the flowshop scheduling problem with the consideration of sequence-dependent setup times of jobs. The objective is to minimize the makespan. Artificial ants are used to construct solutions for flowshop scheduling problems, and the solutions are subsequently improved by a local search procedure. An existing ant colony algorithm and the proposed ant colony algorithm were compared with two existing heuristics. It was found after extensive computational investigation that the proposed ant colony algorithm gives promising and better results, as compared to those solutions given by the existing ant colony algorithm and the existing heuristics, for the flowshop scheduling problem under study.     

Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems

Ant colony optimization (ACO) is a novel intelligent meta-heuristic originating from the foraging behavior of ants. An efficient heuristic of ACO is the ant colony system (ACS). This study presents a multi-heuristic desirability ACS heuristic for the non-permutation flowshop scheduling problem, and verifies the effectiveness of the proposed heuristic by performing computational experiments on a well-known non-permutation flowshop benchmark problem set. Over three-quarters of the solutions to these experiments are superior to the current best solutions in relevant literature. Since the proposed heuristic is comprehensible and effective, this study successfully explores the excellent potential of ACO for solving non-permutation flowshop scheduling problems.     

Simulated annealing and ant colony optimization algorithms for the dynamic throughput maximization problem

In many industries, inspection data is determined to merely serve for verification and validation purposes. It is rarely used to directly enhance the product quality because of the lack of approaches and difficulties of doing so. Given that a batch of subassembly items have been inspected, it is sometimes more profitable to exploit the data of the measured features of the subassemblies in order to further reduce the variation in the final assemblies so the rolled yield throughput is maximized. This can be achieved by selectively and dynamically assembling the subassemblies so we can maximize the throughput of the final assemblies. In this paper, we introduce and solve the dynamic throughput maximization (DTM) problem. The problem is found to have grown substantially by increasing the size of the assembly (number of subassembly groups and number of items in each group). Therefore, we resort to five algorithms: simple greedy sorting algorithm, two simulated annealing (SA) algorithms and two ant colony optimization (ACO) algorithms. Numerical examples have been solved to compare the performances of the proposed algorithms. We found that our ACO algorithms generally outperform the other algorithms.