Multi-Objective Node Placement Problem in Wireless Network.pdf

1、無線網(wǎng)絡(luò)規(guī)劃包括很多應(yīng)該考慮的重要問題。尤其是許多研究者試圖提出各種方案來提高網(wǎng)絡(luò)的性能和效率:通過尋找最佳規(guī)劃的蜂窩網(wǎng)絡(luò)，選擇節(jié)點(diǎn)在無線局域網(wǎng)(Wlans)的位置和訪問類型，以及將基站和節(jié)點(diǎn)放置在中的多目標(biāo)網(wǎng)絡(luò)中。
　　對(duì)于提高網(wǎng)絡(luò)的效率及性能魯棒性、自我管理、靈活性和任務(wù)支持，無線網(wǎng)絡(luò)基礎(chǔ)設(shè)施的管理起著非常重要和關(guān)鍵的作用。
　　基礎(chǔ)設(shè)施位置的設(shè)定可分為基站布置問題和天線的布置問題。前者與基站的位置有關(guān)，而后者與對(duì)某些特

2、定候選基站的節(jié)點(diǎn)天線分配有關(guān)。本論文所述無線節(jié)點(diǎn)布置問題是一個(gè)天線問題。基站布置問題和天線的布置問題，就目前所知，都是NP難的。即在P≠NP的假設(shè)下，沒有確定的算法可以在多項(xiàng)式時(shí)間內(nèi)解決這一問題。
　　值得一提的是，布置一個(gè)新的天線非常昂貴，不僅僅是因?yàn)樵O(shè)備上的花費(fèi)，還有正確的設(shè)備安裝方法和系統(tǒng)規(guī)劃的花費(fèi)，這使得通過常規(guī)的方法（如單元分裂）增加系統(tǒng)容量不具有吸引力。此外，由于有限的無線帶寬，網(wǎng)絡(luò)無法同時(shí)支持大量用戶，尤其是對(duì)于需要

3、大量、快速的數(shù)據(jù)傳輸速率的應(yīng)用程序。
　　無線網(wǎng)絡(luò)集成也許可以以較高數(shù)據(jù)傳輸率提供服務(wù)，同時(shí)節(jié)約成本。然而，無線局域網(wǎng)的信號(hào)覆蓋范圍很?。ㄌ貏e是在城市地區(qū)），只能向在其覆蓋面積內(nèi)的用戶，通過固定的接入點(diǎn)方式提供服務(wù)。為了克服這一缺點(diǎn)，使其能夠?yàn)榇蠖鄶?shù)用戶服務(wù)，必須要部署高密度的無線局域網(wǎng)接入點(diǎn)。但是，此解決方案會(huì)導(dǎo)致成本增加，并降低固定基礎(chǔ)設(shè)施的效率。
　　無線節(jié)點(diǎn)布置問題就是構(gòu)建一個(gè)優(yōu)化的基礎(chǔ)設(shè)施，即確定發(fā)射站的最佳位置—

