跳到主要內容

臺灣博碩士論文加值系統

(3.90.139.113) 您好!臺灣時間:2022/01/16 18:33
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:郭贊章
研究生(外文):Tsan-Chang Kuo
論文名稱:應用分散式計算與HermiteNormalForm轉換於線性整數最佳化
論文名稱(外文):A Distributed Algorithm For A Class of Linear Integer Programs By Modified Hermite Normal Form Transformation
指導教授:黎漢林黎漢林引用關係
指導教授(外文):Han-Lin Li
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊管理所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:52
中文關鍵詞:赫密正規化演算法LLL 赫密正規化演算法線性整數最佳化問題分散式計算
外文關鍵詞:Hermite Normal Form AlgorithmLLL Based Hermite Normal AlgorithmLinear Integer ProgramDistributed Algorithm
相關次數:
  • 被引用被引用: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-534
2.David E. Goldberg, Genetic Algorithms in Search, Optimization, & Machine Learning, Michigan, 1989
3.George L. Nemhauser, Laurence A. Wolsey, Integer and Combinatorial Optimization, USA, 1988
4.Keith R. Matthews, Extended gcd and Hermite Normal Form Algorithms via Lattices Basis Reduction, New Zealand, 1998
5.Michalewicz, Z., Genetic Algorithm + Data Structure = Evolution Programs, 3rd edition, Springer-Verlag, New York, 1996
6.Mitsuo Gen, Run-Wen Cheng, Genetic Algorithms And Engineering Optimization, 2nd edition, USA, 1999

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top