最佳化問題中有一廣為周知的問題為集合涵蓋問題(SCP)，因其可作為許多資源選擇問題的模型，因此在現實生活中有許多重要的應用。由於集合涵蓋問題為一NP-hard問題，而基因演算法也常被使用來求解此類問題，且可獲得不錯的結果。本論文設計一混合式基因演算法(TGA)，其結合二階段最佳化演算法（TPOA）與基因演算法（GA）來求解集合涵蓋問題。TGA使用TPOA來產生GA之初始族群，能夠盡可能產生一些好的基因於族群中，並保證其在族群中有一定的數量，以提高這些好的基因在早期於族群中之存活率，期望這些好的基因能夠提供GA快速的收斂，以及提高尋找最佳解的機會。由實驗結果顯示，TGA可較使用亂數產生族群之Beasly和Chu所提出的GA (BeCh GA)能在短時間內得到較佳的解，而在長時間中兩者則是差不多的。因此TGA提供一增加GA初始族群之多變性與強化性之系統化架構，可以有效的讓GA在短時間內獲得一近似最佳解，而不減少GA尋找最佳解的機會。

Set covering problem (SCP) is a well-known combinatorial optimization problem. SCP has widely been used to model the resource selection problem and adopted in many real-life applications. Since it is NP-hard, much effort has been spent on designing good genetic algorithms(GA) for this problem. In this thesis, we design a hybrid GA, TPOA-GA (TGA), which combines GA and Two-Phase Optimization Algorithm (TPOA) to solve SCP. TGA relies on TPOA to generate the initial population so that TGA can get some prime genes within the population. It keeps an enough quantity of the prime genes in the population in order to increase their survival probabilities in earlier generations. The prime genes generated by TPOA can not only cause GA to rapidly converge, but also help to increase the probability of finding the optimal solution. Using the benchmarks from “OR-Library”, the experiment results show that TGA can get better solutions than BeCh GA proposed by Beasly and Chu in a short time. However, in a long time, both results are close to each other. Obviously, TGA provides a framework to increase the diversification and intensification of the initial population that can help to obtain a near-optimal solution in a short time and doesn’t decrease the probability to obtain the optimal solution.

[1] E. Balas and A. Ho, “Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study,” Mathematical Programming, 12 (1980) 37-60.
[2] E. Balas, “A class of location, distribution and scheduling problems: modeling and solution methods,” in P. Gray and L. Yuanzhang (eds.), Proceedings of the Chinese-U.S. Symposium on Systems Analysis, J. Wiley and Sons (1983).
[3] E. Balas and M.C. Carrera, “A dynamic subgradient-based branch-and-bound procedure for set covering,” Operations Research 44 (1996) 875-890.
[4] J. E. Beasley, “An algorithm for set covering problems,” European Journal of Operational Research 31 (1987) 85-93.
[5] J. E. Beasley, “A lagrangian heuristic for set covering problems,” Naval Research Logistics 39 (1990) 151-164.
[6] J. E. Beasley, “OR-Library: distributing test problems by electronic mail,” Journal of the Operational Research Society 41 (1990) 1069-1072.
[7] J. E. Beasley and K. Jrnsten, “Enhancing an algorithm for set covering problems,” European Journal of Operational Research 58 (1992) 293-300.
[8] J. E. Beasley and P.C. Chu, “A genetic algorithm for the set covering problem,” European Journal of Operational Research 94 (1996) 392-404.
[9] P. Beraldi and A. Ruszczyński, “The probabilistic set-covering problem,” Operations Research 2002 INFORMS 50 (2002) 956-967.
[10] M. J. Brusco, L. W. Jacobs and G. M. Thompson, “A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems,” Annals of Operations Research 86 (1999) 611-627.
[11] A. Caprara, M. Fischetti and P. Toth, “A heuristic method for the set covering problem,” Operations Research 47 (1999) 730-743.
[12] A. Caprara, P. Toth, M and Fichetti, “Algorithms for the set covering problem,” Annals of Operations Research 98 (2000) 353-371.
[13] S. Ceria, P. Nobili and A. Sassano, “A lagrangian based heuristic for large scale set-covering problems,” Mathematical Programming 81 (1998) 215-228.
[14] S. T. Chen, S. S. Lin and L. T. Huang, “TPOA: A two-phase optimization algorithm for hard-combinatorial problems,” Fifteenth Australasian Workshop on Combinatorial Algorithm (2004) 248-259.
[15] M. L. Fisher, “The lagrangian relaxation method for solving integer programming problems,” Management Science 27 (1981) 1-18.
[16] M. L. Fisher and P. Kedia, “Optimal solution of set covering/partitioning problems using dual heuristics,” Management Science 36 (1990) 674-688.
[17] M. Held and R. Karp, “The traveling salesman problem and minimum spanning trees,” Operations Research 18 (1970) 1138-1162.
[18] J. H. Holland, “Adaptation in natural and artificial systems,” University of Michigan Press (1975).
[19] T. K. Jenssen and S. A. Vinterbo, “A set-covering approach to specific search for literature about human genes,” Proceedings AMIA Symposium, October (2000) 384-8.
[20] L. A. N. Lorena and F. B. Lopes, “A surrogate heuristic for set covering problems,” European Journal of Operational Research 79 (1994)138-50.
[21] E. Marchiori and A. Steenbeek, “An evolutionary algorithm for large scale set covering problems with application to airline crew scheduling,” EvoWorkshops (2000) 367-381.
[22] T. A. Moreira and Y. Kohayakawa, “Bounds for optimal coverings,” Discrete Applied Mathematics 141 (2004) 263-276.
[23] K. Prasanna and D. Khemani, “Applying set covering problem in instance set reduction for machine learning algorithms,” WSEAS Transactions on Computers 3 (2004) 661-666.
[24] D. Wedelin, “An algorithm for large scale 0-1 integer optimization,” Annals of Operations Research 57 (1995) 283-301.
[25] F. Wen and C. S. Chang, “A tabu search approach to fault section estimation in power systems,” Electric Power Systems Research 40 (1997) 63-73.
[26] 鍾金城，”最佳化設計多重位置型聚合鏈反應引子組”，國立臺灣大學資訊工程學研究所碩士論文，2003。
[27] 張育彰，”應用基因演算法於台鐵列車駕駛員排班與輪班整合問題之研究”，國立成功大學交通管理研究所碩士論文，2003。
[28] 詹佳叡，”應用群聚技術求解P中位問題”，大葉大學工業工程研究所碩士論文，2003。
[29] 官長輝，”基因演算法於國道客運最適車數及排程之整合研究”，輔仁大學管理學研究所碩士論文，2003。
[30] 劉東育，”解單純設施位址問題之基因區域搜尋法”，國立中興大學資訊科學研究所碩士論文，2003。
[31] http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html.