軟件構(gòu)件選擇方法研究

賴曉燕,林 娟

(1.福建農(nóng)林大學(xué) 金山學(xué)院， 福建 福州 350002;2.福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院， 福建 福州 350002)

軟件構(gòu)件選擇方法研究

賴曉燕1,林 娟2

(1.福建農(nóng)林大學(xué) 金山學(xué)院， 福建 福州 350002;2.福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院， 福建 福州 350002)

為了有效地進(jìn)行軟件構(gòu)件選擇，將軟件構(gòu)件選擇分成單構(gòu)件選擇和多構(gòu)件選擇兩類問(wèn)題.針對(duì)單構(gòu)件選擇問(wèn)題，把改進(jìn)的Vague集引入構(gòu)件質(zhì)量評(píng)價(jià)，通過(guò)評(píng)價(jià)給出構(gòu)件質(zhì)量的優(yōu)劣排序，將多構(gòu)件選擇問(wèn)題映射為一個(gè)多選擇背包問(wèn)題，提出一種混合的自適應(yīng)遺傳算法，該算法在迭代初期采用固定的交叉概率和變異概率，在迭代末期采用改進(jìn)的自適應(yīng)遺傳算法.通過(guò)仿真實(shí)驗(yàn)表明，與其他算法比較該算法具有較好的全局尋優(yōu)能力和執(zhí)行效率.

單構(gòu)件選擇；Vague集；構(gòu)件質(zhì)量評(píng)價(jià)；多構(gòu)件選擇；自適應(yīng)遺傳算法

基于構(gòu)件的軟件開(kāi)發(fā)(Component-based Software Development, CBSD)通過(guò)對(duì)已有構(gòu)件的復(fù)用和組裝來(lái)構(gòu)建新的軟件系統(tǒng)，大幅度的降低了軟件開(kāi)發(fā)成本，提高了軟件開(kāi)發(fā)效率，是目前主流的軟件開(kāi)發(fā)方法.隨著CBSD技術(shù)的日益成熟，在開(kāi)放的互聯(lián)網(wǎng)中分布了大量的構(gòu)件，如何快速、有效地選擇合適的構(gòu)件，是基于構(gòu)件的軟件工程(Component-based Software Engineering, CBSE)所面臨的首要問(wèn)題.

目前，在軟件構(gòu)件選擇方面的研究已經(jīng)取得了一些成果，文獻(xiàn)[1]提出了基于場(chǎng)景匹配的可信構(gòu)件選擇方法，文獻(xiàn)[2]提出了一種滿足用戶可信度期望的構(gòu)件選擇方法，文獻(xiàn)[3]提出了基于非線性模糊質(zhì)量功能展開(kāi)的構(gòu)件選擇模型.上述文獻(xiàn)從不同角度探討了軟件構(gòu)件的選擇方法，為構(gòu)件選擇方法的研究提供了重要的參考，但是現(xiàn)有的方法大多針對(duì)單個(gè)構(gòu)件的選擇，對(duì)于多構(gòu)件選擇的研究甚少，文獻(xiàn)[4]指出了多構(gòu)件選擇為特定約束下的組合優(yōu)化問(wèn)題，但并沒(méi)有建立具體的實(shí)現(xiàn)模型.按選擇構(gòu)件的數(shù)量可將用戶分為兩種：選擇單個(gè)構(gòu)件用戶和選擇多個(gè)構(gòu)件用戶，而在具體操作過(guò)程中，選擇單構(gòu)件的用戶通過(guò)檢索技術(shù)在構(gòu)件庫(kù)中檢索出的滿足用戶基本要求的構(gòu)件少則幾十種，多則幾百種，而多構(gòu)件選擇用戶的檢索結(jié)果則達(dá)上千種，因而，如何在檢索結(jié)果集中挑選出最滿意的目標(biāo)構(gòu)件或構(gòu)件組合具有非常重要的現(xiàn)實(shí)意義.基于此，本文分別對(duì)單構(gòu)件和多構(gòu)件選擇問(wèn)題進(jìn)行研究，并給出相應(yīng)的構(gòu)件選擇方法.

1 單構(gòu)件選擇

1.1 單構(gòu)件評(píng)價(jià)與選擇

