基于改進(jìn)的遺傳算法無線通信網(wǎng)頻率指配問題研究

劉田間　高小玲

摘 要： 通過對(duì)無線通信頻率指配問題的分析，結(jié)合遺傳算法在頻率指配領(lǐng)域的應(yīng)用，提出了一種啟發(fā)式的指配方法。該方法通過改進(jìn)選擇方式，自適應(yīng)地調(diào)整交叉、變異概率來指配信道分配。仿真分析證明，該算法科學(xué)可行，有效地避免陷入局優(yōu)解，加快了種群進(jìn)化速度，減少了迭代次數(shù)，較快收斂到最優(yōu)解。

關(guān)鍵詞： 遺傳算法； 無線通信網(wǎng)； 頻率指配； 信道分配

中圖分類號(hào)： TN92?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

在無線通信網(wǎng)絡(luò)中，可利用的頻譜資源是十分有限的。隨著經(jīng)濟(jì)、科技和軍事的發(fā)展，大量的無線通信設(shè)備將投入使用，必將造成頻譜資源擁擠，頻率使用效率低下。為了有效解決此類問題，避免用頻設(shè)備的自擾和互擾，頻率指配技術(shù)是近年來得到快速發(fā)展的一種軟策略。近幾十年來，一些通過模擬自然生態(tài)系統(tǒng)機(jī)制的智能優(yōu)化算法廣泛應(yīng)用于頻率指配問題。如模擬退火算法[1]、禁忌搜索法[2]、遺傳算法[3]等。這些傳統(tǒng)的算法在實(shí)際求解中仍不能滿足要求。本文旨在通過對(duì)遺傳算法的改進(jìn)，為頻率指配問題提供切實(shí)可行的解決方案。有效地避免陷入局優(yōu)解，加快種群進(jìn)化速度，提高算法的整體性能。

1 頻率指配數(shù)學(xué)模型

1.1 頻率指配問題描述

頻率指配是在電波傳播預(yù)測(cè)基礎(chǔ)上，對(duì)電磁信號(hào)的分布進(jìn)行計(jì)算，分析各通信設(shè)備之間可能存在的電磁干擾?？梢詺w結(jié)為滿足約束條件的頻率指配最佳方案的搜索，此處的最佳含義是指無違約或違約數(shù)最少意義上的最佳頻率指配。簡(jiǎn)單地講，頻率指配問題可以歸納為在滿足約束條件下，尋找使得通信容量最大且總干擾代價(jià)最小的頻率指配方案。

由圖1可以看出，改進(jìn)后的算法在100代適應(yīng)度函數(shù)值趨近于1，即收斂于最佳適應(yīng)度值。而傳統(tǒng)算法在150代才趨近于最佳適應(yīng)度值。收斂速度提高了近33.3%，同時(shí)減少了迭代次數(shù)使其較快達(dá)到全局最優(yōu)，和理論分析結(jié)果基本一致。

3 結(jié) 語(yǔ)

遺傳算法用在無線通信網(wǎng)頻率指配研究中是一個(gè)很好的案例。本文通過對(duì)遺傳算法的理解，研究了遺傳算子對(duì)算法性能的影響，提出了一種新的方法來代替?zhèn)鹘y(tǒng)的輪盤賭法選擇算子，自適應(yīng)地調(diào)整交叉和變異算子使算法較快的收斂到最優(yōu)解。但在實(shí)際應(yīng)用中還沒有進(jìn)行有效的定量分析，這是下一步要重點(diǎn)研究的內(nèi)容。

參考文獻(xiàn)

[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] 陳浩.遺傳算法在頻率指配問題中的應(yīng)用研究[D].北京：北京交通大學(xué)，2009.

[5] 陳有青，徐蔡星，鐘文亮，等.一種改進(jìn)選擇算子的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，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] 崔珊珊.遺傳算法的一些改進(jìn)及應(yīng)用[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2010.

摘 要： 通過對(duì)無線通信頻率指配問題的分析，結(jié)合遺傳算法在頻率指配領(lǐng)域的應(yīng)用，提出了一種啟發(fā)式的指配方法。該方法通過改進(jìn)選擇方式，自適應(yīng)地調(diào)整交叉、變異概率來指配信道分配。仿真分析證明，該算法科學(xué)可行，有效地避免陷入局優(yōu)解，加快了種群進(jìn)化速度，減少了迭代次數(shù)，較快收斂到最優(yōu)解。

關(guān)鍵詞： 遺傳算法； 無線通信網(wǎng)； 頻率指配； 信道分配

中圖分類號(hào)： TN92?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

在無線通信網(wǎng)絡(luò)中，可利用的頻譜資源是十分有限的。隨著經(jīng)濟(jì)、科技和軍事的發(fā)展，大量的無線通信設(shè)備將投入使用，必將造成頻譜資源擁擠，頻率使用效率低下。為了有效解決此類問題，避免用頻設(shè)備的自擾和互擾，頻率指配技術(shù)是近年來得到快速發(fā)展的一種軟策略。近幾十年來，一些通過模擬自然生態(tài)系統(tǒng)機(jī)制的智能優(yōu)化算法廣泛應(yīng)用于頻率指配問題。如模擬退火算法[1]、禁忌搜索法[2]、遺傳算法[3]等。這些傳統(tǒng)的算法在實(shí)際求解中仍不能滿足要求。本文旨在通過對(duì)遺傳算法的改進(jìn)，為頻率指配問題提供切實(shí)可行的解決方案。有效地避免陷入局優(yōu)解，加快種群進(jìn)化速度，提高算法的整體性能。

1 頻率指配數(shù)學(xué)模型

1.1 頻率指配問題描述

頻率指配是在電波傳播預(yù)測(cè)基礎(chǔ)上，對(duì)電磁信號(hào)的分布進(jìn)行計(jì)算，分析各通信設(shè)備之間可能存在的電磁干擾?？梢詺w結(jié)為滿足約束條件的頻率指配最佳方案的搜索，此處的最佳含義是指無違約或違約數(shù)最少意義上的最佳頻率指配。簡(jiǎn)單地講，頻率指配問題可以歸納為在滿足約束條件下，尋找使得通信容量最大且總干擾代價(jià)最小的頻率指配方案。

由圖1可以看出，改進(jìn)后的算法在100代適應(yīng)度函數(shù)值趨近于1，即收斂于最佳適應(yīng)度值。而傳統(tǒng)算法在150代才趨近于最佳適應(yīng)度值。收斂速度提高了近33.3%，同時(shí)減少了迭代次數(shù)使其較快達(dá)到全局最優(yōu)，和理論分析結(jié)果基本一致。

3 結(jié) 語(yǔ)

遺傳算法用在無線通信網(wǎng)頻率指配研究中是一個(gè)很好的案例。本文通過對(duì)遺傳算法的理解，研究了遺傳算子對(duì)算法性能的影響，提出了一種新的方法來代替?zhèn)鹘y(tǒng)的輪盤賭法選擇算子，自適應(yīng)地調(diào)整交叉和變異算子使算法較快的收斂到最優(yōu)解。但在實(shí)際應(yīng)用中還沒有進(jìn)行有效的定量分析，這是下一步要重點(diǎn)研究的內(nèi)容。