4、—要考慮到覆蓋面、成本、容量、干擾和切換這些特定因素。這些元素在問題模型中通常被定為目標(biāo)、約束或兩者都是，并會(huì)受到無線網(wǎng)絡(luò)類型的影響，例如，數(shù)據(jù)通信或電信。己知這個(gè)問題是NP難的。
　　在下文中，我們將詳細(xì)描述節(jié)點(diǎn)布置問題，在本論文中使用的模型是基于這樣一個(gè)模型——它與我們解決該問題的目標(biāo)相適應(yīng)，問題的說明與有關(guān)常數(shù)如下:
　　候選站E:考慮給定一組有限的候選站{e1，e2，……，eE｝,D可用通信設(shè)備的總數(shù)。這些候選站eu

5、的位置為（αu，βu）(V)u通信設(shè)備D:考慮給定一組有限的通信設(shè)備{d1，d2，……，dD｝,D是可用設(shè)備的總數(shù)。每個(gè)設(shè)備dv有功率pv，容量sv,消耗Cv，類型tv和功率范圍wv接收器R:考慮有一組有限的接收器｛r1，r2……，rR｝被置于位置（αg，βg），R為接收器總數(shù)通信設(shè)備dv可能被給定與其相關(guān)的接收器rg不同的信號(hào)閾值θdg和信號(hào)強(qiáng)度Svg, i，u。信號(hào)閾值和信號(hào)強(qiáng)度一起，決定了節(jié)點(diǎn)覆蓋范圍。σdg是接收器rg從設(shè)備dv

6、.索要數(shù)據(jù)的數(shù)據(jù)率節(jié)點(diǎn)N:節(jié)點(diǎn)集{n1，n2,……，nN｝，N為需要布置的節(jié)點(diǎn)總數(shù)一個(gè)網(wǎng)絡(luò)由從候選站點(diǎn)列表中的選定的站點(diǎn)和設(shè)備（從通信設(shè)備中選擇不同的給定的數(shù)目和位置）組成。任務(wù)是在服務(wù)范圍內(nèi)布置一組節(jié)點(diǎn)ni，即使在有小干擾發(fā)生的情況下，所有與這些節(jié)點(diǎn)相關(guān)聯(lián)的接收器rg都能被覆蓋。
　　在本論文中，我們要處理異構(gòu)網(wǎng)絡(luò)的節(jié)點(diǎn)布置問題，我們必須優(yōu)化節(jié)點(diǎn)位置，使其通信能夠覆蓋新建立的網(wǎng)絡(luò)，此外我們解決了新的節(jié)點(diǎn)部署問題和將它們組合到原有

7、基礎(chǔ)設(shè)施的問題。
　　每個(gè)節(jié)點(diǎn)的ni有一組特定的標(biāo)識(shí)，比如:成本為c，功率和容量等等。我們?cè)诒疚闹杏袃蓚€(gè)假設(shè):首先，如果有一個(gè)新的基礎(chǔ)設(shè)施，并想要在其中配置一組節(jié)點(diǎn)必須要考慮我們的目標(biāo)和約束條件:其次，我們假設(shè)我們通過現(xiàn)有網(wǎng)絡(luò)的時(shí)間范圍知道了需求分布，同時(shí)我們想要部署新節(jié)點(diǎn)，并通過現(xiàn)有的基礎(chǔ)設(shè)施將其組合進(jìn)去。
　　現(xiàn)有的基礎(chǔ)設(shè)施架構(gòu)是一個(gè)同質(zhì)或異質(zhì)的節(jié)點(diǎn)集合，這些節(jié)點(diǎn)與穩(wěn)定的分層網(wǎng)絡(luò)關(guān)聯(lián)，并連接每個(gè)通信設(shè)備類型。這些構(gòu)成了現(xiàn)

8、有網(wǎng)絡(luò)的節(jié)點(diǎn)有一系列特征如:功率、計(jì)算能力和覆蓋范圍的大小。此外，我們必須有一個(gè)現(xiàn)有網(wǎng)絡(luò)基礎(chǔ)設(shè)施的主要集，定義為Hd，其中基礎(chǔ)設(shè)施與每個(gè)通信設(shè)備dv相關(guān)聯(lián)。只有在有需要時(shí)，我們才添加這些額外節(jié)點(diǎn)。此外，這些額外的節(jié)點(diǎn)應(yīng)滿足系統(tǒng)的限制，還應(yīng)該能夠通過網(wǎng)絡(luò)進(jìn)行協(xié)作、通信和協(xié)商。我們提供了我們知道的通信設(shè)備dv和節(jié)點(diǎn)集N。我們的主要目標(biāo)是在特定區(qū)域的覆蓋范圍中找到最佳位置、數(shù)目、通信類型和連接。
　　進(jìn)一步的，我們還解釋了節(jié)點(diǎn)和通信設(shè)備

9、D，候選站點(diǎn)M及其它節(jié)點(diǎn)ni之間的通信過程。
　　與通信設(shè)備相關(guān)聯(lián)的節(jié)點(diǎn)我們認(rèn)為，為每個(gè)節(jié)點(diǎn)ni可分配給一組通信設(shè)備D。也就是說，對(duì)于每個(gè)節(jié)點(diǎn)的ni可以通過一些通信設(shè)備dv連接到不同的通信網(wǎng)絡(luò)。通信設(shè)備dv特征由不同的參數(shù)設(shè)定。我們的模型提出考慮了功率、容量、成本、通信設(shè)備類型、功率范圍和帶寬，每個(gè)通信設(shè)備dv可以描述為六元組τ=(p、s、c、t、w、b)，其中p表示要將節(jié)點(diǎn)連接到接收器的功率，s表示節(jié)點(diǎn)提供的控制測(cè)試點(diǎn)的數(shù)據(jù)需求

10、的帶寬或者能力，c表示通訊設(shè)備成本，t表示通信設(shè)備類型，在這里，我們只使用一種類型，w表示要連接網(wǎng)絡(luò)中的節(jié)點(diǎn)所需的功率范圍，b表示兩個(gè)連接網(wǎng)絡(luò)的節(jié)點(diǎn)之間的帶寬。
　　與候選站點(diǎn)相關(guān)聯(lián)的節(jié)點(diǎn)我們還必須考慮候選站點(diǎn)集E與空間坐標(biāo)(αu，βu)來表示節(jié)點(diǎn)的可能位置。每個(gè)節(jié)點(diǎn)ni應(yīng)該只與一個(gè)候選站點(diǎn)eu通信。我們還用一組接收器rg來模擬流量通信需求，這些接收器為了連接到通信網(wǎng)絡(luò)需要特=特別的信號(hào)強(qiáng)度，該強(qiáng)度來自通信設(shè)備d。我們可以標(biāo)識(shí)這些

11、測(cè)試點(diǎn)作為一個(gè)或一組移動(dòng)終端用來做覆蓋。在我們的案例研究中，接收器rg都假定通過這片區(qū)域能夠得到均勻分配和用于最大化我們的網(wǎng)絡(luò)通信覆蓋。我們認(rèn)為每個(gè)接收器rg具有空間坐標(biāo)（αg，βg），它從節(jié)點(diǎn)獲得無線信號(hào)。無線連通性通過數(shù)據(jù)速率需求θdg和信號(hào)閾值σde來評(píng)價(jià)，以保持服務(wù)質(zhì)量。
　　目標(biāo)
　　在規(guī)劃無線網(wǎng)絡(luò)基礎(chǔ)設(shè)施時(shí)有幾個(gè)影響因素。對(duì)于網(wǎng)絡(luò)運(yùn)營(yíng)商來說，安裝一個(gè)新的節(jié)點(diǎn)或額外節(jié)點(diǎn)通常是非常昂貴的。為此，本文的主要目標(biāo)是優(yōu)化節(jié)

12、點(diǎn)數(shù)量，通過考慮4個(gè)事情:覆蓋、成本、容量和重疊。其中覆蓋和重疊是考慮節(jié)點(diǎn)的位置，成本與節(jié)點(diǎn)數(shù)量有關(guān)，容量則受節(jié)點(diǎn)和通信設(shè)備類型的影響。
　　覆蓋優(yōu)化通常包括兩個(gè)目的:盡量減少信號(hào)質(zhì)量差的地區(qū)和提高整個(gè)服務(wù)區(qū)的平均信號(hào)質(zhì)量。覆蓋范圍的最大化是融合網(wǎng)絡(luò)的主要問題。就我們的問題來說，我們考慮了一大組接收器來最大化通信覆蓋。第二個(gè)目標(biāo)是盡量減少網(wǎng)絡(luò)的建造成本，即安裝節(jié)點(diǎn)和與它相關(guān)聯(lián)的通信設(shè)備的成本。在我們問題中，使得節(jié)點(diǎn)放置數(shù)最小，同時(shí)

13、實(shí)現(xiàn)重疊率最低的全覆蓋，使得安置成本最小化。第三個(gè)目標(biāo)是最小化最大帶寬，網(wǎng)絡(luò)設(shè)計(jì)模型必須提供足夠的數(shù)據(jù)速率（帶寬）給用戶用戶，這一目標(biāo)的主要問題是最大化網(wǎng)絡(luò)的最小帶寬容量。換句話說，我們需要盡量減小通信設(shè)備帶寬和覆蓋接收器的數(shù)據(jù)速率需求的總和的絕對(duì)差額。第四個(gè)目標(biāo)是盡量減少重疊，這個(gè)目標(biāo)函數(shù)旨在減少引起通信設(shè)備之間的重疊覆蓋的網(wǎng)絡(luò)干擾?？梢酝ㄟ^接收器由多個(gè)通信設(shè)備覆蓋數(shù)目來確定網(wǎng)絡(luò)中的重疊。此外所有以前的目標(biāo)，我們處理一些約束時(shí)必須滿足

14、符合我們模型問題的可行的解決方案。第一個(gè)約束是與特定的通信設(shè)備連接到的任何節(jié)點(diǎn)的所有指定接收器的總數(shù)據(jù)速率需求的總和應(yīng)該小于或等于該通訊設(shè)備的能力，第二個(gè)約束是為每個(gè)節(jié)點(diǎn)可以分配多個(gè)通信設(shè)備，第三項(xiàng)約束就是每個(gè)分配給多個(gè)候選站點(diǎn)的節(jié)點(diǎn)，第四個(gè)約束是大多數(shù)一個(gè)節(jié)點(diǎn)分配給每個(gè)候選站點(diǎn)，第五的約束是每個(gè)接收器最多可以被一個(gè)節(jié)點(diǎn)連接到通訊設(shè)備。
　　主要有三個(gè)通過使用進(jìn)化的技術(shù)解決優(yōu)化問題的方法:基于算法的帕累托最優(yōu)實(shí)現(xiàn)、基于算法的指標(biāo)和

15、基于算法的分解。帕累托優(yōu)勢(shì)算法，因?yàn)榻鉀Q了MOPs，所以實(shí)現(xiàn)了很好的性能，但在應(yīng)用于多目標(biāo)問題（超過4個(gè)目標(biāo)）時(shí)，性能很差。性能的下降隨著非優(yōu)勢(shì)解的增長(zhǎng)是呈指數(shù)增長(zhǎng)的，所有人體在群體中都不會(huì)有帕累托優(yōu)勢(shì)，即使在如所述的早期。超體積指標(biāo)的頻繁使用表明目標(biāo)為7個(gè)時(shí)技術(shù)規(guī)模比較好，雖然僅當(dāng)指標(biāo)能被評(píng)估時(shí)才發(fā)生。分解方法:似乎是一個(gè)求解多目標(biāo)優(yōu)化問題的不錯(cuò)的選擇。它能簡(jiǎn)單的實(shí)現(xiàn)和解決多個(gè)單目標(biāo)問題。這種方法的主要優(yōu)點(diǎn)是良好的可擴(kuò)展性和考慮目標(biāo)的

16、數(shù)目情況下的計(jì)算效率。舉個(gè)例子，基于分解(MOEA/D)的多目標(biāo)進(jìn)化算法解決PF逼近問題時(shí)，通過將多目標(biāo)優(yōu)化問題分解為若干個(gè)標(biāo)量的優(yōu)化子問題，同時(shí)優(yōu)化它們。MOEA/D使用切比雪夫分解方法來近似Pareto Front(PF)問題轉(zhuǎn)化成大量標(biāo)量?jī)?yōu)化子問題。每個(gè)子問題利用其相鄰的子問題用于優(yōu)化的信息來做優(yōu)化，它通過眾多的解發(fā)展，同時(shí)解決優(yōu)化問題。在每一代中，群體包括了每個(gè)子問題目前為止找到的最優(yōu)解。這些子問題的鄰接關(guān)系是它們聚集系數(shù)向量之

