生龍，廣曉蕓

（河北工程大學 信息與電氣工程學院，河北 邯鄲 056038）

進化計算與復雜網(wǎng)絡(luò)結(jié)構(gòu)關(guān)系的研究★

生龍，廣曉蕓

（河北工程大學 信息與電氣工程學院，河北 邯鄲 056038）

基于達爾文進化論的進化算法可以將問題的求解過程模擬為群體的適者生存過程，通過群體不斷進化，求得最終解。但進化過程的描述不夠清晰，且只注重最終結(jié)果，常常忽略算法的中間過程。復雜網(wǎng)絡(luò)結(jié)構(gòu)可有效彌補這一缺陷。通過分析算法的優(yōu)化過程，將個體之間的關(guān)系進行動力學過程描述，并討論其蘊含的復雜網(wǎng)絡(luò)結(jié)構(gòu)，最終利用復雜網(wǎng)絡(luò)技術(shù)控制或改進算法。設(shè)置相關(guān)參數(shù)進行動力學描述的實驗設(shè)計并驗證網(wǎng)絡(luò)結(jié)構(gòu)是否符合復雜網(wǎng)絡(luò)特征。研究結(jié)果表明進化計算的優(yōu)化過程可以描述為復雜網(wǎng)絡(luò)結(jié)構(gòu)或類似于復雜網(wǎng)絡(luò)的結(jié)構(gòu)。這對于復雜網(wǎng)絡(luò)的深入研究及進化計算的改進、優(yōu)化和控制有一定的理論意義和應(yīng)用價值。

進化計算；復雜網(wǎng)絡(luò)；動力學；網(wǎng)絡(luò)結(jié)構(gòu)；優(yōu)化

0 引言

本文對兩個看似完全不同的研究領(lǐng)域：進化計算和復雜網(wǎng)絡(luò)的相互關(guān)系進行簡要研究[1]。進化算法（Evolutionary Algorithms，EAs）是以達爾文的進化論思想為基礎(chǔ)，通過模擬生物進化過程與機制的求解問題的自組織、自適應(yīng)的人工智能技術(shù)，遵循優(yōu)勝劣汰，適者生存的原則[2]。進化計算具有效率高、簡單、易操作、魯棒性強和通用性好等特點，能夠不受問題性質(zhì)的限制，有效地處理傳統(tǒng)優(yōu)化算法難以解決的復雜問題。但傳統(tǒng)的描述形式不夠清晰，直觀，不利于理解，且只注重計算結(jié)果，忽視了算法的中間過程。因此分析算法的優(yōu)化過程，用隱含的網(wǎng)絡(luò)結(jié)構(gòu)動力學演化過程描述優(yōu)化過程并分析網(wǎng)絡(luò)結(jié)構(gòu)動力學特征將成為進化計算和復雜網(wǎng)絡(luò)研究的一大亮點[2，3]。

復雜網(wǎng)絡(luò)作為大量真實復雜系統(tǒng)的高度抽象，為研究問題的解決提供了一種新視角、新方法、新工具。通過復雜網(wǎng)絡(luò)結(jié)構(gòu)的分析可以揭示網(wǎng)絡(luò)內(nèi)部的拓撲結(jié)構(gòu)，理解其功能，預測其行為。這兩個看似無關(guān)的研究領(lǐng)域：進化計算和復雜網(wǎng)絡(luò)，是否存在某種隱含關(guān)系將成為研究重點。如何根據(jù)優(yōu)化過程中染色體的相互關(guān)系構(gòu)建網(wǎng)絡(luò)拓撲結(jié)構(gòu)模型并展現(xiàn)進化計算中隱含的拓撲結(jié)構(gòu)的動力學演化過程將成為研究的難點與關(guān)鍵。

目前為止關(guān)于進化計算和復雜網(wǎng)絡(luò)動力學關(guān)系的研究文獻較少。本文從進化計算的優(yōu)化過程入手，重點分析進化計算和復雜網(wǎng)絡(luò)之間的相互關(guān)系，詳述算法的中間過程，并討論進化算法的可視化步驟。希望對國內(nèi)關(guān)于進化計算中復雜網(wǎng)絡(luò)動力學的研究起到推動作用。

1 進化計算的基本概念

進化計算是計算科學的子學科，屬于生物計算領(lǐng)域。二戰(zhàn)結(jié)束以來，進化計算的主要思想被廣泛的引入到科學界[1]。進化算法主要包括遺傳算法（Genetic Algorithms，GA）[4]、遺傳規(guī)劃（Genetic Programming，GP）[5]、進化策略（Evolution Strategies，ES）[6]和進化規(guī)劃（Evolution Programming，EP）[7]等。進化算法能有效處理傳統(tǒng)優(yōu)化算法難以解決的復雜問題，因此這些算法和設(shè)計一經(jīng)發(fā)表就受到人們的青睞。

進化算法最主要的兩大特點是群體搜索策略和個體之間相互交換信息。目前進化計算的應(yīng)用領(lǐng)域已滲透到許多學科，同時應(yīng)用實踐又促進了進化計算的發(fā)展和完善[8-12]。

