臺灣博碩士論文加值系統

多目標問題有別於單一目標問題，其困難之處在於如何在不同的目標中做衡量，如規劃旅程中的移動速度與金錢成本，或是自然生態指數與城市人文指數兩兩間有著互相衝突的特性，旅行者往往面臨到眾多景點中不同特性，在有限的時間與金錢預算中難以做出取捨，然而在多目標規劃(Multi-objective programming)問題中，僅有單一最佳解的情形十分罕見，因此需要一組凌越解集合(Noninferior Solutions)，再提供給旅行者做評估、參考或是實際走訪。
過去諸多研究均以透過權重組合函數，使問題簡化為單一目標問題，透過調整權重改變鄰近解的搜尋方向，然而這樣的方法並無考量到在執行鄰近解搜尋時，所有解的集合空間內產生出的新鄰近解與現有凌越勢解集合的相對位置，因此本研究以模擬退火法結合加權函數與解的相對位置發展多目標最佳化演算法，經運算測試後，對於提升求解效率有顯著效果。

Unlike Single-objective programming, the difficulty of Multi-objective programming lies in how to evaluate the different categories of objectives, such as planning the moving speed and money cost during a journey, or analyzing and calculating the conflicting feature between the natural Ecological index and Humanities index. Travelers often encounter numerous characteristics in different tourist attractions, and it becomes hard for them to make choices due to the limitation of time and money. However, in a Multi-objective programming, the case that contains only one optimal solution is very rare, therefore, it is necessary to set up a set of Noninferior Solutions, and then provide these solutions for travelers’ own assessment, reference or visit.
Various studies in the past simplifies a problem into a Single-objective function by increasing weights, and adjusts the searching direction of near solutions by arranging the weights. Nevertheless, this method doesn’t take into account the relative position between the near solutions produced by the all solutions set, and the existing Noninferior solutions set when conducting near solution searching. As a consequence, this study develops an optimal Multi-objective programming algorithm by combining Simulated Annealing and the relative position between weight function and its solution.

摘要 i
ABSTRACT ii
目錄 iii
圖目錄 vii
表目錄 ix
一、緒論 1
1.1研究背景與動機 1
1.2研究目的 1
1.3研究流程 2
二、文獻探討 4
2.1越野問題 4
2.2通用啟發式演算法 5
2.2.1模擬退火法 5
2.2.2禁忌搜尋法 6
2.2.3基因演算法 7
2.2.4變動鄰域搜尋法 8
2.2多目標最佳化(Multi-Objective Optimization) 8
三、求解過程 12
3.1問題特性描述 12
3.2問題基本假設 12
3.2.1參數 13
3.2.2變數 13
3.2.3問題基本定義 13
3.3雙目標模擬退火法(Bi-objective Simulated Annealing；BOSA) 14
3.4 起始解 22
3.5 調整權重 22
3.6 編碼與解碼 22
3.7 鄰近解搜尋 24
3.7.1 Swap 交換 24
3.8.2 Reverse 反序 24
3.7.3 Insert 插入 25
4.8更新目前解與否 25
四、求解結果 27
4.1測試例題 27
4.2評量指標 29
4.2.1 Hypervolume指標 30
4.2.2 Unary Epsilon 指標 30
4.2.3 R3指標 31
4.2.4 Pareto Frontier Approximation指標 31
4.3參數設置 32
4.3.1退火機制權重參數α 33
4.3.2模擬退火法基本參數 34
4.4運算測試 35
五、結論與建議 40
5.1研究結論與貢獻 40
5.2建議及未來發展 42
參考文獻 44
附錄A 運算測試結果 47

Arkin, E. M., M. Held, J. S. B. Mitchell and S. S. Skiena (1998). "Recognizing polygonal parts from width measurements." Computational Geometry-Theory and Applications 9(4): 237-246.
Arkin, E. M., J. S. B. Mitchell and G. Narasimhan (1998). "Resource-constrained geometric network optimization." Proceedings of the fourteenth annual symposium on Computational geometry: 307-316.
Battiti, R. and G. Tecchiolli (1994). "The Reactive Tabu Search." ORSA Journal on Computing 6: 126-140.
Boussaid, I., J. Lepagnot and P. Siarry (2013). "A survey on optimization metaheuristics." Information Sciences 237: 82-117.
Butt, S. E. and T. M. Cavalier (1994). "A heuristic for the multiple tour maximum collection problem." Computers & Operations Research 21(1): 101-111.
Chao, I. M., B. L. Golden and E. A. Wasil (1996). "The team orienteering problem." European Journal of Operational Research 88(3): 464-474.
Czyzak, P., & Jaszkiewicz, A. (1996). "A multiobjective metaheuristic approach to the localization of a chain of petrol stations by the capital budgeting model." Control and Cybernetics 25(1): 177-187.
Gendreau, M., G. Laporte and F. Semet (1998). "A branch-and-cut algorithm for the undirected selective traveling salesman problem." Networks 32(4): 263-273.
Glover, F. (1986). "Future paths for integer programming and links to artificial intelligence." Computers & Operations Research 13(5): 533-549.
Hansen, M. P., A. Jaszkiewicz and D. T. U. I. f. M. Modellering (1998). Evaluating the Quality of Approximations to the Non-dominated Set, IMM, Department of Mathematical Modelling, Technical Universityof Denmark.
Hansen, P., N. Mladenovic and D. Perez-Britos (2001). "Variable neighborhood decomposition search." Journal of Heuristics 7(4): 335-350.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems, University of Michigan Press.
Kataoka, S. and S. Morito (1988). "An algorithm for single constraint maximum collection problem." Journal of the Operations Research Society of Japan 31: 515-530.
Kirkpatrick, S., C. G. . and M. Vecchi (1983). "Optimization by Simulated Annealing." Science 220: 671-680.
Laporte, G. and S. Martello (1990). "The Selective Traveling Salesman Problem." Discrete Applied Mathematics 26(2-3): 193-207.
Schilde, M., K. F. Doerner, R. F. Hartl and G. Kiechle (2009). "Metaheuristics for the bi-objective orienteering problem." Swarm Intelligence 3(3): 179-201.
Serafini, P. (1994). Simulated Annealing for Multi Objective Optimization Problems. Multiple Criteria Decision Making: Proceedings of the Tenth International Conference: Expand and Enrich the Domains of Thinking and Application. G. H. Tzeng, H. F. Wang, U. P. Wen and P. L. Yu. New York, NY, Springer New York: 283-292.
Suppapitnarm, A., K. A. Seffen, G. T. Parks and P. J. Clarkson (2000). "A simulated annealing algorithm for multiobjective optimization." Engineering Optimization 33(1): 59-85.
Vansteenwegen, P., W. Souffriau, G. Vanden Berghe and D. Van Oudheusden (2009). "Iterated local search for the team orienteering problem with time windows." Computers & Operations Research 36(12): 3281-3290.
Zitzler, E. and L. Thiele (1999). "Multiobjective evolutionary algorithms: A comparative case study and the Strength Pareto approach." Ieee Transactions on Evolutionary Computation 3(4): 257-271.
Zitzler, E., L. Thiele, M. Laumanns, C. M. Fonseca and V. G. da Fonseca (2003). "Performance assessment of multiobjective optimizers: An analysis and review." Ieee Transactions on Evolutionary Computation 7(2): 117-132.