軟件發(fā)布規(guī)劃遺傳算法探討

王志剛++高磊

摘 要：好的軟件發(fā)布規(guī)劃可以有效改善軟件質(zhì)量，降低開發(fā)費(fèi)用。然而，軟件發(fā)布規(guī)劃是一個不良問題，適宜采用進(jìn)化方法求解。遺傳算法是一種進(jìn)化方法，其基本原則是“優(yōu)勝劣汰，適者生存”，將問題中的個體看成染色體，通過遺傳變異等一系列模擬生物的進(jìn)化過程來尋求最優(yōu)解。將軟件發(fā)布規(guī)劃問題與遺傳算法相結(jié)合，構(gòu)造可行的遺傳變異進(jìn)化方式和遺傳算法，為實際求解軟件發(fā)布規(guī)劃問題提供可行操作。

關(guān)鍵詞關(guān)鍵詞：軟件發(fā)布規(guī)劃；進(jìn)化；遺傳算法；染色體

DOIDOI：10.11907/rjdk.162416

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：16727800（2016）011005603

0 引言

軟件發(fā)布規(guī)劃問題中存在許多不確定因素，是一種典型的不良問題，該問題也是幾十年來許多計算機(jī)科學(xué)家致力研究的一個問題。較早研究軟件最優(yōu)發(fā)布問題的是A·Goel和K·Okumoto，他們提出了軟件可靠性GO 模型，在此基礎(chǔ)上，還提出了軟件期望總費(fèi)用模型；GO模型成為很多軟件科研人員后續(xù)研究和改進(jìn)的基礎(chǔ)。Koch和Kubat從成本和利潤角度出發(fā)，提出了一種基于JM的可靠性模型，并提出了懲罰費(fèi)用概念[1]。文獻(xiàn)[2]對軟件發(fā)布過程中的關(guān)鍵因素進(jìn)行了研究，在軟件安全生命周期的基礎(chǔ)上提出了一個改進(jìn)的適合于中小型企業(yè)的軟件安全開發(fā)流程。Saliu O和Ruhe G[3]提出了基于進(jìn)化的軟件發(fā)布決策支持模型。目前這些軟件發(fā)布決策模型中存在的不足是對軟件發(fā)布規(guī)劃過程中難以定性的軟因素沒有進(jìn)行全面考量。

本文在軟件發(fā)布規(guī)劃問題形式化的基礎(chǔ)上，運(yùn)用遺傳算法研究軟件發(fā)布規(guī)劃問題，探討遺傳算法在軟件發(fā)布規(guī)劃求解時的算法適應(yīng)性問題及處理流程。遺傳算法的逐步適應(yīng)和多樣化，也使其適合解決軟件發(fā)布規(guī)劃這類不良問題。

1 基本思想

遺傳算法從一個初始種群開始，隨機(jī)全局搜索，它遵循“適者生存，優(yōu)勝劣汰”的生物學(xué)進(jìn)化原理，對優(yōu)化的種群解集進(jìn)行優(yōu)化篩選與迭代，不斷進(jìn)化，最終得到接近最優(yōu)的解。在每一輪進(jìn)化開始之前，需要查找和選擇當(dāng)前種群中適應(yīng)度較大的個體，適應(yīng)度越大說明基因越好。然后借助遺傳算子進(jìn)行組合交叉變異等操作，從而得到新的種群；種群中適應(yīng)度低的個體將被淘汰掉，其整體的適應(yīng)度也會不斷提高，迭代過程直到滿足條件為止；新生成的種群比父代更加優(yōu)秀，能更好地適應(yīng)生存環(huán)境；最終獲得的種群將是歷代種群中最優(yōu)秀的，通過解碼還原便得到解決問題的近似最優(yōu)解。遺傳進(jìn)化的每個步驟被抽象為數(shù)學(xué)運(yùn)算過程，種群中的個體稱為染色體，用一串符號來代替。算法開始時隨機(jī)初始化一個N在 150～500 之間的種群（父個體 1、父個體 2…父個體 N），并計算每個個體的適應(yīng)度函數(shù)，再根據(jù)優(yōu)化原則衍生進(jìn)化與計算下一代。

