# 臺灣博碩士論文加值系統

(98.82.120.188) 您好！臺灣時間：2024/09/11 09:28

:::

### 詳目顯示

:

• 被引用:0
• 點閱:1239
• 評分:
• 下載:87
• 書目收藏:0
 啟發式演算法藉由具意義的猜測，找尋可能得到最佳解的搜尋方向，進而提供求解複雜問題時，一個可行的方法。由於啟發式演算法只需花費極少的計算時間(相對於列舉出所有可行解的計算時間)，用以獲得一個近似解。因此，啟發式演算法似乎提供一個可行的研究方向，讓我們可以面對並解決複雜的問題。但在啟發式演算法的搜尋過程中，仍存有大量且多餘的計算。或者，我們可以說，啟發式演算法在求解的過程中，尚未完全的發揮其應有的效能。本論文提出一個簡單且有效的演算法，用以減少啟發式演算法的計算時間，同時嘗試維持或提升原有演算法之求解品質。這個新穎的演算法稱之被為樣式歸納法，其主要的概念是源自於我們觀察到，在啟發式演算法的收斂程序中，大部分的搜尋存在著重複的計算，且部分解的片段可以被視為最終結果的一部份。藉由移除這些計算，後續的收斂過程將可不需再次計算重複內容。本論文的主要目的不在於我們能夠節省多少的計算時間，而是在於如何減少多餘的計，使啟發式演算法不再浪費其計算能力。最後，根據我們的實驗結果顯示，樣式歸納法可以有效的節省計算時間，並同時維持求解品質。
 Over the past three decades or so, metaheuristics has been one of the most important and successful techniques for finding the true or near optimal solution of complex problems. Instead of systematically enumerating and checking all the candidate solutions that would takeforever to accomplish, it works by guessing the right directions for finding the true or near optimal solution so that the space searched, and thus the time required, can be significantly reduced. However, our observation shows that most of the metaheuristic algorithms face a common problem. That is, because of the requirements of convergence, they all involve a lot of redundant computations during the convergence process. In this thesis, we present a simple but efficient algorithm for solving the problem, called the Pattern Reduction algorithm(or PR for short). The proposed algorithm is motivated by the observation that some of the sub-solutions that are repeatedly computed during the convergence process can be considered as part of the final solutions and thus can be first compressed and then removed to eliminatethe redundant computations at the later iterations during the convergence process. Since PR is basically a concept that is not limited to any particular metaheuristic algorithm, we present several methods derived from the concept for eliminating the duplicate computations of metaheuristics in the thesis. Although our simulation results show that they all perform well in terms of the computation time reduced, they are not perfect in terms of the quality of the end results because in some cases they will cause a small loss of the quality. For this reason, rather than how much computation time the proposed algorithm can reduce, our ultimategoal is to eliminate all the redundant computations while at the same time preserving or even enhancing the quality of the end result of metaheuristics alone.
 List of Tables ivList of Figures vAcknowledgments viiChapter 1 Introduction 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Contributions of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Chapter 2 Related Work 72.1 Combinatorial Optimization Problems . . . . . . . . . . . . . . . . . . . . . 82.1.1 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . 92.1.2 Data Clustering Problem . . . . . . . . . . . . . . . . . . . . . . . . 102.2 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2.1 Single-Solution-Based Algorithms . . . . . . . . . . . . . . . . . . . 142.2.1.1 Simulated Annealing Algorithm . . . . . . . . . . . . . . . 152.2.1.2 Tabu Search Algorithm . . . . . . . . . . . . . . . . . . . 172.2.1.3 k-means Algorithm . . . . . . . . . . . . . . . . . . . . . 182.2.2 Population-Based Algorithms . . . . . . . . . . . . . . . . . . . . . 212.2.2.1 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . 212.2.2.2 Ant Colony Optimization . . . . . . . . . . . . . . . . . . 232.2.2.3 Particle Swarm Optimization . . . . . . . . . . . . . . . . 252.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.3 Improving the Performance of Metaheuristics . . . . . . . . . . . . . . . . . 292.3.1 Initialization Methods . . . . . . . . . . . . . . . . . . . . . . . . . 292.3.2 Local Search Methods . . . . . . . . . . . . . . . . . . . . . . . . . 312.3.3 Hybrid Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.3.4 Speedup Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.4 The Problems of Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . 382.4.1 Diversity and Quality of the End Result . . . . . . . . . . . . . . . . 382.4.2 Convergence Speed and Computation Time . . . . . . . . . . . . . . 402.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Chapter 3 The Proposed Algorithm 443.1 The Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.2 Assumptions and Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . 503.3 The Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.3.1 Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.3.1.1 Time-Oriented . . . . . . . . . . . . . . . . . . . . . . . . 533.3.1.2 Space-Oriented . . . . . . . . . . . . . . . . . . . . . . . 543.3.1.3 Problem-Specific . . . . . . . . . . . . . . . . . . . . . . 563.3.1.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.3.2 Compression and Removal . . . . . . . . . . . . . . . . . . . . . . . 583.3.2.1 Lossy Method . . . . . . . . . . . . . . . . . . . . . . . . 583.3.2.2 Lossless Method . . . . . . . . . . . . . . . . . . . . . . . 593.3.3 Initialization (Optional) . . . . . . . . . . . . . . . . . . . . . . . . 613.3.4 Multi-Start (Optional) . . . . . . . . . . . . . . . . . . . . . . . . . 623.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63Chapter 4 Simulation Results 674.1 The Strategies of PR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.1.1 Time to Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.1.2 Removal Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.2 The Results of Traveling Salesman Problem . . . . . . . . . . . . . . . . . . 734.2.1 Parameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . 744.2.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 754.3 The Results of Data Clustering Problem . . . . . . . . . . . . . . . . . . . . 784.3.1 Parameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . 784.3.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.4 Improving the Results of PR Enhanced Methods . . . . . . . . . . . . . . . . 824.4.1 The Results with Local Search . . . . . . . . . . . . . . . . . . . . . 824.4.2 The Results with Parallel Computing . . . . . . . . . . . . . . . . . 834.5 The Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.5.1 Diversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.5.2 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 894.5.2.1 Time Complexity of k-means with PR . . . . . . . . . . . 904.5.2.2 Time Complexity of GA with PR . . . . . . . . . . . . . . 914.5.2.3 Time Complexity of Metaheuristics with PR . . . . . . . . 934.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93Chapter 5 Conclusion and Future Work 955.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 多重搜尋基因演算法：一個新的有效解決通訊網路及資料庫中複雜問題之方法 2 一個整合的深度學習架構應用於偵測卡車司機使用手機之不良行為 3 改良屬性導向歸納法挖掘多值資料演算法之研究 4 歸納法與演繹法對於國小學童的英文文法習得之研究 5 一個基於樣式歸納法與搜尋經濟學的有效分群演算法 6 演繹法與歸納法應用在英語系大一新生的英文文法寫作課的教學成效 7 一個有效的超參數最佳化演算法應用於捷運人流預測 8 以PAM與V.C.S.解析清末曾國藩的治軍及從政 9 以對計畫行為理論之配適度為效標之自我報告與他人報告環境行為效度比較 10 開發健康材質服飾關鍵成功因素之研究 11 無線感測網路中路徑覆蓋問題之研究 12 以紮根理論初探升遷動機-以國營事業電力工員轉換為職員為例 13 應用計劃行為理論於公部門訓練參與行為之研究 14 周鼎珩易學之研究 15 以分層抽樣之規則歸納法探勘信用卡族群共同特性

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室