文/孟丹 楊子晨

（中國艦船研究設(shè)計(jì)中心信息室 湖北省武漢市 430064）

艦船作戰(zhàn)系統(tǒng)日漸趨于集成化、自動(dòng)化、智能化，用于驅(qū)動(dòng)及控制的系統(tǒng)功能軟件越來越多，作戰(zhàn)系統(tǒng)在發(fā)展方向上有著復(fù)雜、龐大的趨勢。這對(duì)艦船控制、作戰(zhàn)指揮以及信息通信提供了強(qiáng)大的支持。目前，艦船作戰(zhàn)系統(tǒng)正在向分布式體系結(jié)構(gòu)過渡，新一代分布式體系結(jié)構(gòu)是采用分布式計(jì)算機(jī)系統(tǒng)完成作戰(zhàn)指揮和武器控制功能的指揮控制系統(tǒng)，通過數(shù)據(jù)總線和先進(jìn)的數(shù)字通信技術(shù)把分布在艦船上各戰(zhàn)位的本地資源變成系統(tǒng)的全局資源[1]。

分布式系統(tǒng)是將大型計(jì)算任務(wù)分為許多小步驟或計(jì)算機(jī)程序，然后將其分發(fā)到許多計(jì)算機(jī)中，以充分利用所有計(jì)算機(jī)的處理能力。該系統(tǒng)采用標(biāo)準(zhǔn)化、通用化的硬件設(shè)備、軟件及接口，為作戰(zhàn)系統(tǒng)的模塊相互備用創(chuàng)造條件。提高了作戰(zhàn)系統(tǒng)生命，功能分布式的各個(gè)計(jì)算機(jī)可并行完成各種功能，縮短反應(yīng)時(shí)間，顯控臺(tái)標(biāo)準(zhǔn)化、通用化，減少了研制和維修費(fèi)用[1]。與傳統(tǒng)的作戰(zhàn)系統(tǒng)不同，新一代分布式系統(tǒng)軟件和硬件是不綁定的，系統(tǒng)的功能軟件被解耦成一系列重用度很高的子任務(wù)軟件模塊[2]。

本文從通用處理器負(fù)載均衡的角度出發(fā)，建立了帶約束條件的目標(biāo)優(yōu)化數(shù)學(xué)模型，提出了改進(jìn)的遺傳算法求解軟件映射問題，從而對(duì)船舶作戰(zhàn)系統(tǒng)功能軟件進(jìn)行優(yōu)化部署。

1 艦船作戰(zhàn)系統(tǒng)軟件模塊映射問題描述

1.1 軟件模塊映射

由于船舶作戰(zhàn)分布式系統(tǒng)的應(yīng)用軟件不與物理層的特定設(shè)備綁定，即軟件和硬件是分離的，在船舶系統(tǒng)運(yùn)行期間，可根據(jù)航行任務(wù)、航行階段、航行需求加載不同軟件模塊到通用處理器模塊以完成特定的任務(wù)。本文章未對(duì)硬件模塊即處理器模塊做小功能的細(xì)分，把所有處理器模塊當(dāng)作同一實(shí)體討論，即統(tǒng)稱為通用處理器。

在分布式系統(tǒng)中系統(tǒng)功能最終會(huì)細(xì)分成許多子任務(wù)，如何動(dòng)態(tài)有效地管理這些子任務(wù)軟件模塊并滿足用戶的需求成為亟待解決的問題。軟件模塊映射問題就是找到子任務(wù)軟件模塊加載部署到通用處理器模塊的最優(yōu)方案，如圖1 所示。

1.2 軟件模塊映射數(shù)學(xué)模型建立

根據(jù)船舶航行任務(wù)需求，需要進(jìn)行資源管理，負(fù)載分配可在運(yùn)行的處理器之間進(jìn)行遷移整合。在這個(gè)過程中，處理器的負(fù)載會(huì)一直波動(dòng)。

