基于改进的遗传算法无线通信网频率指配问题研究

刘田间　高小玲

摘 要： 通过对无线通信频率指配问题的分析，结合遗传算法在频率指配领域的应用，提出了一种启发式的指配方法。该方法通过改进选择方式，自适应地调整交叉、变异概率来指配信道分配。仿真分析证明，该算法科学可行，有效地避免陷入局优解，加快了种群进化速度，减少了迭代次数，较快收敛到最优解。

关键词： 遗传算法； 无线通信网； 频率指配； 信道分配

中图分类号： TN92?34 文献标识码： A 文章编号： 1004?373X（2014）17?0029?03

Abstract： In combination with the application of genetic algorithm in the field of frequency assignments， a heuristic frequency assignment method is proposed in this paper based on the analysis of frequency assignment link in wireless communication. It can assign the channel allocation by modifying the selection mode， and adjusting the crossover and mutation probability adaptively. The simulation results show that this method is scientific and practicable， can prevent local optimization effectively， accelerate the population evolution， reduce the number of iterations， and converge to the optimal solution quickly.

Keywords： genetic algorithm； wireless communication network； frequency assignment； channel allocation

0 引 言

在无线通信网络中，可利用的频谱资源是十分有限的。随着经济、科技和军事的发展，大量的无线通信设备将投入使用，必将造成频谱资源拥挤，频率使用效率低下。为了有效解决此类问题，避免用频设备的自扰和互扰，频率指配技术是近年来得到快速发展的一种软策略。近几十年来，一些通过模拟自然生态系统机制的智能优化算法广泛应用于频率指配问题。如模拟退火算法[1]、禁忌搜索法[2]、遗传算法[3]等。这些传统的算法在实际求解中仍不能满足要求。本文旨在通过对遗传算法的改进，为频率指配问题提供切实可行的解决方案。有效地避免陷入局优解，加快种群进化速度，提高算法的整体性能。

1 频率指配数学模型

1.1 频率指配问题描述

频率指配是在电波传播预测基础上，对电磁信号的分布进行计算，分析各通信设备之间可能存在的电磁干扰。可以归结为满足约束条件的频率指配最佳方案的搜索，此处的最佳含义是指无违约或违约数最少意义上的最佳频率指配。简单地讲，频率指配问题可以归纳为在满足约束条件下，寻找使得通信容量最大且总干扰代价最小的频率指配方案。

由图1可以看出，改进后的算法在100代适应度函数值趋近于1，即收敛于最佳适应度值。而传统算法在150代才趋近于最佳适应度值。收敛速度提高了近33.3%，同时减少了迭代次数使其较快达到全局最优，和理论分析结果基本一致。

3 结 语

遗传算法用在无线通信网频率指配研究中是一个很好的案例。本文通过对遗传算法的理解，研究了遗传算子对算法性能的影响，提出了一种新的方法来代替传统的轮盘赌法选择算子，自适应地调整交叉和变异算子使算法较快的收敛到最优解。但在实际应用中还没有进行有效的定量分析，这是下一步要重点研究的内容。

参考文献

[1] LU Li?wei， FAN Rong?shuang. Simulated annealing algorithm in solving frequency assignment proble [C]// 2010 3rd International Conference on Advanced Computer Theory and Enginee?ring. Chengdu， China： IEEE， 2010， 1： 361?364.

[2] CASTELINO D J， HURLEY S， STEPHENS N M. A tabu search algorithm for frequency assignment [J]. Annals of Operations Research， 1996， 63（2）： 301?319.

[3] ALABAU M， IDOUMGHAR L， SCHOTT R. New hybrid gene?tic algorithms for the frequency assignment problem [J]. IEEE Transactions on Broadcasting， 2002， 48（1）： 27?34.

[4] 陈浩.遗传算法在频率指配问题中的应用研究[D].北京：北京交通大学，2009.

[5] 陈有青，徐蔡星，钟文亮，等.一种改进选择算子的遗传算法[J].计算机工程与应用，2008，44（2）：44?49.

[6] DE JONG K A. Analysis of the behavior of a class of genetic adaptive systems [R]. USA： University of Michigan， 1975.

