用蚁群算法在刀库索引位置的优化配置外文翻译、英汉互译、中英对照.docx

optimal allocation of index positions on tool magazines using an ant colony algorithmabstract generation of optimal index positions of cutting tools is an important task to reduce the non-machining time of cnc machines and for achievement of optimal process plans. the present work proposes an application of an ant colony algorithm, as a global search technique, for a quick identification of optimal or near optimal index positions of cutting tools to be used on the tool magazines of cnc machines for executing a certain set of manufacturing operations. minimisation of total indexing time is taken as the objective function.keywords indexing time . automatic tool change .cnc machine . optimization . ant colony algorithm1 introduction in todays manufacturing environment, several industries are adapting flexible manufacturing systems (fms) to meet the ever-changing competitive market requirements. cnc machines are widely used in fms due to their high flexibility in processing a wide range of operations of various parts and compatibility to be operated under a computer controlled system. the overall efficiency of the system increases when cnc machines are utilized to their maximum extent. so to improve the utilization, there is a need to allocate the positions of cutting tools optimally on the tool magazines. the cutting tools on cnc machines can be changed or positioned automatically when the cutting tools are called within the part program. to do this turrets are used in cnc lathe machines and automatic tool changers (atc) in cnc milling machines. the present model can be used either for the atc magazines or turrets on cnc machines. the indexing time is defined as the time elapsed in which a turret magazine/atc moves between the two neighbouring tool stations or pockets. bi-directional indexing of the tool magazine is always preferred over uni-directional indexing to reduce the non-machining time of the machine. in this the magazine rotates in both directions to select automatically the nearer path between the current station and target station. the present work considers bi-directional movement of the magazine. in bidirectional indexing, the difference between the index numbers of current station and target station is calculated in such a way that its value is smaller than or equal to half of the magazine capacity. dereli et al. 1 formulated the present problem as a “traveling salesman problem” (tsp), which is np complete. they applied genetic algorithms (ga) to solve the problem. dorigo et al. 2, 3 introduced the ant colony algorithm (aca) for solving the np-complete problems. aca can find the superior solution to other methods such as genetic algorithms, simulated annealing and evolutionary programming for large-sized np-complete problems with minimum computational time. so, aca has been extended to solve the present problem.2 methodologydetermination of the optimal sequence of manufacturing operations is a prerequisite for the present problem. this sequence is usually determined based on minimum total set-up cost. the authors 4 suggested an application of aca to find the optimal sequence of operations. once the sequence of operations is determined, the following approach can be used to get the optimal arrangement of the tools on the magazine.step 1 initially a set of cutting tools required to execute the fixed (optimal) sequence of the manufacturing operations is assigned. each operation is assigned a single cutting tool. each tool is characterized by a certain number. for example, let the sequence of manufacturing operationsm1-m4-m3-m2-m6-m8-m9-m5-m7-m10 be assigned to the set of cutting tools t8-t1-t6-t4-t3-t7-t8-t2-t6-t5. the set of tools can be decoded as 8-1-6-4-3-7-8-2-6-5. here the manufacturing operation m1 requires cutting tool 8, m4 requires 1 and so on. in total there are eight different tools and thus eight factorial ways of tool sequences possible on the tool magazine. step 2 aca is applied as the optimization tool to find the best tool sequence that corresponds to the minimum total indexing time. for every sequence that is generated by the algorithm the same sequence of index positions (numbers) is assigned. for example, let the sequence of tools 4-6-7-8-2-5-3-1 be generated and hence assigned to the indexing positions 1-2-3-4-5-6-7-8 in the sequential order, i.e. tool 4 is assigned to the 1st position, tool 6 to the 2nd position and so on.step 3 the differences between the index numbers of subsequent cutting tools are calculated and then totaled to determine the total number of unit rotations for each sequence of cutting tools. absolute differences are to be taken while calculating the number of unit rotations required from current tool to target tool. this following section describes an example in detail. the first two operations m1 and m4 in the pre-assumed fixed sequence of operations require the cutting tools 8 and 1, respectively. the tool sequence generated by the algorithm is 4-6-7-8-2-5-3-1. in this sequence tools 8 and 1 are placed in the 4th and 8th indexing positions of the turret/ atc. hence the total number of unit rotations required to reach from current tool 8 to target tool 1 is | 4-8 |= 4. similarly the total number of unit rotations required for the entire sequence is | 4-8 |+| 8-2 |+| 2-1 |+| 1-7 |+| 7-3 |+| 3-4 |+|4-5 |+| 5-2 |+| 2-6 |=30. step 4 minimization of total indexing time is taken as the objective function. the value of the objective function is calculated by multiplying the total number of unit rotations with the catalogue value of turret/atc index time. if an index time of 4 s is assumed then the total index time required for the tool sequence becomes 120 s.step 5 as the number of iterations increases aca converges to the optimal solution.3 allocation policy the following are the three cases where the total number of available positions can be related with the total number of cutting tools employed. case 1 the number of index positions is equal to the number of cutting tools case 2 the number of index positions is greater than the number of cutting tools (a) without duplication of tools, (b) with duplication tools case 3 the number of index positions is smaller than the number of cutting tools if the problem falls into case 1, duplication of cutting tools in the tooling set is not required as the second set-up always increases the non-machining time of the machine. table 1 list of features and their abbreviationsin case 2, the effect of duplication of cutting tools should be tested carefully. most of the times the duplication of tooling is too expensive. case 3 leads to finding the cutting tools to be used in the second set-up. however, other subphases are possible in cases 2(b) and 3. the duplicated tools may be used in such a way that no unloaded index is left on atc or some indexing positions are left unloaded.table 2 operations assigned to the features4 ant colony algorithmthe ant colony algorithm (aca) is a population-based optimization approach that has been applied successfully to solve different combinatorial problems like traveling salesman problems 2, 3, quadratic assignment problems 5, 6, and job shop scheduling problems 7. this algorithm is inspired by the foraging behaviour of real life ant colonies in which individual ants deposit a substance called pheromone on the path while moving from one point to another. the paths with higher pheromone would be more likely to be selected by the other ants resulting in further amplification of current pheromone trails. because of this nature, after some time ants will select the shortest path. the algorithm as applicable to the present problem is described in the following section.it is assumed that there is k number of ants and each ant corresponds to a particular node. the number of ants is taken as equal to the number of nodes required to execute the fixed set of manufacturing operations. the task of eachant is to generate a feasible solution by adding a new cutting tool at a time to the current one, till all operations are completed. an ant k situated in state r moves to state s using the following state transition rule:table 3 cutting tools assigned to optimal sequence of operations where (r, s) is called a pheromone level. (r, s)s are changed at run time and are intended to indicate how useful it is to make move s when in state r. (r, s) is a heuristic function, which evaluates the utilityof move s when at r. in the present work, it is the inverse of the number of unit rotations required to move from r to s.parameter weighs the relative importance of the heuristic function. q is a value chosen randomly with uniform probability in 0,1, and q0 e0 q0 1t is a parameter. the smaller the q0, the higher the probability to make a random choice. in short q0 determines the relative importance of exploitation versus exploration in eq. 1.jk(r) represents the number of states still to be visited by the k ant when at r.s is a random variable selected according to the distributiongiven by eq. 2, which gives the probability with which an ant in operation r chooses s to move to. this state transition rule will favour transitions towards nodes connected by short edges with high amount of trail.4.1 local updating rule while building a solution, ants change their trails by applying the following local updating rule:where 0 represents the initial pheromone value.4.2 global updating rule global trail updating provides a higher amount of trail to shorter solutions. in a sense this is similar to a reinforcement learning scheme in which better solutions get a higher reinforcement.once all ants have completed their solutions, edges (r, s) belonging to the shortest solution made by an ant have their trail changed by applying the following global updating rule. where lbest-iter is the best solution obtained in an iteration that has the minimum total indexing time. is the pheromone decay parameter, which is a value in between 0 and 1. the parameter values 3 are set as =2, q0=0.9, and.4.3 local search mechanismmany ant systems are hybrid algorithms employing some kind of local optimization techniques such as 2-opt technique, tabu search, simulated annealing etc. once each ant has constructed a solution, a local search mechanism is used to further improve the solution to its local optimum and finally the pheromone levels are updated based on its solution. this integration significantly increases the effectiveness and efficiency of ant colony algorithms. in the present work, the 2-opt technique is used as the local search. fig. 3 convergence of aca5 case study the example part taken for the present work is shown in fig. 1. it contains 18 features. the features and their abbreviations are listed in table 1. the operations required to execute the features are exhibited in table 2. the preassumed fixed sequence of operations and the assignmentof a cutting tool to each operation are shown in table 3. the maximum number of cutting tools and the indexing time of atc are taken as 28 and 0.69 s, respectively. the objective lies in finding the positions of cuttingtools on the tool magazine for completing the sequence of operations: m1-m2-m3-m4-m5-m6-m7-m8-m9-m10-m11-m12-m13-m14-m15-m16-m17-m18-m19-m20-m21-m22-m23-m24-m25-m26-m27. the corresponding tools required to perform the above operations in the sequential order are t1-t1-t2-t3-t4-t2-t2-t2-t2-t5-t6-t5-t7-t5-t5-t8-t9-t5-t10-t5-t11-t5-t12-t5-t13-t5-t14.the total number of different tools required here are 14and hence there are 14 (!) ways of sequencing the cutting tools. the problem described here falls into case 2(a) where the total number of index positions is greater than the number of cutting tools without duplication of tools. aca is applied to get the set of positions of cutting tools that results in the minimum total indexing time to complete the above stated fixed sequence of operations.execution time has been reduced to 14 s. it is observed that aca gets the optimal solution in quicker time than ga. figure 3 exhibits the convergence of aca. the best solution obtained in each iteration is plotted against the iteration number. the optimal solution is obtained in the 10th iteration. to ensure the optimal solution, the graph is extended for a maximum of 18 iterations.7 conclusion since the present problem can be modeled as a traveling salesman problem, the present work deals with the development of an aca-based system for the optimization of turret index positions of cutting tools to be used on the turret or atc magazine of the cnc machine tools. even a small saving in the total turret indexing time will cause a significant increase in machining time in high-volume production. this leads to increased utilization of cnc machine tools and hence the overall efficiency of the system.references1. dereli t, filiz h (2000) allocating optimal index positions ontool magazines using genetic algorithms. robotics auton syst33:1551672. dorigo m, maniezzo v, colorni a (1996) the ant system:optimisation by a colony of cooperating agents. ieee transsyst man cybern 26(1):29413. dorigo m, gambardella lm (1997) ant colony system: a cooperativelearning approach to the traveling salesman problem.ieee trans evol comput 1(1)53664. krishna ag, rao km (2004) optimisation of operationssequence in capp using ant colony algorithm. int j adv manuftechnol (in press)5. gambardella lm, taillard ed, dorigo m (1999) ant coloniesfor the qap. j oper res soc 50:1671766. stutzle t, dorigo m (1999) aco algorithms for the quadraticassignment problems. in: corne d, dorigo m, glover f (eds)new ideas in optimization. mcgraw-hill, new york7. colorni a, dorigo m, maniezzo v, trubian m (1994) antsystem for job-shop scheduling. belg j oper res stat computsci 34(1):3953 用蚁群算法在刀库索引位置的优化配置摘要:生成最优的索引位置切割工具是一个重要的任务，以减少非加工时间数控机床和成就的最佳工艺计划.目前的工作提出了蚂蚁的应用蚁群算法，作为一个全球性的搜索技术，为迅速确定的最优或接近最优的索引位置刀具上使用数控刀库机器执行一组特定的制造业务。最小化的总的索引时间被当作目标函数.关键字:索引的时间 自动换刀 数控机床 优化 蚁群算法1 引言 在当今的制造环境中，几个行业适应柔性制造系统（fms），以满足不断变化的竞争市场需求。 cnc机广泛应用于fms中，由于其高的灵活性在加工范围广泛的各种操作下一个计算机控制的操作部件和兼容性系统。该系统的整体效率增加数控机床是其最大的利用程度。因此，为了提高利用率，有一个需要分配优化刀具的位置的刀库。 数控机床的切削工具，可以改变或自动定位切割工具被称为时内的部分程序。要做到这刀塔采用数控车床，cnc自动换刀装置（atc）在铣床。本模型可以使用，也可以用于atc刀库或刀塔数控机床。 索引的时间被定义为经过这两者之间的时间的刀塔刀库/ atc移动邻近的工具站或口袋。双向刀库的索引总是优于单方向的索引，以减少非加工时间的机器。在此刀库在两个方向上旋转自动选择较近的路径之间的当前的测站和目标站。本工作考虑双向运动的刀库。在双向索引，索引之间的差异当前站和目标站的数目来计算在这样一种方式，它的值是小于或等于一半的弹匣容量。 dereli等制定本问题作为“旅行商问题 ”（tsp），这是np完全的。他们采用遗传算法（ga）来解决问题，多里戈等。 2，3介绍了蚁群算法（aca）用于解决np完全问题。aca可以找到其他方法优越的解决方案，如遗传算法，模拟退火和进化编程大型np完全问题以最小的计算时间。因此，aca一直延伸到解决目前的问题。2 方法现在的问题是制造的最优序列测定操作的前提条件。这通常是确定的基础上最低的总序列设置成本。文献4提出了应用aca找到最佳的操作顺序。一旦的操作顺序来确定，下面的方法可以使用，以获得最佳的安排刀库上的工具。步骤1 首先需要执行的一组刀具制造业务的固定序列（最佳）被分配。每个操作都被分配了一个单一的切割工具。每个工具的特征在于由一定数目。为例如，让我们制造业务的序列m1-m4-m3-m2-m6-m8-m9-m5-m7-m10分配一套刀具t8-t1-t6-t4-t3-t7-t8-t2-t6-t5。工具集可以被解码为8-1-6-4-3-7-8-2- 6-5。这里经营生产的m1要求切削刀具8，m4要求1，依此类推。总共有八个不同的工具，从而8阶乘方式工具序列可能在刀库。步骤2 aca优化工具找到最好的工具的序列，该序列对应于最小的总索引的时间。对于每一个所产生的序列，该序列算法相同顺序的索引位置（数字）被分配。例如，让我们的工具4-6-7的顺序 - 8-2-5-3-1来生成，因此分配给索引的位置1-2-3-4-5-6-7-8的顺序，即工具4被分配到第一位置，工具6的第二位置等。 步骤3 索引号之间的差异随后的切削工具的计算，然后合计为确定的总数为每个单元的旋转序列的切割工具。绝对差异是计算所需的单位转数时拍摄从当前工具目标的工具。在此之前，本节中详细描述的一个例子。前两个操作在预先假设的m1和m4固定的操作顺序要求刀具分别是8和1。由算法生成的刀具序列是4-6-7-8-2-5-3-1。在这个序列中的工具8和1被放置在转台/第4和第8的分度位置atc。因此，总的数量所需的单位转从目前的工具达到8目标工具1|4-8| = 4。同样，所需的单元转总数整个序列是|4-8|+|8-2|+|2-1| +|1-7|+|7-3| +|3-4|+ |4-5| +|5-2| +|2-6|= 30。步骤4 最小化总的索引时间被当作目标函数。目标函数的值是计算的总数乘以单位转的目录价值的刀塔/ atc指数的时间。如果时间为4 s，假定指数总指数时间所需的刀具序列变为120秒。步骤5 随着迭代次数的增加aca收敛到最优解。3 分配政策以下是3个的情况下的总数目可利用的位置的总数可以与切削工具。第1种情况 索引位置的数目等于数量的切削工具 第2种情况 的索引位置的数目是大于一些刀具（a）不重复的工具，（b）与复制工具第3种情况 索引位置的数目是小于数量的切削工具如果问题落入第1种情况，重复切割工具，在工具中不是必需的作为第二设置总是增加的机器的非加工时间。 图1例部分 表1列出的功能和它们的缩写在第2种情况中，重复切削工具的效果应该仔细测试。大部分的时候，重复工装是太贵了。第3种情况寻找切削刀具可以使用在所述第二设定。然而，其他的子阶段可能在例2（b）和3。所复制的工具可能是以这样的方式，没有卸载指数被留在atc或使用卸载留下一些索引位置。 表2 操作的特点4 蚁群算法蚁群算法（aca）是一个以人群为基础的优化方法，已被成功地应用于解决不同的组合问题，如旅行商问题2，3，二次分配问题5，6，作业车间调度问题7。该算法是现实生活中蚂蚁的觅食行为的启发在单个蚂蚁存入一个被称为信息素的物质的路径上移动的同时从一个点到另一个。信息素具有较高的路径，将更有可能被选择的其他的蚂蚁造成进一步放大目前的信息素。由于这种性质，经过一段时间后，蚂蚁会选择最短的路径。算法适用于现在的问题是在下面的部分中。它是假定存在数k蚂蚁数量和每个蚂蚁对应于一个特定的节点。蚂蚁的数量是执行所需的节点的数目等于组固定的生产业务。每个蚂蚁的任务是产生一个可行的解决方案，通过添加新的切割工具，在当前的