基于構(gòu)件組裝的軟件產(chǎn)品的質(zhì)量很大程度依賴于構(gòu)件的質(zhì)量.面對(duì)眾多的構(gòu)件產(chǎn)品，構(gòu)件質(zhì)量是用戶進(jìn)行構(gòu)件選擇的重要依據(jù).因此，為了選擇合適的單個(gè)構(gòu)件，必須對(duì)符合用戶需求的批量構(gòu)件進(jìn)行質(zhì)量評(píng)價(jià)，并根據(jù)評(píng)價(jià)的結(jié)果對(duì)構(gòu)件進(jìn)行優(yōu)劣排序.但是目前針對(duì)構(gòu)件質(zhì)量的有效評(píng)價(jià)模型比較缺乏，為此，本文提出一種基于改進(jìn)Vague集的構(gòu)件質(zhì)量評(píng)價(jià)模型，為用戶選擇構(gòu)件提供一種度量參考.

1.2 Vague集的改進(jìn)

構(gòu)件質(zhì)量評(píng)價(jià)是涉及多指標(biāo)的決策，多數(shù)的指標(biāo)具有模糊性和不確定性，為了增加決策的柔性，引入Vague集，它是模糊集的一個(gè)擴(kuò)展，可以同時(shí)表示評(píng)價(jià)者肯定、否定兩個(gè)方面的信息，而改進(jìn)的Vague集除了可以同時(shí)考慮隸屬度、非隸屬度，還增加了猶豫度，描述了人類對(duì)事物的認(rèn)知過(guò)程中存在不同程度的猶豫的現(xiàn)象，能更客觀地刻畫(huà)事物的模糊性本質(zhì).

定義1 設(shè)μA(x),νA(x),πA(x)分別表示x關(guān)于A的隸屬度，非隸屬度和猶豫度，則稱

A={<μA(x),νA(x)>|x∈X,X≠Φ}

(1)

d(α1,α2,…,αn)=

(2)

(3)

為方案的貼近度.

1.3 基于改進(jìn)Vague集的構(gòu)件質(zhì)量評(píng)價(jià)與選擇

1.3.1 確定評(píng)價(jià)指標(biāo)體系及權(quán)重系數(shù)

結(jié)合ISO/IEC25010軟件質(zhì)量模型，參照文獻(xiàn)[6]中軟件構(gòu)件質(zhì)量特性與子特性的選擇需求，通過(guò)增加質(zhì)量特性、質(zhì)量子特性，甄選、裁剪子特性，構(gòu)建了兩級(jí)的構(gòu)件質(zhì)量評(píng)價(jià)指標(biāo)體系見(jiàn)表1.

表1 構(gòu)件質(zhì)量評(píng)價(jià)體系

質(zhì)量特性子特性功能性適合性、準(zhǔn)確性、互操作性、安全性可靠性成熟性、容錯(cuò)性、易恢復(fù)性易用性易理解性、易操作性、吸引性效率時(shí)間特性、資源利用性維護(hù)性易分析性、易改變性、穩(wěn)定性、易測(cè)試性可移植性適應(yīng)性、共存性、易替換性可復(fù)用性接口成熟性、易組裝性、獨(dú)立性、通用性、演化兼容性

權(quán)重系數(shù)是指標(biāo)重要程度的度量，為了減少權(quán)重確定的主觀性和盲目性，本文參照文獻(xiàn)[7]中的基于改進(jìn)的層次分析法與專家群體決策相結(jié)合的方法，確定了二級(jí)指標(biāo)體系的權(quán)重.

第一級(jí)指標(biāo)體系U的權(quán)重向量為

(4)

第二級(jí)指標(biāo)體系Ui的權(quán)重向量為

(5)

其中i=1,…,n，ni為質(zhì)量特性Ui所對(duì)應(yīng)的質(zhì)量子特性的個(gè)數(shù).

1.3.2 構(gòu)造二級(jí)決策矩陣

(6)

其中ni為質(zhì)量特性Ui所對(duì)應(yīng)的質(zhì)量子特性的個(gè)數(shù).

根據(jù)(2)式，可以得到第二級(jí)指標(biāo)的綜合屬性值di:

(7)

所有的第二級(jí)指標(biāo)的綜合屬性值構(gòu)成了第一級(jí)指標(biāo)的決策矩陣D：

(8)

根據(jù)(2)式，可以得到第一級(jí)指標(biāo)的綜合屬性值d：

(9)

1.3.3 計(jì)算貼近度及排序

根據(jù)式(3)，分別計(jì)算m個(gè)構(gòu)件最終評(píng)價(jià)值dCk(k=1,2,…，m)的貼近度，并按照貼近度的大小進(jìn)行排序.

2 基于混合的自適應(yīng)遺傳算法的多構(gòu)件選擇

2.1 多構(gòu)件選擇問(wèn)題

在組裝應(yīng)用系統(tǒng)的過(guò)程中，為了實(shí)現(xiàn)一個(gè)較復(fù)雜的任務(wù)，用戶往往需要同時(shí)選擇不同類型的多個(gè)構(gòu)件.假設(shè)某用戶為了實(shí)現(xiàn)一個(gè)較大的任務(wù)，需要功能獨(dú)立，低耦合的M個(gè)構(gòu)件，但是考慮到成本問(wèn)題，經(jīng)費(fèi)限定為COST千元.多構(gòu)件選擇過(guò)程為：首先該用戶在構(gòu)件庫(kù)中基于功能刻面分類檢索，得到M類構(gòu)件，其中第i類中有Ni個(gè)不同的構(gòu)件；然后該用戶從每一類中選擇一個(gè)構(gòu)件，每類必須且只能選擇一個(gè)構(gòu)件，將得到一個(gè)M個(gè)構(gòu)件的組合，為了獲得最高的性價(jià)比，該組合構(gòu)件的費(fèi)用在COST之內(nèi)，但是組合構(gòu)件的綜合評(píng)價(jià)值最高.因此，多構(gòu)件選擇是一個(gè)多選擇背包問(wèn)題，為0/1背包問(wèn)題的其中一種變形，被定義為有附加約束的背包問(wèn)題，多構(gòu)件選擇的數(shù)學(xué)模型描述如下：

(10)

(11)

(12)

其中，cij表示第i類中第j個(gè)構(gòu)件的評(píng)價(jià)值，wij表示第i類中第j個(gè)構(gòu)件的費(fèi)用，COST是購(gòu)買構(gòu)件的最大費(fèi)用.xij的值表示第i類中第j個(gè)構(gòu)件是否被選擇，如果被選擇則取1，否則取0.式(10)為目標(biāo)函數(shù)，目標(biāo)是構(gòu)件的綜合評(píng)價(jià)值最高，式(11)和式(12)為約束條件，分別表示總費(fèi)用限制和每類必須選擇一個(gè)構(gòu)件.

多構(gòu)件選擇是一個(gè)NP難問(wèn)題.下面采用改進(jìn)的自適應(yīng)遺傳算法來(lái)求解構(gòu)件組合的最優(yōu)解.

2.2 自適應(yīng)遺傳算法的改進(jìn)

2.2.1 交叉概率和變異概率的改進(jìn)

遺傳算法在求解0-1背包問(wèn)題上應(yīng)用廣泛，但在實(shí)際操作中，基本的遺傳算法存在容易早熟，收斂速度慢等缺點(diǎn)，使得求解質(zhì)量不高，執(zhí)行效率不理想.遺傳算法中控制搜索能力的交叉算子、變異算子的取值直接影響了算法的收斂速度和全局尋優(yōu)能力，交叉概率越大，產(chǎn)生新個(gè)體的速度越快，然而，具有低價(jià)、短定義距的高適應(yīng)度個(gè)體的模式串被破壞的可能性也越大，將不利于尋找全局最優(yōu)解，交叉概率越小，搜索過(guò)程越慢；對(duì)于變異概率，取值很小，將不利于生成新的模式，取值過(guò)大，遺傳算法就變成了隨機(jī)搜索方法.很多學(xué)者研究了如何在遺傳操作中控制交叉算子、變異算子，如傳統(tǒng)的自適應(yīng)遺傳算法中，交叉概率和變異概率可以隨著適應(yīng)度自動(dòng)改變，其定義公式如下[8-10]：

