Research On Frequency Assignment Problem Based On Graph Coloring Algorithm

Frequency assignment problem, which belongs to multi-objective combinatorial optimization problems, is a completely non-deterministic polynomial problem. Typically, frequency assignment algorithms include deterministic algorithms, heuristic algorithms, computational intelligence methods and so on. Results of deterministic algorithms for each step can be identified, but the running time cannot be determined; Heuristic algorithm can usually work out answers in a reasonable time, but cannot guarantee efficiency; Computational intelligence methods have the characteristics of self-learning, self-organizing, adaptive and simple, universal, strong robustness, suitable for the advantages of parallel processing. This graph coloring algorithm is one of computational intelligence method.For most frequency assignment algorithms has some deficiencies in aspect of astringency and balance, this paper carries out research on the application of the vertex coloring algorithm and T-colorings coloring algorithm in frequency assignment problem, based on the features of coloring problem in graph theory. Revolved round the essential technologies of frequency assignment, in this paper the main research work is following:(1) Towards the issue of poor astringency, high time complexity and weak local search capability in traditional frequency assignment algorithm, this paper presents a hybrid optimization algorithm based on graph vertex coloring. Firstly, the proposed algorithm initializes the problem with genetic algorithm and colors the vertex by order according to the degree of vertexes, which leads to reduce the randomness of coding implementation in the same space complexity and improve the fairness of the entire system; In order to reduce the roundabout which is generated from algorithm into local optimal, the hybrid optimization algorithm does alternately search on two neighborhood, which improves the convergence speed of the algorithm greatly.(2) For the adjacent frequency interference in frequency assignment problem, this paper proposes a novel optimization algorithm based on T-colorings. The algorithm regards every node in the network as independent and synchronous based on the vertex coloring hybrid optimization algorithm. By distributed parallel execution, the algorithm has effectively improves the algorithm speed. In order to reduce the system cost significantly, a new frequency allocation is completed by making small modify compensation through comparing the original information and present information through instead of regenerate assignment.(3) For some well-known benchmark problems, the results are obtained by the simulation on Microsoft Visual Studio.NET 2013 platform. The experimental results show that the hybrid optimization algorithm based on vertex coloring has good optimization ability and faster convergence speed. With considering the fairness of users, this algorithm can obtained solution accurately which meets the goals of the global optimal. Using the Philadelphia instance conduct simulation test, experimental verify T-colorings optimization algorithm improves the anti-interference ability between signals to a certain extent, and maximizes the value of frequency resources.