Metaheuristics Laboratory, Evolution and Scheduling

啟發式演算法與最佳化

　談到最佳化，推銷員旅行問題 (Traveling Salesman Problem, TSP) 是資工背景同學最熟知的最佳化問題之一，其問題是在給定 n 個城市及其相互間距離後，求取一條經過所有城市各一次的最短循環路徑。事實上，最佳化問題在生活中無所不在：以有限資源在最短時間內完成指定工作、以最少成本滿足人力需求、在有限空間內存放最多數量的貨物、以最少車輛數完成所有客戶的運輸需求等等。這些問題大多具有很高的複雜度，意味著目前並沒有能在有限時間內保證求得最佳解的演算法。

　啟發式演算法為一類最佳化演算法的總稱，這類演算法常起源於自然界觀察而來的現象，如有模仿生物進化過程的演化演算法 (evolutionary algorithms)，有習自蟻群覓食的蟻拓搜尋法 (ant colony optimization)，也有效法鳥類覓食的粒子群搜尋法 (particle swarm optimization) 等等。由於這些演算法具有高彈性（不限於求解某一特定問題）、實作簡單、求解效率高等等特質，目前已成為最佳化演算法中的新興熱門領域。

　演化演算法之概念來自於生物演化，意指生物經過交配、突變產生後代，並經由物競天擇、適者生存選擇存活者的方式，逐漸提升生物對環境之適應力的過程。當我們求解一個問題 (如 TSP 問題) 時，可將該問題各個可能的解 (solution) 視為一個生物個體，透過模仿生物演化的演算法流程，逐漸提升解的品質（以 TSP 問題而言，解的總路徑長會在演化過程中越來越小），以滿足解題的目標（最小化總路徑長）。

	指導教授簡歷我的研究興趣為啟發式演算法 (metaheuristics) 之設計與應用，主要焦聚於演化計算 (evolutionary computation)、多目標演化最佳化 (evolutionary multiobjective optimization, EMO)、資源最佳化（如生產排程、路線規畫、電力規畫），也對遊戲人工智慧有興趣。主持（共同主持）科技部和教育部計畫二十餘件，發表學術論文著作七十篇，論文引用數逾千次，曾獲科技部特殊優秀人才獎勵。熱愛教學，歷年指導碩博士生逾五十人，曾獲校級教學傑出獎。
	啟發式演算法與最佳化　談到最佳化，推銷員旅行問題 (Traveling Salesman Problem, TSP) 是資工背景同學最熟知的最佳化問題之一，其問題是在給定 n 個城市及其相互間距離後，求取一條經過所有城市各一次的最短循環路徑。事實上，最佳化問題在生活中無所不在：以有限資源在最短時間內完成指定工作、以最少成本滿足人力需求、在有限空間內存放最多數量的貨物、以最少車輛數完成所有客戶的運輸需求等等。這些問題大多具有很高的複雜度，意味著目前並沒有能在有限時間內保證求得最佳解的演算法。　啟發式演算法為一類最佳化演算法的總稱，這類演算法常起源於自然界觀察而來的現象，如有模仿生物進化過程的演化演算法 (evolutionary algorithms)，有習自蟻群覓食的蟻拓搜尋法 (ant colony optimization)，也有效法鳥類覓食的粒子群搜尋法 (particle swarm optimization) 等等。由於這些演算法具有高彈性（不限於求解某一特定問題）、實作簡單、求解效率高等等特質，目前已成為最佳化演算法中的新興熱門領域。　演化演算法之概念來自於生物演化，意指生物經過交配、突變產生後代，並經由物競天擇、適者生存選擇存活者的方式，逐漸提升生物對環境之適應力的過程。當我們求解一個問題 (如 TSP 問題) 時，可將該問題各個可能的解 (solution) 視為一個生物個體，透過模仿生物演化的演算法流程，逐漸提升解的品質（以 TSP 問題而言，解的總路徑長會在演化過程中越來越小），以滿足解題的目標（最小化總路徑長）。
	歡迎新血加入歡迎各位新生同學加入師大資工所，我的研究興趣主要為演化演算法之設計與應用，運用這些啟發式演算法的概念，設計與實作出易懂、實作方便、使用簡單、效率快速、求解品質高的演算法，並應用在各種具有挑戰性與高實用價值的最佳化問題上。相關主題包括：資源（人力、機器、車輛）規畫應用：在發電系統中，如何安排發電機組始得以滿足用電需求，同時減少碳排放量？(emission economic dispatch) 在生產系統中，如何安排機器處理工件，以提高生產效率、滿足顧客滿足度並減少能源消耗和環境污染？ (shop scheduling) 在人力有限的狀況下，如何決定專案中各任務的負責人以及各任務的執行順利，以縮短專案完成時間和減少人事成本？(project scheduling) 想去的旅遊景點好多，該如何安排才能在假期中走訪最多最好玩的景點？ (orienteering problem, OP) 校車、油罐車、黑貓宅急便等各類運輸系統，該如何以最少的車輛數，最短的路徑完成客戶們的需求？ (vehicle routing with time windows, VRPTW) 演化演算法設計與實作：當最佳化的目標不只一個（如時間與成本），當魚與熊掌不能兼得時，我們該如何有效地產生最佳解？(evolutionary multiobjective optimization, EMO) 如何結合演化演算法與機器學習方法（如類神經網路與強化學習），彼此合作改善原有方法之效能？面對不同特性的問題，該如何省去人為調校，使演算法可以自我學習以調整演算法參數？(adaptive parameter control) 演化演算法的應用如此廣泛，是否有一個易學、易用且高效率的軟體框架，讓一般使用者和研究者能快速完成其應用？其它應用：由於啟發式演算法具有高度彈性，故其應用領域十分廣泛。近年我的大學部專題生也將它們應用於許多遊戲如小精靈虛擬玩家、Eternity-II 拼圖、超級瑪莉的關卡產生器等等。未來我也希望能將它用在醫療照護、能源管理與娛樂遊戲的研究上。
	FAQ Q：「演化計算聽起來很有趣，但對我而言有點陌生，這是屬於哪個領域的研究呢？」 A: 演化計算屬於「人工智慧」領域，在科技部資訊工程學門/智慧計算學門的研究領域中，我們可以看到「人工智慧與仿生計算」子領域，該領域的規畫書提到「演化計算」為重點子領域之一。以資訊領域熟知的國際電子電機工程學會 (IEEE) 與計算機學會 (ACM) 來說，前者每年都會舉辦演化計算國際會議 (IEEE Congress on Evolutionary Computation, CEC)，後者同樣也會每年舉辦演化計算會議 (Genetic and Evolutionary Computation COnference, GECCO)。其中 IEEE CEC 每兩年還會結合模糊系統 (Fuzzy systems) 和類神經網路 (Neural networks) 合辦大型的人工智慧會議 (World Congress on Computational Intelligence, WCCI)。 Q：「演化/啟發式演算法可以作些什麼呢？」 A：演化/啟發式演算法是一種演算法框架，具有高度彈性，應用領域廣泛，以下只簡單列出一些例子。經典問題：旅行推銷員問題 (traveling salesperson problem, TSP)、布林運算式滿足問題 (satisfiability problem, SAT)、背包問題 (knapsack problem)、分批問題 (bin packing) 資源管理問題：生產排程 (production scheduling)、課程安排 (course timetabling)、航班排程 (flight scheduling)、車輛路由 (vehicle routing)、賽程安排 (sports timetabling)、平行環境中的工作指派問題 (task scheduling) 影像處理：資料壓縮 (vector quantization)、影像分區 (image segmentation)、人臉辨識 (face recognition) 資料探勘：分類法則 (classification rule extraction)、特徵選取 (feature selection) 設計問題：網路拓撲 (network topology)、類神經網路 (neural network)、貝氏網路 (Bayesian network)、積體電路設計 (VLSI layout) 軟體工程：測資生成 (generation of testing instances)、錯誤修復 (fault repair) 網路應用：問題回答 (question answering)、垃圾信偵測 (spam detection) 遊戲智慧：控制器生成 (game controller)、參數最佳化 (parameter optimization) 我的研究主要是資源管理類型的問題，不過同學們如果有特別感興趣的主題，我也很歡迎同學們為實驗室帶來新的研究主題。 Q：「演化計算看起來很有趣，但我不確定會不會進老師的實驗室，這樣也可以找老師談嗎？」 A：當然可以，研究生活要過得充實愉快，一定要對研究主題感興趣。選實驗室就像買東西一樣，貨比三家不吃虧，歡迎同學來進一步了解我們的研究主題。 Q：「老師什麼時候會在辦公室呢？」 A：不上課的時候我大部份都在辦公室，如果有興趣找我面談，請 email 給我。　如果你愛思考、有創意，歡迎你一起來設計與創造新的啟發式演算法。如果你喜歡撰寫程式、開發軟體，歡迎你一起來實作並測試誰才是最厲害的啟發式演算法。如果你不服輸、有毅力，歡迎你一起來挑戰經過二、三十年都還沒有人解出來的問題集。歡迎有興趣的同學與我聯絡，或可至我的實驗室 R205 與目前在學同學詢問相關問題。