(13)

(14)

式中：fmax為群體中最大的適應(yīng)度值；favg為每代群體中的平均適應(yīng)度值；fbig為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；f為要變異個(gè)體的適應(yīng)度值.

從式(13)和式(14)可以看出，對(duì)于較差的個(gè)體，采用較大的交叉和變異概率，將其淘汰；對(duì)于較好的個(gè)體，采用較低的交叉和變異概率，使其優(yōu)良的性能得以保護(hù)；每代中的最優(yōu)個(gè)體的交叉和變異概率都為零，即不參與交叉和變異，直接保存下來(lái)，這種策略比較適合進(jìn)化的后期，在迭代的早期，最優(yōu)個(gè)體其極易“迷惑”遺傳算法，使其陷入局部解的陷阱.為此對(duì)交叉概率和變異概率作進(jìn)一步的改進(jìn)，定義如下：

(15)

其中，當(dāng)參與交叉、變異的個(gè)體的適應(yīng)度為最大值時(shí)，交叉概率為k1-k2，變異概率為k3，均為正數(shù)，可以確保最優(yōu)個(gè)體也參與交叉和變異運(yùn)算.另外，鑒于自適應(yīng)算法比較適合迭代末期的情況，本文將采用混合的自適應(yīng)遺傳算法，設(shè)定一個(gè)固定參數(shù)將遺傳算法分成初期和后期兩部分，當(dāng)?shù)螖?shù)小于固定參數(shù)時(shí)執(zhí)行固定的交叉概率和變異概率的遺傳操作，當(dāng)?shù)螖?shù)大于固定參數(shù)時(shí)，執(zhí)行自適應(yīng)遺傳算法.固定參數(shù)由多次實(shí)驗(yàn)獲得.

2.2.2 修復(fù)操作

遺傳算法中的交叉和變異操作都可以使群體多樣性得到維持，其中，變異操作是對(duì)個(gè)體串中的某些基因座上的基因值用其基因座的等位基因來(lái)替換，從而生成一個(gè)新的個(gè)體，保持了群體的多樣性.但是在基本遺傳算法中，變異操作的基因座是隨機(jī)確定的，替換過(guò)程也是在一定變異概率下的基因突變，是對(duì)單個(gè)個(gè)體的行為，如果將群體看成是一個(gè)矩陣，那么一個(gè)個(gè)體可以看成是一行，基本遺傳算法中的變異是從行的角度考慮的，但是這種操作方式?jīng)]有從列的方向即從整個(gè)群體的角度來(lái)進(jìn)行突變，進(jìn)而增加群體的多樣性.我們?cè)趯?shí)驗(yàn)過(guò)程中發(fā)現(xiàn)當(dāng)某一代群體中某一列取值都相同時(shí)，如圖1所示，假設(shè)群體規(guī)模為5，染色體長(zhǎng)度為8，在某一次遺傳操作后，所有5個(gè)個(gè)體的第4個(gè)基因座的基因值都為3，表示父代第4位的很多特征在子代丟失，按照通常的交叉和變異操作，在該位的基因?qū)⒑茈y有突破，群體多樣性提高很困難，從而發(fā)生不成熟收斂的現(xiàn)象.基于此，提出群體修復(fù)操作，以提高種群的多樣性.修復(fù)的方法是：在遺傳進(jìn)程進(jìn)入下一代之前，統(tǒng)計(jì)種群矩陣中每列的取值情況，若在某一列取值都相同時(shí)，則強(qiáng)制其中某一個(gè)(或某幾個(gè))個(gè)體在該列所對(duì)應(yīng)的基因在變異概率下發(fā)生突變.

個(gè)體1個(gè)體2個(gè)體3個(gè)體4個(gè)體51453748612436215716324846523727154133476

圖1 迭代中的群體

2.3 利用改進(jìn)的自適應(yīng)遺傳算法進(jìn)行多構(gòu)件選擇

2.3.1 編碼

