基于演化優(yōu)化的系統(tǒng)可靠性設(shè)計(jì).pdf

1、自六十年代以來，在電力系統(tǒng)、電子系統(tǒng)、軟硬件等系統(tǒng)設(shè)計(jì)中，可靠性作為一個(gè)重要指標(biāo)地位愈發(fā)突出，系統(tǒng)可靠性設(shè)計(jì)(system reliability design，SRD)也吸引了越來越多的科研工作者。近些年來，伴隨著工業(yè)化進(jìn)程中系統(tǒng)規(guī)模的不斷擴(kuò)大，如何設(shè)計(jì)更加可靠的系統(tǒng)已變得越來越重要。為了改進(jìn)系統(tǒng)的可靠性．有兩類問題需要更加有效地解決：一類是冗余分配問題(redundancy allocation problem，RAP)；另一類是測

2、試資源分配問題(testingresource allocation problem，TRAP)。在本論文中，我們用演化算法更好地解決了這兩類問題中的兩個(gè)難點(diǎn)問題，分別是多層冗余分配問題(multi—levelredundancy allocation problem，MLRAP)和多目標(biāo)測試資源分配問題(multi—objective testing resource allocation problem，MOTRAP)。
　　

3、 在過去的三十年里，冗余分配問題因其在各種系統(tǒng)中的應(yīng)用價(jià)值得到了廣泛關(guān)注。在冗余分配問題的研究中，絕大部分是以單層系統(tǒng)為研究對象。但是現(xiàn)實(shí)的系統(tǒng)一般包含了多個(gè)層次，從最高的系統(tǒng)層到最低的單元層。因此，研究多層冗余分配問題變得十分重要。在本論文之前解決多層冗余分配問題的算法中，缺乏細(xì)致的局部搜索過程。為了更進(jìn)一步地細(xì)致地探索解空間，我們設(shè)計(jì)了一個(gè)模因演算法(memetic algorithm)。作為演化算法的分支，模因演算法是結(jié)合了全局

4、搜索策略和局部啟發(fā)探索策略的群體搜索混合啟發(fā)式方法。模因演算法已經(jīng)被證實(shí)在解的質(zhì)量和搜索能力上比傳統(tǒng)的演化算法具有優(yōu)勢。我們在工作中，基于變量的分層屬性表示，首先設(shè)計(jì)了兩個(gè)寬度優(yōu)先的演化算子(寬度優(yōu)先交叉算子和寬度優(yōu)先變異算子)以及針對問題的局部搜索算子，然后將這些算子結(jié)合到模因演算法框架中，從而得到一個(gè)新穎的模因演算法。我們的模因演算法在性能上要比以往的其它算法中的的最好算法(分層遺傳算法)有明顯的性能提升。
　　 在多層系統(tǒng)

5、中，冗余度可以分配到任意層次上去，因此問題的解空間比單層冗余分配問題要大很多。通過對現(xiàn)存分層遺傳算法和模因演算法的解的結(jié)構(gòu)分析，我們可以看出這兩個(gè)算法的搜索區(qū)域是局限在某個(gè)局部范圍內(nèi)的，也就是說，這兩個(gè)算法的全局搜索能力較差。因?yàn)槎鄬尤哂喾峙鋯栴}的解空間十分巨大，約束控制能力將是解決此類問題的關(guān)鍵，同時(shí)如何快速地收斂到有潛力的區(qū)域也是全局搜索的根本要求。為了使我們的搜索過程更加高效，我們?yōu)闈摿^(qū)域外的解設(shè)計(jì)了一個(gè)全局修復(fù)算子(globa

6、l repair operator)。通過實(shí)驗(yàn)可以證明，這個(gè)專門的約束處理方法可以明顯提升在我們的工作之前存在的最好算法(分層遺傳算法)的全局搜索能力。隨后，我們將全局修復(fù)算子融入到我們的模因演算法中，得到一個(gè)新的算法，叫作全局修復(fù)模因演算法(GRo+MA)，這個(gè)新算法在多個(gè)系統(tǒng)上被證實(shí)是在現(xiàn)存的算法中最優(yōu)的算法。
　　 在有效地解決了困難的多層冗余分配問題后，我們關(guān)注系統(tǒng)設(shè)計(jì)中的另一個(gè)重要問題，測試資源分配問題(testing

7、 resource allocation problem)。我們把軟件系統(tǒng)作為本文的研究模型。今天，伴隨著軟件系統(tǒng)的復(fù)雜度和規(guī)模的不斷提升，如何合理分配有限的測試資源變得愈發(fā)重要和困難。傳統(tǒng)的測試資源分配問題只考慮一個(gè)目標(biāo)(可靠度值或測試代價(jià))。在本文中，測試資源分配問題被定義為兩個(gè)多目標(biāo)問題：第一個(gè)是同時(shí)考慮可靠度值和代測試價(jià)；第二個(gè)是在第一個(gè)的基礎(chǔ)上考慮總的資源消耗。在定義問題后，我們在兩個(gè)軟件系統(tǒng)上用一個(gè)著名的多目標(biāo)演化算法，即第

8、二代非支配排序演化算法(NondominatedSorting Genetic AlgorithmⅡ，NSGA—Ⅱ)去解決定義的多目標(biāo)問題。但是，實(shí)驗(yàn)結(jié)果告訴我們NSGA—Ⅱ并不能很好地解決第二類多目標(biāo)問題。因此，我們進(jìn)一步設(shè)計(jì)了一個(gè)基于調(diào)和距離的多目標(biāo)演化算法(Harmonic Distance BasedMulti—Objective Evolutionary Algorithm，HaD—MOEA)。通過在三個(gè)串并行系統(tǒng)和一個(gè)星狀系