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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:梁錫卿
研究生(外文):Shyi Ching Liang
論文名稱:解旅行推銷員問題及二次分配問題之混合超啓發式演算法
論文名稱(外文):Hybrid Metaheuristics for the Traveling Salesman Problem and the Quadratic Assignment Problem
指導教授:曾怜玉曾怜玉引用關係
指導教授(外文):Lin Yu Tseng
學位類別:博士
校院名稱:國立中興大學
系所名稱:應用數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:英文
論文頁數:95
中文關鍵詞:超啓發式演算法旅行推銷員問題二次分配問題遺傳演算法蟻群演算法區域搜尋法
外文關鍵詞:MetaheuristicTraveling Saleman ProblemQuadratic Assignment ProblemGenetic AlgorithmAnt Colony OptimizationLocal Search
相關次數:
  • 被引用被引用:0
  • 點閱點閱:205
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
這篇論文呈現了針對複雜問題尋求最佳解而發展的超啓發式 (Metaheuristic) 演算法所做的研究,這個新的超啓發式演算法是以結合三個演算法為基礎,分別為蟻群最佳化演算法 (Ant Colony Optimization)、遺傳演算法 (Genetic Algorithm)、以及區域搜尋方法,我們將之命名為ANGEL,其主要構想為藉由整合全域搜尋法與區域搜尋法來加強探索 (exploration) 及利用 (exploitation) 的能力。在遺傳演算法中,初始母體不是經由隨機產生而是擷取蟻群最佳化演算法產生的解來組成以提供效能的提昇。同時我們也利用費洛蒙更新 (pheromone updating) 來記憶遺傳演算法的搜尋努力,並將之利用在隨後的蟻群最佳化演算法中,以將蟻群最佳化演算法引導到較好的區域。遺傳演算法及蟻群最佳化演算法所產生的解會藉由區域搜尋方法來做改善,區域搜尋對於探索區域地貌是很有用的方法,對於特定解的鄰近解的檢視,所使用的是某種類型的操作。蟻群最佳化演算法與遺傳演算法交互合作的執行以協助對方,我們也提出一個概念稱為優生策略 (Eugenic Strategy),它能在不損失解品質的情況下加速GA的收斂。
我們使用了兩個測試問題,分別為旅行推銷員問題 (Traveling Salesman Problem) 及二次分配問題 (Quadratic Assignment Problem)。在解決旅行推銷員問題時,經由重複粹取最小擴展樹 (Minimum Spanning Tree),可以得到一組有希望包含最佳解的邊之集合,稱之為Promising Edges Set (PES),藉此特性,我們提出了一個新的遺傳演算法exploring PES GA (EPGA) 及一個新的交配子 exploring edge set crossover operator (EESX),同時,也提出另一個新的交配子 eugenic edge preserving crossover operator (EEPX),它是藉由利用PES來改善解的品質。
藉著執行一系列的實驗來評估這個新超啓發式演算法的能力,這兩個問題所使用的問題組包含各種大小的實驗組合,均取自相關著名的比較基準問題組,實驗結果顯明ANGEL的效能相當好。
This dissertation represents the research of the development of new metaheuristics for locating optimal solutions to difficult problems. The new metaheuristic is founded upon the combination of three algorithms, the ant colony optimization (ACO), the genetic algorithm (GA), and the local search method, which is called ANGEL. The key idea is to enhance the ability of exploration and exploitation by incorporating global search with local search. Instead of starting from randomly generated population, GA retrieves the solutions previously constructed by ACO to provide a performance boost. In GA, the pheromone updating is used to memorize the GA’s search efforts. The updated pheromone will guide ACO to a hopefully better area. The solutions generated by ACO and GA are refined by means of the local search. Local search is useful for exploring a localized landscape. The examination of the neighborhood of a given solution is derived from some class of operations. The ACO and the GA runs alternatively and cooperatively to enhance each other. A concept called the eugenic strategy that guides the GA to converge quickly without degenerating solution quality also has been proposed.
Two test problems were used – the Traveling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP). In solving TSP, a set of promising edges, called promising edge set (PES), is derived by iteratively extracting the minimum spanning trees. A new genetic algorithm called the exploring PES GA (EPGA) with a new crossover operator called the exploring edge set crossover (EESX) is proposed. Also, a new crossover operator, called the eugenic edge preserving crossover (EEPX), is proposed to improve the solutions by exploiting PES.
A series of experiments were conducted to assess the capabilities of this new metaheuristic. Instances of these two problems were taken from well known benchmarks with different problem sizes.
Contents
1 Introduction ……………………………………………………………………… 1
1.1 Motivation …………………………………………………………………… 1
1.2 An Overview ………………………………………………………………… 3
2 Two Combinatorial Optimization Problems …………………………………… 5
2.1 The Traveling Salesman Problem …………………………………………… 5
2.1.1 Definition ………………………………………………………………… 5
2.1.2 Previously Proposed Algorithms ………………………………………… 6
2.2 The Quadratic Assignment Problem ………………………………………… 7
2.2.1 Definition ………………………………………………………………… 7
2.2.2 Previously Proposed Algorithms ………………………………………… 8
3 Techniques Used in ANGEL………………………………………………………… 10
3.1 Ant Colony Optimization …………………………………………………… 10
3.1.1 Overview of the Ant Colony Optimization ……………………………… 10
3.1.2 Ants, Pheromones, and Solutions Evaluation …………………………… 11
3.2 Genetic Algorithm …………………………………………………………… 13
3.2.1 Overview of the Genetic Algorithm …………………………………… 13
3.2.2 Genetic Operators ……………………………………………………… 14
3.3 Local Search ………………………………………………………………… 14
3.3.1 Overview of the Local Search …………………………………………… 14
3.3.2 2-OPT, 3-OPT, and Their Variants ……………………………………… 15
3.3.3 The Lin-Kernighan Algorithm …………………………………………… 16
4 Two Hybrid Metaheuristics for the Traveling Salesman Problem ……………… 18
4.1 The Exploring PES Genetic Algorithm ……………………………………… 18
4.1.1 Generation of the Promising Edge Set …………………………………… 19
4.1.2 Applying EPGA for the TSP ……………………………………………… 24
4.1.3 Solution representation …………………………………………………… 24
4.1.4 Decoding and evaluation ………………………………………………… 24
4.1.5 Genetic operators ………………………………………………………… 25
4.1.6 Initialization ……………………………………………………………… 27
4.1.7 Experimental results and discussions …………………………………… 29
4.2 ANGEL Metaheuristic for the TSP ………………………………………… 31
4.2.1 The Ant Colony Optimization …………………………………………… 32
4.2.2 The Genetic Algorithm …………………………………………………… 34
4.2.3 The Lin-Kernighan Heuristic……………………………………………… 39
4.2.4 Design of Experiments …………………………………………………… 39
4.2.5 Evaluation of Experimental Results ……………………………………… 41
5 ANGEL Metaheuristic for the Quadratic Assignment Problem ……………… 50
5.1 ANGEL Metaheuristic for the QAP ………………………………………… 51
5.1.1 The ACO Phase …………………………………………………………… 53
5.1.2 The GA Phase …………………………………………………………… 55
5.1.3 The Local Search ………………………………………………………… 61
5.2 Design of Experiments ………………………………………………………… 62
5.3 Evaluation of Experimental Results …………………………………………… 64
6 Conclusions and Future Research Works ……………………………………… 82
Bibliography …………………………………………………………………………… 84
VITA …………………………………………………………………………………… 93
Publications ……………………………………………………………………………… 94

