基于啟發(fā)式遺傳算法的通信光纜網(wǎng)絡(luò)線路規(guī)劃布局方法

樂乾巍

摘? 要：由于通信光纜網(wǎng)絡(luò)線路規(guī)劃受到多種限制條件的制約，導(dǎo)致最優(yōu)解比例低。針對上述問題，提出基于啟發(fā)式遺傳算法的通信光纜網(wǎng)絡(luò)線路規(guī)劃布局方法。通過建立數(shù)學(xué)模型明確目標(biāo)和約束條件，利用啟發(fā)式遺傳算法進(jìn)行線路初始化，并通過選擇、交叉、變異等方法持續(xù)優(yōu)化群體，直至滿足終止條件。實(shí)驗(yàn)結(jié)果表明：這種方法通過明確約束條件，獲取高比例最優(yōu)解，為通信光纜網(wǎng)絡(luò)線路規(guī)劃布局提供了更優(yōu)方案。

關(guān)鍵詞：啟發(fā)式遺傳算法? 通信光纜? 網(wǎng)絡(luò)線路? 規(guī)劃布局方法

中圖分類號：TP399

A Layout Method for the Planning of Optical Communication Cable Network Routes Based on the Heuristic Genetic Algorithm

LE Qianwei

Shanghai Posts & Telecommunications Designing Consulting Institute Co.， Ltd.， Shanghai，200092 China

Abstract： Due to the constraint of various constraints on the planning of optical communication cable network routes， the proportion of optimal solutions is low. A layout method for the planning of optical communication cable network routes based on the sheuristic genetic algorithm is proposed to address the above issue. By establishing a mathematical model， goals and constraints are clarified， the heuristic genetic algorithm is used for route initialization， and the population is continuously optimized through selection， crossover， mutation and other methods until the termination conditions are met. Experimental results show that this method obtains a high proportion of optimal solutions by clarifying constraints， which provides a more optimal solution for the layout of the planning of optical communication cable network lines.

Key Words： Heuristic genetic algorithm; Optical communication cable; Network line; Planning and layout methods

隨著信息技術(shù)的飛速發(fā)展，通信光纜網(wǎng)絡(luò)布局規(guī)劃的重要性日益凸顯，需確保信息高效、穩(wěn)定、安全傳輸。傳統(tǒng)方法在處理復(fù)雜網(wǎng)絡(luò)布局問題時難以找到全局最優(yōu)解。因此尋求更智能、高效的規(guī)劃方法至關(guān)重要。啟發(fā)式遺傳算法作為一種優(yōu)化算法，通過模擬生物進(jìn)化過程來尋找最優(yōu)解。本文將啟發(fā)式遺傳算法應(yīng)用于通信光纜網(wǎng)絡(luò)線路規(guī)劃布局，旨在通過模擬生物進(jìn)化過程，找到最優(yōu)的光纜路徑方案，以滿足其他優(yōu)化目標(biāo)。

1? 通信光纜網(wǎng)絡(luò)線路規(guī)劃布局方法設(shè)計(jì)

1.1? 建立通信光纜網(wǎng)絡(luò)線路規(guī)劃數(shù)學(xué)模型

通信光纜網(wǎng)絡(luò)線路規(guī)劃需考慮站點(diǎn)位置和現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu)。本文采用圖論視角，將站點(diǎn)視為節(jié)點(diǎn)，光纜線路為邊[1]。將規(guī)劃問題就轉(zhuǎn)化為在給定的候選線路中選擇最合適的線路組合來構(gòu)建網(wǎng)絡(luò)。

為了精確描述和解決通信光纜網(wǎng)絡(luò)線路規(guī)劃問題，本文構(gòu)建其數(shù)學(xué)模型。在這個過程中，首先引入網(wǎng)絡(luò)建設(shè)成本函數(shù)，通信光纜網(wǎng)絡(luò)建設(shè)成本可以表示為：