17、間的距離。兩個(gè)相鄰的子問題的最優(yōu)解應(yīng)該很近。
　　保存可行性解的補(bǔ)償函數(shù)使得可行和不可行的解和混合方法的分離?；诋?dāng)前解決方案中可行解的數(shù)目，并考慮到親子群體的聯(lián)合，約束問題的搜索過程可以分為三個(gè)階段:1）不可行解2）至少一個(gè)可行解和3）結(jié)合親子群體比下一代父群體有更多可行解。多年來在處理EAs中的各種約束條件后，已可以提供了各種約束處理技術(shù)。這些技術(shù)之間的差別是在這三個(gè)搜索階段中如何處理不可行個(gè)體。
　　雖然解決約束單目標(biāo)

18、優(yōu)化問題已經(jīng)研究了幾十年，但在求解約束多目標(biāo)優(yōu)化問題上取得的進(jìn)展很少。
　　MOEA/D需要兩個(gè)參數(shù):小生境參數(shù)和定義鄰域的補(bǔ)償參數(shù)——必須要設(shè)置正確。此外，MOEA/D的作者并不建議任何有效的程序，通過MOEA/D處理約束，此后一個(gè)修正的模型CMOEA/D-DE-ATP被引入用來處理在多目標(biāo)優(yōu)化問題中的約束，它調(diào)節(jié)MOEA/D的替換和更新方案，修改后的方案提出了補(bǔ)償函數(shù)用來拒絕不可行解。補(bǔ)償函數(shù)應(yīng)用閾值管理補(bǔ)償量，不可行解依靠一

