王志剛++高磊

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

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

DOIDOI：10.11907/rjdk.162416

中圖分類號(hào)：TP312

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

0 引言

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

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

1 基本思想

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

1.1 編碼方法

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

1.2 算法的基本操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 算法整體流程

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

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

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

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

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

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

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

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

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

算法流程如圖1所示。

3.2 編碼方式

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

[2] 馮博.軟件安全開(kāi)發(fā)關(guān)鍵技術(shù)的研究和現(xiàn)實(shí)[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ì)洪.考慮不完美排錯(cuò)情況的NHPP類軟件可靠性增長(zhǎng)模型[J]. 軟件學(xué)報(bào)，2010（5）：942949.

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

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

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

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

[9] 胡華軍.軟件最優(yōu)發(fā)布時(shí)間決策研究[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] 鄧鐵清，任艮全，劉英博. 基于遺傳算法的工作流個(gè)人工作列表資源調(diào)度[J].軟件學(xué)報(bào)，2012， 23（7）：17021716.

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

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

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

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

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

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

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