基于遗传禁忌搜索的时隙分配算法

合理的时隙分配可保证数据链战术消息的时效性,提升数据链网络运行效率。现有单一优化的时隙分配算法全局寻优能力低、运算量大、运行效率低。本文基于最小均匀时隙方差模型,提出了一种遗传禁忌搜索的时隙分配算法。该算法充分利用遗传和禁忌搜索两种典型智能优化算法的优势,采用遗传变异操作构造多样性的邻域,使获得全局最优时隙解的概率增强;使用禁忌搜索算法在局部进行搜索,加快收敛速度。采用精度提升率、稳定性和时间开销等指标对算法的精度、稳定性和运行效率进行了验证,结果表明:算法相比单一的遗传和禁忌算法,在保持较高稳定性和运行效率的同时,时隙分配精度有明显提升。当空闲时隙数量为500和1000时,相对遗传时隙分配算法,精度分别提升了6%和9%。

Slot allocation algorithm based on genetic and tabu search

Slot allocation is a key technology in TDMA data link network planning. Reasonable time slot allocation can ensure the timeliness of tactical messages and improve the operation efficiency of data link network. Because the traditional slot allocation algorithm can not realize the allocation of any slot; The single intelligent optimization slot allocation algorithm has the problems of low global optimization ability, large amount of computation and low operation efficiency. Based on the minimum uniform slot variance model, a slot allocation algorithm based on genetic tabu search is proposed in this paper. The algorithm makes full use of the advantages of two typical intelligent optimization algorithms: genetic and tabu search, and uses genetic mutation operation to construct diverse neighborhoods, so as to enhance the probability of obtaining the global optimal slot solution; Tabu search algorithm is used to search locally to speed up the convergence speed. The accuracy, stability and efficiency of the proposed algorithm are evaluated by experiments. The results show that compared with the single genetic algorithm and tabu algorithm, the algorithm not only maintains high stability and operation efficiency, but also significantly improves the time slot allocation accuracy. When the number of free slots is 500 and 1000, the accuracy is improved by 6% and 9% respectively compared with the genetic slot allocation algorithm.