19、個(gè)由MOEA/D提出了更新方案中的自適應(yīng)門限值。我們已經(jīng)使用由MOEA/D算法的實(shí)現(xiàn)的方法來解決我們的多目標(biāo)問題。
　　CMOEA/D-DE-ATP需要將MOP分解為一系列子問題。對(duì)于節(jié)點(diǎn)的問題，在四個(gè)目標(biāo)約束條件下，它將問題分解成m標(biāo)量?jī)?yōu)化子問題。我們建議采用CMOEA/D-DE-ATP作為解決多目標(biāo)最優(yōu)化問題的方案來解決節(jié)點(diǎn)布局問題。
　　此外，被提出的代表性、選擇性、交叉性和突變性，被提出的算法可以自動(dòng)搜索適當(dāng)?shù)墓?jié)點(diǎn)數(shù)

20、，并優(yōu)化它的位置——通過最大化覆蓋、最小化成本、最大化容量滿意度和最小化重疊來考慮約束在異構(gòu)的網(wǎng)絡(luò)基礎(chǔ)設(shè)施中的問題。主要問題應(yīng)該被考慮到——即當(dāng)我們要解決的問題是節(jié)點(diǎn)數(shù)時(shí)，應(yīng)該靈活一點(diǎn)，同時(shí)問題解決者應(yīng)考慮帶約束的多目標(biāo)情形。
　　陳述
　　候選方案，也就是一組額外節(jié)點(diǎn)N被編碼到一條染色體。對(duì)于每個(gè)屬于N的節(jié)點(diǎn)被表示為長(zhǎng)度為n的子串，該子串由位置Z組成（Z與不同的可用通信設(shè)備D的數(shù)目有關(guān)），在網(wǎng)絡(luò)中用Y代表，候選站點(diǎn)用X表示

