群體智能優(yōu)化算法-群體智能和進(jìn)化計(jì)算

1、第一章群體智能和進(jìn)化計(jì)算優(yōu)化問題存在于科學(xué)、工程和工業(yè)的各個(gè)領(lǐng)域。在許多情況下，此類優(yōu)化問題，特 別是在當(dāng)前場(chǎng)景中，涉及各種決策變量、復(fù)雜的結(jié)構(gòu)化目標(biāo)和約束。通常，經(jīng)典或傳統(tǒng) 的優(yōu)化技術(shù)在以其原始形式求解此類現(xiàn)實(shí)優(yōu)化問題時(shí)都會(huì)遇到困難。由于經(jīng)典優(yōu)化算法在求解大規(guī)模、高度非線性、通常不可微的問題時(shí)存在不足，因此需要開發(fā)高效、魯棒 的計(jì)算算法，無論問題大小，都可以對(duì)其進(jìn)行求解。從自然中獲得靈感，開發(fā)計(jì)算效率 高的算法是處理現(xiàn)實(shí)世界優(yōu)化問題的一種方法。從廣義上講，我們可以將這些算法應(yīng)用 于計(jì)算科學(xué)領(lǐng)域，尤其是計(jì)算智能領(lǐng)域。計(jì)算智能(CI)是一組受自然啟發(fā)的計(jì)算方法和途徑，用于解決復(fù)雜的現(xiàn)實(shí)世界問題。

2、CI主要包括模糊系統(tǒng)(Fuzzy Systems FS)、神經(jīng)網(wǎng)絡(luò)(Neural Networks, NN)、群體智能(Swarm Intelligence, SI)和進(jìn)化計(jì)算 (Evolutionary Computation, EC)。計(jì)算智能技術(shù)具有強(qiáng)大、高效、靈活、可靠等諸多 優(yōu)點(diǎn)，其中群體智能和進(jìn)化計(jì)算是計(jì)算智能的兩個(gè)非常有用的組成部分，主要用于解決 優(yōu)化問題。本部分內(nèi)容主要關(guān)注各種群體和進(jìn)化優(yōu)化算法。群體智能單詞“Swarmm的是一群無序移動(dòng)的個(gè)體或?qū)ο?，如昆蟲，鳥，魚。更正式地講， 群體可以看作是相互作用的同類代理或個(gè)體的集合。通過建模和模擬這些個(gè)體的覓食行 為，研究人員已經(jīng)開發(fā)

3、了許多有用的算法。群體智能”一詞是由Beni和Wang1在研究移動(dòng)機(jī)器人系統(tǒng)時(shí)提出的。他們開發(fā)了一套控制機(jī)器人群的算法，然而，早期的研究或 多或少地都利用了鳥類的群居行為。例如，1987年Reynolds2開發(fā)了一套程序，使用 個(gè)體行為來模擬鳥類或其他動(dòng)物的覓食行為。群體智能是一門研究自然和人工系統(tǒng)的學(xué)科，由許多個(gè)體組成，這些個(gè)體基于社會(huì) 實(shí)體間分散的、集體的和自組織的的合作行為進(jìn)行協(xié)調(diào)，如鳥群、魚群、蟻群、動(dòng)物放 牧、細(xì)菌生長(zhǎng)和微生物智能。群體的成員必須是活躍的、動(dòng)態(tài)的和簡(jiǎn)單的(沒有或幾乎 沒有對(duì)周圍環(huán)境的固有知識(shí))。在群體內(nèi)部，由于這種協(xié)作行為，出現(xiàn)了一種比隨機(jī)搜 索更好的搜索策略，所得到