公式（1）中：為待選光纜線路數(shù)；為0～1之間的變量，當(dāng)時，即第條光纜線路未被選中，當(dāng)時，代表第條光纜線路被選中；為第條線路的建設(shè)成本。

在構(gòu)建通信光纜網(wǎng)絡(luò)線路規(guī)劃的數(shù)學(xué)模型時，為了確保網(wǎng)絡(luò)的穩(wěn)定運(yùn)行和高效傳輸，接下來引入網(wǎng)絡(luò)可靠性約束。這一約束通過站點(diǎn)成環(huán)率來量化，表示網(wǎng)絡(luò)中形成環(huán)狀結(jié)構(gòu)的站點(diǎn)數(shù)與總站點(diǎn)數(shù)的比值。

公式（2）中：為站點(diǎn)成環(huán)率，反映網(wǎng)絡(luò)的冗余度和容錯能力；為通信光纜網(wǎng)絡(luò)中站點(diǎn)的總數(shù)；為成環(huán)站點(diǎn)。

在通信光纜網(wǎng)絡(luò)線路規(guī)劃布局過程中，同時考慮站點(diǎn)之間的業(yè)務(wù)流量分布，尤其是那些具有大量業(yè)務(wù)往來的站點(diǎn)對，需要確保它們之間的數(shù)據(jù)傳輸具有盡可能小的時延和路由跳數(shù)。為了實(shí)現(xiàn)這一目標(biāo)，在進(jìn)行線路規(guī)劃時，優(yōu)先考慮在業(yè)務(wù)繁忙的站點(diǎn)對之間建設(shè)直連光纜。因此，本文引入相應(yīng)的業(yè)務(wù)分布約束條件，確保邊存在，即站點(diǎn)u和站點(diǎn)v之間有一條直接連接的光纜線路，由此，本文構(gòu)建一個完整的通信光纜網(wǎng)絡(luò)線路規(guī)劃數(shù)學(xué)模型為：

公式（3）中，為閾值。在通信光纜網(wǎng)絡(luò)線路規(guī)劃的數(shù)學(xué)模型中，連通性約束是首要的條件，確保所有站點(diǎn)之間都能夠進(jìn)行通信，避免出現(xiàn)網(wǎng)絡(luò)解裂的情況。作為一個可調(diào)節(jié)的參數(shù)，用于設(shè)置站點(diǎn)成環(huán)率的約束條件。

1.2? 確定通信光纜網(wǎng)絡(luò)線路編碼順序

由上述模型可以看出，在不考慮約束條件的情況下，通信光纜網(wǎng)絡(luò)線路規(guī)劃問題與旅行商問題（TSP）相似，都是尋找最短路徑[2]。然而，通信光纜網(wǎng)絡(luò)的規(guī)劃更復(fù)雜，屬于NP一Hard問題，傳統(tǒng)方法難以求解。因此，本文選擇啟發(fā)式遺傳算法來求解通信光纜網(wǎng)絡(luò)線路規(guī)劃問題。算法流程如圖1所示。

算法中采用順序編碼方法描述通信光纜線路規(guī)劃方案。每個染色體長度N代表站點(diǎn)數(shù)量。基因順序即光纜線路連接順序。例如：編碼（2，3，1，5，4，8，6，7）代表了一個布局方案，數(shù)字1～8代表站點(diǎn)，順序指示連接順序。從站點(diǎn)1開始，依次連接到站點(diǎn)2、3等，最后返回到站點(diǎn)1，形成一個閉環(huán)。

1.3? 利用啟發(fā)式遺傳算法進(jìn)行線路初始化

為確保啟發(fā)式遺傳算法在通信光纜線路規(guī)劃中的穩(wěn)定性和效率，本文引入無向圖廣度優(yōu)先搜索技術(shù)。傳統(tǒng)初始化過程存在盲目性，易生成不符合約束條件的無效序列。結(jié)合無向圖廣度優(yōu)先搜索技術(shù)，可在初始化階段篩選出符合約束條件的序列，確保生成的染色體序列滿足站點(diǎn)之間的連接要求。廣度搜索無向圖如圖2所示。