21、。一般CMOEA/D-DE-ATP的方法CMOEA/D-DE-ATP算法的第1步是初始化。初始解由一個(gè)特定問題啟發(fā)式生成或隨機(jī)生成，本論文提出使用一個(gè)均勻的隨機(jī)樣本來生成n個(gè)解來初始化內(nèi)部群體。
　　在步驟2-1，新的解通過使用遺傳算法算子用來生成解。第一是選定算子，它決定某個(gè)個(gè)體將影響下一代的生成。論文提出使用錦標(biāo)賽選擇算子（第3.4.2節(jié)將詳細(xì)介紹）。第二個(gè)算子是交叉度，它需要一定數(shù)量的父代重組它們，并創(chuàng)造新數(shù)目的子代。本論文

22、提出均勻交叉算子（第3.3節(jié)將介紹）。第三個(gè)算子是突變算子，它旨在在搜索空間中生成新的解——現(xiàn)有解的變體而來（第3.5節(jié)）。
　　第二個(gè)和第三個(gè)算子用于步驟2-2，在這一步中啟發(fā)式算子增加了節(jié)點(diǎn)的個(gè)體利用率。它創(chuàng)建解Z，通過在步驟2-3中使用DE算子，Z能用于更新種群，如果y元素超出邊界，通過隨機(jī)選擇步驟2-4邊界內(nèi)的值重置y，并求y值。在步驟2-5，為每個(gè)解zj更新種群。
　　在步驟2-6中考慮所有的ith子問題的鄰居，y

23、是否比xj實(shí)現(xiàn)更好。來考慮jth子問題，它用yo替換xj。在步驟3中，檢查終止準(zhǔn)則，以決定搜索應(yīng)該停止還是繼續(xù)，以便讓我們的算法將在一定代數(shù)后停止。在步驟4中，增加代gen=gen+l。許多進(jìn)化算法實(shí)驗(yàn)者不斷變換算法的關(guān)鍵參數(shù)和相關(guān)的特征值（圖5.2）試圖確定對(duì)于一個(gè)特定的問題實(shí)例或類最有效，最高效的實(shí)現(xiàn)。
　　種群初始化
　　種群初始化是所有EA的第一也是首要任務(wù)。一般來說，這些搜索技術(shù)開始通過一些初始解（初始種群），嘗試

24、在一些最優(yōu)的解的方向改善它們。當(dāng)一些預(yù)定義的標(biāo)準(zhǔn)滿足是停止搜索進(jìn)程。如果有關(guān)該解的預(yù)先信息不存在，我們通常則以隨機(jī)解開始。除其他外，計(jì)算時(shí)間是與這些從最優(yōu)解初始推測(cè)的距離有關(guān)。為了提高我們一開始就得到更靠近（更適合）解的機(jī)會(huì)，就要同時(shí)檢查相反解。在這之后，更合適的解（估計(jì)或相反估計(jì)）可以選擇作為初始解。現(xiàn)在重要的是注意到假設(shè)某一問題是一個(gè)單目標(biāo)優(yōu)化問題，則最好的解是種群中’最高適應(yīng)值’的解決。另一方面，假設(shè)問題是一個(gè)多目標(biāo)優(yōu)化問題，則該

25、算法將在多目標(biāo)域中檢查兩個(gè)解的”基于方法的帕累托”。
　　初始種群在染色體中隨機(jī)生成的子串分配，對(duì)于某一候選站點(diǎn)特定位置的子串的數(shù)量是從一個(gè)可能的索引[1，2,…，M]中隨機(jī)選取的，對(duì)于某一特定通信設(shè)備類型從一組通信設(shè)備集[1，2，…，D]中選取，對(duì)于一定數(shù)量的被連接的其他節(jié)點(diǎn)則隨機(jī)的從[1,…，|Zd|]中創(chuàng)建。然后調(diào)整每個(gè)染色體來驗(yàn)證我們的約束問題，并因此提出一套可行解來表示我們初始解。
　　隨機(jī)生成初始種群后，進(jìn)化算法

26、改善其中的3個(gè)算子:等效于適者生存的選擇算子，引入個(gè)體之間交配的交叉算子，生成隨機(jī)修飾的突變算子。
　　1.1選擇算子就MOP而言選擇算子是最重要的一點(diǎn)。通過使用適合函數(shù)值來選擇的最佳染色體。因此，選擇可以被認(rèn)為是“適者生存”的生存部分。選擇將主要是選擇在生存的有序列表中具有更高的適應(yīng)值的個(gè)體，但也有一些選擇方案，其中有一些具有較低的適應(yīng)值的個(gè)體在以一定的水平在有序列表中求生存。當(dāng)“好”的染色體被需要時(shí)，列表的上部會(huì)被額外使用，而