4、的智能搜索策略一般稱為群體智能。Bonabeau等人3對(duì)群體智能的一個(gè)廣為接受的定義是，由簡(jiǎn)單的個(gè)體組成的群體所產(chǎn)生的集體智慧。在80年代后期的前期工作基礎(chǔ)上，90年代先后開發(fā)出了兩種成功的算法，分別是 1992年的蟻群優(yōu)化算法4和1995年的粒子群優(yōu)化算法5。直到90年代中期，由于種 群利用、隨機(jī)性和應(yīng)用領(lǐng)域的相似性，群體智能方法一直被認(rèn)為是進(jìn)化計(jì)算方法。 然而， 由于SI和EC的基本理念存在著一些內(nèi)在的差異，SI在今天有了自己的身份。SI試圖 模擬簡(jiǎn)單代理的集體和協(xié)同行為，而EC則受到生物進(jìn)化的啟發(fā)。SI作為一種優(yōu)化算法， 由于其簡(jiǎn)單、有效的特點(diǎn)，在解決實(shí)際問題中得到了廣泛的應(yīng)用。Kara

5、boga6給出了群體智能的充分性條件。Karaboga認(rèn)為，當(dāng)且僅當(dāng)群體智能滿足 自組織和分工兩個(gè)條件時(shí)，一組同類智能體才能表現(xiàn)出群體智能。自組織這是一個(gè)起初是無序的群體，通過群體中個(gè)體間的局部相互作用，使運(yùn)動(dòng)變得有序 的過程。Bonabeau等人3將自組織分為四種策略：正反饋：這是從輸出系統(tǒng)中提取的信息，并傳遞給輸入系統(tǒng)，以促進(jìn)適當(dāng)結(jié)構(gòu) 的形成。正反饋為群體智能提供多樣性。負(fù)反饋：用于平衡正反饋，穩(wěn)定集體模式。負(fù)反饋指的是群體智能中的利用。波動(dòng)：這些與系統(tǒng)的隨機(jī)性有關(guān)。波動(dòng)在這一過程中提供了新的情況，有助于 擺脫停滯。多重交互：這提供了向社會(huì)中多個(gè)個(gè)體學(xué)習(xí)的方式，并提高了群體的整體智能。分工

6、分工有助于不同的專業(yè)個(gè)體同時(shí)執(zhí)行不同的任務(wù)，使的群體能夠處理搜索空間中變化的情況。下面列出的是一些常用和成功的群智能算法：粒子群優(yōu)化(Particle Swarm Optimization, PSO) 5蜘蛛猴優(yōu)化(Spider Monkey Optimization, SMO) 7人工蜂群算法(Artificial Bee Colony Algorithm , ABC) 6蟻群優(yōu)化(Ant Colony Optimization , ACO) 4細(xì)菌覓食優(yōu)化(Bacterial Foraging Optimization, BFO) 8螢火蟲算法(Firefly algorithm ) 9粒

7、子群優(yōu)化(PSO)的靈感來源于鳥類的群集或魚群的聚集，人工蜂群優(yōu)化(ABC)的靈 感來源于蜜蜂的覓食行為，蟻群優(yōu)化(ACO)的靈感來源于螞蟻的覓食行為，細(xì)菌覓食優(yōu) 化(BFO)的靈感來自于大腸桿菌和黃原膠等細(xì)菌的群體覓食；螢火蟲算法(Firefly Algorithm, FFA)的靈感來自螢火蟲的閃爍行為，而蜘蛛猴優(yōu)化(Spider Monkey Optimization, SMO)的靈感來自蜘蛛猴的覓食行為。通過文獻(xiàn)檢索發(fā)現(xiàn)，在這些算法中，PSO和蟻群算法是最常用的。因此，可以簡(jiǎn)要 地討論這兩種算法。粒子群優(yōu)化（PSO）是受鳥群或魚群的社會(huì)行為啟發(fā)而產(chǎn)生的，于1995年由Kennedy和Eb

