Afrequency Assignment Approach Based On Selective Mutation Technique

The frequency assignment is a class of NP-complete problems.Conventionally, this kind of problem could be solved by enumeration.However, the computational cost of enumeration exponentially increases as the order of the problem goes up.In the literatures,there are basically three classes of algorithms to solve this problem: exact algorithm, heuristic algorithm and computation intellective algorithm.The frequency assignment approach based on selective mutation technique and selective mutation frequency assignment approach based on shuffled frog-leaping algorithm belong to the class of computation intellective algorithm,are employed in this thesis.First of all, the frequency assignment technology and several commonly used methods to solve the frequency assignment problem are introduced, the frequency assignment approach based on selective mutation technique was proposed. Through dynamic changes in the iterative process to satisfy the constraints required to achieve the rapid optimization of the frequency assignment. Using frequency assignment approach based on selective mutation technique for solving a frequency assignment problem of a GSM system to illustrate how to set parameters of the frequency assignment approach based on selective mutation technique, The frequency assignment approach based on selective mutation technique and shuffled frog-leaping algorithm will be combined to form a selective mutation frequency assignment approach based on shuffled frog-leaping algorithm. The improved selective mutation technique can make sure the algorithm take good advantage of the mutation to search the global minimum and enhance the convergence rate. The proposed algorithm was simulated by solving frequency assignment problem of eight GSM systems. Simulation results indicate that, compared with simulated annealing, micro canonical annealing algorithm and genetic algorithm, the proposed algorithm has more powerful search capability in frequency assignment.