1.1 基本概念

1.1.1 收斂性

收斂性是進化計算研究的重要指標，直接關(guān)系到算法的應(yīng)用價值[10，13]。收斂性的研究可為算法的發(fā)展提供理論依據(jù)和正確方向。

在算法設(shè)計中應(yīng)盡量避免局部收斂或過早收斂。當算法陷入局部收斂時，產(chǎn)生的結(jié)果很可能不滿足目標函數(shù)要求的最優(yōu)解。

種群大小作為影響算法性能和收斂性的一個重要因素。種群太小不足以產(chǎn)生足夠的樣本點，種群太大，則增加計算難度、延長收斂時間。因此選擇或設(shè)計算法時應(yīng)充分運用已有的收斂性分析研究成果，從算法結(jié)構(gòu)、控制參數(shù)選擇、遺傳算子的操作方式等方面綜合考慮[14]。

1.1.2 適應(yīng)度

進化計算中優(yōu)化過程的求解主要依賴于個體的適應(yīng)度值，適應(yīng)度越好，越有利于生存進化。在優(yōu)化過程中應(yīng)盡量讓適應(yīng)度好的個體有更多機會繁殖后代。因此適應(yīng)度函數(shù)的選取非常重要。適應(yīng)度函數(shù)的選取直接影響到算法的收斂速度和能否找到最優(yōu)解。一般而言，適應(yīng)度函數(shù)的設(shè)計要綜合考慮問題本身的要求及其值域的變化范圍等[15，16]。

1.1.3 種群多樣性

進化算法通過對大量個體進行優(yōu)化操作推動種群進化，通常情況下種群的多樣性越大，得到最優(yōu)個體的幾率越大，種群多樣性越小，個體之間差異性越小，越容易發(fā)生過早收斂現(xiàn)象。所以種群多樣性是進化的前提條件，種群只有在保持一定多樣性的情況下才能進化。正確評價種群的多樣性對進化算法的改進有著重要的指導作用。其中種群熵作為種群多樣性評價的指標之一[17，18]。

當種群中所有個體都相同，即Q=1時，熵取最小值，Emin=0。當Q=N時，熵取最大值，即Emax=log（N）。種群中個體類型越多，分配得越平均，熵越大。通過比較熵和最大熵的大小，分析種群多樣性程度，進而判斷進化算法的好壞。令α=Et/Emax，顯然α∈[0,1]。α越大，種群多樣性越大，反之，多樣性越小。定義α≥0.5時，種群具有較大的種群多樣性。

在選擇或設(shè)計算法時，應(yīng)首先考慮收斂性問題。在求最優(yōu)解時，應(yīng)綜合考慮收斂性、適應(yīng)度函數(shù)和種群多樣性。適應(yīng)度函數(shù)的選取直接影響收斂速度和能否得到最優(yōu)解。最后還應(yīng)保證種群的多樣性。種群多樣性越單一，算法越容易陷入局部最優(yōu)，算法性能越差。

1.1.4 缺點

進化算法發(fā)展較早，應(yīng)用廣泛，其中遺傳算法的應(yīng)用最為廣泛。但也存在一些缺點。傳統(tǒng)算法的描述形式包括文字描述，代碼，以及二進制，十進制和結(jié)構(gòu)式編碼等[19]。但這種描述、代碼及編碼形式不便于閱讀理解。且只關(guān)注計算結(jié)果，往往忽視算法的中間過程。優(yōu)化過程中各個染色體之間有什么關(guān)系，這種關(guān)系是否會影響進化結(jié)果?進化策略是否唯一?最優(yōu)個體具有什么樣的配對方式?若生成最優(yōu)個體的配對染色體相似率較高，則不利于種群多樣性的發(fā)展，也不利于種群進化。通過分析中間過程，將這個過程用復雜網(wǎng)絡(luò)結(jié)構(gòu)進行可視化，利用復雜網(wǎng)絡(luò)技術(shù)找出能生成最優(yōu)個體的相似率較低的染色體，推動種群進化。

因此復雜網(wǎng)絡(luò)結(jié)構(gòu)動力學能有效彌補這一缺點。受到2014年進化計算會議（IEEE CEC）上一篇名為《Evolutionary Algorithms Dynamics and its Hidden Complex Network Structures》文章的啟發(fā)，可以將進化算法的優(yōu)化過程用復雜網(wǎng)絡(luò)動力學描述，將復雜的中間過程描述為清晰的網(wǎng)絡(luò)結(jié)構(gòu)圖[2]。用復雜網(wǎng)絡(luò)工具分析形成的結(jié)構(gòu)圖，進而控制算法。用基因片段相似度低的染色體產(chǎn)生最優(yōu)個體，提高種群多樣性。并對算法提出指導和改進意見。

2 復雜網(wǎng)絡(luò)的研究發(fā)展

2.1 起源