如圖2所示，從隨機(jī)選取的起始結(jié)點(diǎn)A開始，利用無向圖廣度優(yōu)先搜索查找鄰接結(jié)點(diǎn)B、D、E并存儲在待選集中。根據(jù)權(quán)重隨機(jī)選擇B為下一個訪問的結(jié)點(diǎn)，移除B并存儲結(jié)點(diǎn)D、E。繼續(xù)搜索B的未訪問鄰接結(jié)點(diǎn)C、F、G，與D、E一起存儲。重復(fù)此過程，直到所有結(jié)點(diǎn)都被訪問[3]。最終得到由可行解組成的初始種群。

1.4? 輸出通信光纜網(wǎng)絡(luò)線路規(guī)劃布局方案

在完成了種群的初始化之后，本文將采用一種基于動態(tài)罰函數(shù)的約束處理方法來確保每個染色體滿足通信光纜網(wǎng)絡(luò)線路規(guī)劃的約束條件。在每一條染色體上引入懲罰函數(shù)FP，當(dāng)一條染色體違背其中一條限制時，它的懲罰函數(shù)FP就會被設(shè)置成一個正的值，這個值等于這條染色體違背全部限制的總數(shù)。反之，若一條染色體不受限制，它的懲罰函數(shù)FP就是0，這就意味著它滿足了這個問題的所有條件[4]。本文通過罰值和懲罰因子相乘，再用它的反數(shù)作懲罰函數(shù)，從而得到一種改進(jìn)的適應(yīng)值：

式（4）中：、為常數(shù)；為目前迭代次數(shù)；為最大迭代次數(shù)。隨著迭代次數(shù)的增加，懲罰因子增大。在迭代初始階段，罰值越小，則可以拓展到更廣闊的解域，也就有更多的機(jī)會尋找到更好的解。接下來在滿足約束條件的前提下進(jìn)行搜索，采用動態(tài)線性標(biāo)定的方法計(jì)算初始適應(yīng)度函數(shù)F。

公式（5）中：、分別是第k個代次的最大目標(biāo)函數(shù)值和最小目標(biāo)函數(shù)的值；隨迭代次數(shù)的增大而逐漸降低，以此來調(diào)整選擇壓力，達(dá)到全局與局部的均衡。

接下來針對通信光纜網(wǎng)絡(luò)線路規(guī)劃問題，本文使用局部映射法和交叉法。選取兩對父方，按交叉概率隨機(jī)選取兩對切點(diǎn)X、Y，互換編碼片段實(shí)現(xiàn)遺傳重組。確保編碼合法性，置換非互換部分中的重復(fù)碼。同時，利用倒位變異增強(qiáng)群體的多樣性。遍歷染色體，按突變概率選擇片段編碼，反轉(zhuǎn)次序得到新遺傳結(jié)合。通過選擇、交叉和變異操作，種群中個體逐步進(jìn)化，適應(yīng)度提高[5]。達(dá)到終止條件時，算法停止并輸出最優(yōu)個體作為最終規(guī)劃方案。

2? 實(shí)驗(yàn)與結(jié)果分析

2.1? 實(shí)驗(yàn)準(zhǔn)備

為了驗(yàn)證本文方法的有效性，以某地市通信光纜為對象進(jìn)行實(shí)驗(yàn)。該網(wǎng)絡(luò)需要規(guī)劃光纜線路以連接各個站點(diǎn)，滿足位置、需求、長度、成本和帶寬要求，并遵循地形、建筑物等約束條件。在滿足所有約束條件的前提下，找到一條總成本最低、總長度最短且滿足帶寬需求的光纜線路布局方案。該網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，涵蓋了4種不同類型站點(diǎn)和數(shù)十個站點(diǎn)，通過35條線路連接。節(jié)點(diǎn)網(wǎng)絡(luò)示意圖如圖3所示。