在文獻(xiàn)[3][4]中對(duì)動(dòng)態(tài)預(yù)配置和負(fù)載進(jìn)行了廣泛的研究,處于活動(dòng)狀態(tài)的服務(wù)器。即使處于空閑狀態(tài)，也要消耗不小的功率（消耗高達(dá)峰值功率的66%）。因?yàn)榧词巩?dāng)服務(wù)器未加載用戶任務(wù)時(shí)，運(yùn)行操作系統(tǒng)和維護(hù)硬件外圍設(shè)備（例如內(nèi)存，磁盤，主板，PCI 插槽和風(fēng)扇）所需的功率不可忽略。所以我們需要?jiǎng)討B(tài)配置滿足特定于應(yīng)用程序的服務(wù)質(zhì)量所需的最少數(shù)量的服務(wù)器，以增大負(fù)載，提高資源利用率。在船舶作戰(zhàn)系統(tǒng)平臺(tái)中，允許負(fù)載根據(jù)需要有多種分配方式，也可將較多的負(fù)載分配到較少的處理器上，來提高通用處理器的資源利用率。當(dāng)請求資源的數(shù)量快要接近物理節(jié)點(diǎn)的剩余資源數(shù)量時(shí)，資源利用率很高，但由于資源爭奪導(dǎo)致執(zhí)行時(shí)間變長，所以平均能耗也會(huì)變高[3]。

負(fù)載平衡是一種在處理器之間公平分配工作以獲取最佳響應(yīng)時(shí)間，資源利用率和吞吐量的方法，所以系統(tǒng)的負(fù)載均衡程度是軟件部署需要考慮的重要因素之一。通用處理器上不同的負(fù)載分配代表不用的軟件模塊部署策略，也對(duì)應(yīng)著不同的平均能源消耗，服務(wù)質(zhì)量及執(zhí)行效率。因此合理的負(fù)載分配是必要的。本文以最小化負(fù)載均衡作為軟件模塊部署策略的優(yōu)化目標(biāo)。

圖1：軟件模塊映射示意圖

圖2：軟件模塊的部署結(jié)果示意圖

圖3：輪盤賭算法

軟件模塊初始化部署問題，類似于裝箱問題，具體的資源大小約束關(guān)系如下所示：

上式公式（1）表示：第j 個(gè)物理機(jī)通用處理器上安裝的軟件模塊不大于該處理器上對(duì)應(yīng)資源的剩余量。Xij=1 表示第i 個(gè)軟件模塊存在于第j 個(gè)物理機(jī)上，且一個(gè)軟件模塊只能存在某一個(gè)通用處理器上。

對(duì)于物理機(jī)負(fù)載定義如下：

其中Pj表示第j 個(gè)通用處理器上安裝的軟件模塊安裝的數(shù)量，Rj表示第j 個(gè)通用處理器上能安裝的負(fù)載的最大值。

通用處理器負(fù)載均衡度用負(fù)載資源的標(biāo)準(zhǔn)差表示，建立目標(biāo)函數(shù)如下。

負(fù)載均衡適應(yīng)度函數(shù)：

當(dāng)適應(yīng)度函數(shù)值越大，其系統(tǒng)的負(fù)載均衡度越小，代表通用處理器上的資源分布的標(biāo)準(zhǔn)差越小，即系統(tǒng)負(fù)載分布越均衡，此時(shí)的部署方案也是最好的。

2 軟件模塊映射問題優(yōu)化求解

2.1 確認(rèn)優(yōu)化算法

并行和分布式系統(tǒng)中任務(wù)的分配和調(diào)度已被認(rèn)為是一個(gè)NP 完全問題，受到了廣泛的關(guān)注[9]。即在確定的多項(xiàng)式時(shí)間內(nèi)無法通過窮舉法找最優(yōu)解。目前有許多研究工作通過啟發(fā)式算法解決這類問題，常見的目標(biāo)優(yōu)化自啟發(fā)式算法[5]有：遺傳算法，粒子群算法，蟻群算法等，每一種算法都有不同的優(yōu)勢和缺點(diǎn)。