復雜網(wǎng)絡(luò)的研究起源于兩篇標志性的論文：一篇是發(fā)表在Nature上的小世界網(wǎng)絡(luò)（Small World Networks）[20]，另一篇是發(fā)表在Science上的無標度網(wǎng)絡(luò)（Scale-free Networks）[21]。這兩篇論文可以看作是復雜網(wǎng)絡(luò)研究新紀元開始的標志。自然界中的許多系統(tǒng)都可以用復雜網(wǎng)絡(luò)描述，同時，復雜網(wǎng)絡(luò)可以量化和預測這個復雜多變的社會。如交通網(wǎng)、因特網(wǎng)、科學合作網(wǎng)、人類語言網(wǎng)、神經(jīng)網(wǎng)、生態(tài)食物鏈網(wǎng)、細胞網(wǎng)、蛋白質(zhì)網(wǎng)等?！皬碗s網(wǎng)絡(luò)”一詞來源于具有既不完全規(guī)則又不完全隨機的連接模式，且表現(xiàn)出實質(zhì)性和非平凡拓撲特征的網(wǎng)絡(luò)。這些特征包括具有長長尾部的度分布、高聚類系數(shù)和分層結(jié)構(gòu)。復雜網(wǎng)絡(luò)是連接進化算法的另一個研究領(lǐng)域[3]。

復雜網(wǎng)絡(luò)中，人們熟知的特征是無標度特性和小世界網(wǎng)絡(luò)。這兩個特征的研究和發(fā)現(xiàn)對復雜網(wǎng)絡(luò)的研究有著非常重要的作用。其具體結(jié)構(gòu)特點是具有冪率度分布的無標度網(wǎng)絡(luò)和具有相對短的平均路徑長度和高聚類系數(shù)的小世界網(wǎng)絡(luò)[22]。

2.2 統(tǒng)計特征

2.2.1 度分布

復雜網(wǎng)絡(luò)中，最基本的概念即為度：一個節(jié)點與其他節(jié)點連邊的數(shù)目。

有向網(wǎng)絡(luò)中，節(jié)點度可以分為出度（out-degree）和入度（in-degree）。出度指從該節(jié)點指向其他節(jié)點的邊的數(shù)目，入度指其他節(jié)點指向該節(jié)點的邊的數(shù)目。

度分布p（k）定義為網(wǎng)絡(luò)中節(jié)點度為K的概率。節(jié)點度越大，對網(wǎng)絡(luò)的影響力就越大。許多真實的網(wǎng)絡(luò)度分布都遵循冪律分布，P(k)~k-γ（通常2＜=γ＜= 3）[23，24]。冪律分布也稱為無標度分布。

度大的節(jié)點具有較大的度中心性，在網(wǎng)絡(luò)中越重要。利用度中心性分析種群的停滯或早熟收斂現(xiàn)象[25]，進而保留最優(yōu)個體，改善較差個體。

2.2.2 平均路徑長度

復雜網(wǎng)絡(luò)具有相對較小的平均路徑長度。計算進化算法形成的網(wǎng)絡(luò)結(jié)構(gòu)的平均路徑長度判斷進化算法能否用復雜網(wǎng)絡(luò)或類似復雜網(wǎng)絡(luò)的結(jié)構(gòu)描述。

2.2.3 聚類系數(shù)

進化算法中，聚類可反映個體基因的分布。

2.2.4 介數(shù)

介數(shù)值來源于社會網(wǎng)絡(luò)中對個體重要性的評估，度量特定節(jié)點和網(wǎng)絡(luò)中其他節(jié)點長度的介數(shù)中心性定理首先是由Anthonisse（1971）和Freeman （1977）提出的。一個節(jié)點（邊）的介數(shù)值表示所有的節(jié)點對之間通過該節(jié)點（邊）的最短路徑條數(shù)占所有最短路徑的比例。因此，它能夠刻畫節(jié)點和邊在網(wǎng)絡(luò)中的重要程度[27]。

任意節(jié)點v的介數(shù)值定義如下：

其中，?st表示節(jié)點s到t的最短路徑數(shù)目；?st(v)為節(jié)點s到t的最短路徑中經(jīng)過節(jié)點v的最短路徑數(shù)目[23]。也可以導出任意邊e的介數(shù)計算公式。

由介數(shù)值的定義可知，計算節(jié)點和邊的介數(shù)值，需要查找圖中任意節(jié)點對之間的所有最短路徑，因此計算方法具有非常高的計算復雜性。目前，已知最快的介數(shù)計算方法是Ulrik Brandes提出的。如果圖中包含n個節(jié)點和e條邊，如果是無權(quán)圖，該算法的計算復雜性為O（en）；如果是加權(quán)圖，則計算復雜性為O（en+n2log（n））。

具有相對高的介數(shù)中心性的節(jié)點，其適應(yīng)度值相對較大。若節(jié)點的最大適應(yīng)度值改變，則系統(tǒng)的介數(shù)中心性也隨之改變。

2.3 研究現(xiàn)狀