根據(jù)多選擇背包問(wèn)題的特點(diǎn)，本文選用一維染色體編碼.一條染色體由m個(gè)基因組成，對(duì)應(yīng)m個(gè)構(gòu)件類，基因位置表示構(gòu)件的類，每一個(gè)基因的值表示所對(duì)應(yīng)構(gòu)件類中選出的一個(gè)構(gòu)件，如個(gè)體的第i個(gè)基因取值為k，表示從第i個(gè)構(gòu)件類中選擇了第k個(gè)構(gòu)件.如一條染色體序列為52381，表示在五個(gè)構(gòu)件類中，第一個(gè)構(gòu)件類中的第5個(gè)構(gòu)件，第二個(gè)構(gòu)件類中的第2個(gè)構(gòu)件，第三個(gè)構(gòu)件類中的第3個(gè)構(gòu)件，第四個(gè)構(gòu)件類中的第8個(gè)構(gòu)件，第五個(gè)構(gòu)件類中的第1個(gè)構(gòu)件被用戶選中.

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

適應(yīng)度函數(shù)是對(duì)群體中各個(gè)個(gè)體的環(huán)境適應(yīng)能力進(jìn)行評(píng)價(jià)的函數(shù)，是遺傳算法進(jìn)化過(guò)程的驅(qū)動(dòng)力.環(huán)境適應(yīng)能力強(qiáng)即適應(yīng)度高的個(gè)體相較于適應(yīng)度低的個(gè)體遺傳到下一代的概率較大，對(duì)于多構(gòu)件選擇來(lái)說(shuō)，適應(yīng)度越高，表示該個(gè)體的多構(gòu)件組合方式的綜合評(píng)價(jià)值越高，用戶對(duì)其越青睞.本文選擇用式(10)作為適應(yīng)度評(píng)價(jià)函數(shù)，其中每個(gè)構(gòu)件的評(píng)價(jià)值由上文中的單構(gòu)件評(píng)價(jià)方法獲得.

2.3.3 遺傳操作

遺傳操作是實(shí)現(xiàn)優(yōu)勝劣汰的過(guò)程，通過(guò)選擇、交叉和變異的遺傳操作，可以使得群體一代又一代地優(yōu)化，進(jìn)而逐步逼近最優(yōu)解.在對(duì)群體中個(gè)體的適應(yīng)度評(píng)估完后，可以進(jìn)行選擇操作，本文采用最基本的適應(yīng)度比例選擇機(jī)制——賭輪方式進(jìn)行隨機(jī)選擇，在選擇輪盤(pán)時(shí)，采用折半查找的方法提高搜索效率.

基于上述染色體編碼的特殊結(jié)構(gòu)，采用一致交叉算子.采用位點(diǎn)變異操作，其基本步驟如下：先從染色體編碼串中隨機(jī)挑選一個(gè)或多個(gè)變異點(diǎn)，然后在變異概率下，將變異點(diǎn)的基因替換為其他的等位基因，當(dāng)其他等位基因有多個(gè)時(shí)，通過(guò)隨機(jī)選擇，在構(gòu)件選擇中，位點(diǎn)變異是指在變異概率下從基因位置所對(duì)應(yīng)的構(gòu)件類中找一個(gè)任意構(gòu)件來(lái)替換當(dāng)前被選構(gòu)件.

在一致交叉、位點(diǎn)變異后檢查群體中所有個(gè)體同一個(gè)基因座的取值情況，如果出現(xiàn)同一個(gè)基因座取值都相同時(shí)，從群體中隨機(jī)挑選一個(gè)或多個(gè)的個(gè)體，在變異概率下進(jìn)行修復(fù)操作.

為了確保算法收斂及收斂效率，本文采用精英保留策略.改進(jìn)的自適應(yīng)遺傳算法的基本流程如圖2所示.

圖2 改進(jìn)遺傳算法的基本流程

3 算例研究

3.1 單構(gòu)件選擇實(shí)例

某用戶為了實(shí)現(xiàn)一個(gè)簡(jiǎn)單的任務(wù)需要一個(gè)構(gòu)件，在構(gòu)件庫(kù)中經(jīng)檢索找到了一批功能相近的構(gòu)件，假設(shè)在用戶期望的價(jià)格區(qū)間仍有3個(gè)軟件構(gòu)件(構(gòu)件1、構(gòu)件2和構(gòu)件3)供其選擇，運(yùn)用本文的基于改進(jìn)Vague集的構(gòu)件質(zhì)量評(píng)價(jià)方法對(duì)3個(gè)構(gòu)件進(jìn)行評(píng)價(jià)并給出排序結(jié)果.