8、erhart5提出。通常，一群鳥沒有領(lǐng)頭，它們通過合作試錯(cuò)的方式來尋找食物，跟 隨群體中與食物源位置最接近的個(gè)體移動(dòng)，其他個(gè)體則通過與已經(jīng)擁有更好位置的個(gè)體 溝通來同時(shí)更新他們的位置，重復(fù)這個(gè)過程，直到找到最佳的食物源。粒子群優(yōu)化是由 許多個(gè)體組成，這些構(gòu)成一個(gè)群體，每個(gè)個(gè)體稱為一個(gè)粒子，表示多維搜索空間中的一 個(gè)位置或可能的候選解。蟻群優(yōu)化（ACO）4是群體智能第一個(gè)成功的例子，該算法用于在圖中尋找最優(yōu)路徑。 蟻群優(yōu)化算法的靈感來自螞蟻尋找巢穴與食物源之間最短路徑的能力（圖1）。螞蟻初始時(shí)隨機(jī)開始覓食，一旦螞蟻找到食物源，它將按原路返回巢穴，并在路上留下信息素。 這種信息素的濃度可以引導(dǎo)其他

9、螞蟻尋找食物，當(dāng)其他螞蟻發(fā)現(xiàn)信息素時(shí)，它們會(huì)沿著 這條路徑前進(jìn)，其概率與信息素的濃度成正比?，F(xiàn)在，如果其他螞蟻也能找到食物源， 它們也會(huì)在返回巢穴時(shí)留下信息素。隨著越來越多的螞蟻找到了路徑，信息素的濃度也 越來越高。信息素也會(huì)隨著時(shí)間的推移而衰減，因此與較短的路徑相比，較長(zhǎng)的路徑會(huì) 有更多的衰減蒸發(fā)。蟻群算法在求解離散優(yōu)化問題中得到了廣泛的應(yīng)用。旅行商問題、 機(jī)器人路徑規(guī)劃、最小生成樹、數(shù)據(jù)挖掘、分類、調(diào)度問題等都體現(xiàn)了蟻群算法在提供 有效解決方案方面的優(yōu)勢(shì)。進(jìn)化計(jì)算植物、動(dòng)物、鳥類等生物在不斷地進(jìn)化，使自己適應(yīng)動(dòng)態(tài)的環(huán)境。與其他候選人相 比，那些足夠強(qiáng)壯（更適應(yīng)環(huán)境）的候選人更有可能產(chǎn)生能夠

10、存活下來的后代。達(dá)爾文進(jìn) 化論和自然選擇法則是這種進(jìn)化的原因，進(jìn)化計(jì)算的靈感就是來自于生物進(jìn)化。很難確 切地說明什么時(shí)候第一次使用進(jìn)化原理來解決計(jì)算問題。然而，為了給出一些概念，在 這里引用De Jong等人10的描述，”有關(guān)使用進(jìn)化過程解決計(jì)算機(jī)問題的最早描述之一 出現(xiàn)在Friedberg11和Friedberg等人12的文章中。這代表了機(jī)器學(xué)習(xí)的一些早期工作， 并描述了使用進(jìn)化算法用于自動(dòng)編程，即尋找計(jì)算給定輸入輸出函數(shù)的程序的任務(wù)?！毕肓私飧嚓P(guān)于進(jìn)化計(jì)算的歷史，讀者可以直接參考到De Jong等人的成果10 0Food SourceNeit圖1螞蟻如何找到離巢穴最近的路徑進(jìn)化計(jì)算（EC

11、）主要用于求解優(yōu)化問題。進(jìn)化計(jì)算是一系列基于生物進(jìn)化原理（如自然 選擇和遺傳）的問題解決技術(shù)的統(tǒng)稱。這些算法試圖找到全局最優(yōu)解。在很短的時(shí)間內(nèi)， 這些技術(shù)已經(jīng)在包括工程、科學(xué)和農(nóng)業(yè)在內(nèi)的各個(gè)領(lǐng)域的許多問題上得到了應(yīng)用。EC在搜索過程中模擬了自然選擇過程。該類算法從隨機(jī)生成一組潛在解開始，然后通過迭 代更新這些可能的解得到一個(gè)新的種群。更新是通過迭代應(yīng)用選擇、交叉和變異操作來 完成的。這個(gè)過程隨機(jī)丟棄不好的解，并進(jìn)化出更適合 （更好）的解。通過這些操作，期 望所改進(jìn)的解將一代一代（迭代）地變得更好。進(jìn)化計(jì)算成員有很多不同的算法都屬于 EC,如遺傳算法（GAs）13、遺傳規(guī)劃（GP）14、進(jìn)化規(guī)