在實(shí)驗(yàn)過程中，將采用本文提出的線路規(guī)劃方法，結(jié)合該地市光傳輸網(wǎng)的實(shí)際情況，進(jìn)行詳細(xì)的網(wǎng)絡(luò)分析和規(guī)劃。

2.2? 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文方法的優(yōu)越性，將本文方法與貪心算法、模擬退火算法做對比實(shí)驗(yàn)，采用相同的通信光纜網(wǎng)絡(luò)線路規(guī)劃問題作為實(shí)驗(yàn)對象，并設(shè)置了相同的約束條件和優(yōu)化目標(biāo)。對于每種算法，進(jìn)行多獨(dú)立實(shí)驗(yàn)，形成如下表所示的實(shí)驗(yàn)結(jié)果。

根據(jù)表1可以看出，隨著場景復(fù)雜度的增加（從場景A到場景C），本文方法的最優(yōu)解比例從98%下降到94%，表明在更復(fù)雜的場景中，找到最優(yōu)解的難度增加。盡管如此，相比其他算法，本文方法在所有場景中仍然表現(xiàn)出較好的尋優(yōu)能力。貪心算法的最優(yōu)解比例隨著場景復(fù)雜度的增加而顯著下降，從場景A的86%下降到場景C的71%。貪心算法求解高復(fù)雜性問題的過程中極易陷入局部極值，導(dǎo)致整體性能下降。模擬退火算法在場景A和場景B中的最優(yōu)解比例相對較高，分別為90%和87%，但在場景C中下降到73%。雖然模擬退火算法能夠通過引入隨機(jī)性來避免局部最優(yōu)解，但在高復(fù)雜度場景中其性能仍然受到一定限制。綜上所述，本文方法在通信光纜網(wǎng)絡(luò)線路規(guī)劃布局問題中表現(xiàn)出較好的性能，尤其是在高復(fù)雜度場景中，其尋優(yōu)能力和穩(wěn)定性相比其他算法具有明顯優(yōu)勢。

3 結(jié)語

本文研究了基于啟發(fā)式遺傳算法的通信光纜網(wǎng)絡(luò)線路規(guī)劃布局方法，并探討了其在實(shí)際應(yīng)用中的潛力和效果。盡管本文的研究取得了一定的成果，但仍存在一些不足之處。算法的性能和效率可能會受到參數(shù)設(shè)置、初始種群選擇等因素的影響，需要進(jìn)一步研究和優(yōu)化。未來，我們將繼續(xù)深入研究啟發(fā)式遺傳算法在通信光纜網(wǎng)絡(luò)線路規(guī)劃布局中的應(yīng)用，并探索與其他優(yōu)化算法的結(jié)合，以提高求解質(zhì)量和效率。同時，也將關(guān)注新技術(shù)、新標(biāo)準(zhǔn)對光纜網(wǎng)絡(luò)規(guī)劃布局的影響，不斷更新和完善我們的研究方法和工具。

參考文獻(xiàn)

[1]孫睿男，初翔，陳昱，等.基于混合啟發(fā)式算法的快遞末端選址路徑優(yōu)化研究[J].計(jì)算機(jī)工程與科學(xué)，2024，46（1）：159-169.

[2]楊帆.基于智能優(yōu)化算法的通信光纜網(wǎng)絡(luò)線路規(guī)劃設(shè)計(jì)[J].信息系統(tǒng)工程，2023（11）：74-77.

[3]潘超，呂翹楚，肖巍.基于啟發(fā)式遺傳算法的即時通信網(wǎng)絡(luò)漏洞檢測[J].計(jì)算機(jī)仿真，2023，40（8）：191-195.

[4]趙紅宇，代軍麗.通信光纜線路規(guī)劃設(shè)計(jì)及關(guān)鍵問題分析[J].數(shù)字通信世界，2022（6）：97-99.

[5]宋婧旖.海底光纜信息傳輸網(wǎng)絡(luò)規(guī)劃分析[J].中國新通信，2021，23（13）：54-55.