27、對(duì)于“壞”的染色體則使用列表的下部。
　　選擇總是在種群上實(shí)現(xiàn)第一個(gè)算子。選擇算子在一個(gè)種群中選擇好的一系列種群同時(shí)構(gòu)建了一個(gè)交配池。這就是選擇操作有時(shí)作為繁殖操縱算子的理由之一。正常選擇的選擇操縱基因方法導(dǎo)致這些個(gè)體編碼成功的結(jié)構(gòu)來更規(guī)律地創(chuàng)建副本。在對(duì)于遺傳算法(GA)中的用于選擇染色體的幾種方法已演變成，輪盤選擇父母來與他們的適應(yīng)性一致。
　　更好的染色體將有更多的機(jī)會(huì)來選擇。該染色體將被選擇的機(jī)會(huì)與它的適應(yīng)性是成正比

28、的。排名選擇，首先，躋身種群和在這之后，每個(gè)染色體接收來自這個(gè)排名的適應(yīng)性。最好將擁有等于N的適應(yīng)性，其中N表示種群中的染色體數(shù)目。最壞的適應(yīng)性會(huì)有等于1的適應(yīng)性，第二個(gè)最差的適應(yīng)性等于2等等。這里的想法是根據(jù)他們的適應(yīng)值安排染色體的遞減順序。
　　然后在安排的集合中來對(duì)每?jī)蓷l染色體應(yīng)用選擇。以這種方式，遺傳算法將在強(qiáng)染色體之間或弱染色體之間使用。這意味著沒有機(jī)會(huì)在弱和強(qiáng)染色體之間運(yùn)用遺傳算法，本次選擇的穩(wěn)定選擇的主要目標(biāo)是染色體

29、的很大一部分，其為將要生存并且遺傳給下一代。GA然后以下面方式的執(zhí)行。
　　對(duì)于創(chuàng)建一個(gè)新的后代，在每一代中選擇幾個(gè)（良好適應(yīng)度高）的染色體。最后競(jìng)爭(zhēng)，但在這里我們會(huì)處理競(jìng)爭(zhēng)。競(jìng)爭(zhēng)選擇是從中種群隨機(jī)選擇某些數(shù)量的個(gè)體，并從該組復(fù)制最佳個(gè)體到使用進(jìn)化算法的選擇方法的中間種群。對(duì)于最簡(jiǎn)單的競(jìng)爭(zhēng)選擇是選擇從種群中隨機(jī)選擇兩個(gè)隨機(jī)個(gè)體來展開競(jìng)爭(zhēng)以決定哪一個(gè)體當(dāng)選。此外，它可以被有效地執(zhí)行。
　　步驟2中的遺傳算法用于產(chǎn)生一個(gè)新的解，

30、特別是在CMOEA/D-DE-ATP步驟2.1的第i個(gè)循環(huán)，這里的選擇算子的主要目標(biāo)是選擇M模式最近的子問題的兩個(gè)親本染色體，通過計(jì)算它們的權(quán)重[λ1……，λM]中的歐氏距離來找到一個(gè)子問題i在Pint中，并找到Xis鄰居中，它們?cè)谝粋€(gè)交配中為競(jìng)爭(zhēng)的關(guān)系，意味著我們的問題選擇算子將選擇對(duì)于節(jié)點(diǎn)最好的兩個(gè)位置，其節(jié)點(diǎn)與競(jìng)爭(zhēng)的位置和所選擇的父母將提交到雜交基因之后的通信設(shè)備均相關(guān)。
　　1.2交叉算子通過選擇算法選擇了2對(duì)父母后。交叉

31、是結(jié)合了2對(duì)父母來構(gòu)建一個(gè)新的后代染色體的操作。交叉的主要概念是，由于可能得到了父母雙方最好的特征，新的染色體可能比父母雙方更好。
　　有幾種方法介紹了交叉操作，首先是單點(diǎn)交叉，它是最常使用的交叉技術(shù)，單點(diǎn)交叉式進(jìn)行隨機(jī)的選擇交叉點(diǎn)。第二個(gè)父母的第二部分是一個(gè)鏈接，該鏈接通過第一個(gè)父母的第一部來創(chuàng)造第一個(gè)后代。第二個(gè)父母的第一部分和第一個(gè)父母的第二部分來進(jìn)行連接去建立第二個(gè)后代。
　　兩點(diǎn)交叉式是在父母有機(jī)體字符串中選擇2點(diǎn)

32、。它連接了三部分，染色體開始的二進(jìn)制字符串到第一個(gè)交叉點(diǎn)是從一個(gè)父母中派生出來的，第一個(gè)點(diǎn)到第二個(gè)交叉點(diǎn)的部分是從第二個(gè)父母和它第一個(gè)父母衍生品中派生出來的。
　　第三、均勻交叉式是這樣的一個(gè)交叉操作:允許染色體的比特位從第一個(gè)父母或者第二個(gè)父母進(jìn)中進(jìn)行混合。
　　中間交叉:中間產(chǎn)生的后代使用了父母的加權(quán)平均值。中間交叉依賴于一個(gè)參數(shù)的比例。
　　如果比例是在(0，1)范圍內(nèi)，之后創(chuàng)建的后代位置是在父母位置相反的頂點(diǎn)上

