论文部分内容阅读
摘要：频率优化是GSM网络优化的重要内容，可以有效地降低干扰，保障网络服务质量。传统的频率优化采用单目标算法，将同频干扰、邻频干扰作为干扰的衡量指标，用目标组合函数将同邻频干扰组合成单个目标。然而，简单的线性组合难以反映同邻频干扰不同的重要性，且实际网络中，还需要考虑具有同频或邻频的小区的地理位置关系、方向角关系等。因此本文将多目标遗传算法MOGA应用于GSM网络的频率优化，采用二维分配矩阵的基因编码方式，并将对打度纳入到频率优化的目标中，以极小化同频干扰、邻频干扰和对打度作为三个优化子目标。通过在交叉算子中以个体的几何距离决定交叉地配对，在变异算子中动态地调整变异概率等方式，增大差异后代产生得概率，防止算法陷入局部极大极小解。使用共享适应度值的小生境技术及自适应网格法维持种群在解空间的均匀分布及解集多样性。并采用层次分析法，从Pareto最优解集中，选择偏好最优解。运用大规模现网数据实验结果证明，该算法能在较快时间内，得到符合偏好、满足多个优化目标的频率优化方案。上述工作说明，在实际网络频率优化工作中，基于多目标遗传算法的频率优化算法能够合理地反映多种频率优化目标，快速得到有效解，具有很好的应用价值。
关键词：GSM网络；频率优化；多目标遗传算法；频率干扰；对打度
中图分类号：TP18
文献标识码：A
0 引言
通话质量是GSM网络服务质量的重要衡量标准。影响通话质量的因素主要来源于网络覆盖不足或网络覆盖完全的情况下无线信号干扰的存在，而无线信号干扰分为网间干扰和网内干扰两种。本论文主要针对GSM网络的内部干扰。
由于频谱资源的有限，随着移动通信网络的高速发展，越来越多的移动小区共享着有限的频谱资源，造成高度的频率资源复用。在GSM网络中，主要体现为频点的复用。由于频点复用、小区同邻频导致的内部干扰是影响通话质量的关键因素，因此对GSM网络频率资源优化配置进行研究有非常重要的意义。
传统的GSM网络频率优化一般依赖手工配频，而手工配频较大程度地依赖网络优化工作人员的经验，并且依靠人力很难将影响网络质量的各方面的因素考虑全面，网络优化效果有限。近年来，模拟退火算法SA（Simulated Annealing）、粒子群优化算法PSO（Particle Swarm Optimization）、遗传算法GA等智能优化算法被引入到网络优化领域。智能优化算法地引入在一定程度上优化了移动通信网络的频率资源配置，达到了较理想的网络优化目标。但这些算法运用在网络优化领域时均通过一定的方式将实际网络优化中的多种优化目标组合成单个的优化目标，而不同优化目标可能具有不同的量纲，因此存在着一定的局限性。在实际网络优化中，为了更好的模拟复杂的GSM网络环境，达到多个网络优化目标的均衡，需要更复杂更智能的多目标优化算法。
遗传算法具有对NP完全问题良好的寻优求解能力，能在一定的时间限制内，寻找到较理想的NP完全问题解决方案，同时还可以处理多目标优化问题。GSM网络频率资源优化配置问题是一个NP完全问题，并且具有多种优化目标需求，如全网同频干扰极小化、全网邻频干扰极小化、同邻频小区尽可能避免对打、各频点复用度尽可能均衡等。本论文采用了多目标遗传算法MOGA解决GSM网络频率优化问题。
2.5交叉算子
交叉算子是遗传算法中的关键步骤，主要用于产生下一代差异个体。
本文为增大下一代差异个体的产生概率，采用引入个体几何距离的改进的两点交叉法。选择当前待交叉个体集中，几何距离最大的两个个体A和B，随机生成交叉起始点i，j，交换个体A和B的min（i，j）到max（i，j）行。其中个体间几何距离即两个个体二维向量编码中的编码不同的个数。
2.6变异算子
变异算子同样用于产生下一代进化个体，在解空间内搜索可能的最优解，并加快算法的收敛速度。
本文为使避免算法陷入局部最优解，采用动态调整变异区间的变异算子。
1.按照变异概率pm生成待变异个体Indiv。依据Indiv中已分配的频点所产生的目标向量Obj三个子目标上的增量评估所以已分配频点，选择被支配度最大的k个点作为待变异点集，在待变异点集中，随机选取待变异点frea。
2.选择评估变异点frea后，根据frea点所在小区的其他未分配的点若分配所带来的目标向量Obj上的增量，选择支配度最大的p个点作为待变异点集，在其中随机选取变异点freb。待变异点选择区间长度p随着进化代数地增加而增大。
3.将freb频点分配给变异个体，收回frea频点。
2.7优胜集生成
算法MOGA的收敛过程，就是通过在每一个进化时构造当前进化群体的非支配集，并通过最优个体保留机制，使每一代所构造的非支配集一步步逼近Pareto最优边界。本文采用结合排除法与自适应网格法的优胜集构造算法（见表1）。
2.8最优解地选择
从优胜集中选择符合偏好的最优解时，需要按照实际工程中全网同频干扰极小化、全网邻频干扰极小化、同邻频小区间对打度极小化三个子目标对网络服务质量影响的重要程度来选择。然而由于对打度与同邻频干扰属于不同的量纲，选用的方法需要可以评价不同量纲的目标。层次分析法AHP（Analytic Hierarchy Process）是一种定性分析与定量分析相结合的多准则决策方法，因此选择层次分析法来选择偏好最优解。
按照层次分析法，对解集中个体的三个子目标按照重要性等级两两比较构造判断矩阵，验证判断矩阵的一致性，并得到目标的重要性排序。根据重要性与三个子目标的加权值为优胜集中的个体评分，得到评分最高的个体作为最优解。
MOGA解个体的三个子目标的判断矩矩阵及重要性结果见表2。
3 应用案例
利用南方某省会城市某运营商GSM网络实际数据验证基于MOGA的多目标遗传算法性能。
所需数据包括基站和小区的工参，MR测量报告、小区间干扰数据和全网可用频点范围等信息。网络规模为1971个基站，6310个扇区，共36739个频点需求。TCH可用频点为：1-56，81-95，BCCH可用频点为：57-80。
案例中小区频点的初始化分配完成后，Pareto优胜集的展示如图4（a）。Pareto优胜集中的解在解空间中分布均匀。
随着进化的进程，优胜集内个体在目标向量Obj的同频干扰、邻频干扰、对打度三个维度上的平均值的收敛如图5。优胜集内解个体目标向量各维度的均值随着进化的过程而逐渐下降，最终稳定在一个较理想的水平。种群进化到60代左右时目标向量值收敛到较优水平，收敛速度较快。
进化结束后，Paret优胜集中解个体展示如图4（b）。与进化前Pareto优胜集内个体图4a对比，个体在解空间内分布性维持较好。解个体基本覆盖到了解空间的Pareto前端。
对优胜集中个体采用层次分析法得到个体的部分AHP评估值如表3，最终优胜的解个体的目标向量值为[0，0.0484，0.48625]。
4 结论
本文将多目标遗传算法应用于GSM网络频率资源优化配置问题。该算法在现网环境下的应用证明，该算法具有较好的收敛性与寻优能力，可以较快的得到符合偏好的GSM网络频率优化配置方案，具有实用价值。在本文提出的算法中，由于利用Pareto排序来进行频点预分配与变异，增加了计算的复杂度。如何提高预分配与变异效率以进一步提高算法性能是将来要研究的问题。
关键词：GSM网络；频率优化；多目标遗传算法；频率干扰；对打度
中图分类号：TP18
文献标识码：A
0 引言
通话质量是GSM网络服务质量的重要衡量标准。影响通话质量的因素主要来源于网络覆盖不足或网络覆盖完全的情况下无线信号干扰的存在，而无线信号干扰分为网间干扰和网内干扰两种。本论文主要针对GSM网络的内部干扰。
由于频谱资源的有限，随着移动通信网络的高速发展，越来越多的移动小区共享着有限的频谱资源，造成高度的频率资源复用。在GSM网络中，主要体现为频点的复用。由于频点复用、小区同邻频导致的内部干扰是影响通话质量的关键因素，因此对GSM网络频率资源优化配置进行研究有非常重要的意义。
传统的GSM网络频率优化一般依赖手工配频，而手工配频较大程度地依赖网络优化工作人员的经验，并且依靠人力很难将影响网络质量的各方面的因素考虑全面，网络优化效果有限。近年来，模拟退火算法SA（Simulated Annealing）、粒子群优化算法PSO（Particle Swarm Optimization）、遗传算法GA等智能优化算法被引入到网络优化领域。智能优化算法地引入在一定程度上优化了移动通信网络的频率资源配置，达到了较理想的网络优化目标。但这些算法运用在网络优化领域时均通过一定的方式将实际网络优化中的多种优化目标组合成单个的优化目标，而不同优化目标可能具有不同的量纲，因此存在着一定的局限性。在实际网络优化中，为了更好的模拟复杂的GSM网络环境，达到多个网络优化目标的均衡，需要更复杂更智能的多目标优化算法。
遗传算法具有对NP完全问题良好的寻优求解能力，能在一定的时间限制内，寻找到较理想的NP完全问题解决方案，同时还可以处理多目标优化问题。GSM网络频率资源优化配置问题是一个NP完全问题，并且具有多种优化目标需求，如全网同频干扰极小化、全网邻频干扰极小化、同邻频小区尽可能避免对打、各频点复用度尽可能均衡等。本论文采用了多目标遗传算法MOGA解决GSM网络频率优化问题。
2.5交叉算子
交叉算子是遗传算法中的关键步骤，主要用于产生下一代差异个体。
本文为增大下一代差异个体的产生概率，采用引入个体几何距离的改进的两点交叉法。选择当前待交叉个体集中，几何距离最大的两个个体A和B，随机生成交叉起始点i，j，交换个体A和B的min（i，j）到max（i，j）行。其中个体间几何距离即两个个体二维向量编码中的编码不同的个数。
2.6变异算子
变异算子同样用于产生下一代进化个体，在解空间内搜索可能的最优解，并加快算法的收敛速度。
本文为使避免算法陷入局部最优解，采用动态调整变异区间的变异算子。
1.按照变异概率pm生成待变异个体Indiv。依据Indiv中已分配的频点所产生的目标向量Obj三个子目标上的增量评估所以已分配频点，选择被支配度最大的k个点作为待变异点集，在待变异点集中，随机选取待变异点frea。
2.选择评估变异点frea后，根据frea点所在小区的其他未分配的点若分配所带来的目标向量Obj上的增量，选择支配度最大的p个点作为待变异点集，在其中随机选取变异点freb。待变异点选择区间长度p随着进化代数地增加而增大。
3.将freb频点分配给变异个体，收回frea频点。
2.7优胜集生成
算法MOGA的收敛过程，就是通过在每一个进化时构造当前进化群体的非支配集，并通过最优个体保留机制，使每一代所构造的非支配集一步步逼近Pareto最优边界。本文采用结合排除法与自适应网格法的优胜集构造算法（见表1）。
2.8最优解地选择
从优胜集中选择符合偏好的最优解时，需要按照实际工程中全网同频干扰极小化、全网邻频干扰极小化、同邻频小区间对打度极小化三个子目标对网络服务质量影响的重要程度来选择。然而由于对打度与同邻频干扰属于不同的量纲，选用的方法需要可以评价不同量纲的目标。层次分析法AHP（Analytic Hierarchy Process）是一种定性分析与定量分析相结合的多准则决策方法，因此选择层次分析法来选择偏好最优解。
按照层次分析法，对解集中个体的三个子目标按照重要性等级两两比较构造判断矩阵，验证判断矩阵的一致性，并得到目标的重要性排序。根据重要性与三个子目标的加权值为优胜集中的个体评分，得到评分最高的个体作为最优解。
MOGA解个体的三个子目标的判断矩矩阵及重要性结果见表2。
3 应用案例
利用南方某省会城市某运营商GSM网络实际数据验证基于MOGA的多目标遗传算法性能。
所需数据包括基站和小区的工参，MR测量报告、小区间干扰数据和全网可用频点范围等信息。网络规模为1971个基站，6310个扇区，共36739个频点需求。TCH可用频点为：1-56，81-95，BCCH可用频点为：57-80。
案例中小区频点的初始化分配完成后，Pareto优胜集的展示如图4（a）。Pareto优胜集中的解在解空间中分布均匀。
随着进化的进程，优胜集内个体在目标向量Obj的同频干扰、邻频干扰、对打度三个维度上的平均值的收敛如图5。优胜集内解个体目标向量各维度的均值随着进化的过程而逐渐下降，最终稳定在一个较理想的水平。种群进化到60代左右时目标向量值收敛到较优水平，收敛速度较快。
进化结束后，Paret优胜集中解个体展示如图4（b）。与进化前Pareto优胜集内个体图4a对比，个体在解空间内分布性维持较好。解个体基本覆盖到了解空间的Pareto前端。
对优胜集中个体采用层次分析法得到个体的部分AHP评估值如表3，最终优胜的解个体的目标向量值为[0，0.0484，0.48625]。
4 结论
本文将多目标遗传算法应用于GSM网络频率资源优化配置问题。该算法在现网环境下的应用证明，该算法具有较好的收敛性与寻优能力，可以较快的得到符合偏好的GSM网络频率优化配置方案，具有实用价值。在本文提出的算法中，由于利用Pareto排序来进行频点预分配与变异，增加了计算的复杂度。如何提高预分配与变异效率以进一步提高算法性能是将来要研究的问题。