Research Article
Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
School of Mechanical Engineering, Qingdao Technological University, Qingdao 266033, China
LiveDNA: 86.5072
Laser processing is widely used in sheet cutting and rapid prototyping and the path planning problem is involved in these process (Huang et al., 2009; Chou et al., 2008). Path planning affects the processing time, the accuracy (Huang and Lan, 2006) etc. In this study, we considered the processing time that is the typical objective. In the process of laser cutting or laminated object manufacturing, the total processing time equal to the sum of laser scanning time and spare travel time. The length of workpiece contour is unchanged, that is the laser scanning time is unchanged, so the processing time is reduced only if the spare travel time is shortened (Liu et al., 2004). There are many workpiece contours in one steel plate or one layer, if the scanning path is improper for designing, there will be exit many redundant path and the productivity will be reduced. So, contour path planning has practical significance, it can shorten redundant path, save processing time (Wang and Xie, 2005; Chou et al., 2008).
In laser cutting and laminated object manufacturing, the workpiece contours are all enclosed loops, the movement trajectory of laser head is uniquely and the starting point and end point of scanning are the same point, therefore. When optimization the path, the specific trajectory of workpiece contour can be ignored, instead by a feature point which selected from the contour and the feature point stands for the starting and end point of scanning. The contour can be simplified to the point set in the plane and the path planning problem is transformed into finding the shortest path among the point sets. Thus, the contour path planning problem is similar to the Traveling Salesman Problem (TSP) (Wiener et al., 2009), but the starting and end point of contour is variable and the point is selected from feature points of contour, that can reduce the computation time (Son et al., 2003).
THE OPTIMIZATION MODEL
The essence of contour path planning in laser processing is the optimization of spare travel path. We only need to select a feature point from each contour and the feature point is the starting and end point of scanning. A permutation of all the feature points is one path.
The shortest path is usually taken as objective function, but the shortest path is not equal to the fastest path. For laser processing, the laser head can move with the maximum speed along X and Y axis during spare travel and the maximum speed is fixed. Therefore, the spare travel time from feature point pi(xi, yi) of one contour to feature point pj(xj, yj) of another contour depends on the value max(|xj-xi|, |yj-yi|) and not depends on the distance between the two points (Yang et al., 2005). For example, in Fig. 1, it takes the same amount of time from O point moving to A, B, C and D point, although their length are not equal. But the running time from O point moving to E point is longer than above time.
Therefore, we get optimization model of contour path planning with the optimization objective of minimum spare travel time. That is:
(1) |
where, n is the total number of contours.
Fig. 1: | The diagram of spare travel time |
At the same time, two restricts need to be considered, all the contours must be manufactured and the movement trajectory of laser head should not repeat.
IMPROVED ALGORITHM DESIGN
Dual coding method: The coding method is the basis for solving problem effectively in genetic algorithm. Contour path planning is similar to the TSP, but they are different. Contour path planning is not only to optimize the scanning sequence of contours, but also to optimize the starting point for each contour. In order to optimize the two subproblems simultaneously, we designed the dual coding method and the integer coding are adopted in the two layers. The first layer indicates the contour processing sequence and the second layer indicates the starting point of each contour.
In the processing sequence layer, the gene indicates the contour number, the permutation of gene indicates the processing sequence of contours. The genes include all the contour number and the value of gene is not repeated, so the two restricts can be satisfied.
In the starting point layer, the integer gene indicates the scanning starting point of each contour and the gene value is selected from the feature points of corresponding contour. In order to reduce computation time, we select some special points from each contour as the feature points. When the contour is a polygon, the vertexes are feature points.
Fig. 2(a-b): | Example of (a) Contour path and (b) The corresponding chromosome |
When the contour is circle or ellipse, we can divide the 360 degrees into m equal parts, the gene {1,2, ..., m} corresponds to {360°/m, 2x360°/m, , 360°}. In this study, we divide 360 degrees into 8 equal parts.
An example of contour path as shown in Fig. 2a, the chromosome C1 as shown in Fig. 2b is corresponding to the path.
The processing sequence is contour 1 (the starting point is 6), contour 4 (the starting point is 1), contour 2 (the starting point is 3), contour 5 (the starting point is 2), contour 3 (the starting point is 4).
Generation of initial solution: In order to meet the constraints and avoid generating infeasible solutions, we designed the following method of generating initial solutions. The coding of the processing sequence layer should be generated firstly, let the first gene value equal to one integer that is randomly selected from 1 to n, the second gene value is another integer that is randomly selected from the others number and so on, until all the contour number are included in the genes. Then the coding of the starting point layer is generated, the gene value is equal to a random integer in the range from 1 to the number of feature points which correspond to their own contour. The initial solutions generated by this method are all feasible solutions.
Fitness function: The genetic algorithm is only suitable for maximum optimization problem, but the objective of the contour path planning is to minimise the spare travel time. At the same time, in order to improve the performance of the algorithm. In the initial period, the fitness function value of each individual should be equal approximately, to avoid occupying the whole population by some better individuals and overcome the premature convergence. With the algorithm going on, the variance of fitness function value of different individuals should increase gradually, in order to prevent search from being in stagnation behavior. Therefore, based on the objective function, we designed the following transformation method:
(2) |
where, Fi is the fitness function value, is the average, objective function value of current population, fmax, fmin are the maximum and minimum objective function value in the current population, respectively, λ, α are adjustment parameters, k is the iteration number. In this study, we set λ and α equal to 0.1 and 1.02, respectively. So in the first iteration, the ratio of the minimum fitness function value Fmin to the maximum fitness function value Fmax is 0.907. When in the 200th iteration, the ratio is 0.16. The adjustment goal is achieved.
Crossover operation: Crossover can be considered as the backbone of the genetic algorithm, it determines the quality of the whole algorithm. In order to make the improved genetic algorithm adapt to the contour path planning, it is important to guarantee the feasibility of offspring. In order to avoid generating infeasible solution, and improve optimal performance of the algorithm, we design a variety of crossover methods that adapt with the problem, randomly select one method from the following three methods.
Contour processing sequence crossover: This crossover method is aimed at the first layer. The order crossover method is adopted and the starting point of each contour is not changed. Randomly select two parent individuals and two crossover points, the two substrings between two points (include the two points) are copied to the new offspring individuals, respectively. The remaining coding of offspring individuals obtained through removing existing coding in another parent individual. For example, as shown in Fig. 3, we select C1 and C2 as parent individuals. Assuming the crossover points are 2 and 3, so the gene 4 and 2 in C1 are copied to Ccc1 and their place remain unchanged. Removing gene 4 and 2 in C2, the remaining gene 5, 3 and 1 are filled into Ccc1, and keeping permutation constant, so we can get the offspring Ccc1. Using similar method, we can get the offspring Ccc2.
Starting point crossover: In this crossover, keeps the contour processing sequence unchanged, we designed two kinds of methods, select one randomly. The first method is improved single point crossover.
Fig. 3: | Example of contour processing sequence crossover |
Fig. 4: | Example of starting point crossover |
The crossover point is randomly generated that is larger than 1 and not exceeding n, if the two parent individuals have the same contour number on the left side of the crossover point, then exchange the starting point of the contour. For example, as shown in Fig. 4.
We also select C1 and C2 as parent individuals, the crossover point is 4. The two parents have contours 2, 4 and 5 in common on the left side of crossover point 4, so we exchange the starting point of contours 2, 4 and 5, respectively and the other starting point are not changed. So, we can get the offspring Csc1 and Csc2.
The second method is arithmetic crossover method. For the same contour, we select the starting point x and y in the two parent individuals, respectively, if the two gene values are not equal, then do crossover, replace x by x', replace y by y'. The detailed calculation method is:
(3) |
where, round is the function rounds a number to the nearest integer, ε is a random decimal between 0 and 1.
Hybrid crossover: Above two kinds of crossover method are all adopted.
Mutation operation: In order to maintain, the diversity of the population and prevent premature, we applied mutation operation in our algorithm. We designed three kinds of mutation methods that can also avoid generating infeasible solution and randomly select one method from the three kinds of mutation methods.
Contour processing sequence mutation: In the mutation method two points mutation is adopted and the starting point corresponding to the each contour is not changed.
Fig. 5: | Example of contour processing sequence mutation |
Fig. 6: | The actual processing path |
Randomly select two points, and exchange the coding of two points. For example, as shown in Fig. 5, we select C1 as parent individual, the two mutation points are 1 and 3, we can get the offspring Cm1.
Starting point mutation: We randomly select one gene in starting point layer and replace the starting point by a new feasible one that is selected from the feature points of the corresponding contour. For example, we select C1 as parent individual and select the third coding 3 for mutation. The third coding belongs to the second contour, there are five feature points in the second contour and the new value of this starting point is randomly selected from 1, 2, 4 and 5.
Hybrid mutation: Above two kinds of mutation method are all adopted.
OPTIMIZATION EXAMPLE
To validate the algorithm proposed above, we select one instance to optimize the path, there are 27 contours, 22 contours are polygon, the vertex number is between 3 and 12, 4 contours are circle, 1 contour is ellipse and divide 360 degrees into 8 equal parts. The maximum speed along X and Y axis are equal. The existing path is formed through that the contour is selected orderly and the starting point is selected by the shortest path with the previous point, as shown in Fig. 6.
In the course of the optimization, the population size is 50, the crossover probability is 0.8 and the mutation probability is 0.05.
Fig. 7: | The optimal processing path |
After optimization, as shown in Fig. 7, the length of the path reduced 7.2% and the spare travel time saved 10.4%, the optimization efficiency is obvious.
In the contour path planning of laser processing, the laser head can move with the maximum speed along X and Y axis, so the shortest path is not equal to the shortest processing time and the spare travel time decided the processing time. This study presents an efficient improved dual coding genetic algorithm for solving contour path planning, therefore, the processing sequence of contours and starting point of each contour can be optimized simultaneously and the starting point is selected from the feature points of contour. Aiming at the coding features, many new crossover and mutation methods that adapted to the problem are designed and the infeasible solutions are avoided. The computing method of fitness function value is adjusted, so the self adapting capability of the algorithm is enhanced. The algorithm is proven effective by the given example.
This study was supported by the National Natural Science Foundation, China (51075220) and the Specialized Construct Fund for Taishan Scholars.