33、。
　　最后是算術(shù)交叉:在算術(shù)交叉中(AC)，算法生成的孩子，這些孩子是2個(gè)父母的加權(quán)算術(shù)平均值。孩子與線性約束和邊界無關(guān)是可行的。Alpha是在(O，1)中隨機(jī)選擇的一個(gè)數(shù)。如果是父母，則是一個(gè)最適合的值，該函數(shù)返回孩子。
　　在步驟2.1中，2對(duì)父母隨機(jī)的進(jìn)行交叉配對(duì)來產(chǎn)生一個(gè)新的解決方案。尤其是在我們的問題中，交叉會(huì)改變節(jié)點(diǎn)與候選網(wǎng)站和通信設(shè)備進(jìn)行聯(lián)系的位置。
　　1.3突變算子執(zhí)行交叉操作后，變化的操作應(yīng)用于單

34、個(gè)解決方案，該解決方案是一個(gè)基因會(huì)在小概率的情況下進(jìn)行隨機(jī)改變，最后生成一個(gè)新的染色體。該操作的主要目標(biāo)是維持種群的多樣性、增加不丟失任何潛在方案的機(jī)會(huì)、保持全局最優(yōu)，而交叉操作則是搜索空間的一個(gè)快速探測(cè)方法。突變?cè)跓o性繁殖中是一個(gè)很常見的，它通常在為保持多樣性的人群中和抑制早熟的集合中執(zhí)行作為一個(gè)位的翻轉(zhuǎn)。在這個(gè)算法中，我們維持了突變的速率，每一位都有概率進(jìn)行翻轉(zhuǎn)。
　　選擇和突變（沒有進(jìn)行交叉）生成一些低概率的部分，這些部分會(huì)

35、有一些進(jìn)行位的翻轉(zhuǎn)。突變僅僅是在搜索空間中產(chǎn)生了一個(gè)隨機(jī)的搜索。
　　該算法的性能已經(jīng)通過一系列不同測(cè)試問題的評(píng)估，我們?cè)?個(gè)測(cè)試實(shí)例中設(shè)置了不同的問題，每個(gè)測(cè)試實(shí)例有兩個(gè)問題需要解決1）確定異構(gòu)網(wǎng)絡(luò)基礎(chǔ)設(shè)施中節(jié)點(diǎn)的位置2）同時(shí)最優(yōu)化我們關(guān)心的四個(gè)對(duì)象:覆蓋率、開銷、能力和重疊性，同時(shí)考慮約束性條件。三個(gè)通訊設(shè)備各自的覆蓋半徑為13、15和17千米內(nèi)性能分別為150，160，170 Mb/s，（隨機(jī)數(shù)據(jù)傳輸速率的要求對(duì)于所有的設(shè)備

36、只有一種類型存在）但是各自開銷分別是3500，4500，5500。節(jié)點(diǎn)和接收器的增益提前被設(shè)定，兩個(gè)節(jié)點(diǎn)間的帶寬為500MHz，波長(zhǎng)是0.025km。所有的接收器閾值為1，所有節(jié)點(diǎn)的成本各不相同。
　　測(cè)試用例被分為兩類:接收器所在位置區(qū)域的大小和及接收器密度的大小;根據(jù)接收器不同的密度和區(qū)域大小的參數(shù)結(jié)合，共有9個(gè)測(cè)試實(shí)例;所有的用例都是可用的，并且為單獨(dú)實(shí)現(xiàn)的30倍。當(dāng)?shù)螖?shù)超過最大次數(shù)300次時(shí)，算法停止運(yùn)行或者運(yùn)行到目標(biāo)

37、函數(shù)不在擴(kuò)大。在100次迭代之后表現(xiàn)出30人的規(guī)模。此外在我們的問題類中設(shè)置了種群數(shù)量為隨機(jī)數(shù)。
　　我們?cè)贛atLAb上實(shí)現(xiàn)這個(gè)算法，實(shí)驗(yàn)環(huán)境為Windows7平臺(tái)Intel(R) CoreTMi5-2450QM CPU，2.50GHz，4G內(nèi)存。
　　實(shí)驗(yàn)結(jié)果表明MOEA/D在合理的運(yùn)行時(shí)間內(nèi)表現(xiàn)出很好的性能。更重要的是，比較的結(jié)果表明我們算法的性能都在預(yù)期目標(biāo)內(nèi)有效率。結(jié)果證明所提出的解決方案是有效的，此外我們還研究了

