| 摘要: | 本研究係針對運用在分群問題上之基因演算法，提出一種以關係為導向之編碼方式，並修改傳統基因運算，以符合此編碼結構，稱為關係基因演算法(Relational Genetic Algorithm, RGA)。由等價關係延伸而來的關係編碼，其編碼為一矩陣結構，將其運用在分群問題上，可以適當描述問題結構，不會產生任何重覆性，藉此提升演算法的效能。在基因運算之設計上，RGA可不依賴問題本身的經驗法則，即可達到良好的效能。 分群問題，為一NP-hard問題，如果使用一般的線性搜尋的話，很難找出最佳解。因此需要使用「基因演算法」這種人工智慧的方法，來進行全域搜尋，以逼近最佳解。 現行運用在分群問題上的基因演算法，可分為三種：群號編碼( Group-number Encoding )、排列編碼( Permutation Encoding )以及分群基因演算法( Grouping Genetic Algorithms, GGA )。前兩種屬於比較傳統的編碼方式，由於編碼會產生高度重覆性，減低演算法的效能，因此，本研究的實驗主要以GGA為比較的對象，在不使用經驗法則( Heuristic )的情形下，實驗結果為RGA的效能顯著優於GGA。同時，在使用類似的經驗法則時，RGA仍可擊敗GGA。由此可知，RGA具有較良好的演算法結構與效能。 In this paper, we focus on the genetic algorithms for partitioning problems and purpose a new type of genetic algorithms called Relational Genetic Algorithm (RGA) including a new encoding called Relational Encoding and suitable genetic operators. Relational encoding is extended from equivalence relation and its structure is a matrix. It can suitably describe the structure of partitioning problems and the search space of genetic algorithms can be reduced. Therefore, this encoding can improve the efficiency of the genetic algorithm. At the same time, the operations of relational genetic algorithm does’nt have to depend on the heuristics for the specific problems. The partitioning problems are NP-hard problems. If we use normally linear search to solve these problems, it is hard to optimize the solutions. Thus, we use artificial intelligent methods to search globally and try to find the optimal solution. In the previous researches, there are three types of genetic algorithms for partitioning problems, and they are group-number encoding, permutation encoding, and grouping genetic algorithms (GGA). The first one and the second one belong to traditional encoding, so these encodings have high redundancy and would reduce the efficiency of the algorithms. Therefore, in this paper, our experiments are to compare our proposed algorithm, RGA, with GGA. Using random repair, the results of the experiments show that the performance of RGA is outstandingly better than that of GGA. Besides, using similar heuristics, RGA is also greater than GGA. These results prove that RGA is really a better genetic algorithm for the partitioning problems. |