目前復雜網(wǎng)絡(luò)的研究已經(jīng)應(yīng)用到許多領(lǐng)域。例如，文本抗毀性研究，城市網(wǎng)絡(luò)信息空間局部聚集和整體聯(lián)通的研究[28，29]?；趶碗s網(wǎng)絡(luò)理論，可有效分析復雜的綜合電力問題、中國股票市場及網(wǎng)絡(luò)游戲系統(tǒng)[29，30]。網(wǎng)絡(luò)中節(jié)點重要性的分析與評價，可有效防止整個網(wǎng)絡(luò)癱瘓[31]。基于復雜網(wǎng)絡(luò)的高速公路網(wǎng)的結(jié)構(gòu)和可靠性分析，有助于道路規(guī)劃和突發(fā)事件的控制[32]。將復雜網(wǎng)絡(luò)理論應(yīng)用到城市交通網(wǎng)的信號控制研究中，尋找最優(yōu)信號網(wǎng)絡(luò)拓撲的演化過程。最優(yōu)的信號配時和網(wǎng)絡(luò)拓撲可緩解交通擁堵現(xiàn)象[33]。

在近幾年的研究中，學者開始關(guān)注進化計算中隱含的復雜網(wǎng)絡(luò)結(jié)構(gòu)，并取得一些成果。2010年，Zelinka Ivan等人開始討論進化計算和復雜網(wǎng)絡(luò)的關(guān)系，研究討論進化計算是否可以可視化或模擬成復雜網(wǎng)絡(luò)。Zelinka Ivan等人發(fā)現(xiàn)進化計算可以可視化為類似于復雜網(wǎng)絡(luò)的結(jié)構(gòu)，而網(wǎng)絡(luò)結(jié)構(gòu)的構(gòu)建依賴于多個因素。如果進化計算能被可視化，那么復雜網(wǎng)絡(luò)的特點可用于描述算法或在以后的研究中控制算法的動態(tài)[34]。隨后又對這兩者之間的關(guān)系進行了進一步研究。在2011年，討論了如何用復雜網(wǎng)絡(luò)工具可視化進化算法。如果進化算法能被可視化，那么我們有理由相信復雜網(wǎng)絡(luò)技術(shù)可用于控制進化算法[3，35，36]。在隨后的幾年，繼續(xù)研究這兩個研究領(lǐng)域的相互關(guān)系，并分析了差分進化算法、自組織遷移算法和遺傳算法等的可視化結(jié)果[1，2，36-38]。

如果進化計算中蘊含著復雜網(wǎng)絡(luò)結(jié)構(gòu)，則存在一種改善進化算法的控制技術(shù)。但在以往的研究中沒有考慮復雜網(wǎng)絡(luò)動力學。而復雜網(wǎng)絡(luò)動力學已成為研究的一個熱點。

網(wǎng)絡(luò)上的動力學行為稱為建立在網(wǎng)絡(luò)上的系統(tǒng)動態(tài)性質(zhì)。研究復雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu)也是為了理解和解釋發(fā)生在網(wǎng)絡(luò)上的動力學行為或過程。由于拓撲結(jié)構(gòu)特征的統(tǒng)計量準確衡量了復雜網(wǎng)絡(luò)的結(jié)構(gòu)特性，故對復雜網(wǎng)絡(luò)結(jié)構(gòu)的研究有關(guān)鍵作用，因此歷來是研究的熱點所在。網(wǎng)絡(luò)結(jié)構(gòu)決定網(wǎng)絡(luò)所承擔的各種“功能”，這些功能是通過網(wǎng)絡(luò)上運行的各種“動力學過程”實現(xiàn)的，故動力學過程的行為受拓撲結(jié)構(gòu)的影響?？梢?，對網(wǎng)絡(luò)結(jié)構(gòu)的研究，是復雜網(wǎng)絡(luò)其它一切研究的基礎(chǔ)所在。不過，對復雜網(wǎng)絡(luò)結(jié)構(gòu)的研究，最終目的還是要用來解釋網(wǎng)絡(luò)上的動力學過程的行為[25]。值得注意的是，真實網(wǎng)絡(luò)結(jié)構(gòu)是不斷變化的，網(wǎng)絡(luò)上的動力學過程有可能反過來影響網(wǎng)絡(luò)結(jié)構(gòu)的變化，網(wǎng)絡(luò)結(jié)構(gòu)與網(wǎng)絡(luò)動力學過程之間的復雜的相互影響和作用被稱為“共同演化”，是近年來研究的熱點。復雜網(wǎng)絡(luò)拓撲結(jié)構(gòu)對其傳播動力學影響的研究是復雜網(wǎng)絡(luò)研究的一大熱點，具有許多現(xiàn)實的應(yīng)用，如傳染性疾病，計算機病毒，手機病毒，輿論在社會中的傳播與擴散等，都可以看作是發(fā)生在網(wǎng)絡(luò)上的某種傳播動力學行為，通過對其傳播行為的研究可以揭示其規(guī)律，制定相應(yīng)的控制策略[39]。

復雜網(wǎng)絡(luò)動力學的應(yīng)用很廣，但是用復雜網(wǎng)絡(luò)動力學特性描述進化算法中間過程的文章還較少。本文將對網(wǎng)絡(luò)動力學特征表示算法的優(yōu)化過程進行簡單分析，并討論其可視化步驟。