[7] 崔珊珊.遗传算法的一些改进及应用[D].合肥：中国科学技术大学，2010.

摘 要： 通过对无线通信频率指配问题的分析，结合遗传算法在频率指配领域的应用，提出了一种启发式的指配方法。该方法通过改进选择方式，自适应地调整交叉、变异概率来指配信道分配。仿真分析证明，该算法科学可行，有效地避免陷入局优解，加快了种群进化速度，减少了迭代次数，较快收敛到最优解。

关键词： 遗传算法； 无线通信网； 频率指配； 信道分配

中图分类号： TN92?34 文献标识码： A 文章编号： 1004?373X（2014）17?0029?03

Abstract： In combination with the application of genetic algorithm in the field of frequency assignments， a heuristic frequency assignment method is proposed in this paper based on the analysis of frequency assignment link in wireless communication. It can assign the channel allocation by modifying the selection mode， and adjusting the crossover and mutation probability adaptively. The simulation results show that this method is scientific and practicable， can prevent local optimization effectively， accelerate the population evolution， reduce the number of iterations， and converge to the optimal solution quickly.

Keywords： genetic algorithm； wireless communication network； frequency assignment； channel allocation

0 引 言

在无线通信网络中，可利用的频谱资源是十分有限的。随着经济、科技和军事的发展，大量的无线通信设备将投入使用，必将造成频谱资源拥挤，频率使用效率低下。为了有效解决此类问题，避免用频设备的自扰和互扰，频率指配技术是近年来得到快速发展的一种软策略。近几十年来，一些通过模拟自然生态系统机制的智能优化算法广泛应用于频率指配问题。如模拟退火算法[1]、禁忌搜索法[2]、遗传算法[3]等。这些传统的算法在实际求解中仍不能满足要求。本文旨在通过对遗传算法的改进，为频率指配问题提供切实可行的解决方案。有效地避免陷入局优解，加快种群进化速度，提高算法的整体性能。

1 频率指配数学模型

1.1 频率指配问题描述

频率指配是在电波传播预测基础上，对电磁信号的分布进行计算，分析各通信设备之间可能存在的电磁干扰。可以归结为满足约束条件的频率指配最佳方案的搜索，此处的最佳含义是指无违约或违约数最少意义上的最佳频率指配。简单地讲，频率指配问题可以归纳为在满足约束条件下，寻找使得通信容量最大且总干扰代价最小的频率指配方案。

由图1可以看出，改进后的算法在100代适应度函数值趋近于1，即收敛于最佳适应度值。而传统算法在150代才趋近于最佳适应度值。收敛速度提高了近33.3%，同时减少了迭代次数使其较快达到全局最优，和理论分析结果基本一致。

3 结 语

遗传算法用在无线通信网频率指配研究中是一个很好的案例。本文通过对遗传算法的理解，研究了遗传算子对算法性能的影响，提出了一种新的方法来代替传统的轮盘赌法选择算子，自适应地调整交叉和变异算子使算法较快的收敛到最优解。但在实际应用中还没有进行有效的定量分析，这是下一步要重点研究的内容。

参考文献

[1] LU Li?wei， FAN Rong?shuang. Simulated annealing algorithm in solving frequency assignment proble [C]// 2010 3rd International Conference on Advanced Computer Theory and Enginee?ring. Chengdu， China： IEEE， 2010， 1： 361?364.

[2] CASTELINO D J， HURLEY S， STEPHENS N M. A tabu search algorithm for frequency assignment [J]. Annals of Operations Research， 1996， 63（2）： 301?319.

[3] ALABAU M， IDOUMGHAR L， SCHOTT R. New hybrid gene?tic algorithms for the frequency assignment problem [J]. IEEE Transactions on Broadcasting， 2002， 48（1）： 27?34.

[4] 陈浩.遗传算法在频率指配问题中的应用研究[D].北京：北京交通大学，2009.

[5] 陈有青，徐蔡星，钟文亮，等.一种改进选择算子的遗传算法[J].计算机工程与应用，2008，44（2）：44?49.

[6] DE JONG K A. Analysis of the behavior of a class of genetic adaptive systems [R]. USA： University of Michigan， 1975.

[7] 崔珊珊.遗传算法的一些改进及应用[D].合肥：中国科学技术大学，2010.