3.1.1 確定兩級(jí)指標(biāo)的權(quán)重

采用改進(jìn)的層次分析法獲得的指標(biāo)權(quán)重與專家權(quán)重進(jìn)行線性相加后獲得的各個(gè)指標(biāo)的綜合權(quán)重為：

第一級(jí)指標(biāo)體系的權(quán)重向量

w=(w1,w2,…,w7)=

(0.3,0.22,0.08,0.21,0.08,0.07,0.04)

第二級(jí)指標(biāo)體系的權(quán)重向量

wU1=(w11,w12,…,w14)=

(0.4,0.3,0.15,0.15)，

wU2=(0.35,0.35,0.3)，

wU3=(0.4,0.5,0.1)，

wU4=(0.5,0.5)，

wU5=(0.3,0.3,0.2,0.2)，

wU6=(0.2,0.5,0.3)，

wU7=(0.2,0.3,0.2,0.1,0.2)

3.1.2 構(gòu)造二級(jí)決策矩陣

聘請(qǐng)10位相關(guān)領(lǐng)域的專家，對(duì)3個(gè)構(gòu)件的質(zhì)量子特性進(jìn)行評(píng)價(jià)，根據(jù)式(6)，可以得到功能性、可靠性、可復(fù)用性等7個(gè)質(zhì)量特性的決策矩陣：

按(2)式計(jì)算，可以得到第二級(jí)指標(biāo)的綜合屬性值:

3.1.3 計(jì)算貼近度并排序

從綜合屬性值可知，所有專家對(duì)3個(gè)構(gòu)件的評(píng)價(jià)是非常接近的，如，對(duì)于第一個(gè)構(gòu)件有71%專家是支持的，16%的專家是反對(duì)的，對(duì)于第二個(gè)構(gòu)件有70%的專家是支持的，17%的專家是反對(duì)的.因此，需要進(jìn)一步計(jì)算3個(gè)構(gòu)件的貼近度，根據(jù)式(3)可得

ε1=0.816，

ε2=0.805，

ε3=0.831

按照貼近度大小，3個(gè)構(gòu)件質(zhì)量的優(yōu)劣排序?yàn)椋簶?gòu)件3>構(gòu)件1>構(gòu)件2.

根據(jù)構(gòu)件質(zhì)量的優(yōu)劣排序，該用戶可以選擇質(zhì)量評(píng)價(jià)最高的第3個(gè)構(gòu)件.

3.2 多構(gòu)件選擇實(shí)例

為了驗(yàn)證本文提出混合的自適應(yīng)遺傳算法的有效性與可行性，對(duì)一個(gè)由8類構(gòu)件，每類構(gòu)件數(shù)目分別為{8,5,6,8,7,5,8,6}的多構(gòu)件選擇進(jìn)行仿真實(shí)驗(yàn)，見(jiàn)式(17).為了比較，使用DEV-C++編寫(xiě)了3套程序來(lái)求解：分別采用基本遺傳算法、自適應(yīng)遺傳算法、本文的混合的自適應(yīng)遺傳算法.為了更好的比較，三種算法的參數(shù)設(shè)置為一樣，種群規(guī)模為40，最大迭代次數(shù)為100，交叉概率pc=0.6，變異概率pm=0.15，自適應(yīng)遺傳算法和本文中混合的自適應(yīng)遺傳算法中的系數(shù)為k1=0.8,k2=0.3,k3=0.2,k4=0.1.

maxf(x)=3x11+4x12+5x13+4x14+8x15+

5x16+4x17+4x18+7x21+9x22+8x23+4x24+

5x25+5x31+6x32+9x33+8x34+4x35+6x36+

2x41+8x42+7x43+5x44+4x45+3x46+7x47+

8x48+8x51+5x52+7x53+9x54+7x55+4x56+

7x57+6x61+8x62+7x63+9x64+5x65+

6x71+9x72+7x73+4x74+3x75+7x76+9x77+