12、劃（EP）15和進(jìn)化策略（ES）16。除GP外，EC的其他成員解決優(yōu)化問題。另一方面， GP通常會(huì)找到能夠解決給定問題的程式。遺傳算法的進(jìn)化基于達(dá)爾文適者生存原則， 個(gè)體的編碼通常是作為二進(jìn)制向量來完成的，而如前所述，GP雖然使用了與遺傳算法相同的適者生存原則，但進(jìn)化個(gè)體是程式。進(jìn)化規(guī)劃的靈感來自于自然選擇的進(jìn)化論： 另一方面，ES是一種基于適應(yīng)和進(jìn)化思想的搜索技術(shù)，它將個(gè)體編碼作為實(shí)數(shù)向量。另一方面，差異進(jìn)化與遺傳在繁殖機(jī)制上是不同的。雖然DE與其他進(jìn)化算法有許多相似之處，但它的顯著不同之處在于，當(dāng)前種群的距離和方向信息用于指導(dǎo)搜索過程。首 先應(yīng)用變異產(chǎn)生一個(gè)試探向量，然后在交叉算子內(nèi)使用該

13、試探向量產(chǎn)生一個(gè)后代，而在 一般EA中，卻是先應(yīng)用交叉算子，再應(yīng)用變異算子。止匕外，差分變異步長(zhǎng)也受當(dāng)前種 群個(gè)體間差異的影響，而EA變異則是按照某種概率分布進(jìn)行采用。EC的一些非常顯著的特征是：它們可以解決非常不結(jié)構(gòu)化的問題，我們只需要有 一種方法來評(píng)估解的質(zhì)量（適合度），而不需要目標(biāo)函數(shù)的可微性。通常，進(jìn)化算法被指 計(jì)算上非常耗時(shí)，不適合解決非常大規(guī)模的問題。盡管這在一般情況下沒毛病，但最近 的一項(xiàng)突破帶來了巨大的希望。最近的一項(xiàng)研究 17表明，自定義進(jìn)化算法可以處理涉 及十億個(gè)變量的整數(shù)線性規(guī)劃問題。討論這兩種方法（SI和EC）背后的哲學(xué)主要植根于自然物體的生物學(xué)行為。這兩種方法 都受到

14、自然現(xiàn)象的啟發(fā)，也都是尋找最優(yōu)解的搜索策略。群集智能是一種研究群居昆蟲 或動(dòng)物在極少規(guī)則下的集體行為。 進(jìn)化算法是基于自然選擇和遺傳進(jìn)化思想的自適應(yīng)啟 發(fā)式搜索算法。在群體智能中，群體中的個(gè)體成員是同一的，隨著時(shí)間的推移，這種同一性會(huì)以移 動(dòng)的形式保留下來。但在進(jìn)化算法中，種群成員會(huì)消亡并被后代取代。SI算法的靈感來自于鳥類、魚類和螞蟻等群體的覓食行為，在這些群體中，成員更新自己的位置只是為 了適應(yīng)環(huán)境。另一方面，進(jìn)化算法是基于達(dá)爾文適者生存的原則。在這些算法中，利用 交叉、變異等自然運(yùn)算符產(chǎn)生新的子代來代替整個(gè)種群。我們?cè)谏弦还?jié)關(guān)于進(jìn)化計(jì)算的討論結(jié)束時(shí)，提到了應(yīng)用EC解決了一個(gè)涉及十億個(gè)變量