3 進化計算中復雜網(wǎng)絡(luò)的相關(guān)研究

本文的研究目的是用復雜網(wǎng)絡(luò)的工具彌補進化計算忽略中間過程的缺點，及進化過程能否如復雜網(wǎng)絡(luò)一樣被可視化和模擬。若進化計算中蘊含著復雜網(wǎng)絡(luò)結(jié)構(gòu)，則存在分析和控制進化算法的某種技術(shù)。這兩個看似完全不同的研究領(lǐng)域之間是否存在某種隱藏的結(jié)構(gòu)關(guān)系，將成為進化計算研究領(lǐng)域的一大亮點[2]。

傳統(tǒng)優(yōu)化過程的描述形式大多為二進制編碼、十進制編碼或文字描述，不夠清晰直觀。傳統(tǒng)方法常常忽略算法的中間過程，而中間過程對算法的結(jié)果有重大影響。從種群進化角度考慮，選擇交叉的個體基因相似度高，不利于種群發(fā)展。然而用復雜網(wǎng)絡(luò)工具可以避免此類問題。分析優(yōu)化過程中染色體之間的相互關(guān)系，將這種關(guān)系可視化為類似于復雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。這種可視化方法能夠清晰直觀的展現(xiàn)算法的優(yōu)化過程。分析網(wǎng)絡(luò)拓撲結(jié)構(gòu)中染色體之間的關(guān)系，動態(tài)的展示算法的優(yōu)化過程，促進種群進化。

3.1 實驗設(shè)計

本文主要利用遺傳算法研究優(yōu)化過程中個體的相互關(guān)系，及這種相互關(guān)系是否能描述為復雜網(wǎng)絡(luò)結(jié)構(gòu)。選定的適應(yīng)度函數(shù)為Ackley函數(shù)：

遺傳算法的參數(shù)設(shè)置如表1所示。根據(jù)算法的優(yōu)化過程，將算法重復運行100次，在100次迭代中10個個體的選擇如圖1所示。圖1中的點代表每次迭代的最優(yōu)位置。

表1 參數(shù)設(shè)置Tab.1 Parameter Setting

圖1 算法迭代100次，個體的不同選擇Fig.1 When algorithm runs 100 times，individuals have different choices

3.2 可視化

本文中可視化的原理遵循自然界中適者生存的原則。適應(yīng)度越好的個體，被保留下來并成功產(chǎn)生后代的幾率越大。進化算法描述為復雜網(wǎng)絡(luò)動力學的步驟為。第一步：學習進化算法的規(guī)則和過程；第二步：分析個體之間的關(guān)系，如哪些個體可用于產(chǎn)生新個體，哪些個體從較差位置移動到較優(yōu)位置。第三步：選擇分析進化算法的復雜網(wǎng)絡(luò)工具；第四步：用復雜網(wǎng)絡(luò)動力學可視化算法的優(yōu)化過程并分析形成的拓撲結(jié)構(gòu)圖。

隨著算法的迭代，個體之間的關(guān)系不斷變化，根據(jù)不斷變化的染色體之間的關(guān)系建立網(wǎng)絡(luò)拓撲結(jié)構(gòu)模型。根據(jù)復雜網(wǎng)絡(luò)動力學將算法的中間過程描述為網(wǎng)絡(luò)結(jié)構(gòu)的變化圖（圖2）。最后利用結(jié)構(gòu)圖驗證各個算法的特點。

圖2 算法優(yōu)化過程的簡單描述Fig.2 the simple description of optimization process

形成的網(wǎng)絡(luò)結(jié)構(gòu)是否符合復雜網(wǎng)絡(luò)特性還需要進一步驗證。將種群大小增大到100，利用上述可視化步驟得到如圖3所示的典型網(wǎng)絡(luò)結(jié)構(gòu)圖。然而圖3是否符合復雜網(wǎng)絡(luò)特點，還需要用復雜網(wǎng)絡(luò)特性進行驗證。

為確定圖3的結(jié)構(gòu)是否類似復雜網(wǎng)絡(luò)，可用復雜網(wǎng)絡(luò)的典型特征進行驗證。例如具有長長尾部的度分布。分析圖3中度的分布特征得度的分布圖（圖4）。從圖4的擬合結(jié)果可知拖著長“尾”的分布曲線基本符合復雜網(wǎng)絡(luò)的度分布特性。

真實網(wǎng)絡(luò)結(jié)構(gòu)的度分布一般符合冪律分布，即“富者越富”理論。冪律分布在雙對數(shù)坐標下近似為一條直線。在圖4得到的冪律分布圖（圖5）中除去距離較遠的點外，前半部分的線性特性較弱，而后半部分近似于一條直線。因此可以說，圖3的結(jié)構(gòu)圖類似于復雜網(wǎng)絡(luò)結(jié)構(gòu)。

