| dc.description.abstract | 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. | en_US |