38、該模型的性能以及9個(gè)測(cè)試用例與第一個(gè)對(duì)象之間的關(guān)系，發(fā)現(xiàn)覆蓋率和測(cè)試點(diǎn)之間呈現(xiàn)正相關(guān)。隨著測(cè)試點(diǎn)的增加（測(cè)試點(diǎn)是通過一些測(cè)試問題實(shí)例設(shè)定三個(gè)不同區(qū)域大小來呈現(xiàn)），第一個(gè)對(duì)象將增加到可以覆蓋整個(gè)網(wǎng)絡(luò)中所有的這些測(cè)試點(diǎn)。
　　很明顯一個(gè)網(wǎng)絡(luò)規(guī)劃最重要的目標(biāo)是成本最小化（在我們的模型中節(jié)點(diǎn)數(shù)代表成本）因此我們運(yùn)行算法尋求一種最實(shí)惠的解決方案，這個(gè)方案給出每個(gè)節(jié)點(diǎn)的位置的同時(shí)也能達(dá)到其他所有目標(biāo)的需求。此外我們還研究了該模型的性能以及9個(gè)

39、測(cè)試用例與第二個(gè)對(duì)象之間的關(guān)系，說明了不同測(cè)試問題實(shí)例的成本之間的關(guān)系。很明顯，成本與覆蓋區(qū)域的大小之間是存在比例關(guān)系的。
　　實(shí)驗(yàn)結(jié)果表明，通過將我們算法針對(duì)MOGA算法（該算法解決同一節(jié)點(diǎn)放置問題）的解決方案與同樣的問題實(shí)例中引入的相同的3個(gè)第一目標(biāo)函數(shù)的解決方案進(jìn)行比較，與此同時(shí)，我們?cè)黾恿酥丿B的目標(biāo)函數(shù)和使用的5個(gè)重要約束條件，其適用于我們的問題。
　　實(shí)驗(yàn)結(jié)果闡述具有帶寬不同的測(cè)試問題實(shí)例之間的關(guān)系，其中，在各個(gè)問

40、題的情況下，幾乎所有的測(cè)試點(diǎn)覆蓋，而且他們的條件均被滿足，我們可以觀察到，對(duì)于我們必須覆蓋的測(cè)試點(diǎn)，由于用于通信設(shè)備帶寬的局限性，對(duì)于我們的位置獲得更少的帶寬，因此帶寬目標(biāo)與覆蓋區(qū)的大小成反比。通過改變測(cè)試點(diǎn)的數(shù)量，我們觀察到的節(jié)點(diǎn)數(shù)量增加時(shí)，測(cè)試點(diǎn)的數(shù)量增加。這是由于連接網(wǎng)絡(luò)和分別提供更多帶寬的需要所致。
　　如果通信裝置之間存在過多的重疊，干擾將會(huì)非常大而且頻譜效率會(huì)很差。相反的是，對(duì)于移動(dòng)性管理重疊是必需的。因此，我們需要不

41、過大的重疊。實(shí)驗(yàn)結(jié)果示出了使用Z4不同測(cè)試問題實(shí)例之間的關(guān)系，很顯然，重疊與覆蓋的區(qū)域的大小成比例，另外，該重疊與額外的測(cè)試點(diǎn)和區(qū)域也相關(guān)聯(lián)，很明顯，隨著不同區(qū)域的大小的測(cè)試點(diǎn)增加，第四個(gè)目標(biāo)（重疊）也將增加。
　　我們將我們的解決方案與推出了同樣問題的同一目標(biāo)函數(shù)進(jìn)行對(duì)比，而且我們?cè)黾恿酥丿B的目標(biāo)函數(shù)和使用的5個(gè)重要約束條件，其適用于我們的問題。結(jié)果表明，我們的算法在所有3個(gè)目標(biāo)的應(yīng)用中比MOGA算法要號(hào)很多，此外我們介紹另一個(gè)

42、客觀值，由于CPU時(shí)間與目標(biāo)數(shù)量和問題規(guī)模是相關(guān)的，因此我們的算法超過MOGA算法0.983039秒的平均CPU時(shí)間。
　　最后，在本文給出的結(jié)果可以很容易地?cái)U(kuò)展到以下的情況，在其中我們有一個(gè)現(xiàn)有的網(wǎng)絡(luò)，我們想要通過放置一些新節(jié)點(diǎn)將其展開。即假定，我們知道對(duì)于已經(jīng)存在的網(wǎng)絡(luò)通過一定時(shí)間范圍為其進(jìn)行需求分配，我們想要部署新的節(jié)點(diǎn)和通過現(xiàn)有的基礎(chǔ)設(shè)施將它們結(jié)合起來。這個(gè)現(xiàn)有的基礎(chǔ)設(shè)施是一組同構(gòu)和異構(gòu)的節(jié)點(diǎn)，其與固定和分層網(wǎng)絡(luò)相關(guān)聯(lián)，并