8x78+9x81+2x82+5x83+5x84+8x85+6x86

(17)

約束條件為

6x11+8x12+5x13+4x14+9x15+5x16+9x17+

3x18+6x21+5x22+3x23+5x24+9x25+

8x31+6x32+4x33+8x34+4x35+3x36+

9x41+4x42+8x43+9x44+4x45+9x46+

4x47+5x48+3x51+7x52+4x53+2x54+

3x55+8x56+5x57+8x61+3x62+2x63+8x64+

6x65+5x71+4x72+3x73+8x74+9x75+2x76+

4x77+4x78+2x81+9x82+2x83+6x84+4x85+

3x86≤38

x11+x12+x13+x14+x15+x16+x17+x18=1

x21+x22+x23+x24+x25=1

x31+x32+x33+x34+x35+x36=1

x41+x42+x43+x44+x45+x46+x47+x48=1

x51+x52+x53+x54+x55+x56+x57=1

x61+x62+x63+x64+x65=1

x71+x72+x73+x74+x75+x76+x77+x78=1

x81+x82+x83+x84+x85+x86=1

通過(guò)多次實(shí)驗(yàn)，本文提出的混合的自適應(yīng)遺傳算法引入的固定參數(shù)設(shè)置為20時(shí)，尋優(yōu)的平均結(jié)果最為理想，即在前20代采用固定的交叉、變異概率進(jìn)行遺傳操作，在20代以后采用本文改進(jìn)的自適應(yīng)遺傳算法進(jìn)行遺傳操作.利用本文的混合的自適應(yīng)算法運(yùn)行40次，可以求得該問(wèn)題的最優(yōu)值為70，共找到2個(gè)最優(yōu)解：{5,2,3,2,4,4,2,1}，{5,2,3,2,4,4,7,1}，表示在一定費(fèi)用的限制下，選擇第一類的第5個(gè)構(gòu)件、第二類的第2個(gè)構(gòu)件、第三類的第3個(gè)構(gòu)件、第四類的第2個(gè)構(gòu)件、第五類的第4個(gè)構(gòu)件、第六類的第4個(gè)構(gòu)件，第七類的第2個(gè)或第7個(gè)構(gòu)件、第八類的第1個(gè)構(gòu)件的多構(gòu)件組合方式最貼近用戶的需求.

對(duì)于多構(gòu)件選擇問(wèn)題，將本文的算法與基本遺傳算法、自適應(yīng)遺傳算法進(jìn)行比較，三種算法各進(jìn)行40次的運(yùn)算，平均適應(yīng)度隨迭代次數(shù)的變化曲線如圖3所示，三種算法的運(yùn)行對(duì)比結(jié)果見(jiàn)表2.

圖3 平均適應(yīng)值變化

從圖3 可知，本文的算法在較少的迭代次數(shù)下可以獲得較高的平均適應(yīng)度值，在相同的迭代次數(shù)下，本文算法獲得的群體平均適應(yīng)度最好，明顯高于另外兩種算法，自適應(yīng)遺傳算法的平均適應(yīng)度其次，基本遺傳算法的最差.

表2 三種算法比較

算法最優(yōu)值找到最優(yōu)解次數(shù)找到最優(yōu)解的概率基本遺傳算法7016次40%自適應(yīng)遺傳算法7018次45%混合的自適應(yīng)遺傳算法7027次67．5%

由表2可知，三種算法都可以找出最佳的多構(gòu)件組合，但是在找到最優(yōu)解的頻次上不同，本文的算法在40次的實(shí)驗(yàn)中，找到最優(yōu)解的次數(shù)可以達(dá)到27次，找到最優(yōu)解概率可達(dá)67.5%，比基本遺傳算法找到最優(yōu)解的概率40%提升了27.5%，比自適應(yīng)遺傳算法的求解概率也提升了22.5%，說(shuō)明本文的算法提高了求解質(zhì)量，算法有效.

4 結(jié)束語(yǔ)