1.1 編碼方法

編碼方法影響基因空間到問題表現(xiàn)空間的映射和遺傳算子對個體的操作。目前針對不同問題有多種不同的編碼方式，常用的編碼有二進(jìn)制、實數(shù)、證書或者字母排列和一般數(shù)據(jù)結(jié)構(gòu)；根據(jù)結(jié)構(gòu)不同還可以分為一維或二維編碼。

1.2 算法的基本操作

遺傳基因產(chǎn)生子代的過程有選擇、交叉和變異等三種操作。一般的運(yùn)算過程會用到其中的2～3種操作。

（1）選擇。又稱復(fù)制，是在父代種群中選取優(yōu)秀的個體來生產(chǎn)新的種群。選擇目的是讓優(yōu)良的個體有機(jī)會通過配對交叉繁殖遺傳到下一代。選擇策略跟編碼方式無關(guān)，由適應(yīng)度決定，根據(jù)個體的適應(yīng)度值以一定的規(guī)則或方法來選擇優(yōu)良的個體，主要原則是按適應(yīng)度比例或者排序進(jìn)行計算。

輪盤賭算法[4]是一種常用的回放式隨機(jī)取樣方法。在該算法作用下，每個染色體進(jìn)入下一代的概率是它的適應(yīng)度值在所有染色體適應(yīng)度值之和中占的比例，適應(yīng)度越高被選中的可能性就越大，進(jìn)入下一代的機(jī)會也越大。每個染色體在輪盤中所占扇區(qū)面積和其適應(yīng)度成正比；隨機(jī)轉(zhuǎn)動輪盤，當(dāng)輪盤停止轉(zhuǎn)動時指針?biāo)干葏^(qū)對應(yīng)的個體被選中。這個方法選中適應(yīng)度比較高的個體的機(jī)會較多，但也存在問題，由于種群規(guī)模限制和隨機(jī)操作等原因，使得個體實際被選中的次數(shù)與期望值之間可能存在一定的誤差，適應(yīng)度相近的個體不一定會被選中，適應(yīng)度小的個體也有機(jī)會被選中，這樣保證了群體的多樣性。

選擇操作還有（μ+λ）選擇、競爭選擇、穩(wěn)態(tài)復(fù)制、排序與變換比例和共享等。

（2）交叉。所謂交叉是指按某種方式交換兩個相互配對染色體的部分基因，從而產(chǎn)生兩個新的染色體。交叉運(yùn)算是遺傳算法區(qū)別于其它進(jìn)化運(yùn)算的重要特征。

交叉運(yùn)算首先需運(yùn)用隨機(jī)方式將種群中的染色體進(jìn)行兩兩配對，如果種群中有N個染色體，將這N個染色體配成N/2對，交叉操作在這些配好對的染色體對之間進(jìn)行。

（3）變異。選擇和交叉操作并不能保證不遺漏一些重要的遺傳信息，變異操作能較好地減少遺漏。變異操作首先在群體中隨機(jī)選擇一個染色體，然后以一定的概率隨機(jī)改變其編碼串中某個碼位的值，這個概率值介于0.001與0.1之間，稱之為變異概率。[5]

自然界中，生物個體由于偶然因素的作用發(fā)生基因突變，可能導(dǎo)致染色體的適應(yīng)度增強(qiáng)或降低，但能增加生物遺傳基因的多樣性。遺傳算法中的變異雖然沒有交叉操作那么重要，卻為產(chǎn)生新個體提供了機(jī)會，可起到恢復(fù)位串多樣性的作用，通過和交叉運(yùn)算相配合能適當(dāng)提高遺傳算法的搜索效率。