由遺傳算法的熵（圖6）和100個個體在第100代時形成的網(wǎng)絡(luò)結(jié)構(gòu)（圖7）可以看出，算法的熵在一定范圍內(nèi)來回波動，波動范圍在0.8～1.4之間，即0.8＜Et＜1.4，0.4＜α＜0.7。因此遺傳算法基本保持種群多樣性，這與圖7的結(jié)構(gòu)圖基本相符。圖7的結(jié)構(gòu)圖中個體之間有相互關(guān)系但不是全連接。所以遺傳算法能夠有效找到最優(yōu)解且基本保持種群多樣性。

3.3 發(fā)展趨勢

隨著應(yīng)用領(lǐng)域的擴展，進化計算的應(yīng)用潛力以及復雜網(wǎng)絡(luò)的應(yīng)用研究已受到學者們的廣泛關(guān)注。通過本文的研究對于復雜網(wǎng)絡(luò)的深入研究以及進化計算的改進、優(yōu)化和控制等應(yīng)用方面具有一定的理論意義和應(yīng)用價值。

目前關(guān)于進化計算中復雜網(wǎng)絡(luò)結(jié)構(gòu)的研究較少。這兩個看似完全不同的研究領(lǐng)域，是否存在著某些隱藏的結(jié)構(gòu)關(guān)系，將成為進化計算和復雜網(wǎng)絡(luò)研究的一大熱點。進化計算和復雜網(wǎng)絡(luò)結(jié)構(gòu)關(guān)系的發(fā)展前景是廣闊迷人的。

圖3 遺傳算法的可視化圖。頂點指個體，邊代表個體之間的關(guān)系。點越大，適應(yīng)度值越大，個體在結(jié)構(gòu)中的作用越大Fig.3 The visualization of genetic algorithm. Vertices refer to individuals，edges on behalf of the relationship between individuals.the greater dot which has better fitness has more important role in the structure

圖4 度分布圖Fig.4 degree distribution

圖5 冪律分布Fig.5 Power-law distribution

圖6 熵Fig.6 Entropy

圖7 第100代時，遺傳算法形成的結(jié)構(gòu)圖Fig.7 the structure formed by GA，100th generation

4 結(jié)論

該研究可用于復雜網(wǎng)絡(luò)是否存在于進化計算的分析和控制中。實驗結(jié)果證明復雜網(wǎng)絡(luò)結(jié)構(gòu)或類似于復雜網(wǎng)絡(luò)的結(jié)構(gòu)蘊含于進化計算中，那么有理由相信存在一種控制或改進進化算法的技術(shù)。且復雜網(wǎng)絡(luò)結(jié)構(gòu)的出現(xiàn)依賴于多個因素，如種群大小，染色體長度，迭代次數(shù)等。

文中主要討論了進化計算和復雜網(wǎng)絡(luò)動力學的關(guān)系。重點分析了如何用復雜網(wǎng)絡(luò)工具可視化進化算法，通過復雜網(wǎng)絡(luò)特性可分析進化計算的特點并促進算法的進一步改善和發(fā)展。

致謝

感謝中國國家自然科學基金（41373101），河北省高?？茖W技術(shù)研究項目（QN20131081），河北省自然科學基金（F2015402070）和邯鄲市科學技術(shù)研究與發(fā)展計劃項目（1426109077-3）對本項目的支持。

[1] Zelinka I，Davendra D D，Chadli M，Senkerik R，Dao T T and Skanderova L. Evolutionary dynamics as the structure of complex networks[J]. Handbook of Optimization. Springer Berlin Heidelberg，2013：215-243.

[2] Zelinka I，Davendra D，Lampinen J，Senkerik R and Pluhacek M. Evolutionary algorithms dynamics and its hidden complex network structures. Evolutionary Computation （CEC） [J]. IEEE congress on evolutionary computation （CEC），Beijing，China，2014：3246-3251.

[3] Zelinka I，Davendra D，Senkerik R and Jasek R. Do evolutionary algorithm dynamics create complex network structures? [J]. Complex Systems，2011，20（2）：127-140.

[4] Holland J H. Adaptation in natural and artificial systems[J]. Control & Artificial Intelligence University of Michigan Press，1975，6（2）：126-137.

[5] Schwefel H P. Numerische optimierung von Computer-Modellen mittels der evolutionsstrategie[J]. Birkh?user，Basel，1977，26.

[6] Rechenberg I. Cybernetic solution path of an experimental problem[J]. Royal Aircraft Establishment Library Translation，2010，1122.

[7] Fogel D B. Unearthing a fossil from the history of evolutionary computation[J]. Fundamenta Informaticae，1998，35（1-4），1-16.

[8] 汪慎文，丁立新，張文生，等. 差分進化算法研究進展[J]. 武漢大學學報（理學版），2014，60（4）：283-292. Wang Shen-Wen，Ding Li-Xin，Zhang Wen-Sheng，et al. Survey of differential evolution[J]. Journal of Wuhan University，2014，60（4）：283-292.