List of Figures
3.1 An iteration of the ACO metaheuristic ……………………………………………… 11
3.2 A 2-opt move ……………………………………………………………………… 15
3.3 A 3-opt move ……………………………………………………………………… 15
4.1 Construction process of the PES for the instance att48 …………………………… 20
4.2 Representation of a chromosome …………………………………………………… 24
4.3 The decoding procedure …………………………………………………………… 25
4.4 The EESX crossover operator ……………………………………………………… 26
4.5 EPGA for TSP ……………………………………………………………………… 28
4.6 ANGELTSP metaheuristic for the TSP ……………………………………………… 31
4.7 The illustration of the OX1 crossover for TSP ……………………………………… 35
4.8 The illustration of the EEPX crossover for TSP …………………………………… 36
4.9 The illustration of the mutation operator …………………………………………… 38
5.1 The representation of a solution …………………………………………………… 51
5.2 ANGELQAP metaheuristic …………………………………………………………… 52
5.3 The ACOQAP phase of ANGEL for QAP …………………………………………… 53
5.4 The GA phase of ANGEL for QAP ………………………………………………… 56
5.5 The illustration of OX1 crossover for QAP ……………………………………… 58
5.6 The illustration of DPX crossover for QAP ………………………………………… 60

List of Tables
4.1 Analysis of the optimal tour edges’ coverage rate in PES ………………………… 22
4.2 EPGA’s test results of some TSPLIB instances …………………………………… 30
4.3 The comparison of ANGELTSP and LKH on TSPLIB instances
with sizes greater than 500. ………………………………………………………… 44
4.4 ANGELTSP’s test results of the Random Uniform Euclidean instances,
Clustered Euclidean instances, and Random Matrix instances. …………………… 45
4.5 ANGELTSP’s test results of Large TSPLIB instances. ……………………………… 46
4.6 The comparison of ANGELTSP’s results and other methods’ results on
the Random Uniform Euclidean instances (E*), the Clustered Euclidean
instances (C*), and the Random Matrix instances (M*). ………………………… 47
4.7 The comparison of ANGELTSP’s results and other methods’ results on
large instances. ……………………………………………………………………… 48
4.8 The comparison of ANGELTSP, ANGELcandidatelist, Without ACO,
and ANGELw/o eepx. ………………………………………………………………… 49
5.1 The computational results of ANGELQAP on all QAPLIB instances with
sizes not less than 30. ……………………………………………………………… 68
5.2 Comparison of results obtained by ANGELQAP, GA+LS, and ACO+LS. ………… 69
5.3 Comparison of results obtained by ANGELQAP, GA+LS, and ACO+LS. ………… 70
5.4 Comparison of results obtained by ANGELQAP and ANGELQAP +EliteGroup. …… 71
5.5 Comparison of results obtained by ANGELQAP using different
crossover operators. …………………………………………………………… 72
5.6 Quality of various heuristic methods for QAPLIB instances. ……………………… 73
5.7 The computation results of ANGELQAP on QAPLIB nug type instances. ………… 76
5.8 The computation results of ANGELQAP on QAPLIB bur type instances. ………… 76
5.9 The computation results of ANGELQAP on QAPLIB chr type instances. ………… 77
5.10 The computation results of ANGELQAP on QAPLIB esc and els type instances. … 77
5.11 The computation results of ANGELQAP on QAPLIB had and kra type instances. … 78
5.12 The computation results of ANGELQAP on QAPLIB scr and rou type instances. … 78
5.13 The computation results of ANGELQAP on QAPLIB tho, wil and ste type
instances. …………………………………………………………………………… 79
5.14 The computation results of ANGELQAP on QAPLIB sko type instances. ………… 79
5.15 The computation results of ANGELQAP on QAPLIB tai type instances. ………… 80
5.16 The computation results of ANGELQAP on QAPLIB tai-b type instances. ……… 80
5.17 The computation results of ANGELQAP on QAPLIB lipa-a type instances. ……… 81
5.18 The computation results of ANGELQAP on QAPLIB lipa-b type instances. ……… 81
Bibliography