變異方法主要有基本位變異、有效基因變異、自適應(yīng)有效基因變異、概率自調(diào)整變異、均勻變異和非均勻變異等。其中基本位變異相對簡單和常用。

1.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)（評價函數(shù)）是根據(jù)目標(biāo)函數(shù)確定的用于區(qū)分群體總個體好壞的標(biāo)準(zhǔn)，是算法演化過程的驅(qū)動力和自然選擇的重要依據(jù)。適應(yīng)度函數(shù)的值一般為非負(fù)，因為在絕大多數(shù)情況下都期望適應(yīng)度值越大越好。而目標(biāo)函數(shù)則正負(fù)都有可能，也即求最大值或最小值問題，還有多目標(biāo)同時需要優(yōu)化的情況?；谝陨显?，需要將目標(biāo)函數(shù)與適應(yīng)度函數(shù)進(jìn)行一定轉(zhuǎn)換，以滿足適應(yīng)度函數(shù)的要求。染色體適應(yīng)度值的計算方法如下：

（1）對染色體編碼串解碼解析處理，獲得染色體的表現(xiàn)型。

（2）用目標(biāo)函數(shù)計算表現(xiàn)型的值。

（3）根據(jù)問題的類型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出染色體的適應(yīng)度值。

2 軟件發(fā)布規(guī)劃問題的遺傳進(jìn)化描述

不良問題存在很多不確定性因素使得研究的問題很難描述和得以解決。這類問題主要有兩個特點(diǎn)：一是沒有明確的形式化方法用以表達(dá)問題；二是沒有明確的停止規(guī)則。依據(jù)這兩個特點(diǎn)可以將軟件發(fā)布規(guī)劃劃為不良問題[6]。進(jìn)化是一個逐漸求精和力求多樣化的過程，其計算算法是一種軟計算方法，涉及計算搜索、學(xué)習(xí)、優(yōu)化和建模方法等。在決策問題求解過程中，所有元素都會不斷發(fā)生變化，所以決策問題的演化，適宜采用進(jìn)化算法推導(dǎo)。

軟件發(fā)布規(guī)劃決策變量用f（i）來表示某個特征，則N個特征集合是{f（1），f（2），…，f（N）}，規(guī)劃在K個發(fā)布計劃中發(fā)布。這個發(fā)布規(guī)劃的特征用決策向量X來描述，X=（x（1），x（2），…，x（N）），如果特征f（i）在第k次發(fā)布，則x（i）=k[7]。

規(guī)劃中的某個特征發(fā)布階段的值即x（i）對應(yīng)著遺傳算法的基因，向量X構(gòu)成一個染色體，通過遺傳算法的迭代進(jìn)化計算過程產(chǎn)生的最終后代，便是軟件發(fā)布規(guī)劃問題所需要的解集。

3 求解軟件發(fā)布規(guī)劃問題的遺傳算法設(shè)計

3.1 算法整體流程

基于遺傳算法的軟件發(fā)布規(guī)劃問題的求解過程如下：

（1）初始化參數(shù)。

（2）隨機(jī)創(chuàng)建n個染色體，構(gòu)造種群。

（3）檢測種群沖突，若有沖突則消除，無則進(jìn)入（4）。

（4）計算染色體的適應(yīng)度值，若達(dá)到終止條件則轉(zhuǎn)到（8）。

（5）根據(jù)計算得到的適應(yīng)度值進(jìn)行選擇操作，得到中間代。

（6）選擇符合要求的個體進(jìn)行交叉和變異等操作。

（7）用新種群替換舊種群，轉(zhuǎn)到（3）。

（8）對獲得的解集進(jìn)行人工評估，選出最優(yōu)方案。

算法流程如圖1所示。

3.2 編碼方式

為了適應(yīng)軟件發(fā)布規(guī)劃過程中的編碼和解碼，便于進(jìn)行遺傳迭代過程中交叉變異等操作，軟件發(fā)布規(guī)劃問題的解決過程采取實數(shù)編碼方式。