[9] 謝承旺，汪慎文，謝大同，等. 高維目標進化算法研究進展[J]. 武漢大學學報（共學版），2012，45（5）：636-642. Xie Cheng-Wang，Wang Shen-Wen，Xie Da-Ton，et al. Progress of research on many-objective algorithms[J]. Engineering journal of Wuhan University，2012，45（5）：636-642.

[10] 代真真. 基于統(tǒng)計學習方法的進化算法研究[碩士論文] [J]. 華東師范大學，上海，2014. Dai Zhen-Zhen. Evolution algorithm based on statistical learning method[J]. East china normal university，2014.

[11] 任麗娜，呂明月，劉爽爽，等. 基于蜂群算法優(yōu)化的變槳距自抗擾控制器[J]. 新型工業(yè)化，2014（6）：43-48. Ren Lina，Lv Ming-yue，Liu Shuang-shuang，et al. Pitch control using active disturbance rejection controller based on colony optimization algorithm[J]. The Journal of New Industrialization，2014（6）：43-48.

[12] 王永辰，肖伸平，劉先亮. 基于改進自適應(yīng)遺傳算法的配電網(wǎng)重構(gòu)[J]. 新型工業(yè)化，2015，5（8）：6-10. Wang Yong-chen，Xiao Shen-ping，Liu Xian-liang，et al. Distribution system reconfiguration based on improved genetic algorithm[J]. The Journal of New Industrialization，2015，5（8）：6-10.