如何從批量的構(gòu)件中選擇合適的單個(gè)構(gòu)件或構(gòu)件組合是CBSE的首要問(wèn)題，針對(duì)單個(gè)構(gòu)件選擇的基于改進(jìn)Vague集的構(gòu)件質(zhì)量評(píng)價(jià)模型，既考慮了指標(biāo)的模糊性，又考慮了評(píng)價(jià)中存在反對(duì)和不確定性的情況，實(shí)例表明該評(píng)價(jià)方法客觀合理，操作簡(jiǎn)便，可以推廣；針對(duì)多個(gè)構(gòu)件選擇的混合的自適應(yīng)遺傳算法大大提高了算法的尋優(yōu)能力.對(duì)交叉算子和變異算子的改進(jìn)，加快了算法的收斂速度，修復(fù)操作的實(shí)施增強(qiáng)了種群的多樣性.仿真實(shí)驗(yàn)表明，本文方法的求解質(zhì)量?jī)?yōu)于基本遺傳算法和自適應(yīng)遺傳算法，說(shuō)明采用混合的自適應(yīng)遺傳算法進(jìn)行多構(gòu)件選擇方法非常有效.

[1] 魏樂(lè)，趙秋云，舒紅平.一種基于場(chǎng)景匹配的可信構(gòu)件選擇方法[J].微電子學(xué)與計(jì)算機(jī)，2011，28(8)：176-179.

[2]馬華，張紅宇.結(jié)合可信度模糊評(píng)價(jià)與動(dòng)態(tài)聚類的構(gòu)件選擇[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(21):73-76.

[3] 孫劍，徐瑩.基于NF-QFD的構(gòu)件選擇方法[J]. 高師理科學(xué)刊,2013,33(5):24-28.

[4]盛津芳，王斌.基于FCD擴(kuò)展的多構(gòu)件選擇過(guò)程[J].計(jì)算機(jī)應(yīng)用,2007,27(4):860-862.

[5] 徐澤水.直覺(jué)模糊信息集成理論及應(yīng)用[M].北京：北京科學(xué)出版社，2008，13-15.

[6] 李曉麗，劉 超，金茂忠，等.《軟件構(gòu)件產(chǎn)品質(zhì)量》標(biāo)準(zhǔn)介紹[J].信息技術(shù)與標(biāo)準(zhǔn)化,2006(6):19:24.

[7]賀海波，陳立潮，張英俊，等.基于群體決策的軟件構(gòu)件質(zhì)量評(píng)價(jià)模型研究[J].計(jì)算機(jī)工程與設(shè)計(jì). 2010,31 (21):4 639-4 642.

[8]王娜，向鳳紅，毛劍琳.改進(jìn)的自適應(yīng)遺傳算法求解 0/1 背包問(wèn)題 [J]. 計(jì)算機(jī)應(yīng)用，2012，32(6)： 1 682 -1 684.

[9]梁旭,黃明,寧濤，等.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京：電子工業(yè)出版社，2014.

[10]鮑江宏.用遺傳算法實(shí)現(xiàn)罰函數(shù)法解多選擇背包問(wèn)題[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2008，29(17):4 518-4 521.

(編輯：劉寶江)

Research on software component selection methods

LAI Xiao-yan1, LIN Juan2

(1.Jinshan College, Fujian Agriculture and Forestry University， Fuzhou 350002, China;2.College of Computer and Information, Fujian Agriculture and Forestry University, Fuzhou 350002, China)

In order to select software component effectively, the software component selection is divided into two kinds of problem, one is single component selection and the other is multiple component selection. For the single component selection, improved vague set is introduced into the evaluation of component quality. By using the evaluation method the ranking of the component quality is given. Multiple component selection is mapped as the multiple-choice knapsack problem and we propose a hybrid adaptive genetic algorithm. In the algorithm, crossover probability and mutation probability are fixed in the early iterations, while in the last stage of iteration we use improved adaptive genetic algorithm. The simulation experiments show that comparisons with other algorithms the algorithm has strong ability of global optimization and high efficiency.

single component selection; Vague set; evaluation of component quality; multiple component selection; adaptive genetic algorithm

2015-05-12

福建省自然科學(xué)基金資助項(xiàng)目(2014J01219)；福建省教育廳基金A類資助項(xiàng)目(JA14110)

賴曉燕,女，lxyfj@163.com

1672-6197(2015)06-0025-07

TP

A