基因演算法結合二階段最佳化演算法解決集合涵蓋問題之研究

Genetic Algorithms Enhanced with Two-Phase Optimization Algorithm for Set Covering Problem

張書維(Shu-Wei Chang)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2004年)

摘要

最佳化問題中有一廣為周知的問題為集合涵蓋問題(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.

並列關鍵字

Genetic algorithm ； Hybrid algorithm ； Set covering problem ； Two-phase optimization algorithm