組合最佳化問題旅行推銷員問題是理論計算機科學中一個重要的領域，而旅行推銷員問題(Traveling Salesman Problems, TSP)是最常被廣泛應用的問題。從過去到現今都有許多的相關研究，而當中有很多是使用啟發式演算法來解決這類型的問題，如珊瑚礁演算法(Coral Reefs Optimization Algorithm, CRO)等。珊瑚礁演算法是模仿珊瑚在珊瑚礁上繁殖、定居過程的演算法，通過模擬一個大小為A×B個方格的礁，珊瑚會通過散播式產卵和孵卵繁衍下一代，產生的幼蟲會和珊瑚為了生存空間而彼此互相競爭。一次一次的疊代後，會漸漸淘汰掉較差的珊瑚。還增加了使得適應度較優的個體容易被選中的機制─自我複製。這樣的機制和限制使得珊瑚礁演算法較其他啟發式演算法收斂得較快且擁有較廣的搜索範圍。
然而，此演算法執行所需的時間，會隨著問題的複雜化而有指數性的提高，且因為解空間的變大，其執行結果也會較差。為解決此問題，許多研究的做法是針對繁殖環節去優化交配運算子，因此本研究開發出新的交配運算子模型，此模型由邊緣重組交配運算子(Edge Recombination crossover operator, ERX)、邊緣建設性重組交配運算子(Edge Constructive Recombination crossover operator, ECRX)、反向邊緣建設性重組交配運算子(Opposite Edge Constructive Recombination crossover operator, OECRX)、邊緣多層重組交配運算子(Edge Multiple Recombination crossover operator, EMRX)所組成，模型結合四種交配運算子的優勢，有效簡化資料集，在合理的運算時間內找出最優解。
本研究所使用的旅行推銷員問題資料集取自TSPLIB的12個TSP實例，當中有9個是國家城市數據集取自World TSP，另外3個則是超大型積體電路(very-large-scale integration, VLSI)的數據集。將優化的交配運算子模型─混合邊緣建設性重組交配運算子模型(Hybrid Edge Constructive Recombination Crossover Model, HECRM)與珊瑚礁演算法結合為CRO-HECRM演算法，與CRO的原始版本、基因演算法(Genetic Algorithm, GA)的原始版本和蟻群演算法(Ant Colony Optimization, ACO)的原始版本進行實驗並比較性能，實驗結果表明CRO-HECRM演算法在各個數據集比其他著名的元啟發式演算法還要好。CRO-HECRM的實驗平均值誤差在各個數據集上都低於8%、實驗最優值誤差上在各個數據集都低於5%，因此證明了利用本研究提出的方法，在較小的資料集上能有效的減少運算成本，而對於複雜且大數據的資料集則能有效的簡化資料集，顯著的減少誤差，找到實際最佳值。這也代表著本研究的CRO-HECRM演算法在複雜且大數據資料集的旅行推銷員問題上具有相當高的潛力。

Combinatorial Optimization Problem is an important field in theoretical computer science, and the Traveling Salesman Problem (TSP) is the most commonly used problem. There are many related studies from the past to the present, and many of them use heuristic algorithms to solve this type of problems, such as Coral Reefs Optimization (CRO) and so on. However, the execution time of this algorithm increases exponentially with the complexity of the problem, and the execution result will be poor as the solution space becomes larger. In order to solve this problem, many research methods are to optimize the crossover operator. Therefore, this study developed a new crossover operator model.

This study proposed a new crossover operator model, which uses four crossover operators to combine. The model combines the advantages of the four crossover operators to effectively simplify the data set and find the optimal solution within a reasonable computing time. The experimental results It is shown that the new crossover operator model algorithm outperforms other algorithms on various datasets. The experimental average error of new crossover operator model is lower than 8% in each dataset, and the experimental optimal value error is lower than 5% in each dataset.

