一種社會網(wǎng)絡(luò)搜索免疫優(yōu)化算法

摘 要：社會網(wǎng)絡(luò)搜索免疫優(yōu)化算法是在社會網(wǎng)絡(luò)體現(xiàn)出強大的信息搜索及傳播能力的基礎(chǔ)上，進一步提出的一種較為新型的免疫優(yōu)化算法。本課題筆者在分析社會網(wǎng)絡(luò)搜索與免疫克隆選擇算法的基礎(chǔ)上，進一步對基于社會網(wǎng)絡(luò)搜索模型的免疫優(yōu)化算法進行了探究，希望以此能夠?qū)ι鐣W(wǎng)絡(luò)搜索免疫優(yōu)化算法的了解提供理論依據(jù)。

關(guān)鍵詞：社會網(wǎng)絡(luò)搜索；免疫優(yōu)化算法；傳播能力

社會網(wǎng)絡(luò)搜索免疫優(yōu)化算法把優(yōu)化問題的求解當(dāng)中是信息的傳遞過程[1]。在免疫算法的尋優(yōu)進化過程中，所使用的模型為Kleinberg網(wǎng)絡(luò)模型，以網(wǎng)絡(luò)的結(jié)構(gòu)增長機制為依據(jù)，以分別的方式由短程對算子進行連接、由長程對算子進行連接，進一步將抗體種群當(dāng)中的新個體引入，在搜索進行在一定的時候，對長程連接搜索概率進行自適應(yīng)調(diào)整，以此使算法陷入局部極值情況得以有效規(guī)避，最終找出目標(biāo)的最優(yōu)解。鑒于此，本課題對“一種社會網(wǎng)絡(luò)搜索免疫優(yōu)化算法”進行分析與探究具有尤為深遠的重要意義。

1 社會網(wǎng)絡(luò)搜索與免疫克隆選擇算法分析

由Watts和Strogatz[2]所提出的小世界模型表示：短程連接，即為小世界情況，基于各類顯示網(wǎng)絡(luò)當(dāng)中是普遍存在的。但是，Kleinberg對WS小世界模型的數(shù)學(xué)分析結(jié)果表示：該網(wǎng)絡(luò)模型雖然據(jù)別短程連接，但是局部信息不能對這些短程連接進行構(gòu)建，換而言之便是Watts和Strogatz所提出的小世界模型不能解釋網(wǎng)絡(luò)的可搜索特性。Kleinberg對Watts和Strogatz小世界模型做了細(xì)微的改動，并第一次基于理論層面對這一問題進行研究，進而很好地解釋了網(wǎng)絡(luò)的可搜索特性。下面筆者利用Kleinberg網(wǎng)絡(luò)模型的建模方法，進一步對免疫優(yōu)化算法的尋優(yōu)進化過程進行構(gòu)造。

1.1 Kleinberg網(wǎng)絡(luò)搜索模型

Kleinberg J.所提出的是一種快速，且有效性高的搜索模型[3]。基于模型當(dāng)中，其節(jié)點分布在一個二維規(guī)則網(wǎng)格上，每一個節(jié)點和自身的全部鄰居相互連接；與此同時，模型當(dāng)中還具備少量的長程連接。如圖1，為基于網(wǎng)絡(luò)中節(jié)點α與鄰居的關(guān)系圖示。