對(duì)于遺傳算法而言，它具有良好的全局搜索能力，可以在不陷入局部最優(yōu)解的陷阱的情況下，快速地求解出該解空間中的所有解；而且因其固有的并行性，有利于進(jìn)行分布式計(jì)算，同時(shí)可以加快求解速度。然而，遺傳算法會(huì)發(fā)生早熟即過早收斂的問題，遺傳算法的局部搜索能力較差，導(dǎo)致經(jīng)典的遺傳算法耗時(shí)大，進(jìn)化后期搜索效率較低[6][7]。

這要求一方面應(yīng)該促進(jìn)種群的多樣性，以便算法可以掃描可行解的整個(gè)空間。另一方面，最佳解決方案的收斂速度也不容忽視。

本文可以采用改進(jìn)后的遺傳算法，如通過調(diào)節(jié)變異、交叉概率，改變編碼方式緩解遺傳算法早熟收斂等問題，求解軟件模塊部署優(yōu)化問題。即可以使優(yōu)良個(gè)體得以保留，又可以維持群體的多樣性[8]。

2.2 編碼與解碼

編碼就是把最優(yōu)問題的可行解轉(zhuǎn)換成染色體的形式，染色體上的基因分布表示負(fù)載映射方案，染色體的長度代表著需要部署軟件模塊的總數(shù)。為了避免漢明懸崖問題，這里采用實(shí)數(shù)編碼形式。假設(shè)n 個(gè)軟件模塊需要映射到m 個(gè)通用處理器上，編碼得到一個(gè)染色體，形如：{x1,……,xn-1}，x1,……,xn-1∈[0,m-1]。xn-1：第n-1 個(gè)軟件模塊部署在第xn-1個(gè)通用處理器上。

例如將13 個(gè)軟件模塊安裝到6 個(gè)通用處理器上，即n=13，m=6，則編碼產(chǎn)生的染色體的長度為13，如{3，5，1，1，2，4，2，3，0，,0,5,2，4}的部署方案如圖2 所示。

總共有n 個(gè)軟件需要安裝，記為（0, 1，2，3，…，n-1）。m個(gè)通用處理器，假設(shè)n 編號(hào)為（0, 1，2，3，…，m-1），n ≤ m。

上例的染色體解碼結(jié)果為：軟件模塊0 部署在通用處理器3 上，軟件模塊1 部署在通用處理器5，依此類推，軟件模塊12 部署在通用處理器4。

結(jié)果如下：

通用處理器0：{軟件模塊8， 9}；

通用處理器1：{軟件模塊2， 3}；

通用處理器2：{軟件模塊4， 6, 11}；

通用處理器3：{軟件模塊0， 7}；

通用處理器4：{軟件模塊2, 12}；

通用處理器5：{軟件模塊1, 10}。

2.3 種群初始化

種群規(guī)模是指任意一代中的個(gè)體總數(shù)，種群的個(gè)體數(shù)決定了遺傳算法的多樣性。數(shù)目越多，種群的多樣性越好，但是會(huì)增加計(jì)算量，降低運(yùn)行效率。但如果數(shù)目過少，會(huì)因?yàn)檫z傳多樣性降低而導(dǎo)致比較容易出現(xiàn)早熟現(xiàn)象。所謂早熟問題，就是在遺傳運(yùn)算初期，少數(shù)個(gè)體適應(yīng)度非常高（可能是局部最優(yōu)解），這樣在遺傳過程中，這些個(gè)體在下一代所占的比例很高，使得交叉和變異對(duì)種群多樣性的作用被嚴(yán)重降低，種群多樣性無法保證。最終因?yàn)榫植孔顑?yōu)解的存在而錯(cuò)過全局最優(yōu)解。

除合理確定種群大小之外，本文對(duì)初始化染色體還做了篩選：先隨機(jī)產(chǎn)生一條染色體，然后對(duì)染色體的資源利用率進(jìn)行約束，保證負(fù)載在[Laodl, Laodh ]內(nèi)。設(shè)定初始種群的染色體數(shù)為 S，軟件模塊數(shù)為n，通用處理器為 m。