[1] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., 1989.
[2] J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proceedings of the 1995 IEEE International Conference on Neural Networks. Part 4 (of 6), Nov 27 - Dec 1 1995, Perth, Aust, 1995, vol. 4: IEEE, in IEEE International Conference on Neural Networks - Conference Proceedings, pp. 1942-1948, doi: 10.1109/ICNN.1995.488968. [Online]. Available: http://dx.doi.org/10.1109/ICNN.1995.488968
[3] A. Colorni, M. Dorigo, and V. Maniezzo, Distributed Optimization by Ant Colonies. 1991.
[4] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29-41, 1996, doi: 10.1109/3477.484436.
[5] D. Karaboga, "AN IDEA BASED ON HONEY BEE SWARM FOR NUMERICAL OPTIMIZATION," 2005.
[6] S. Salcedo-Sanz, J. Del Ser, I. Landa-Torres, S. Gil-López, and J. A. Portilla-Figueras, "The Coral Reefs Optimization Algorithm: A Novel Metaheuristic for Efficiently Solving Optimization Problems," The Scientific World Journal, vol. 2014, p. 739768, 2014/07/22 2014, doi: 10.1155/2014/739768.
[7] G. B. Mathews, "On the Partition of Numbers," Proceedings of the London Mathematical Society, vol. s1-28, no. 1, pp. 486-490, 1896, doi: 10.1112/plms/s1-28.1.486.
[8] T. Dantzig, J. Mazur, and B. Mazur, Number: The Language of Science. Pi Press, 2005.
[9] N. Biggs, P. M. L. S. E. N. L. Biggs, E. K. Lloyd, and R. J. Wilson, Graph Theory 1736-1936. Clarendon Press, 1976.
[10] N. Biggs, E. K. Lloyd, and R. J. Wilson, Graph Theory, 1736-1936. Clarendon Press, 1986.
[11] A. Schrijver, "On the History of Combinatorial Optimization (Till 1960)," Handbooks in Operations Research and Management Science, vol. 12, 08/24 2001, doi: 10.1016/S0927-0507(05)12001-5.
[12] M. Munlin and M. Anantathanavit, "Hybrid K-means and Particle Swarm Optimization for symmetric Traveling Salesman Problem," in 2015 IEEE 10th Conference on Industrial Electronics and Applications (ICIEA), 15-17 June 2015 2015, pp. 671-676, doi: 10.1109/ICIEA.2015.7334194.
[13] Z. Ahmed, "Adaptive Sequential Constructive Crossover Operator in a Genetic Algorithm for Solving the Traveling Salesman Problem," 02/29 2020.
[14] I. K. Gupta, A. Choubey, and S. Choubey, "Randomized bias genetic algorithm to solve traveling salesman problem," in 2017 8th International Conference on Computing, Communication and Networking Technologies (ICCCNT), 3-5 July 2017 2017, pp. 1-6, doi: 10.1109/ICCCNT.2017.8204127.
[15] Z. Jiang, "Discrete Bat Algorithm for Traveling Salesman Problem," in 2016 3rd International Conference on Information Science and Control Engineering (ICISCE), 8-10 July 2016 2016, pp. 343-347, doi: 10.1109/ICISCE.2016.83.
[16] D. E. Goldberg, "Alleles, loci, and the traveling salesman problem," in Proceedings of an international conference on genetic algorithms and their applications, 1985, vol. 154: Carnegie-Mellon University Pittsburgh, PA, pp. 154-159.
[17] P. Larranaga, C. Kuijpers, R. Murga, I. Inza, and S. Dizdarevic, "Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators," Artificial Intelligence Review, vol. 13, pp. 129-170, 01/04 1999, doi: 10.1023/A:1006529012972.
[18] I. M. Oliver, D. J. Smith, and J. R. C. Holland, "study of permutation crossover operators on the traveling salesman problem," (in English), 1987.
[19] L. D. Whitley, T. Starkweather, and D. A. Fuquay, "Scheduling Problems and Traveling Salesmen: The Genetic Edge Recombination Operator," presented at the Proceedings of the 3rd International Conference on Genetic Algorithms, 1989.
[20] Z. Ahmed, "Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator," International Journal of Biometric and Bioinformatics, vol. 3, 03/01 2010, doi: 10.14569/IJACSA.2020.0110275.
[21] Y. Nagata and S. Kobayashi, "Edge Assembly Crossover: A High-Power Genetic Algorithm for the Travelling Salesman Problem," in ICGA, 1997.
[22] Y. Nagata and S. Kobayashi, "An analysis of edge assembly crossover for the traveling salesman problem," in IEEE SMC'99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No.99CH37028), 12-15 Oct. 1999 1999, vol. 3, pp. 628-633 vol.3, doi: 10.1109/ICSMC.1999.823285.
[23] P. Kora and P. Yadlapalli, "Crossover Operators in Genetic Algorithms: A Review," International Journal of Computer Applications, vol. 162, pp. 34-36, 03/15 2017, doi: 10.5120/ijca2017913370.
[24] A. Otman, J. Abouchabaka, and C. Tajani, "Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem," Int. J. Emerg. Sci., vol. 2, 03/14 2012.
[25] M. Davarynejad, M. R. Akbarzadeh-T, and N. Pariz, "A novel general framework for evolutionary optimization: Adaptive fuzzy fitness granulation," in 2007 IEEE Congress on Evolutionary Computation, 25-28 Sept. 2007 2007, pp. 951-956, doi: 10.1109/CEC.2007.4424572.
[26] A. L. Nelson, G. J. Barlow, and L. Doitsidis, "Fitness functions in evolutionary robotics: A survey and analysis," Robotics and Autonomous Systems, vol. 57, no. 4, pp. 345-370, 2009/04/30/ 2009, doi: https://doi.org/10.1016/j.robot.2008.09.009.
[27] M. Davarynejad, C. W. Ahn, J. Vrancken, J. van den Berg, and C. A. Coello Coello, "Evolutionary hidden information detection by granulation-based fitness approximation," Applied Soft Computing, vol. 10, no. 3, pp. 719-729, 2010/06/01/ 2010, doi: https://doi.org/10.1016/j.asoc.2009.09.001.
[28] H. D. Nguyen, I. Yoshihara, and M. Yasunaga, "Modified edge recombination operators of genetic algorithms for the traveling salesman problem," in 2000 26th Annual Conference of the IEEE Industrial Electronics Society. IECON 2000. 2000 IEEE International Conference on Industrial Electronics, Control and Instrumentation. 21st Century Technologies, 22-28 Oct. 2000 2000, vol. 4, pp. 2815-2820 vol.4, doi: 10.1109/IECON.2000.972444.
[29] P. Black, "Dictionary of Algorithms and Data Structures," 01/01 2006.
[30] G. Gutin, A. Yeo, and A. Zverovich, "Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP," Discrete Applied Mathematics, vol. 117, no. 1, pp. 81-86, 2002/03/15/ 2002, doi: https://doi.org/10.1016/S0166-218X(01)00195-0.
[31] H. J. Berliner, "Some Necessary Conditions for a Master Chess Program," 1973. [Online]. Available: http://ijcai.org/Proceedings/73/Papers/010.pdf.
[32] E. L. Lawler, The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons, 1985.
[33] J. J. Robinson, "On the Hamiltonian Game (A Traveling Salesman Problem)," 1949.
[34] R. Wilson and J. J. Watkins, Combinatorics: Ancient & Modern. OUP Oxford, 2013.
[35] E. A. B. S. G. Williamson, Lists, Decisions and Graphs. S. Gill Williamson.
[36] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Second Edition). 2009.
[37] R. J. Trudeau, Introduction to Graph Theory. Dover Pub., 1993.
[38] P. Deloukas, "Radiation Hybrid Mapping," in eLS.
[39] D. Cox, M. Burmeister, E. Price, S. Kim, and R. Myers, "Radiation Hybrid Mapping: A Somatic Cell Genetic Method for Constructing High-Resolution Maps of Mammalian Chromosomes," Science (New York, N.Y.), vol. 250, pp. 245-50, 11/01 1990, doi: 10.1126/science.2218528.
[40] R. Agarwala, D. Applegate, D. Maglott, G. Schuler, and A. Schaffer, "A Fast and Scalable Radiation Hybrid Map Construction and Integration Strategy," Genome research, vol. 10, pp. 350-64, 04/01 2000.
[41] P. Avner et al., "A radiation hybrid transcript map of the mouse genome," (in eng), Nat Genet, vol. 29, no. 2, pp. 194-200, Oct 2001, doi: 10.1038/ng1001-194.
[42] P. Bartoš, Z. Kotásek, and J. Dohnal, "Decreasing test time by scan chain reorganization," in 14th IEEE International Symposium on Design and Diagnostics of Electronic Circuits and Systems, 13-15 April 2011 2011, pp. 371-374, doi: 10.1109/DDECS.2011.5783113.
[43] T. Zhou, C. Hu, A. Zhu, C.-p. Xu, and C. Wan, "Wrapper scan chain design algorithm for testing of embedded cores based on chaotic dragonfly algorithm," Evolutionary Intelligence, pp. 1-11, 2020.
[44] T. H. Sloane, F. Mann, and H. Kaveh, "Powering the last mile: an alternative to powering FITL," in Proceedings of Power and Energy Systems in Converging Markets, 23-23 Oct. 1997 1997, pp. 536-543, doi: 10.1109/INTLEC.1997.646046.
[45] C. Bailey, T. McLain, and R. Beard, "Fuel Saving Strategies for Separated Spacecraft Interferometry," 02/12 2000, doi: 10.2514/6.2000-4441.
[46] W. Cook, "World TSP," 2nd Jan, 2022 2021. [Online]. Available: https://www.math.uwaterloo.ca/tsp/world/index.html.
[47] R. Tinós, K. Helsgaun, and D. Whitley, "Efficient Recombination in the Lin-Kernighan-Helsgaun Traveling Salesman Heuristic," Cham, 2018: Springer International Publishing, in Parallel Problem Solving from Nature – PPSN XV, pp. 95-107.
[48] W. Cook, "Star Tours," 2nd Jan, 2021 2011. [Online]. Available: https://www.math.uwaterloo.ca/tsp/star/index.html.
[49] V. Panicker, R. Vanga, and R. Sridharan, "Ant colony optimisation algorithm for distribution-allocation problem in a two-stage supply chain with a fixed transportation charge," International Journal of Production Research, vol. 51, pp. 698-717, 03/27 2012, doi: 10.1080/00207543.2012.658118.
[50] "National Traveling Salesman Problems." [Online]. Available: http://www.math.uwaterloo.ca/tsp/world/countries.html.
[51] "VLSI Data Sets." [Online]. Available: http://www.math.uwaterloo.ca/tsp/vlsi/index.html.
[52] A. Dutot and D. Olivier, "5 - Swarm Problem-Solving," in Agent-based Spatial Simulation with NetLogo, Volume 2, A. Banos, C. Lang, and N. Marilleau Eds.: Elsevier, 2017, pp. 117-172.
[53] N. Xiao, "Evolutionary Algorithms," in International Encyclopedia of Human Geography, R. Kitchin and N. Thrift Eds. Oxford: Elsevier, 2009, pp. 660-665.
[54] W. S. Yackinous, "Chapter 4 - Reductionism and Information Loss," in Understanding Complex Ecosystem Dynamics, W. S. Yackinous Ed. Boston: Academic Press, 2015, pp. 65-79.
[55] "Apache Hadoop," 2018. [Online]. Available: https://hadoop.apache.org/.
[56] "Apache Spark," 2018. [Online]. Available: https://spark.apache.org/.