HDI板孔群的K-means聚类及加工路径优化研究

Research on K-means Clustering and Path Optimization Process of HDI Plate Group

电路板的激光打孔路径优化是一个NP完全问题,随着孔群数量的增加,其复杂性和解空间会成指数性增长。文章采用K-means算法和改进模拟退火算法,并结合孔群加工的数学模型研究HDI激光打孔的路径优化。首先采用K-means算法聚类分析得到相似度高的孔群,初始种群运用贪婪选择策略,降低起始搜索范围,提高收敛效率;寻优过程中加入遗传算法的DIM(Displaced Inversion Mutation)变异算子,避免模拟退火算法陷入局部最优解。仿真试验结果表明,该方案求解出的最优路径比采用模拟退火算法有明显改善。

The optimization of laser drilling path of circuit board is a NP complete problem.With the increase of microviasits complexity and solution space will increase exponentially.In this paper,the K-means algorithm and the improved simulated annealing algorithm are combined with the mathematical model of hole processing to study the optimization of HDI laser drilling.Firstly,it obtains high Similar microvias by K-means clustering algorithm;In the initial population,the greedy selection strategy is adopted to reduce the initial search search range and improve the convergence efficiency;The genetic algorithm is added in the searching process of DIM(Displaced Inversion Mutation)mutation operator to avoid local optima.The simulation results show that the optimal path solved by the proposed scheme is better than the simulated annealing algorithm.