旅行推銷員問題與 0-1 背包問題都是著名的離散最佳化問題。旅行推銷員問題欲求旅行推銷員行走各城市的最短路徑。0-1 背包問題求解物品挑選利益最大化。旅行小偷問題將旅行推銷員問題與 0-1 背包問題結合，使得需同時求解路徑排序與物品組合。在旅行推銷員問題與 0-1 背包問題各自的文獻中，常見以啟發式演算法求解。然而，若是以啟發式演算法直接求解旅行小偷問題，將面臨巨大的搜尋空間。因此，我們提出雙族群式的遺傳演算法，分別專注搜尋兩個子問題，以此縮小搜尋空間。每間隔一段時間，兩個族群使用遷移機制進行資訊的交換，達到互相幫助的效果。搜尋單一子問題過程中，好的解碼函式能夠讓個體在另一子問題中獲得更好的基因。因此，我們針對解碼函式中的參數使用自適應控制機制，以提升個體解碼後的品質。本研究詳細探討自適應控制機制的作用與效果，實驗結果證明使用自適應控制機制能夠提升演化搜尋最佳解，並且我們觀察自適應控制的參數演化圖，在不同測試資料中，都能演化收斂在合理的數值。本研究探討雙族群演化方式的作用與效果，實驗證明相較單一族群的演化方式，使用雙族群式遺傳演算法效果更好。我們觀察雙族群遺傳演算法中，兩個族群在演化互助的過程，也確認遷移機制能夠提升雙族群遺傳演算法的演化結果。最後我們所提出之雙族群遺傳演算法相比近年文獻演算法更為優秀，代表雙族群遺傳演算法在近年求解旅行小偷問題的演算法中頗具競爭力。

