The paper provides an improved genetic algorithm based on full combination breeding strategy (FCGA). FCBC increases the probability of producing excellent individuals by full combination breeding and improves the quality of initial population by greedy algorithm. In this paper, all holes of printed circuit boards (PCB) are grouped by adjacency list. The distance matrix of all groups is obtained by coordinate quadrant method. Then the improved genetic algorithm is used to search the shortest path of all groups. Finally, the improved genetic algorithm is used to search the shortest path of all holes in each group. Test results with five traveling salesman problem(TSP) examples show that FCGA significantly reduces the number of iterations in comparison to classical genetic algorithm(CGA). Similarly, the average running time are reduced by an average of 17.04%. The experimental results also show that the proposed algorithm applied to PCB drill path optimization can effectively solve the problem of large-scale printed circuit board drilling path optimization.
Paper
Full text
PCB Drill Path Optimization by Improved Genetic Algorithm
Semantic Scholar · Engineering · 2019
Abstract
The paper provides an improved genetic algorithm based on full combination breeding strategy (FCGA). FCBC increases the probability of producing excellent individuals by full combination breeding and improves the quality of initial population by greedy algorithm. In this paper, all holes of printed circuit boards (PCB) are grouped by adjacency list. The distance matrix of all groups is obtained by coordinate quadrant method. Then the improved genetic algorithm is used to search the shortest path of all groups. Finally, the improved genetic algorithm is used to search the shortest path of all holes in each group. Test results with five traveling salesman problem(TSP) examples show that FCGA significantly reduces the number of iterations in comparison to classical genetic algorithm(CGA). Similarly, the average running time are reduced by an average of 17.04%. The experimental results also show that the proposed algorithm applied to PCB drill path optimization can effectively solve the problem of large-scale printed circuit board drilling path optimization.