基于集群計(jì)算的免疫優(yōu)化算法及其應(yīng)用研究.pdf

1、免疫優(yōu)化算法是受免疫學(xué)啟發(fā)，模擬自然免疫系統(tǒng)功能、原理和模型來解決復(fù)雜問題的一種新的智能計(jì)算方法，已經(jīng)廣泛應(yīng)用于各個(gè)領(lǐng)域。隨著信息技術(shù)的飛速發(fā)展，產(chǎn)生了越來越多的復(fù)雜海量數(shù)據(jù)，在應(yīng)用免疫優(yōu)化算法求解這些數(shù)據(jù)時(shí)要面臨提高解的質(zhì)量和求解速度等問題。近十年來，集群系統(tǒng)作為一種新的高性能計(jì)算平臺得到了長足的發(fā)展，基于集群的計(jì)算技術(shù)為解決上述問題提供了一條途徑。本文基于集群計(jì)算技術(shù)，將免疫算法應(yīng)用于求解特征選擇、圖像降維和裝箱等問題，提出了四種新

2、的算法和并行策略，主要工作概括如下：
　　 (1)針對數(shù)據(jù)挖掘和模式識別等領(lǐng)域的高維數(shù)據(jù)降維問題，提出了基于免疫記憶克隆的特征選擇算法。該算法利用抗體種群進(jìn)行全局搜索，通過設(shè)立記憶單元來保留歷史最好個(gè)體，并對其嵌入可控制搜索深度的局部搜索算子，用以加快抗體親和力成熟速度，同時(shí)對抗體種群和記憶單元采用不同的親合度函數(shù)以獲得更好的搜索能力。在MATLAB并行計(jì)算環(huán)境下，將該算法用于6個(gè)高維數(shù)據(jù)集進(jìn)行特征子集選擇，實(shí)驗(yàn)結(jié)果表明，與標(biāo)準(zhǔn)

3、遺傳算法相比新算法具有更低的復(fù)雜度和更好的搜索能力，其魯棒性也優(yōu)于經(jīng)典的串行浮點(diǎn)前向搜索算法。
　　 (2)針對封裝式特征選擇的耗時(shí)問題，提出了一種負(fù)載均衡的主從式并行免疫克隆模型。主進(jìn)程利用免疫克隆算法進(jìn)行特征選擇，從進(jìn)程并行計(jì)算個(gè)體親和度。為進(jìn)一步降低算法運(yùn)行時(shí)間，基于LPT和MULTIFIT設(shè)計(jì)了啟發(fā)式任務(wù)調(diào)度算法，首先基于時(shí)間復(fù)雜度預(yù)先估計(jì)種群中個(gè)體親和度的計(jì)算時(shí)間，然后按照個(gè)體的親和度計(jì)算時(shí)間利用提出的調(diào)度算法分配這些

4、個(gè)體到從進(jìn)程，由于考慮了負(fù)載均衡，相比直接利用數(shù)量分配個(gè)體的傳統(tǒng)方法能獲得更短的執(zhí)行時(shí)間。在Linux刀片集群上基于MPICH軟件對UCI數(shù)據(jù)集進(jìn)行特征子集選擇實(shí)驗(yàn)，特征子集采用最近鄰分類和留一法驗(yàn)證評價(jià)，結(jié)果表明該算法可有效降低實(shí)驗(yàn)時(shí)間，在40個(gè)進(jìn)程時(shí)效率最高可達(dá)75％。
　　 (3)基于生物免疫系統(tǒng)理論和消息傳遞接口提出了一種粗粒度并行免疫克隆算法，利用分布在多個(gè)處理器上的多個(gè)抗體種群同時(shí)并行搜索空間。為了避免算法早熟收斂和

5、提高種群多樣性，種群使用環(huán)狀通信拓?fù)浣Y(jié)構(gòu)，互相通過疫苗遷移算子來交流信息。對Brodatz紋理庫和真實(shí)SAR紋理圖像利用Contourlet變換提取能量特征，用該算法選出的特征子集采用最近鄰分類器評價(jià)，在Linux集群上的仿真結(jié)果表明算法性能優(yōu)于SFFS和SGA算法，且可有效降低實(shí)驗(yàn)時(shí)間，在13個(gè)處理器時(shí)效率最高可達(dá)91％。
　　 (4)為了提高求解一維裝箱問題解的性能和降低算法運(yùn)行時(shí)間，提出了一種并行免疫克隆裝箱算法。使用占優(yōu)