基因演算法應用於TGV雷射加工路徑優化
作者：
陳穎融、孫翊淳、曾介亭、江宜霖、林于中、林順傑
刊登日期：2024/02/02
摘要：在半導體產業快速的成長、製程工藝不斷的進步下，先進封裝技術TGV製程每次需要規劃的孔位數量也從數十萬點上升至百萬點，該如何在點數規模如此龐大下找到一有效最佳加工路徑儼然成為一大議題。路徑規劃問題被歸類於旅行業務員問題 (Traveling Salesman Problem, TSP)，且在TGV製程上規劃路徑時需考慮雷射平台作動特性，加工時間比路徑長度來的更為重要，因此本文將簡介三種常見的TSP演算法類型，其中會針對基因演算法(Genetic Algorithm)特別說明，包含染色體的設計、機制、流程等細節，同時也會提及挑選此演算法之原因。在文末，我們也實際開發一套基因演算法模組，並對六種不同數量規模的圖檔進行測試，結果來說，在點數規模達百萬點時，基因演算法所取得的最佳路徑可節省1小時至10小時不等的加工時間，有效降低生產成本。
Abstract：With the rapid growth of the semiconductor industry and the continuous progress of process technology, the number of holes to be planned in each advanced packaging technology TGV process has increased from tens of thousands to millions. How to find an effective and optimal machining path in such a large scale is becoming a major issue.The path planning problem is classified as the Traveling Salesman Problem (TSP), and when planning the path for the TGV process, the characteristics of the laser platform need to be considered. The processing time is more important than the path length, so this article introduces three common types of TSP algorithms, including a detailed explanation of the Genetic Algorithm, which includes the design of chromosomes, mechanisms, and flow processes. At the same time, the reasons for choosing this algorithm are also mentioned. Finally, a genetic algorithm module is actually developed, and six different-sized patterns are tested. The results show that when the number of nodes reaches millions, the genetic algorithm can save 1 to 10 hours of processing time, effectively reducing production costs.
關鍵詞：基因演算法、玻璃穿孔TGV、路徑規劃
Keywords：Genetic algorithm, Through Glass Via, Path planning
前言
近年來，電子產品快速發展，加上COVID-19疫情，使得全球晶片需求量大增，帶動半導體產業快速成長，而設備銷售金額也屢創新高。根據SEMI國際半導體產業協會的報告指出，2022年全球的半導體製造設備銷售金額高達1,076 億美元，創下歷史新高。雖然中國地區已經連續三年拿下全球最大半導體設備市場寶座，但臺灣身為第二大市場，已連續四年走揚，從2021年的249億美元，到2022年增加8%，達到268億美元，與中國地區的差距正在逐漸縮小。為了提高半導體性能及可靠度，使晶片能整合更多不同功能模組，半導體製程工藝不斷進步，晶片尺寸也逐漸縮小，更多的IO通道使先進封裝技術的TGV(Through Glass Via)通孔間距密度逐漸增大、孔位數量大幅增加，製程成本也爆炸性成長。當需要規劃的點數從數十萬上升至百萬時，加工路徑規劃變得非常困難且複雜。因此，為了縮短雷射加工時間[1]，以節省加工時間，降低生產成本，本文將探討如何應用TSP來解決最佳化加工路徑規劃問題，並以基因演算法在限制的時間內取得最佳解。
玻璃穿孔TGV
1975年，Intel創始人之一的Gordon Earle Moore所提出的摩爾定律(Moore's law)中提到「積體電路上可容納的電晶體每隔24個月會增加一倍；電晶體的體積不斷縮小，成本得以降低，效能得以提高」，為因應這些變化，中介層的開發技術也從傳統的金屬導線，到後來發展出使用矽(Silicon)晶圓以矽穿孔(Through Silicon Via, TSV)的封裝技術，但矽屬於半導體材料，而非一種電性絕緣體且價格昂貴，反觀玻璃，不但是一種絕緣體，同時還具有可大面積生產、製程步驟少、化學穩定性高、低成本等特性，因此近年來不少研發單位與廠商開始積極投入研發「玻璃穿孔(Through Glass Via, TGV)」，期望以玻璃取代矽作為中介層。
TGV製程大多以線性掃描(Line-Scan Path)的路線進行加工，但在與專家討論及實驗後發現，傳統走法存在50 %以上的無效路徑，加工效率較差、時間較長。此外，基於雷射平台作動特性，當雷射點路徑在同一直線上時，平台可維持在最高速移動，不過，當路徑方向改變時，平台需減速直到靜止後，才能重新提升速度到最高速。因此在加工時間的計算上，須考慮雷射路徑方向改變而產生的加減速時間成本，若規劃之路徑改變方向頻繁，便會產生大量的加減速時間成本，同時也會造成設備的耗損。
初期，在開放原始碼的支援下，我們快速的實驗了萬用啟發式演算法(Meta-Heuristic Algorithm)的模擬退火演算法(Simulated Annealing)以確認可行性，觀察圖1後可發現到，模擬退火演算法所找到之路徑的路徑長為線性掃描路徑的三分之一，明顯優於線性掃描路徑。但實際應用在場域時發現，除了路徑長度之外，需考慮雷射平台作動特性，每當路徑方向改變時，平台需減速直到靜止後，才能重新提升速度到最高速，運動模型示意圖請參考圖2。實驗過程中，我們採用表1的運動參數將路徑換算為加工時間，進而發現圖1(b)的路徑因為頻繁加減速，導致最終花費的加工時間較長，我們也因此將目標函數變更為加工時間最小化，並在比較其他演算法後，決定採用基因演算法來求解。
(a) (b)
圖1 (a)為線性掃描路徑，路徑長614 mm，加工時間16秒
(b)為模擬退火演算法所找到之路徑，路徑長201 mm，加工時間17秒
圖2 加工平台運動模型示意圖
表1 運動參數
Large-Scale TSP研究
路徑規劃問題屬於旅行業務員問題 (Traveling Salesman Problem, TSP)，而此問題被定義為NP-hard問題，亦即計算時間將隨節點數量的增加呈指數成長，但由於TSP應用廣泛，如交通、物流、生產排程…等，因此吸引許多學者在此最佳化問題上不斷鑽研，文獻上的求解方法及演算法更是不勝枚舉[2][3]。常用以下幾種演算法求解：精確演算法(Exact Algorithm)、近似演算法(Approximation Algorithm)、萬用啟發式演算法(Meta-Heuristic Algorithm)。
第一種，精確演算法(Exact Algorithm)，是指可取得問題最佳解的演算法，如：窮舉法、分支界限法，當資料量較小時，此法可找到最佳解，但資料增加時，運算時間會指數性成長，在TGV製程規劃點數規模如此龐大之下，精確演算法無法在合理時間內取得最佳解，因此不適合應用在TGV問題上。
第二種，近似演算法(Approximation Algorithm)，是指在最佳化問題上找尋近似解的演算法，例如：鄰域搜尋演算法。通常近似演算法可於較短時間內求得可行解，但不保證為最佳解，且容易陷入局部最佳解。
第三種，萬用啟發式演算法(Meta-Heuristic Algorithm)，是一種經由觀察生物界的自然現象所獲得的靈感，再結合亂數搜尋，避免陷入局部最佳解的演算法，例如：基因演算法(Genetic Algorithm)、模擬退火演算法(Simulated Annealing)、蟻群演算法(Ant Colony System)。萬用啟發式演算法在運算時間上更優於第一種精確演算法，在求解的品質上與第二種近似演算法相比，也略勝一籌。綜合來看，萬用啟發式演算法不僅能在有限的時間內求得可行解，同時又可以避免陷入局部最佳解，因此常被應用於加工路徑規劃等最佳化問題上。
然而在TGV加工製程上，因為孔位數量眾多，所以被視為Large-Scale TSP問題。而在Large-Scale TSP問題求解策略上常見的方式包含單一問題求解及劃分問題求解。單一問題求解是指將整個TSP問題視為單一問題，直接透過演算法求解，常見的演算法有萬用啟發式演算法、啟發式演算法、局部搜索演算法，此作法在大規模TSP問題上求解時，需要較長的運算時間。而劃分問題求解則是透過分群演算法將整個TSP問題劃分至多個TSP問題，有效地降低問題規模大小，使單一TSP問題的資料量降低至現有TSP最佳化方法可求解之規模，最後再將各分群結果合併。通常會將TSP問題分為三個層次，第一層先運用單一問題的演算法求解各分群內的TSP問題(cluster-level graph)，接著將各分群的群中心視為城市後，再透過單一問題的演算法求解各分群間的TSP問題(meta-level graph)，最後再將連續兩分群最鄰近的結點進行連接的分群組合問題。不過因為此作法無法將全局同時納入考慮，較容易產生次優解(suboptimal choice)，所以經常再透過一些微調(fine-tuning)針對分群邊界進行優化。
綜合以上，為處理不同規模的TSP問題，又能在有限時間內取得可行解，本文最終決定採用基因演算法作為解決最佳化加工路徑規劃問題之工具，其優勢包括彈性大、可依據不同需求設計染色體及行為機制、具備強韌且全域的隨機搜尋能力。
基因演算法及其應用於TGV雷射加工路徑
- 基因演算法(Genetic Algorithm, GA)
基因演算法是人類依照生物學中「適者生存，不適者淘汰」的觀念所發展出來的一種演算法，利用「選擇(Selection)」、「複製(Reproduction)」、「交配(Crossover)」、「突變(Mutation)」等步驟去尋找最適合環境的染色體，即問題的解。
在基因演算法中，一條染色體代表一個可行解(feasible solution) 。透過目標函數計算出各染色體的適應值，以此來評估解的優劣，適應值越高的染色體，被選擇的機會越高；而適應值低的，被選擇的機會就低。為了避免演算法快速收斂至局部最佳解，在選擇染色體並將其複製組成母體(Population)時，通常會採用輪盤法去挑選染色體，複製完成後，母體接著進行交配與突變，突變是為了擴大搜尋範圍，避免過早收斂於局部最佳解。但如果目標函數設定得不佳，也是會影響收斂速度及結果，使得無法找到全域最佳解。
…本文未結束
更完整的內容 歡迎訂購 2024年2月號 491期
機械工業雜誌‧每期240元‧一年12期2400元
我要訂購