2.4 遺傳算子優(yōu)化

遺傳算子用于通過選擇，雜交和突變來繁殖新種群。所以遺傳算子優(yōu)化主要從對(duì)選擇算子、交叉算子、變異算子等的優(yōu)化實(shí)現(xiàn)的。

2.4.1 選擇算子

選擇操作是遺傳算法中的一個(gè)關(guān)鍵操作，它的主要作用就是根據(jù)一定的策略隨機(jī)選擇個(gè)體保留至下一代。根據(jù)個(gè)體的適應(yīng)度，按照一定的規(guī)則，從第n 代群體中選擇出一些具有優(yōu)良性狀的個(gè)體遺傳到下一代（n+1）群體中。在這一選擇過程中，個(gè)體適應(yīng)度越大，則被選擇到下一代的機(jī)會(huì)越大。

本文先對(duì)所有染色體按照適應(yīng)度函數(shù)值進(jìn)行排序，采用精英個(gè)體保存策略，選中適應(yīng)度(匹配度)最高的，刪除最低的，用匹配最高的復(fù)制代替適應(yīng)度最低的。接著使用輪盤賭算法。每條染色體能進(jìn)入下一代進(jìn)化的概率等于其適應(yīng)度值與整個(gè)種群所有個(gè)體適應(yīng)度值的和的比率。即假設(shè)某個(gè)體i 的適應(yīng)度Fi，種群大小NP，則i被選擇的概率公式為：

輪盤賭選擇法的模擬實(shí)現(xiàn)過程如下步驟：

（1）產(chǎn)生一個(gè)隨機(jī)概率P = rand(1)。

（2）若Pk-1＜ P ≤Pk(2 ≤ k ≤ NP), 則選擇第k 條染色體。

（3）若P ≤ P1，則選擇第1 條染色體。

其中的Pi稱為染色體xi(i=1,2,…,N)的積累概率，其計(jì)算公式如圖3 所示。

2.4.2 交叉算子

交叉操作過程中，從種群中隨機(jī)選擇兩條染色體，并生成一個(gè)隨機(jī)數(shù)作為時(shí)間點(diǎn)，以將每個(gè)染色體分為兩個(gè)部分，交換位于該時(shí)間點(diǎn)右側(cè)的各個(gè)部分以生成新的后代。其中交叉算子起核心作用。這里對(duì)交叉操作進(jìn)行優(yōu)化改進(jìn)，采用多點(diǎn)交叉方式，有利于增大種群的多樣性，增大了得到優(yōu)良染色體的可能性，提高遺傳算法的局部搜索能力和收斂速度，具體操作如下。

（1）選擇父代染色體對(duì) A、B，用隨機(jī)數(shù)確定第一個(gè)交叉位點(diǎn) Y，Y □ [0, n-1]，接下來進(jìn)行循環(huán)交叉，其中n 為染色體的長度；

（2）從父代染色體A 第Y 個(gè)基因開始，獲得并交換與第Y 個(gè)基因在B 中的位置相對(duì)應(yīng)的基因值a。 然后再從A 中找到基因值a，得到對(duì)應(yīng)于B 中相同位置的基因值b，并交換； 以此類推，從A 中找到基因b……直到當(dāng)在B 中找到A 的第一個(gè)基因值時(shí)為止，循環(huán)交叉結(jié)束。

（3）如果整個(gè)搜索過程中，在另一條染色體中未找到相應(yīng)的基因，則可以交換該位置的基因即可。

如下所示，假設(shè)有下面兩個(gè)個(gè)體：

染色體A：2 4 5 3 8 9 6 1 7

染色體B：3 9 8 6 5 4 2 7 1

隨機(jī)選擇一個(gè)交叉點(diǎn)：

找到匹配基因, 交叉算子查找操作：

接著繼續(xù)交叉交換操作：

圖4：變異操作

圖5：種群進(jìn)化情況

直至沒有匹配交叉完成, 交叉算子執(zhí)行結(jié)果：