參考文獻(xiàn)

[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] 陳浩.遺傳算法在頻率指配問題中的應(yīng)用研究[D].北京：北京交通大學(xué)，2009.

[5] 陳有青，徐蔡星，鐘文亮，等.一種改進(jìn)選擇算子的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，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] 崔珊珊.遺傳算法的一些改進(jìn)及應(yīng)用[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2010.

摘 要： 通過對(duì)無線通信頻率指配問題的分析，結(jié)合遺傳算法在頻率指配領(lǐng)域的應(yīng)用，提出了一種啟發(fā)式的指配方法。該方法通過改進(jìn)選擇方式，自適應(yīng)地調(diào)整交叉、變異概率來指配信道分配。仿真分析證明，該算法科學(xué)可行，有效地避免陷入局優(yōu)解，加快了種群進(jìn)化速度，減少了迭代次數(shù)，較快收斂到最優(yōu)解。

關(guān)鍵詞： 遺傳算法； 無線通信網(wǎng)； 頻率指配； 信道分配

中圖分類號(hào)： TN92?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

在無線通信網(wǎng)絡(luò)中，可利用的頻譜資源是十分有限的。隨著經(jīng)濟(jì)、科技和軍事的發(fā)展，大量的無線通信設(shè)備將投入使用，必將造成頻譜資源擁擠，頻率使用效率低下。為了有效解決此類問題，避免用頻設(shè)備的自擾和互擾，頻率指配技術(shù)是近年來得到快速發(fā)展的一種軟策略。近幾十年來，一些通過模擬自然生態(tài)系統(tǒng)機(jī)制的智能優(yōu)化算法廣泛應(yīng)用于頻率指配問題。如模擬退火算法[1]、禁忌搜索法[2]、遺傳算法[3]等。這些傳統(tǒng)的算法在實(shí)際求解中仍不能滿足要求。本文旨在通過對(duì)遺傳算法的改進(jìn)，為頻率指配問題提供切實(shí)可行的解決方案。有效地避免陷入局優(yōu)解，加快種群進(jìn)化速度，提高算法的整體性能。

1 頻率指配數(shù)學(xué)模型

1.1 頻率指配問題描述

頻率指配是在電波傳播預(yù)測(cè)基礎(chǔ)上，對(duì)電磁信號(hào)的分布進(jìn)行計(jì)算，分析各通信設(shè)備之間可能存在的電磁干擾?？梢詺w結(jié)為滿足約束條件的頻率指配最佳方案的搜索，此處的最佳含義是指無違約或違約數(shù)最少意義上的最佳頻率指配。簡(jiǎn)單地講，頻率指配問題可以歸納為在滿足約束條件下，尋找使得通信容量最大且總干擾代價(jià)最小的頻率指配方案。

由圖1可以看出，改進(jìn)后的算法在100代適應(yīng)度函數(shù)值趨近于1，即收斂于最佳適應(yīng)度值。而傳統(tǒng)算法在150代才趨近于最佳適應(yīng)度值。收斂速度提高了近33.3%，同時(shí)減少了迭代次數(shù)使其較快達(dá)到全局最優(yōu)，和理論分析結(jié)果基本一致。

3 結(jié) 語(yǔ)

遺傳算法用在無線通信網(wǎng)頻率指配研究中是一個(gè)很好的案例。本文通過對(duì)遺傳算法的理解，研究了遺傳算子對(duì)算法性能的影響，提出了一種新的方法來代替?zhèn)鹘y(tǒng)的輪盤賭法選擇算子，自適應(yīng)地調(diào)整交叉和變異算子使算法較快的收斂到最優(yōu)解。但在實(shí)際應(yīng)用中還沒有進(jìn)行有效的定量分析，這是下一步要重點(diǎn)研究的內(nèi)容。

參考文獻(xiàn)

[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] 陳浩.遺傳算法在頻率指配問題中的應(yīng)用研究[D].北京：北京交通大學(xué)，2009.

[5] 陳有青，徐蔡星，鐘文亮，等.一種改進(jìn)選擇算子的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，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] 崔珊珊.遺傳算法的一些改進(jìn)及應(yīng)用[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2010.