技術名稱 改良式跳蛙演算法應用於自動射出黏著機台零件黏著順序及零件槽指派最佳化
計畫單位 國立高雄科技大學
計畫主持人 徐賢斌
技術簡介
跳蛙演算法(shuffled frog-leaping algorithm, SFLA)是屬於一種群體智慧(swarm intelligence)之仿生萬用演算法(metaheuristic)。其有別於數學模式及一般啟發式演算法。數學模式一般用於求解最佳解,但其缺點是對於一般實務問題無法在可接受之時間內求解。反之,一般啟發式演算法雖可快速求解,但其所求解之品質則相對不佳。原始版跳蛙演算法為Kennedy and Eberhart在1995年所提出,原作者將其應用在水管線路佈線規劃,並獲致良好成果。該演算法模仿青蛙覓食行為來探索解空間,以找尋最佳或近似最佳解。該技術近年來漸受重視並被廣泛應用於各領域,例如最佳化應用、排程、資源指派等。萬用演算法是一種高階之演算法,其具有反覆求解之特性,故可持續改善解之品質。與一般之啟法式法相較,可改善其品質不佳之缺點。與數學模式相較,經由演算法的求解代數設定,可限制其運算時間,因此可避免運算時間不可行之問題。跳蛙演算法基本上利用青蛙群組之人口優勢及進化之特性來持續改善解,故此演算法又可稱為群組與進化導向之萬用演算法。另外,跳蛙演算法採用的是一種資訊回饋搜尋(informed search)而非隨機搜尋(random search)。本研究將原始版跳蛙演算法進行改良,並發展出進階改良版。詳言之,改良版的跳蛙演算法新增了如下之特性: (1)應用Sobol Sequence 產生亂數(此應用產生較平均分佈之青蛙初始位置); (2)應用了全域搜尋轉換至區域探索之策略搜尋(此方式乃轉換全方位搜尋收斂至區域優勢搜尋); (3)全體群組青蛙參與尋解(此方式可獲致更佳的人口優勢); (4)應用調適跳距(此特性避免青蛙隨機搜尋); (5)應用調適變異(此特性避免青蛙執著於區域最佳解); (6)應用臨域搜尋(此特性防止青蛙無效搜尋); (7)應用強迫搜尋(此特性防止青蛙怠惰)。上述特性改良了原始版跳蛙演算法,使其更具備解空間之搜尋能力,並收斂到最佳或是近似最佳解。
科學突破性
改良版跳蛙演算法特徵:(1)Sobol Sequence產生亂數; (2)全域搜尋收斂至區域搜尋策略; (3)全員參與; (4)調適跳距; (5)調適變異; (6)臨域搜尋; (7)強迫搜尋。實驗顯示I-SFLA2優於SFLA、I-SFLA1及PSO2分別達165.3%、78.5%及171.2%。
產業應用性
本研究發展之改良式跳蛙演算法主要用來協助自動射出黏著機台之印刷電路板生產。詳言之,該演算法可用來做印刷電路板之零件組裝順序規劃(component sequencing problem, CSP)以及槽指派(feeder assignment problem, FAP),以達到最佳化生產。
關鍵字 印刷電路板 印刷電路板組裝 跳蛙演算法 群體智慧 零件黏著順序問題 零件槽位置指派問題 萬用演算法 自動射出黏著機台 生產力 自動化
備註
本技術內容已發表於如下期刊: (如附件資料)
H.P. Hsu, S.W. Yang, 2020, “Optimization of Component Sequencing and Feeder assignment for a Chip Shooter Machine Using Shuffled Frog-Leaping Algorithm,” IEEE Transactions on Automation Science and Engineering, Vol. 17, No. 1, 56-71.
  • 聯絡人
  • 徐賢斌
其他人也看了