15、的整數(shù)線性規(guī)劃問題，這可能是任何優(yōu)化方法處理過的最大的實(shí)際約束優(yōu)化問題。 在17中，作者提出了一種非?？焖俚幕诜N群的獲取近似最優(yōu)解的方法。這個(gè)成功的 故事顯然說明了 EC可能還沒有以正確的方式得到充分地探索研究，它強(qiáng)大到足以解決 真正的大規(guī)模問題，因此有必要進(jìn)行更多的研究，并且研究這樣的算法是很重要的，因 為隨著先進(jìn)技術(shù)的發(fā)展，會(huì)產(chǎn)生更多不同性質(zhì)的數(shù)據(jù)，研究人員/實(shí)踐者試圖解決更復(fù)雜 的高計(jì)算量的大規(guī)模問題。對(duì)于此類問題，傳統(tǒng)的優(yōu)化算法有時(shí)會(huì)變得不合適。止匕外， 在大多數(shù)優(yōu)化問題中，復(fù)雜系統(tǒng)都是用復(fù)雜的多維函數(shù)來建模的，有時(shí)不適合使用經(jīng)典 的優(yōu)化技術(shù)。眾所周知，經(jīng)典或傳統(tǒng)的優(yōu)化技術(shù)在解決實(shí)際

16、優(yōu)化問題時(shí)存在一定的局限 性，這主要是由于這些技術(shù)固有的解決機(jī)制，它們的效率也很大程度上取決于問題的維 數(shù)以及凸或非凸等求解空間的結(jié)構(gòu)。例如，單純形法只能用于求解具有線性約束的線性 目標(biāo)函數(shù)，但是，當(dāng)前場(chǎng)景中的大多數(shù)優(yōu)化問題都涉及各種決策變量和復(fù)雜的結(jié)構(gòu)化目 標(biāo)和約束（線性或非線性），因此，傳統(tǒng)的或數(shù)學(xué)的優(yōu)化程序通常是不易于求解。如果我 們對(duì)這些問題進(jìn)行建模，使它們能夠用經(jīng)典方法解決，那么幾乎可以肯定，我們將不得 不對(duì)精確表達(dá)進(jìn)行折衷，進(jìn)而降低了解的質(zhì)量。由于經(jīng)典優(yōu)化算法在求解大規(guī)模復(fù)雜優(yōu) 化問題時(shí)的局限性，基于群體智能和進(jìn)化計(jì)算的算法已成為研究熱點(diǎn)。這些技術(shù)非常有 效且靈活，只需要簡(jiǎn)單修改就

17、可以適應(yīng)特定的問題需求。需要強(qiáng)調(diào)的是，這里并不是說EC是一種萬能的方法，總是能優(yōu)于經(jīng)典方法，而應(yīng)該是當(dāng)情況需要時(shí)才會(huì)使用基于EC的方法，也就是說如果經(jīng)典優(yōu)化方法能有效解決，當(dāng)然優(yōu)先使用。例如，如果需要求解 具有線性約束的二次優(yōu)化問題或合理大小的線性規(guī)劃問題，就必須使用經(jīng)典方法，因?yàn)?這些方法具有良好的數(shù)學(xué)性質(zhì)和收斂結(jié)果。結(jié)束語對(duì)于一些復(fù)雜的優(yōu)化問題，EC算法和SI算法是較好的選擇，因?yàn)樗鼈儗?duì)目標(biāo)的數(shù) 學(xué)性質(zhì)和約束條件（如凸性、連續(xù)性或顯式定義）要求不高。這些方法使用隨機(jī)方法，可 以應(yīng)用于更廣泛的問題。但是，這種適用性伴隨著代價(jià)，即全局最優(yōu)的概率收斂性。此 外，這些算法有時(shí)也無法在當(dāng)前狀態(tài)下在搜

