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

(3.90.139.113) 您好！臺灣時間：2022/01/16 18:33

:::

### 詳目顯示

:

• 被引用:0
• 點閱:299
• 評分:
• 下載:0
• 書目收藏:0
 線性整數最佳化被廣泛的應用在許多組合最佳化的問題上，典型的問題像是，排程、包裝、運輸、旅行的推銷員問題等，不像是一般解連續解的問題，我們無法經由斜率取得任何有關目標值的資訊，以往解這類問題最有效的方法是Branch and Bound，但是Branch and Bound 演算法會消耗不確定的記憶體與時間，本文提出一個新的方法有效地找出線性整數最佳化的可能解，對於一個線性整數最佳化的問題，我們可以先利用基因演算法求得初始解，再應用Hermite Normal Form 演算法取得可能解與目標值所構成類似窗格的關係，最後運用分散式計算的觀念加速可能解檢驗的流程，我們運用了修正後的演算法求Hermite Normal Form，以克服在大型問題上典型Hermite Normal Form 演算法所面臨矩陣值過大的問題。實驗的結果證明，我們可以有效的解決幾個大型的問題，並取得最佳解。
 Linear integer programs are extensively applied in many combinational optimization problems. Typical problems of this type include scheduling, knapsack, transformation, traveling salesman problem and more. Unlike continuous programs, we cannot have any information about the objective value of integer programs with gradient. The most well known algorithm for solving linear integer program is branch and bound algorithm, which however consumes uncertain time and memory space. This paper proposed a novel algorithm to efficiently find potential solutions of linear integer programs. For a linear integer program with an initial solution obtained by genetic algorithm or neural network, we may first collect coefficients from objective functions and equality constraints to form a basic matrix. Then, We may utilize Hermite normal form algorithm to gain advance information about the relationship between objective value and individual term of potential solutions in a polynomial time. The advance information will provide a better visibility in finding potential solutions of this linear programming problem. Finally, we utilized a distributed concept to verify those potential solutions in order to gain the final solution efficiently. While expending the size of linear integer programs, we found the original Hermite normal form algorithm has a severe drawback, which the size of items in the basic matrix will grow explosively. We thereby employee another efficient algorithm, LLL Hermite normal form algorithm proposed by Mathew, to overcome the problem that we previously mentioned. Experimental result shows that the proposed algorithm can successfully solve some of the linear integer programs.
 Chapter 1 Introduction 1 1.1 Introduction 1 1.2 Motivation 4 Chapter 2 Literature Review 6 2.1 Linear Integer Program 6 2.2 Hermite Normal Form Algorithm 7 2.3 LLL based Hermite Normal Form Algorithm 12 2.4 Genetic Algorithms 17 2.4.1 Introduction 17 2.4.2 Genetic Algorithms in Solving Optimization Problems 18 Chapter 4 Examples 28 Chapter 5 Conclusions 43 Appendix A 44 A Survey of Genetic Algorithm Software — Genetik 44 Appendix B 49 A Test on LLL based Hermite Normal Form Algorithm 49 Reference 52
 1.A.K.Lenstra, H.W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261(1982) 515-5342.David E. Goldberg, Genetic Algorithms in Search, Optimization, & Machine Learning, Michigan, 19893.George L. Nemhauser, Laurence A. Wolsey, Integer and Combinatorial Optimization, USA, 19884.Keith R. Matthews, Extended gcd and Hermite Normal Form Algorithms via Lattices Basis Reduction, New Zealand, 19985.Michalewicz, Z., Genetic Algorithm + Data Structure = Evolution Programs, 3rd edition, Springer-Verlag, New York, 19966.Mitsuo Gen, Run-Wen Cheng, Genetic Algorithms And Engineering Optimization, 2nd edition, USA, 1999
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 1 楊建俊，廖婕玲，陳美惠。1991。幾丁質類系列產品作為藥品釋出控制擔體之應用研究。中國農業化學會誌。29(3)： 281-289。 2 陳榮輝，金曉珍。1995。水產甲殼類廢棄物開發高經濟價值之幾丁質、幾丁聚醣、幾丁寡醣研究之規劃報導。科學發展月刊。23(6)：550-562。 3 李遠豐。1998。蟹殼膠特性應用及其生產技術。生物產業。9（1）： 27-37。

 1 網路可靠性設計之整數規劃問題全域最佳化 2 供應鏈中產能擴充與存貨管理的最佳化模式 3 多國供應鏈最佳化設廠及生產模式 4 矛盾下的抉擇—決策球的運用 5 以地理資訊為介面之跨國供應鏈決策支援系統設計 6 設計以代理人程式為基礎應用於虛擬團隊之軟體架構 7 建構以遺傳演算法結合塑模工具為基礎之玻璃工廠模擬排程系統 8 以角色識能的概念導入知識管理系統 9 從能力集觀點探討企業能力檢索模型之建構 10 從知識管理及習慣領域理論探討企業創新 11 以RBAC架構設計XML-based電子金融服務入口之存取權控管 12 一個關連式資料庫的物件界面元件產生器 13 手持式裝置在無線傳輸環境中的委任式身份認證安全機制 14 一個針對快取以使用者行為為基礎之預先擷取機制 15 一個在無線網路上之電子郵件傳輸系統

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