[1]E. H. L. Aarts and H. P. Stehouwer, “Neural networks and the traveling salesman problem,” in Proc. Int. Conf. on Artificial Neural Networks, Springer-Verlag, pp. 950-955, 1993.
[2]R. K. Ahuja, J. B. Orlin, and A. Tiwari, “A greedy genetic algorithm for the quadratic assignment problem,” Computers & Operations Research, vol. 27, pp. 917-934, 2000.
[3]J. R. A. Allwright, and D. B. Capenter, “A distributed implementation of simulated annealing for the traveling salesman problem,” Parallel Computing, vol. 10, pp. 335-338, 1989.
[4]E. Angel, and V. Zissimopoulos, “On the landscape ruggedness of the quadratic assignment problem,” Theoretical Computer Science, vol. 263, pp. 159-172, 2001.
[5]D. Applegate, R. Bixby, V. Chvátal, and W. Cook, “Finding tours in the TSP,” http://www.tsp.gatech.edu//papers/index.html.
[6]D. Applegate, W. Cook, A. Rohe, “Chained Lin-Kernighan for large traveling salesman problems,” http://www.isye.gatech.edu/~wcook/.
[7]R. Baraglia, J. I. Hidalgo, and R. Perego, “A hybrid heuristic for the traveling salesman problem,” IEEE Trans. Evol. Comput., vol. 5, no. 6, pp. 613-622, December 2001.
[8]R. Battiti and G. Tecchiolli, “The reactive tabu search,” ORSA Journal on Computing, vol. 6, pp. 126-140, 1994.
[9]J. L. Bentley, “Fast algorithms for geometric traveling salesman problem,” ORSA J. Comput., vol. 4, pp. 397-411, 1992.
[10]F. Bock, ‘‘An algorithm for solving ‘‘traveling-salesman’’ and related network optimization problems,’’ unpublished manuscript associated with talk presented at the 14th ORSA National Meeting, 1958.
[11]R. E. Burkard and U. Derigs, “Assignment and matching problems: solution methods with FORTRAN programs,” Lecture Notes in Economics and Mathematical Systems, Springer-Verlag: Berlin, 1980.
[12]R. E. Burkard, S. E. Karisch, and F. Rendl, “QAPLIB-A quadratic assignment problem library, Journal of Global Optimization,” vol. 10, pp.391-403, 1997. [URL: http://fmatbhp1.tu-graz.ac.at/~karisch/qaplib/]
[13]R. E. Burkard and J. Offermann, “Entwurf von schreibmaschinentastaturen mittels quadratischer zuordnungsprobleme,” Zeitschrift für Operations Research, vol. 21, pp. B121-B132, 1977.
[14]J. Chakrapani and J. Skorin-Kapov, “A connectionist approach to the quadratic assignment problem,” Computers & Operations Reasearch, vol. 19, no. 3/4, pp. 287-295, 1992.
[15]N. Christofides, ‘‘Worst-case analysis of a new heuristic for the traveling salesman problem,’’ Report No. 388, GSIA, Carnegie-Mellon University, Pittsburgh, PA, 1976.
[16]N. Christofides, S. Eilson, “Algorithms for large-scale traveling salesman problems,” Oper. Res. Quarterly, vol. 23, pp. 511-518, 1972.
[17]G. Clarke AND J. W. Wright, ‘‘Scheduling of vehicles from a central depot to a number of delivery points,’’ Oper. Res., vol. 12, pp. 568-581, 1964.
[18]D. T. Connolly, “An improved annealing scheme for the qap,” European Journal of Operational Research, vol. 46, pp. 93-100, 1990.
[19]G. A. Croes, ‘‘A method for solving traveling salesman problems,’’ Oper. Res., vol. 6, pp. 791-812, 1958.
[20]M. Dorigo, “Optimization, learning and natural algorithms,” PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, IT, 1992.
[21]M. Dorigo, L. M. Gambardella, ‘‘Ant colony system: A cooperative learning approach to the traveling salesman problem, ’’ IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 53-66, April 1997.
[22]M. Dorigo, V. Maniezzo, and A. Colorni, “Positive feedback as a search strategy,” Tech. Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, IT, 1991.
[23]M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol. 26, pp. 29-41, 1996.
[24]R. Durbin, R. Szeliski, and A. Yuille, “An analysis of the elastic net approach to the traveling salesman problem,” Neural Computation, vol. 1, pp. 348-358, 1989.
[25]L. Fiechter, “A parallel Tabu search algorithm for large traveling salesman problems,” Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, vol. 51, pp. 243-267, 1994.
[26]C. Fleurent and J. Ferland, “Genetic hybrids for the quadratic assignment problems,” in Quadratic Assignment and Related Problems, P.M. Pardalos and H. Wolkowicz (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16, AMS: Providence, Rhode Island, 1994, pp. 190-206.
[27]B. Freisleben and P. Merz, ‘‘A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems,’’ in Proc. IEEE Int. Conf. Evol. Comput., 1996.
[28]B. Freisleben and M. Schulte. “Combinatorial optimization with parallel adaptive threshold accepting”. In Proc. 1992 European Workshop on Parallel Computing, Barcelona, IOS Press, 1992, pp. 176-179.
[29]L. M. Gambardella and M. Dorigo, “Ant-Q: A reinforcement learning approach to the traveling salesman problem," in Proc.12th Int. Conf. on Machine Learning, Morgan Kaufmann, 1995, pp. 252-260.
[30]L. M. Gambardella, É. D. Taillard, and M. Dorigo, “Ant colonies for the quadratic assignment problem,” Journal of the operational research society, vol. 50, pp. 167-176, 1999.
[31]M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.
[32]A. M. Geoffrion and G. W. Graves, “Scheduling parallel production lines with changeover costs: practical application of a quadratic assignment/LP approach,” Operations Research, vol. 24, pp. 595-610, 1976.
[33]D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.
[34]M. Gorges-Schleuter, “ASPARAGOS An asynchronous parallel genetic optimization strategy,” in Proc. of the Third Int. Conf. On Genetic Algorithms, Morgan Kaufmann, 1989.
[35]M. Gorges-Schleuter, “On the power of evolutionary optimization at the example of ATSP and large TSP problems,” in Proc. of the IEEE Int. Conf. Evol. Comput., 1997.
[36]G. Harik, F. Lobo, D. Goldberg, “The compact genetic algorithm,” IEEE Trans. Evol. Comput., vol. 3, pp. 287-297, Nov. 1999.
[37]K. Helsgaun, “An effective implementation of the Lin–Kernighan traveling salesman heuristic,” Eur. J. Oper. Res., vol. 126, pp. 106-130, 2000.
[38]K. Helsgaun, LKH, an effective implementation of the Lin-Kernighan heuristic, http://www.dat.ruc.dk/~keld/research/LKH/, 2002.
[39]P. Hansen and N. Mladenovic, “An introduction to variable neighborhood search,” In S. Voss, S. Martello, I.H. Osman, and C.Roucairol, editors, Meta-heuristics, Advances and trends in local search paradigms for optimization, Kluwer Academic Publishers, 1998, pp. 433-458.
[40]J. H. Holland, “Adaptation in natural and artificial systems,” Ann Arbor: The University of Michigan Press, 1975.
[41]J. H. Holland, “Genetic algorithms,” Scientific American, pp. 44-51, July, 1992.
[42]L. Homaifar, C. Guan, and G. Liepins, “A new approach to the traveling salesman problem by genetic algorithms," in Proc.5th Int. Conf. on Genetic Algorithms, Morgan Kaufmann Publishers, 1993, pp. 460-466.
[43]D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, “Optimization by Simulated Annealing: An experimental evaluation, Part I (Graph Partitioning),” Oper. Res., vol. 37, pp. 865-892, 1989.
[44]D. S. Johnson, L. A. McGeoch, “The traveling salesman problem: A case study in local optimization,” in Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra, Eds. , New York: Wiley: New York, 1997.
[45]D. S. Johnson, L. A. McGeoch, F. W. Glover, C. Rego, 8th DIMACS implementation challenge on the STSP, http://www.research.att.com/~dsj/chtsp/, 2001.
[46]S. Kirkpatrick, “Optimization by simulating annealing: Quantitative studies,” J. of Statistical Physics, vol. 34, pp. 975-986, 1984.
[47]T. C. Koopmans and M. J. Beckmann, “Assignment problems and the location of economic activities,” Econometrica, vol. 25, pp. 53-76, 1957.
[48]J. Krarup and P. M. Pruzan, “Computer-aided layout design,” Mathematical Programming Study, vol. 9, 75-94, 1978.
[49]P. Van Laarhoven and E. H. L. Aarts, Simulated Annealing: Theory and Applications. Kluwer Academic Publishers, 1987.
[50]P. S. Laursen, “Simulated annealing for the QAP-Optimal tradeoff between simulation time and solution quality,” European Journal of Operational Research, vol. 69, pp. 238-243, 1993.
[51]E. L. Lawler, “The quadratic assignment problem,” Management Science, vol. 9, pp. 586-599, 1963.
[52]E. Lawler, J. K. Lenstra and D. B. Shmoys, The Traveling Salesman Problems: A Guided Tour of Combinatorial Optimization. Wiley, 1985.
[53]Y. Li, P. M. Pardalos, and M. G. C. Resende, “A greedy randomized adaptive search procedure for the quadratic assignment problem,” in Quadratic Assignment and Related Problems, P.M. Pardalos and H. Wolkowicz (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16, AMS: Providence, Rhode Island, 1994, pp. 173-187.
[54]M. H. Lim, Y. Yuan, and S. Omatu, “Efficient genetic algorithms using simple genes exchange local search policy for the quadratic assignment problem,” Computational Optimization and Applications, vol. 15, no. 3, pp. 249-268, 2000.
[55]M. H. Lim, Y. Yuan, and S. Omatu, “Extensive testing of a hybrid genetic algorithm for solving quadratic assignment problems,” Computational Optimization and Applications, vol. 23, no. 1, pp. 47-64, 2002.
[56]S. Lin, ‘‘Computer solutions of the traveling salesman problem,’’ Bell Syst. Tech. J., vol. 44, pp. 2245-2269, 1965.
[57]S. Lin , B. W. Kernighan, ‘‘An effective heuristic algorithm for the traveling-salesman problem,’’ Oper. Res., vol. 21, pp. 498-516, 1973.
[58]V. Maniezzo and A. Colorni, “The ant system applied to the quadratic assignment problem,” IEEE Transactions on Knowledge and Data Engineering, vol. 11 (5), pp. 769-778, 1999.
[59]P. Merz and B. Freisleben, ‘‘Genetic local search for the TSP: New results,’’ in Proc. IEEE Int. Conf. Evol. Comput., 1997.
[60]P. Merz and B. Freisleben, “A genetic local search approach to the quadratic assignment problem,” Proc. of the 7th International Conference of Genetic Algorithms, Morgan Kauffman Publishers, 1997, pp. 465-472.
[61]P. Merz and B. Freisleben, “Fitness landscape analysis and memetic algorithms for the quadratic assignment problem,” IEEE Transactions on Evolutionary Computation, vol. 4 (4), pp. 337-352, 2000.
[62]A. Misevicius, “Genetic algorithm hybridized with ruin and recreate procedure: application to the quadratic assignment problem,” Knowledge-Based Systems, vol. 16, pp. 261-268, 2003.
[63]R. Moll, A. Barto, T. Perkins, and R. Sutton, “Reinforcement learning and local search: A case study,” CMPSCI Tech. Report 9744, 1997
[64]H. Muhlebein, Evolution in Time and Space – The Parallel Genetic Algorithm. Foundations of Genetic Algorithms. Morgan Kaufmann, 1991.
[65]Y. Nagata and S. Kobayashi, “Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem,” in Proc. of the 7th Int. Conf. On Gas, Morgan Kaufmann, 1997, pp. 450-457.
[66]D. Neto, “Efficient Cluster Compensation for Lin-Kernighan Heuristics,” Ph.D. Thesis, Computer Science Department, University of Toronto, 1999
[67]J. W. Pepper, B. L. Golden, and E. A. Wasil, “Solving the traveling salesman problem with annealing-based heuristics: a computational study,” IEEE Trans. Syst., Man, Cybern. A, vol. 32, no. 1, pp. 72-77, January 2002.
[68]J. Perttunen, “On the significance of the initial solution in traveling salesman heuristics,” J. of Operational Research Society, vol. 45, pp. 1131-1140, 1994.
[69]L. S. Pitsoulis, P. M. Pardalos, and D. W. Hearn, “Approximate solutions to the turbine balancing problem,” European Journal of Operational Research, vol. 130, pp. 147-155, 2001.
[70]C. R. Reeves, “Modern heuristic techniques for combinatorial problems,” Oxford: Blackwell Scientific Publications, 1993.
[71]G. Reinelt, “The traveling salesman: Computational solutions for TSP applications.” Lecture Notes in Computer Science, vol. 840, Springer-Verlag, 1994.
[72]G. Reinelt, “TSPLIB – A traveling salesman problem library,” ORSA Journal of Computing, vol. 3, no. 4, pp. 376-384, 1991.
[73]M. Rijal, Scheduling, design and assignment problems with quadratic costs, PhD thesis, New York University, New York, USA, 1995.
[74]D. F. Rossin, M. C. Springer, and B. D. Klein, “New complexity measures for the facility layout problem: an empirical study using traditional and neural network analysis,” Computers & Industrial Engineering, vol. 36, pp. 585-602, 1999.
[75]J. Skorin-Kapov, “Extensions of a tabu search adaptation to the quadratic assignment problem,” Computers & Operations Research, vol. 21, no. 8, pp. 855-865, 1994.
[76]T. Starkweather, D. Whitley, C. Whitley, K. Mathial, “A comparison of genetic sequencing operators,” in Proc. Fourth Int. Conf. On Genetic Algorithms, Morgan Kaufmann, 1991, pp. 69-76.
[77]L. Steinberg, “The backboard wiring problem: a placement algorithm,” SIAM Review, vol. 3, pp. 37-50, 1961.
[78]T. Stützle, “MAX-MIN Ant system for the quadratic assignment problems,” Technical Report AIDA-97-04, FG Intellektik, FB Informatik, TU Darmstadt, march 1997.
[79]T. Stützle, “Iterated local search for the quadratic assignment problem,” Technical Report AIDA-99-03, FG Intellektik, FB Informatik, TU Darmstadt, march 1999.
[80]T. Stützle, M. Dorigo, “ACO Algorithms for the quadratic assignment problem,” D. Corne, M. Dorigo and F. Glove, editors, New Ideas in Optimization, McGraw-Hill, 1999.
[81]E. D. Taillard, “Robust taboo search for the quadratic assignment problem,” Parallel Computing, vol. 17, pp. 443-455, 1991.
[82]E. D. Taillard, “Comparison of iterative searches for the quadratic assignment problem,” Location Science, vol. 3, pp.87-105, 1995.
[83]E.-G. Talbi, Z. Hafidi, J-M Geib, “Parallel adaptive tabu search for large optimization problems,” in Second Metaheuristics International Conference, MIC’97, Sophia-Antipolis, France, 1997, pp. 137-142.
[84]E.-G. Talbi, O. Roux, C. Fonlupt, and D. Robillard, “Parallel ant colonies for the quadratic assignment problem,” Future Generation Computer Systems, vol. 17, pp. 441-449, 2001.
[85]D. M. Tate and A. E. Smith, “A genetic approach to the quadratic assignment problem,” Computers and Operations Research, vol. 22 (1), pp. 73-83, 1995.
[86]C. Walshaw, "A multilevel approach to the traveling salesman problem," Operations Research, to appear.
[87]D. Whitley, T. Starkweather, and D. Fuquay, “Scheduling problems and traveling salesman: The genetic edge recombination operator,” in Proc. Third Int. Conf. On Genetic Algorithms, Morgan Kaufmann, 1989, pp. 133-140.
[88]H. Yoon and B. Moon, “An empirical study on the synergy of multiple crossover operators,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 212-223, April 2002.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top