18、索空間的探索和利用之間取得適當(dāng)?shù)钠胶狻?通常，指導(dǎo)搜索過程的參數(shù)的選擇會(huì)變得很困難，結(jié)果可能在很大程度上取決于這些選 擇?？紤]到這些限制，在群體智能和進(jìn)化算法方面其實(shí)有很大的改進(jìn)空間。為了使這些 算法高效、準(zhǔn)確、可靠，這些領(lǐng)域的改進(jìn)和開發(fā)是一個(gè)持續(xù)不斷的過程。高計(jì)算能力的可用性促使人們利用 EC和SI更有效地解決復(fù)雜的問題。群體算法和 進(jìn)化算法可以為解決這類問題提供工具。沒有免費(fèi)午餐定理告訴我們，沒有單一的算法 可以被指定為最佳算法，只要它經(jīng)過足夠多的問題的測(cè)試，總是會(huì)激勵(lì)研究人員開發(fā)新 的計(jì)算智能算法。群體算法和進(jìn)化算法也被廣泛地與其他機(jī)器學(xué)習(xí)方法融合。近年來， 基于群體算法或進(jìn)化算法的深度

19、學(xué)習(xí)顯示出其作為一種非常有前途的機(jī)器學(xué)習(xí)算法13的潛力。在此我們注意到，當(dāng)目標(biāo)函數(shù)復(fù)雜、不可微、非凸時(shí)，EC和SI具有一定的優(yōu)勢(shì)。然而，也存在數(shù)據(jù)挖掘問題，除了問題的復(fù)雜表示之外，涉及的數(shù)據(jù)量可能非常大 （例如，在大氣科學(xué)、衛(wèi)生保健、天體物理學(xué)和社交媒體中）。在大數(shù)據(jù)時(shí)代，利用 EC和SI來挖掘這樣的數(shù)據(jù)集，可能會(huì)給研究人員帶來巨大的挑戰(zhàn)。這當(dāng)然并不意味著沒 有改進(jìn)的余地，而是表明我們需要在這些領(lǐng)域進(jìn)行更多的研究工作。參考文獻(xiàn)Beni, G. and J. Wang, Swarm Intelligence in Cellular Robotic Systems Robots and Biolo

20、gical Systems: Towards a New Bionics? 1993, Berlin: Springer.Reynolds, C., Flocks, Herds, and Schools: A Distributed Behavioral Model. ACM SIGGRAPH Computer Graphics, 1987.21: p. 25-34.Bonabeau, E., M. Dorigo, and G. TheraulazSwarm intelligence: from natural to artificial systems 1999: Oxford Univer

21、sity Press, Inc. 307.Dorigo, M., Optimization, Learning and Natural Algorithms （in Italian） . 1992.Kennedy, J. and R. Eberhart.Particle swarm optimization . in Proceedings of ICNN95 - International Conference on Neural Networks 1995.Karaboga, D.,An Idea Based on Honey Bee Swarm for Numerical Optimiz

22、ation, Technical Report - TR06. Technical Report, Erciyes University, 2005.Bansal, J.C., et al., Spider Monkey Optimization algorithm for numerical optimization. Memetic Computing, 2014. 6(1): p. 31-47.Passino, K.M., Biomimicry of bacterial foraging for distributed optimization and control. Ieee Con

23、trol Systems Magazine, 200222(3): p. 52-67.Yang, X.-S. Firefly Algorithms for Multimodal Optimization . in Stochastic Algorithms: Foundations and Applications. 2009. Berlin, Heidelberg: Springer Berlin Heidelberg.De Jong, K., The Handbook of Evolutionary Computation. 1999.M. Friedberg, R., A learning machine: Part I. Ibm Journal of Research and Development - IBMRD, 1958. 2: p. 2-13.Friedberg, R.M., B. Dunham, and J.H. North, A Learning Machine: Part II. IBM Journal o