Abstract: |
In this paper, we describe an efficient Genetic Algorithm (GA) for solving the minimum interference frequency assignment problem (MI-FAP) using a new problem representation. The GA we present looks for the best assignment of a limited number of frequencies to a set of stations minimizing the total disturbance caused by stations operating at the same frequencies. We show that our problem representation based on permutation encoding and clustering gives better results in comparison with the existing problem representations in the literature. Our problem representation reduces the search space from f^n to (f!)^(n/f) and improves the time complexity of the fitness function from O(n^2) to O(n^2/f) where f is the number of frequencies and n is the number of stations. We compare the performance of our algorithm with the algorithms using other problem representations and confirm our results on a real-world problem. |
