跳到主要內容

臺灣博碩士論文加值系統

(18.205.192.201) 您好!臺灣時間:2021/08/06 05:19
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張桓輔
研究生(外文):Huan-Fu Chang
論文名稱:以調適記憶投射法求解附有一般上限限制式之多維袋裝問題
論文名稱(外文):The Adaptive Memory Projection Method for Multidimensional Knapsack problems with generalized Upper Bound Constraints
指導教授:梁韵嘉梁韵嘉引用關係
指導教授(外文):Yun-Chia Liang
學位類別:碩士
校院名稱:元智大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:106
中文關鍵詞:調適記憶法關鍵事件禁忌搜尋法附有一般上限限制式之多維裝袋問題切割平面法限制搜尋解空間
外文關鍵詞:Adaptive MemoryCritical Event Tabu SearchGUBMKPCutting PlanesRestricted Search Space
相關次數:
  • 被引用被引用:0
  • 點閱點閱:163
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
本研究提出調適記憶投射法(Adaptive Memory Projection, AMP)求解附有一般上限限制式的多維背包問題(Multidimensional Knapsack Problem with Generalized Upper Bound Constraints, GUBMKP)。此問題中,所有變數被分派至數個一般上限集合中,且每一個一般上限集合中,最多有一個變數被選擇。GUBMKP可被應用在資本預算、資源分派、貨運裝載與專案分配等實際問題上,且GUBMKP是多維背包問題的一個特殊類型,而多維背包問題則隸屬於NP-hard的範疇。因此,當求解問題規模較大例子時,使用萬用啟發式演算法在計算上是較有優勢的。
調適記憶法(Adaptive Memory)紀錄演算法搜尋到的較好解,並根據這些解產生新的解。投射法即固定所選擇子集合中的變數,並最佳化其所對應之子問題;投射法在萬用啟發式演算法中是非常有用的法則,特別是在大規模問題的最佳化上。此調適記憶投射法使用關鍵事件禁忌搜尋法(Critical Event Tabu Search)與精確演算法,並利用假切面不等式(Pseudo-cut Inequality)與長期記憶來增加多樣化。
本研究根據調適記憶投射法中所使用的參數及策略進行詳盡之敏感度分析,並以大小不等之九組測試例題加以測試。運算結果具體呈現本方法之優勢。
An adaptive memory projection (referred as AMP) method is developed for multidimensional knapsack problems with generalized upper bound constraints (referred as the GUBMKP). All the variables are divided into several generalized upper bound (referred as GUB) sets and at most one variable can be chosen from each GUB set. The GUBMKP can be applied to many real-world problems, such as capital budgeting, resource allocation, cargo loading, project selection, just to name a few. The GUBMKP is a special case of multidimensional knapsack problems (referred as MKP), a well-known NP-hard problem. Therefore, it is justified to use metaheuristics to approximate the optimal solution for large problem instances.
The adaptive memory procedure keeps track of components of good solutions during the search and creates provisional solution by combining components of better solutions. The projection method, which fixes the selected variables while varying the others, is very useful for metaheuristics, especially in large scale optimization. In this study, the AMP method is implemented by incorporating critical event tabu search and the branch and bound method built in a commercial optimization solver. In addition to the diversification effect within critical event tabu search, the pseudo-cut inequalities and an adjusted frequency penalty scalar are also applied to increase opportunities of exploring new regions.
This study conducts a comprehensive sensitivity analysis on the parameters and strategies used in the proposed AMP algorithm. The performance of the algorithm is verified using a set of nine instances that consists of small- to large-scale instances. Therefore, this study has provided a fundamental basis for applying the AMP method to solve the GUBMKP.
摘 要 i
ABSTRACT ii
致 謝 iv
CONTENTS v
LIST OF FIGURES vii
LIST OF TABLES x
CHAPTER 1 INTRODUCTION 1
1.1 Background and Motivation 1
1.2 Research Procedures 3
CHAPTER 2 LITERATURE SURVEY 5
2.1 Formulation of Knapsack Problems 5
2.2 Exact Methods for the MKP 6
2.3 Metaheuristics Methods for the MKP 7
2.4 Surrogate Constraints 9
2.5 Controlling Oscillation Span 11
2.6 GUB-size Based Tenure 13
2.7 Adaptive Memory 14
CHAPTER 3 METHODOLOGY 15
3.1 The Adaptive Memory Projection Method 15
3.1.1 Fundamentals of the adaptive memory projection method 16
3.1.2 Types of free variables 19
3.1.3 Pseudo-cut inequalities 24
3.2 Critical Event Tabu Search 28
3.2.1 Fundamental of critical event tabu search 28
3.2.1 Surrogate constraint and choice rules 30
3.2.2 Penalty adjusted ratio 37
3.2.3 Extra tabu list 38
3.2.4 Tabu status 39
3.2.5 Adjusted frequency penalty scalar 40
3.2.6 Controlling oscillation span 41
3.3 Intensification 42
CHAPTER 4 COMPUTATAIONAL RESULTS 45
4.1 Test Problems 45
4.2 Performance Measurement 46
4.3 Parameters and Tests of Strategies 46
4.3.1 Critical events 48
4.3.2 Adjustment of the tabu tenures 50
4.3.3 Changing tabu tenure systematically 52
4.3.4 Oscillation of spans 54
4.3.5 Updating of the surrogate constraints 68
4.3.6 Intensification tests 70
4.3.7 Pseudo-cuts 74
4.3.8 The frequency penalty scalar 77
4.3.9 Sensitivity analysis for consistent variable 83
4.3.10 Parameters sensitivity for attractive candidates 85
4.3.11 Size of free variable set and number of iterations 88
4.3.12 Types of free variables 96
4.4 Experimental Results 99
4.5 Summary 100
CHAPTER 5 CONCLUSIONS AND FUTURE STUDIES 101
5.1 Conclusions 101
5.2 Future Studies 101
REFERENCES 102
Ahmadi, S. and Osman, I. (2005) Greedy random adaptive memory programming search for the capacitated clustering problem. European Journal of Operational Research, 162: 30-44.
Ahuja, R. K., Ergun, O., Orlin, J. B., and Punnen A. P. (2002) Survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics, 123: 75-102.
Bertsimas, D. and Demir, R. (2002) An approximate dynamic programming approach to multidimensional knapsack problems. Management Science, 48: 550-565.
Battiti, R. and Tecchiolli, G.. (1994) The reactive tabu search. ORSA Journal of Computing, 6(2): 126-140.
Bozkaya, B., Erkut, E., and Laporte, G.. (2003) A tabu search heuristic and adaptive memory procedure for political districting. European Journal of Operational Research, 144: 12–26.
Chardaire, P., McKeown, G. P., and Maki, J. A. (2001) Application of GRASP to the multiconstraint knapsack problem. Applications of Evolutionary Computing, LNCS 2037: 30-39.
Chen, Y. S. (2007) Scatter search for multidimenstional knapsack problems with generalized upper bound constraints. Master thesis, Graduate Institute of Global Operations Strategy and Logistics Management, National Dong Hwa University, Taiwan.
Chu, P. C. and Beasley, J. E. (1998) A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4: 63-86.
Danna, E., Rothberg, E., and Pape, C. (2005) Exploring relaxation induced neighborhoods to improve MIP solutions. Mathematical Programming, 102: 71-90.
Drexl, A. (1988) A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing, 40: 1-8.
Fischetti, M. and Lodi, A. (2003) Local branching. Mathematical Programming, 98: 23-47.
Feo, T. A. and Resende, M. G. C. (1995) Greedy randomized adaptive search procedures. Journal of Global Optimization, 6: 109-133.
Fisher, M. L. and Shapiro, J. F. (1974) Constructive duality in integer programming. SIAM Journal on Applied Mathematics, 27: 31-52.
Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: a guide to the theory of NP-completeness. Freeman: San Francisco.
Gilmore, P.C. and Gomory, R.E. (1966) The theory and computation of knapsack functions. Operations Research, 14: 1045-1075.
Glover, F. (2000) Multi-start and strategic oscillation methods - principles to exploit adaptive memory. Computing Tools for Modeling, Optimization and simulation: Interfaces in Computer Science and Operations Research, in Laguna Laguna, M. and Gonzales Velarde, J. L. (eds.), Kluwer Academic Publishers, 1-24.
Glover, F. (2002) Surrogate constraint in optimization V tutorial notes, University of Colorado, Boulder.
Glover, F (2005) Adaptive memory projection methods for integer programming. In Rego, C., Alidaee, B. (eds.),Metaheuristic Optimization Via Memory and Evolution, 425-440.
Glover, F. and Kochenberger, G.A. (1996) Critical event tabu search for multidimensional knapsack problems. In Osman, I.H. and Kelly, J. P. (eds.), Meta-heuristics: Theory and Applications. Kluwer Academic Publishers, 407-427.
Hanafi, S. and Freville, A. (1998) An efficient tabu search approach for 0-1 multidimensional knapsack problem. European Journal of Operational Research, 106(2-3): 659-675.
Hanafi, S., Freville, A., and Plateau, G.. (1982) Methods heuristiques performantes pour les programmes en variables 0-1. Working paper, ANO-91, Universite des Sciences et Techniques de Lille, France.
Hanafi, S. and Wilbaut, C. (2008) Scatter search for the 0-1 multidimensional knapsack problem. Journal of Mathematical Modelling and Algorithms, 7: 143-159.
Held, M. and Karp, R. M. (1970) The traveling salesman problem and minimum spanning trees. Operations Research, 18: 1138-1162.
Holland, J.H. (1975) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press.
Hvattum, L., Løkketangen, A., and Glover, F. (2004) Adaptive memory search for boolean optimization problems. Discrete Applied Mathematics. 142: 99–109.
Kolesar P. J. (1967) A branch and bound algorithm for the knapsack problem. Management science, 13: 723-735.
Land, A. H. and Doig, A. G.. (1960) An automatic method of solving discrete programming problems. Econometrica, 28: 497-520.
Li, V. C. (2005) Tight oscillation tabu search for multidimensional knapsack problems with generalized upper bound constraints. Computers & Operations Research, 32: 2843-2852.
Li, V. C. and Curry, G. L. (2005) Solving multidimensional knapsack problem with generalized upper bound constraints using critical event tabu search. Computers & Operations Research, 32: 825-848.
Li, V. C., Curry, G. L., and Boyd, E. A. (2004) Towards the real time solution of strike force asset allocation problems. Computers & Operations Research, 31: 273-291.
Lorie, J. and Savage, L.J. (1955) Three problems in capital rationing. Journal of Business, 28: 229-239.
Magazine, M. J. and Oguz, O. (1984) A heuristic algorithm for the multidimensional 0-1 knapsack problem. European Journal of Operational Research, 16: 319-326.
Olivera, A. and Viera, O. (2007) Adaptive memory programming for the vehicle routing problem with multiple trips. Computers & Operations Research. 34: 28-47.
Petersen, C.C. (1967) Computational experience with variants of the Balas algorithm applied to the selection of R&D projects. Management Sciences 13: 736-750.
Plateau, G. and Elkihel, M. (1985) A hybrid method for the 0-1 knapsack problem. Methods of Operations Research, 49: 277-293.
Rochat, Y. and Taillard, E. D. (1995) Probabilistic diversication andintensication in local search for vehicle routing. Journal of Heuristics. 1: 147–67.
Shapiro, J. F. (1971) Generalized Lagrange multipliers in integer programming. Operations Research, 19: 68-76.
Shih, W. (1979) A branch and bound method for the multiconstraint zero-one knapsack problem. Journal of the Operations Research Society, 30: 369-378.
Tang, H. and Miller-Hooks, E. (2005) A TABU search heuristic for the team orienteering problem. Computers and Operations Research. 32: 1379–407.
Weingartner, H.M. (1963) Mathematical programming and the analysis of capital budgeting problems. Prentice-Hall, Englewoods Cliffs, NJ.
Weingartner, H. M. and Ness, D. N. (1967) Methods for the solution for the multidimensional 0–1 knapsack problem. Operations Research, 15: 83–103.
Wilbaut, C., Salhi, S., and Hanafi S. (2009) An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem. European Journal of Operational Research, 199: 339-348.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top