[13] Bagrow J P and Bollt E M. Local method for detecting communities[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics，2005，72（2）：72-046108.

[14] 王莉. 遺傳算法的收斂性統(tǒng)一[J]. 自動化技術(shù)與應(yīng)用，2004，23（6）：16-19. Wang Li. A unified convergence criterion for genetic algorithms[J]. Automation Technology and Application，2004，23（6）：16-19.

[15] 金芬，孫春華，鐘鳴. 遺傳算法中適應(yīng)度函數(shù)的改進[J]. 機械設(shè)計與制造，2010，3：218-219. Jin Fen，Sun Chun-Hua，and Zhong Ming. Improvement of fitness function in genetic algorithm[J]. Machinery Design & Manufacture，2010，3：218-219.

[16] Xuan D Y，Wang F L，Gao M H and Ma H Z. An improved fitness function of genetic algorithm[J]. Mathematics in Practice and Theory，2015，46（16）：232-238.

[17] 路景，周春艷. 基于種群多樣性評價的自適應(yīng)遺傳算法[J]. 計算機仿真，2008，25（2）：206-231. Lu Jing and Zhou Chun-Yan. An adaptive genetic algorithm based on measurement of population diversity[J]. Computer Simulation，2008，25（2）：206-231.

[18] 張曉績，戴冠中，徐乃平. 遺傳算法種群多樣性的分析研究[J]. 控制理論與應(yīng)用.1998，15（1）：17-22. Zhang Xiao-Ji，Dai Guan-Zhong and Xu Nai-Ping. Study on diversity of population in genetic algorithms[J]. Control Theory andApplications，1998，1（1）：17-22.

[19] Lin Z and Yuming L U. Diversity of cellular genetic algorithm[J]. Electronic Science & Technology，2015.

[20] Watts DJ and Strogatz SH. Collective dynamics of 'small-world' networks[J]. Nature，1998，393（6684）：440-442.

[21] Barabasi A L and Albert R. Emergence of Scaling in Random Networks[J]. Science，1999，286（5439）：509-512.

[22] Wang X F and Chen G. Complex networks：small-world，scale-free and beyond[J]. IEEE Circuits & Systems Magazine，2003，3（1）：6-20.

[23] Wang J，Mo H，Wang F. Exploring the network structure and nodal centrality of China’s air transport network：A complex network approach[J]. Journal of Transport Geography，2011，19（4）：712-721.

[24] Lordan O，Sallan J M ，Simo P. Study of the topology and robustness of airline route networks from the complex network approach：a survey and research agenda[J]. Journal of transport geography，2014，37：112–120.

[25] Davendra D，Zelinka I，Senkerik R，et al. Complex network analysis of evolutionary algorithms applied to combinatorial optimization problem. Proceedings of the Fifth International Conference on Innovations in Bio-Inspired Computing and Applications IBICA 2014[J]. Springer International Publishing，2014，141-150.

[26] 吳增海. 社交網(wǎng)絡(luò)模型的研究[博士論文] [J]. 中國科學技術(shù)大學，合肥，2012. Wu Zeng-Hai. Research on the model of social network[J]. University of Science and Technology of China，2012.

[27] Chen Y Z，Huang Z G ，Lai Y C. Controlling extreme events on complex networks[J]. Scientific Reports，2014. 4：6121-6121.

[28] 申艷光，王杰，生龍，等. 基于復雜網(wǎng)絡(luò)的文本抗毀性分析[J]. 計算機應(yīng)用研究，2015，32（3）：679-682. Shen Yan-Guang，Wang Jie，Sheng Long ，et al. Text invulnerability analysis based on complex network[J]. Computer Application Research，2015，32（3）：679-682.

[29] 王旭文. 復雜網(wǎng)絡(luò)上的演化博弈及可控性研究[博士論文] [J]. 中國科學技術(shù)大學，合肥，2015. Wang Xu-Wen. Evolutionary games and controllability on complex networks[J]. University of science and technology of china，2015.

[30] 莊新田，張鼎，苑瑩，莊霄威. 中國股市復雜網(wǎng)絡(luò)中的分形特征[J]. 系統(tǒng)工程理論與實踐，2015，35（2）：273-282. Zhuang Xin-Tian，Zhang Ding，Yuan Ying and Zhuang Xiao-Wei. Fractal characteristic of the Chinese stock market complex network[J]. Systems Engineering-Theory & Practice，2015，35（2）：273-282.

[31] 秦李，楊子龍，黃曙光. 復雜網(wǎng)絡(luò)的節(jié)點重要性綜合評價[J]. 計算機科學，2015，42（2）：60-64. Qin Li，Yang Zi-Long and Huang Shu-Guang. Systhesis evaluation method for node importance in complex networks[J]. Computer science，2015，42（2）：60-64.

[32] Dai H，Yao E，Lu N，Bian K and Zhang B. Freeway network connective reliability analysis based complex network approach[J]. Procedia Engineering，2016，137：372-381.

[33] Li S B，Li Y，F(xiàn)u B B and Dang W X. Study on simulation optimization of dynamic traffic signal based on complex networks[J]. Procedia Engineering，2016，137：1-10. ，.

[34] Zelinka I，Davendra D，Sná?El V，Ja?ek R，?enkerík R and Oplatková Z. Preliminary investigation on relations between complex networks and evolutionary algorithms dynamics[J]. Computer Information Systems and Industrial Management Applications （CISIM），2010 International Conference on. IEEE，2010，148-153.

[35] Klimkova E and Fekiac J. Vizualization of evolutionary algorithms by means of complex networks[J]. Annals of Daaam & Proceedings，2011，22（1）：1521-1522.

[36] Zelinka I. Investigation on relationship between complex networks and evolutionary algorithms dynamics[J]. Numerical Analysis & Applied Mathematics Icna. AIP Publishing，2011，1011-1014.

[37] Zelinka I. On Analysis and Performance Improvement of Evolutionary Algorithms Based on its Complex Network Structure. Advances in Artificial Intelligence and Soft Computing[J]. Springer International Publishing，2015，389-400.

[38] Zelinka I. A survey on evolutionary algorithms dynamics and its complexity – Mutual relations，past，present and future[J]. Swarm & Evolutionary Computation，2015，25：2-14.

[39] 姚新，陳國良，徐惠敏，等. 進化算法研究進展[J]. 計算機學報，1995，18（9）：694-706. Yao Xin，Chen Guo-Liang，Xu Hui-Min，et al. A survey of evolutionary algorithms[J]. Chinese Journal of Computers，1995，18（9）：694-706．

Research on the Relationship Between Evolutionary Algorithms and Complex Network Structure

SHENG Long, GUANG Xiao-yun
(School of Information Electrical Engineering, Hebei University of Engineering, Hebei Handan 056038)

Evolutionary algorithm is a kind of optimization algorithms which based on Darwinism and imitated the process of survival of the fittest. After the evolution of several generations, the finally optimal solution will be obtained. But the description of evolutionary process is not clear, and people only focus on results, often ignores the intermediate process. Complex network structure can effectively compensate for the shortcomings of evolutionary algorithm. The relationship among individuals is described as dynamic processes, and complex network structure is discussed by analyzing the optimization process. Finally using the complex network technology to control or improve algorithm. Set the relevant parameters of dynamic experiment and verify whether the network has complex network characteristics. The result of experiments indicates that the optimization process of evolutionary computation can be described as complex networks structure or similar to the structure of complex networks. For further study of complex networks and the improvement, optimization and control of evolutionary algorithms, it has certain theoretical significance and practical value.

Evolutionary algorithm; Complex network; Dynamic; Networks structure; Optimization

生龍，廣曉蕓.進化計算與復雜網(wǎng)絡(luò)結(jié)構(gòu)關(guān)系的研究[J]. 新型工業(yè)化，2016，6（11）：1-9.

10.19335/j.cnki.2095-6649.2016.11.001

: SHENG Long, GUANG Xiao-yun. Research on the Relationship Between Evolutionary Algorithms and Complex Network Structure[J]. The Journal of New Industrialization, 2016, 6(11) : 1-9.

中國國家自然科學基金（NO. 41373101），河北省高?？茖W技術(shù)研究項目（No. QN2013 1081），河北省自然科學基金（No. F2015402070），邯鄲市科學技術(shù)研究與發(fā)展計劃項目（NO. 1426109077-3）

生龍（1982-），男，博士，講師，計算機學會（CCF）會員,主要研究領(lǐng)域為復雜網(wǎng)絡(luò)、機器學習、數(shù)據(jù)挖掘

廣曉蕓（1990-），女，碩士研究生，計算機學會（CCF）會員（NO.51300G）,主要研究領(lǐng)域為復雜網(wǎng)絡(luò)