4 結(jié)語

本文運(yùn)用遺傳算法對軟件發(fā)布規(guī)劃問題進(jìn)行了研究，基于遺傳算法這種進(jìn)化的方法設(shè)計了解決軟件發(fā)布規(guī)劃獲取發(fā)布規(guī)劃決策的算法。從理論上講，通過最后的評估計算，求得的解也只是最優(yōu)推薦解，因為整個規(guī)劃過程中存在一些難以精確的因素，所以通過這種方式的計算也只能是盡力達(dá)到最優(yōu)。

參考文獻(xiàn)：

[1] 胡海宏.軟件可靠性模型與軟件最優(yōu)發(fā)布問題的研究[D].南京：南京郵電大學(xué)，2011.

[2] 馮博.軟件安全開發(fā)關(guān)鍵技術(shù)的研究和現(xiàn)實[D].北京：北京郵電大學(xué)，2010.

[3] SALIU O， RUHE G. Supporting software release planning decisions for evolving systems[C].Proceedings of the 29th IEEE/NASA Software Engineering Workshop. Greenbelt， MD， USA， 2005：1424.

[4] 謝景燕， 安金霞， 朱紀(jì)洪.考慮不完美排錯情況的NHPP類軟件可靠性增長模型[J]. 軟件學(xué)報，2010（5）：942949.

[5] 汪曉飛.基于多維編碼方案的遺傳算法在高校排課系統(tǒng)中的應(yīng)用[D].成都：四川師范大學(xué)，2008.

[6] 王志剛，高磊.軟件發(fā)布規(guī)劃的迭代求解過程[J].現(xiàn)代計算機(jī)，2013（12）：3941.

[7] 王志剛，高磊.軟件發(fā)布規(guī)劃的形式化探討[J].計算機(jī)時代，2013（12）：1214.

[8] 王志剛，高磊.軟件發(fā)布規(guī)劃案例研究[J].軟件導(dǎo)刊，2014（12）：13.

[9] 胡華軍.軟件最優(yōu)發(fā)布時間決策研究[D].成都：電子科技大學(xué)，2009.

[10] ZIY H， RICHARDSON DJ， KLSCH R. The uncertainty principle in software engineering[R]. Technical report UCITR9633， University of California， Irvine， 1996.

[11] CARLSHAMRE P. Release planning in marketdriven software product development：provoking an understanding[J]. Requirements Engineering，2002（3）：139151.

[12] RUHE G， NGOTHE A. Hybrid intelligence in software release planning[J]. International journal on hybrid intelligent systems. 2004（1）：99110.

[13] DU G， RICHTER M， AND RUHE G. An explanation oriented dialogue approach and its application to wicked planning problems[J]. Journal of Computing and informatics， 2006（25）：10011027.

[14] 鄧鐵清，任艮全，劉英博. 基于遺傳算法的工作流個人工作列表資源調(diào)度[J].軟件學(xué)報，2012， 23（7）：17021716.

[15] 滕云龍.軟件可靠性與費(fèi)用模型的研究[D].成都：電子科技大學(xué)，2008.

[16] 楊標(biāo). 軟件可靠性模型與軟件最優(yōu)發(fā)布問題的研究[D].成都：電子科技大學(xué)，2007.

[17] 馮靜，朱小冬，甘茂治.軟件發(fā)布周期費(fèi)用估算方法研究[J]. 微計算機(jī)信息，2006，22（7）：288290.

[18] 劉甜.軟件發(fā)布機(jī)制的研究與應(yīng)用[D]. 石家莊：石家莊鐵道大學(xué)，2014.

[19] 許琦.基于遺傳算法的高校排課問題的研究[D].廣州：華南理工大學(xué)，2012.

[20] 李云.基于遺傳算法的動態(tài)路徑優(yōu)化[D].太原：太原理工大學(xué)，2013.

（責(zé)任編輯：陳福時）