• [email protected]
  • +971 507 888 742
Submit Manuscript
SciAlert
  • Home
  • Journals
  • Information
    • For Authors
    • For Referees
    • For Librarian
    • For Societies
  • Contact
  1. Information Technology Journal
  2. Vol 12 (4), 2013
  3. 862-866
  • Issues
    Online First Current Issue All Issues
  • Information About
    Aims and Scope Editorial Board Guide to Authors Article Processing Charges
    Submit a Manuscript

Information Technology Journal

Year: 2013 | Volume: 12 | Issue: 4 | Page No.: 862-866
DOI: 10.3923/itj.2013.862.866
crossmark

Facebook Twitter Reddit Linkedin E-mail
Research Article

Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing

Jianjun Yang
School of Mechanical Engineering, Qingdao Technological University, Qingdao 266033, China
LiveDNA: 86.5072

ABSTRACT


An optimization model for contour path in laser processing is established, in which the minimal spare travel time is taken as objective function and not the shortest path, because the spare travel time decided the processing time. In the problem, two kinds of subpromlems that are the scanning sequence of contours and the starting point of each contour should be optimized simultaneously. Based on the features, the improved dual coding genetic algorithm is designed to optimize the problem. For the contour shape, the polygon and circle are all taken into account and the coding method that adapted to the problem is designed. In the algorithm operational process, many crossover and mutation methods are designed and also adapted to the problem, so the infeasible solutions are avoided. In order to improve the performance of the algorithm, the computing method of fitness function value is adjusted. The computation result shows that the algorithm is efficiency.
PDF Abstract XML References Citation

Keywords


  • path planning
  • Laser processing
  • improved genetic algorithm
  • contour path

Article History

Received: September 06, 2012;   Accepted: November 26, 2012;   Published: January 22, 2013

How to cite this article

Jianjun Yang, 2013. Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing. Information Technology Journal, 12: 862-866.

DOI: 10.3923/itj.2013.862.866

URL: https://scialert.net/abstract/?doi=itj.2013.862.866

INTRODUCTION


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:

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
(1)

where, n is the total number of contours.

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
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.

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
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:

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
(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.

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
Fig. 3: Example of contour processing sequence crossover

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
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:

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
(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.

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
Fig. 5: Example of contour processing sequence mutation

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
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.

Image for - Application of Improved Dual Coding Genetic Algorithm for Contour Path Planning in Laser Processing
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.

CONCLUSION


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.

ACKNOWLEDGMENTS


This study was supported by the National Natural Science Foundation, China (51075220) and the Specialized Construct Fund for Taishan Scholars.

REFERENCES


  1. Huang, Y.M. and H.Y. Lan, 2006. Path planning effect for the accuracy of rapid prototyping system. Int. J. Adv. Manuf. Technol., 30: 233-246.
    CrossRef

  2. Liu, H.X., X. Wang and L. Cai, 2004. Modeling and optimizing laser torch path in laminated object manufacturing technology. Chin. J. Lasers, 31: 1137-1142.
    Direct Link

  3. Wang, G.G. and S.Q. Xie, 2005. Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization. Int. J. Prod. Res., 43: 2195-2216.
    Direct Link

  4. Chou, C.C., Y.K. Chen and S.Y. Chou, 2008. A fundamental tool path planning problem for circles in layered manufacturing. Integr. Comput. Aided Eng., 15: 37-52.
    Direct Link

  5. Wiener, J.M., N.N. Ehbauer and H.A. Mallot, 2009. Planning paths to multiple targets: memory involvement and planning heuristics in spatial problem solving. Psychol. Res., 73: 644-658.
    PubMed

  6. Son, S., S. Kim and K.H. Lee, 2003. Path planning of multi-patched freeform surfaces for laser scanning. Int. J. Adv. Manuf. Technol., 22: 424-435.
    Direct Link

  7. Yang, W.D., R.H. Tan, Y.N. Yan and A.P. Xu, 2005. Application of genetic algorithm for scanning path planning in rapid prototyping. J. Comput. Aided Des. Comput. Graphics, 17: 2179-2183.
    Direct Link

  8. Huang, X., F. Xi, J. Li and Z. Zhong, 2009. Optimal layout and path planning for flame cutting of sheet metals. Int. J. Comput. Integr. Manuf., 22: 30-41.

Leave a Comment


Your email address will not be published. Required fields are marked *

Useful Links

  • Journals
  • For Authors
  • For Referees
  • For Librarian
  • For Socities

Contact Us

Office Number 1128,
Tamani Arts Building,
Business Bay,
Deira, Dubai, UAE

Phone: +971 507 888 742
Email: [email protected]

About Science Alert

Science Alert is a technology platform and service provider for scholarly publishers, helping them to publish and distribute their content online. We provide a range of services, including hosting, design, and digital marketing, as well as analytics and other tools to help publishers understand their audience and optimize their content. Science Alert works with a wide variety of publishers, including academic societies, universities, and commercial publishers.

Follow Us
© Copyright Science Alert. All Rights Reserved