2.4.3 變異算子

如圖4 所示，變異操作是將種群中的每個(gè)染色體都將以概率Pm 進(jìn)行突變。變異概率太小不利于產(chǎn)生新個(gè)體，對(duì)種群的多樣性有影響，失去操作的意義。但是變異概率太大也會(huì)使基因的遺傳變的不穩(wěn)定，優(yōu)良的基因比較容易被破壞。根據(jù)遺傳學(xué)原理，基因突變是一個(gè)小概率事件，在遺傳算法中，變異算子對(duì)種群的影響也應(yīng)遠(yuǎn)遠(yuǎn)小于交叉算子。一般建議變異概率取值小于0.2。

變異算子主要解決兩個(gè)問題，一是如何確定變異位置，另一個(gè)是如何進(jìn)行基因變異。具體的變異算法與基因編碼方式有關(guān)。本文采用單點(diǎn)變異，即對(duì)基因編碼隨機(jī)選擇一個(gè)點(diǎn)，以隨機(jī)概率進(jìn)行變異運(yùn)算。確定變異概率Pm，產(chǎn)生隨機(jī)數(shù)rand(1)，當(dāng)rand(1)< Pm 時(shí)，執(zhí)行變異操作。

變異操作的基本步驟如下：

（1）設(shè)定變異概率；

（2）隨機(jī)生成一個(gè)概率，如果大于變異概率就進(jìn)行變異操作；

（3）隨機(jī)產(chǎn)生兩個(gè)突變位置，進(jìn)行基因交換；

（4）當(dāng)處理完所有染色體對(duì)，結(jié)束操作。

2.4.4 算法終止準(zhǔn)則

本文設(shè)置算法迭代次數(shù)來停止算法，但當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到一定的閾值不再變化，即最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，算法也將終止。一般將代數(shù)設(shè)置為50-100 代。

下面描述改進(jìn)后的遺傳算法的主要步驟，具體過程如下所示。

算法：改進(jìn)遺傳算法

(1)定義結(jié)構(gòu)體及相關(guān)參數(shù)種群規(guī)模Popu_size，軟件模塊的數(shù)量Chromosome_length，通用處理器的數(shù)量m。

(2)Initialize() //初始化種群

(3)//進(jìn)行迭代

3 算法結(jié)果分析

本人設(shè)置算法中的參數(shù)如下：負(fù)載最大Uh 為 85%，最小UL為 10%。初始種群大小為 50，即初始化50 條染色體，迭代次數(shù)設(shè)置為90。迭代結(jié)果如圖5。

圖5 中，橫軸表示迭代次數(shù)，縱軸表示每一次迭代所得到的負(fù)載均衡度。隨著迭代過程的進(jìn)行，算法朝著優(yōu)質(zhì)解的方向進(jìn)化。從圖中可以看出當(dāng)種群迭代進(jìn)化到86 代時(shí)，個(gè)體適應(yīng)度函數(shù)值不在變化，算法收斂，并保持平均個(gè)體適應(yīng)度為0.184。此時(shí)對(duì)精英個(gè)體染色體進(jìn)行解碼就得到軟件模塊在物理機(jī)上的部署方案。

4 結(jié)語

本文設(shè)計(jì)了新一代船舶分布式系統(tǒng)軟件部署策略，對(duì)軟件模塊到硬件通用處理器映射問題，提出了從負(fù)載均衡的角度進(jìn)行分析。并針對(duì)建立的帶約束條件單一目標(biāo)最優(yōu)化問題數(shù)學(xué)模型，采用遺傳算法對(duì)其求解。本文還對(duì)求解過程中的編碼方法，遺產(chǎn)算子等根據(jù)數(shù)據(jù)特性進(jìn)行優(yōu)化改進(jìn)，提高算法的收斂速度及全局搜索精度。并且實(shí)驗(yàn)結(jié)果顯示算法收斂，結(jié)果有效，最終得到了負(fù)載均衡最優(yōu)的軟件模塊部署方案。