[1] M. R. Bonyadi, Z. Michalewicz, and L. Barone, “The travelling thief problem: The first step in the transition from theoretical problems to realistic problems,” IEEE Congress on Evolutionary Computation, Cancun, Mexico, pp. 1037–1044 , 2013.
[2] IEEE Congress on Evolutionary Computation 2017 3rd Competition on Optimisation of Problems with Multiple Interdependent Components, url: https://cs.adelaide.edu.au/~optlog/TTP2017Comp/
[3] S. Polyakovskiy, M. R. Bonyadi, M. Wagner, Z. Michalewicz, and F. Neumann, “A comprehensive benchmark set and heuristics for the traveling thief problem,” Genetic and Evolutionary Computation Conference, pp. 477–484, July 2014.
[4] S. Lin, “Computer solutions of the traveling salesman problem,” The Bell System Technical Journal, vol. 44, no. 10, pp. 2245–2269, 1965.
[5] S. Lin and B. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations Research, vol. 21, no 2, pp. 498–516, 1973.
[6] O. Martin, S. W. Otto, and E. W. Felten, “Large-step markov chains for the traveling salesman problem,” Complex Systems, vol. 5, no. 3, pp. 299–326, 1991.
[7] D. Applegate, W. Cook, and A. Rohe, “Chained lin-kernighan for large traveling salesman problems,” INFORMS Journal on Computing, vol. 15, no. 1, pp. 82–92, 2003.
[8] B. C. Gupta and V. P. Prakash, “Greedy heuristics for the travelling thief problem,” National Systems Conference, Greater Noida, India, pp. 1–5, 2015.
[9] H. Faulkner, S. Polyakovskiy, T. Schultz, and M. Wagner, “Approximate approaches to the traveling thief problem,” Genetic and Evolutionary Computation Conference, pp. 385–392, July 2015.
[10] A. Maity and S. Das, “Efficient hybrid local search heuristics for solving the travelling thief problem,” Applied Soft Computing, vol. 93, 2020. url: https://doi.org/10.1016/j.asoc.2020.106284
[11] M. R. Bonyadi, Z. Michalewicz, M. R. Przybylek, and A. Wierzbicki, “Socially inspired algorithms for the travelling thief problem,” Genetic and Evolutionary Computation Conference, pp. 421–428, July 2014.
[12] M. El Yafrani and B. Ahiod, “Cosolver2B: An efficient local search heuristic for the travelling thief problem,” IEEE/ACS 12th International Conference of Computer Systems and Application, Marrakech, Morocco, pp. 1–5, 2015.
[13] B. Delaunay, “Sur la sphère vide,” Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, pp. 793–800, 1934.
[14] M. El Yafrani and B. Ahiod, “Population-based vs. single-solution heuristics for the travelling thief problem,” Genetic and Evolutionary Computation Conference, pp. 317–324, July 2016.
[15] M. El Yafrani and B. Ahiod, “Efficiently solving the traveling thief problem using hill climbing and simulated annealing,” Information Sciences, vol. 432, pp. 231–244, 2018.
[16] R. Nieto-Fuentes, C. Segura, and S. I. Valdez, “A guided local search approach for the travelling thief problem,” IEEE Congress on Evolutionary Computation, Rio de Janeiro, Brazil, pp. 1–8, 2018.
[17] M. El Yafrani and B. Ahiod, “A local search based approach for solving the travelling thief problem: the pros and cons,” Applied Soft Computing, vol. 52, pp. 795–804, March 2017.
[18] Y. Mei, X. Li, and X. Yao, “On investigation of interdependence between sub-problems of the travelling thief problem,” Soft Computing, vol. 20, pp. 157–172, 2016.
[19] S. T Alharbi, “A hybrid genetic algorithm with tabu search for optimization of the traveling thief problem,” International Journal of Advanced Computer Science and Applications, vol. 9, no. 11, pp. 276–287, 2018.
[20] Y. Mei, X. Li, and X. Yao, “Improving efficiency of heuristics for the large scale traveling thief problem,” Simulated Evolution and Learning, pp. 631–643, 2014.
[21] M. Wagner, “Stealing items more efficiently with ants: a swarm intelligence approach to the travelling thief problem,” Swarm Intelligence, ANTS, pp. 273–281, 2016.
[22] T. Stützle and H. H. Hoos, “Max-min ant system,” Future Generation Computer Systems, vol. 16, no. 8, pp. 889–914, June 2020.
[23] D. K. S. Vieira, G. L. Soares, J. A. Vasconcelos, and M. H. S. Mendes, “A genetic algorithm for multi-component optimization problems: the case of the travelling thief problem,” Evolutionary Computation in Combinatorial Optimization, pp. 18–29, 2017.
[24] M. El Yafrani, Yafrani, M. Martins, M. Wagner, B. Ahiod, M. Delgado, and R. Lüders, “A hyperheuristic approach based on low-level heuristics for the travelling thief problem,” Genetic Programming and Evolvable Machines, vol. 19, pp. 121–150, 2018.
[25] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, April 2002.
[26] J. Blank, K. Deb, and S. Mostaghim, “Solving the bi-objective traveling thief problem with multi-objective evolutionary algorithms,” Evolutionary Multi-Criterion Optimization, pp. 46–60, 2017.
[27] M. Laszczyk and P. B. Myszkowski, “A specialized evolutionary approach to the bi-objective travelling thief problem,” Federated Conference on Computer Science and Information Systems, Leipzig, Germany, pp. 47–56, 2019.
[28] J. B. C. Chagas, J. Blank, M. Wagner, M. J. F. Souza, and K. Deb, “A non-dominated sorting based customized random-key genetic algorithm for the bi-objective traveling thief problem,” Journal of Heuristics, pp. 267–301, 2021.
[29] Y. J. Gong, W. N. Chen, Z. H. Zhan, J. Zhang, Y. Li, Q. Zhang, and J. J. Li, “Distributed evolutionary algorithms and their models: A survey of the state-of-the-art,” Applied Soft Computing, vol. 34, pp. 286–300, 2015.
[30] L. Davis, “Applying adaptive algorithms to epistatic domains,” International Joint Conference on Artificial intelligence, vol. 1, pp. 162–164, August 1985.
[31] J. Brest, S. Greiner, B. Boskovic, M. Mernik, and V. Zumer, “Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems,” IEEE Transactions on Evolutionary Computation, vol. 10, no. 6, pp. 646–657, 2006.
[32] Chained Lin–Kernighan heuristic (CLKH) algorithm source code, url: http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm
[33] MATLS source code, url: https://homepages.ecs.vuw.ac.nz/~yimei/Research-LSGO.html
[34] CS2SA source code, url: https://github.com/yafrani/ttplab