Kleinberg對節(jié)點u與v之間的網(wǎng)絡(luò)距離下了定義，將d（u、v）作為兩節(jié)點間的網(wǎng)格步數(shù)，將u坐標(biāo)設(shè)為（i，j），v坐標(biāo)為（k，l），那么便有：d（u，v）=d（i，j），（k，l）=|k-i|+|l-j|。如圖1，常數(shù)p≥1視為節(jié)點u和它的網(wǎng)格距離為p的節(jié)點，以直接的方式連接，所連接的便是節(jié)點u的短程連接[4]。當(dāng)常數(shù)q≥1視為節(jié)點u和q個其他節(jié)點間存在長程連接。由此可見，基于圖1當(dāng)中，節(jié)點α存在四個距離為1的短程連接，同時還具備兩個距離為2的長程連接，與Watts、Strogatz小世界模型當(dāng)中的兩個節(jié)點之間均勻隨機地向長程連接加入存在明顯差異。基于Kleinberg模型當(dāng)中，其節(jié)點u與v兩者間具備長程連接的概率和[-d（u，v）]-α呈正相關(guān)性。其中，α為參數(shù)，在α為零的情況下，長程連接屬于均勻隨機分布，基于此種情況便存在Watts、Strogatz小世界模型。所以，對于Kleinberg模型可視為Watts、Strogatz小世界模型當(dāng)中的一種普遍化模式，在相隔較遠的節(jié)點之間，其長程連接的概率便越小。

1.2 免疫克隆選擇算法

克隆選擇學(xué)說是由Burnet等[5]人在1958年提出來得，主要的核心思想是：抗體是一種天然產(chǎn)物，抗原能夠產(chǎn)生選擇性反應(yīng)。在反應(yīng)過程中知識細(xì)胞克隆發(fā)生增殖，而產(chǎn)生的新群體擁有一樣的抗體特異性。當(dāng)中，一些細(xì)胞克隆會產(chǎn)生分化，主要分化為抗體，進一步生成細(xì)胞。另外，還存在一些細(xì)胞克隆轉(zhuǎn)化成為免疫記憶細(xì)胞，這些細(xì)胞會參與二次免疫反應(yīng)。對于克隆選擇來說，屬于生物免疫系統(tǒng)自適應(yīng)抗原刺激的一種動態(tài)過程，在此過程中表現(xiàn)出來多種生物特性，包括：學(xué)習(xí)、抗體多樣性及記憶等。而這些生物特性便是人工免疫系統(tǒng)加以借鑒等。有學(xué)者基于不同的角度對克隆選擇學(xué)說機理進行了模擬，進而提出了不一樣的克隆選擇算法。在使用傳統(tǒng)克隆選擇算法的基礎(chǔ)上，將基于Kleinberg網(wǎng)絡(luò)模型當(dāng)中的搜索機制引入，進一步對新算法進行構(gòu)造無疑是一種優(yōu)化方法。

1.3 基于Kleinberg模型的優(yōu)化搜索過程

結(jié)合圖1可知，Kleinberg網(wǎng)絡(luò)搜索模型是由一個長程連接子網(wǎng)與一個短程連接子網(wǎng)相互連接，進而構(gòu)成的網(wǎng)絡(luò)。Kleinberg J.表明：對于信息傳遞一類問題，可通過本地信息進一步傳達到目的地[6]。此搜索模型詮釋了客觀世界當(dāng)中諸多網(wǎng)絡(luò)基于運動過程中最具有效性的信息傳遞模式。所以，筆者在對其主要思想借鑒的基礎(chǔ)上，進而對新的免疫算法進行了構(gòu)建，希望能夠使工程優(yōu)化問題得到有效解決。

對最小值優(yōu)化問題進行考慮：minf（x），x=[x1，x2……xD]，x屬于RD；當(dāng)中D代表優(yōu)化函數(shù)的維數(shù)，此表達式為常規(guī)優(yōu)化問題提出了一個較為統(tǒng)一的數(shù)學(xué)模型，把整體候選解空間當(dāng)作是社會網(wǎng)絡(luò)當(dāng)中的搜索空間。當(dāng)中，每一個候選解等同于網(wǎng)絡(luò)當(dāng)中的一個節(jié)點，最小優(yōu)化問題的求解過程便是基于一個節(jié)點到目標(biāo)節(jié)點的搜索過程，也可以當(dāng)作“初始候選解→到全局最優(yōu)解”的信息傳遞過程[7]。鑒于此，可通過短程連接與長程連接搜索機制之間的構(gòu)造，與此同時與抗體克隆選擇學(xué)說相結(jié)合，進一步提出社會網(wǎng)絡(luò)搜索免疫優(yōu)化算法。