摘 要： 通过对无线通信频率指配问题的分析，结合遗传算法在频率指配领域的应用，提出了一种启发式的指配方法。该方法通过改进选择方式，自适应地调整交叉、变异概率来指配信道分配。仿真分析证明，该算法科学可行，有效地避免陷入局优解，加快了种群进化速度，减少了迭代次数，较快收敛到最优解。

关键词： 遗传算法； 无线通信网； 频率指配； 信道分配

中图分类号： TN92?34 文献标识码： A 文章编号： 1004?373X（2014）17?0029?03

Abstract： In combination with the application of genetic algorithm in the field of frequency assignments， a heuristic frequency assignment method is proposed in this paper based on the analysis of frequency assignment link in wireless communication. It can assign the channel allocation by modifying the selection mode， and adjusting the crossover and mutation probability adaptively. The simulation results show that this method is scientific and practicable， can prevent local optimization effectively， accelerate the population evolution， reduce the number of iterations， and converge to the optimal solution quickly.

Keywords： genetic algorithm； wireless communication network； frequency assignment； channel allocation

0 引 言

在无线通信网络中，可利用的频谱资源是十分有限的。随着经济、科技和军事的发展，大量的无线通信设备将投入使用，必将造成频谱资源拥挤，频率使用效率低下。为了有效解决此类问题，避免用频设备的自扰和互扰，频率指配技术是近年来得到快速发展的一种软策略。近几十年来，一些通过模拟自然生态系统机制的智能优化算法广泛应用于频率指配问题。如模拟退火算法[1]、禁忌搜索法[2]、遗传算法[3]等。这些传统的算法在实际求解中仍不能满足要求。本文旨在通过对遗传算法的改进，为频率指配问题提供切实可行的解决方案。有效地避免陷入局优解，加快种群进化速度，提高算法的整体性能。

1 频率指配数学模型

1.1 频率指配问题描述

频率指配是在电波传播预测基础上，对电磁信号的分布进行计算，分析各通信设备之间可能存在的电磁干扰。可以归结为满足约束条件的频率指配最佳方案的搜索，此处的最佳含义是指无违约或违约数最少意义上的最佳频率指配。简单地讲，频率指配问题可以归纳为在满足约束条件下，寻找使得通信容量最大且总干扰代价最小的频率指配方案。

由图1可以看出，改进后的算法在100代适应度函数值趋近于1，即收敛于最佳适应度值。而传统算法在150代才趋近于最佳适应度值。收敛速度提高了近33.3%，同时减少了迭代次数使其较快达到全局最优，和理论分析结果基本一致。

3 结 语

遗传算法用在无线通信网频率指配研究中是一个很好的案例。本文通过对遗传算法的理解，研究了遗传算子对算法性能的影响，提出了一种新的方法来代替传统的轮盘赌法选择算子，自适应地调整交叉和变异算子使算法较快的收敛到最优解。但在实际应用中还没有进行有效的定量分析，这是下一步要重点研究的内容。

参考文献

[1] LU Li?wei， FAN Rong?shuang. Simulated annealing algorithm in solving frequency assignment proble [C]// 2010 3rd International Conference on Advanced Computer Theory and Enginee?ring. Chengdu， China： IEEE， 2010， 1： 361?364.

[2] CASTELINO D J， HURLEY S， STEPHENS N M. A tabu search algorithm for frequency assignment [J]. Annals of Operations Research， 1996， 63（2）： 301?319.

[3] ALABAU M， IDOUMGHAR L， SCHOTT R. New hybrid gene?tic algorithms for the frequency assignment problem [J]. IEEE Transactions on Broadcasting， 2002， 48（1）： 27?34.

[4] 陈浩.遗传算法在频率指配问题中的应用研究[D].北京：北京交通大学，2009.

[5] 陈有青，徐蔡星，钟文亮，等.一种改进选择算子的遗传算法[J].计算机工程与应用，2008，44（2）：44?49.

[6] DE JONG K A. Analysis of the behavior of a class of genetic adaptive systems [R]. USA： University of Michigan， 1975.

[7] 崔珊珊.遗传算法的一些改进及应用[D].合肥：中国科学技术大学，2010.