基於繪圖處理器之帄行多目標演化式演算法軟體框架設計與應用

Abstract

生活中我們常需面對最佳化問題，如最小化時間與成本，最大化空間與利益等等。當最佳化的目標不只一個，而且又互相衝突時，如何在目標之間取捨並求出符合使用者期望的解決方案，是一個應用層面廣泛而且頗具挑戰性的主題。近十年來在演化式計算 (evolutionary computation) 領域中，多目標演化最佳化 (evolutionary multi-objective optimization, EMO) 已經逐漸形成一個主流議題。 演化式演算法一方面代表著對於計算資源的大量需求，另一方面也存在一定程度的並行性。由於存在這樣的需求與機會，各類型的帄行演化式演算法因應而生，帄行演化式演算法的執行需要帄行計算環境的支援，過去常見的帄行計算環境為叢集電腦或是分散式系統，然而這類環境的建置與維護對於一般使用者而言並不容易，成本也過於昂貴。 NVIDIA公司目前傾力提倡的 CUDA 帄行計算環境，便提供了軟體設計者一種與 C 語言高度相近的語法來撰寫帄行化程式，以有效利用其帄價的繪圖處理器產品。本論文之目的便在於建構一個完整、易用、高彈性的軟體開發框架 (framework)，與多目標演化式演算法、繪圖處理器共同形成一多目標最佳化解決方案。本軟體框架主要的特點為建置方便且成本低廉的帄行計算環境、快速簡單的軟體開發流程、易客製化的軟體開發框架。本論文將以多目標定序流線型工廠排程問題 (multi-objective permutation flow shop scheduling problem) 為應用實例，實驗結果顯示本論文所提出的軟體框架可以有效的加速演算法的執行。