2 基于社會網(wǎng)絡(luò)搜索模型的免疫優(yōu)化算法探究

在免疫算法過程中，以多樣化的操作算子為渠道能夠使抗體的種群實現(xiàn)進化。在考慮到測試問題與約束條件，可使用二進制編碼方法，將抗體種群記為A={a1、a2……aNp}，進一步便能夠?qū)崿F(xiàn)SNSIA。

和免疫算法比較起來，SNSIA不只是單方面考慮到每一個抗體，然后實現(xiàn)克隆變異等相關(guān)免疫操作，而是對短程連接與長程連接進行引入，進行連接到機制當(dāng)中。對于短程連接操作來說，便等同于是在基于抗體節(jié)點當(dāng)中的有限鄰域內(nèi)搜索；對于長程連接，主要是在抗體變異的基礎(chǔ)上，進一步實現(xiàn)基因重組工序。這樣，便能夠讓基于種群當(dāng)中的多樣性實現(xiàn)優(yōu)化補充，長度連接操作等同于全局搜索[8]。正是通過短程連接與長程連接兩者之間的實效性配合，使基于算法的局部搜索與全局搜索均能夠得到有效實現(xiàn)。

3 結(jié)語

通過Kleinberg網(wǎng)絡(luò)模型的建模思想，對免疫算法的尋優(yōu)進化過程進行構(gòu)造，進而由短程連接算子與長程連接算子以分別的方式在抗體種群當(dāng)中的新個體中進行引入。在搜索進行到一定程度的情況下，通過自適應(yīng)的方法對長程連接搜索概率進行調(diào)整，以此使算法陷入局部極值的情況實現(xiàn)有效規(guī)避，這樣便能夠?qū)ふ业侥繕?biāo)的最優(yōu)解。無疑，本課題所提出的基于社會網(wǎng)絡(luò)搜索模型的免疫優(yōu)化算法更為優(yōu)化，能夠保持解的多樣性，同時具備收斂速度快、求解精度高等顯著優(yōu)勢。

[參考文獻]

[1]惠淑敏.基于影響強度的社會網(wǎng)絡(luò)搜索算法研究[J].圖書情報工作.2012，02：111-115.

[2]邱曉輝.陳羽中.一種面向社會網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的改進粒子群優(yōu)化算法[J].小型微型計算機系統(tǒng).2014，06：22-26.

[3]自動化技術(shù)、計算機技術(shù)[J].中國無線電電子學(xué)文摘.2010，06：16-22.

[4]張曉芳，李國徽，龐永杰.面向Web社會網(wǎng)絡(luò)搜索的人名同一性判斷[J].計算機工程與科學(xué).2012，09：128-134.

[5]朱玉，趙卿，梅艷.混沌免疫優(yōu)化RBF網(wǎng)絡(luò)在動態(tài)變形預(yù)測中的應(yīng)用[J].大地測量與地球動力學(xué).2012，05：53-57.

[6]戚玉濤，劉芳，常偉遠，馬曉亮，焦李成.求解多目標(biāo)問題的Memetic免疫優(yōu)化算法[J].軟件學(xué)報.2013，07：15-18.

[7]張華偉，魏萌.基于云免疫算法的認(rèn)知無線網(wǎng)絡(luò)參數(shù)優(yōu)化[J].計算機應(yīng)用.2014，03：68-69.

[8]朱思峰，劉芳，柴爭義，戚玉濤，吳建設(shè).簡諧振子免疫優(yōu)化算法求解異構(gòu)無線網(wǎng)絡(luò)垂直切換判決問題[J].物理學(xué)報.2012，09：35-38.