萬有引力搜索算法ppt資料

1、15.2 比較(bjio)PSO與RGA我們應(yīng)用GSA到這些最小化函數(shù)，并且比較RGA與PSO所得出的結(jié)果，在這些情況，群體大小設(shè)置為 。維數(shù) ，表1,2的函數(shù)最大迭代次數(shù)為1000，表3為500，在PSO中 ，慣性因素 從0.9到0.2線性下降，在RGA應(yīng)用算法交叉算子(sun z)，高斯交換以及輪盤算法，交叉和變異的概率分別為0.3和0.1. 在GSA,G用(21)式表示， 為100， 。 是所有迭代次數(shù) (21)共五十三頁引力(ynl)搜索算法GSA：A Gravitational Search Algorithm共五十三頁3近幾年，多種啟發(fā)式優(yōu)化方法(fngf)得到發(fā)展，這些方法(fn

2、gf)中很多是根據(jù)自然中群體行為得到啟示。本節(jié)課介紹一種基于萬有引力定律和質(zhì)量相互作用的新的優(yōu)化算法引力搜索算法。引力搜索算法在2009年被首次提出，是一種基于萬有引力定律和牛頓第二定律的種群優(yōu)化算法。該算法通過種群的粒子位置移動(dòng)來尋找最優(yōu)解，即隨著算法的循環(huán)，粒子靠它們之間的萬有引力在搜索空間內(nèi)不斷運(yùn)動(dòng)，當(dāng)粒子移動(dòng)到最優(yōu)位置時(shí)，最優(yōu)解便找到了。共五十三頁4. 啟發(fā)式算法(sun f)回顧. 萬有引力定律. 引力搜索算法（GSA）. 比較研究. 實(shí)驗(yàn)結(jié)果. 引力搜索算法的研究展望共五十三頁5 Heuristic是希臘語，意為“啟發(fā)式”。啟發(fā)式是尋找好的（近似最佳）解的技術(shù)。對(duì)于那些受大自然的運(yùn)

3、行規(guī)律或者面向具體問題的經(jīng)驗(yàn)、規(guī)則啟發(fā)出來的方法，人們常常稱為啟發(fā)式算法。啟發(fā)式算法是相對(duì)于最優(yōu)化算法提出的。很多實(shí)際的最優(yōu)化問題的計(jì)算是復(fù)雜的。因此，解決這樣問題的實(shí)際方法是運(yùn)用啟發(fā)式算法，這樣可以在合理的計(jì)算時(shí)間內(nèi)找到一個(gè)近似最優(yōu)解。啟發(fā)式算法可以這樣定義：一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（計(jì)算時(shí)間和空間）下給出解決組合優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行(kxng)解該可行(kxng)解與最優(yōu)解的偏離程度一般不能被預(yù)計(jì)。（Heuristic algorithms）. 啟發(fā)式算法(sun f)共五十三頁6啟發(fā)式算法模擬物理或生物過程，例如一些著名的算法，遺傳算法（GA）、模擬退火算法（

4、SA）、蟻群算法（ACO）粒子群優(yōu)化算法（PSO）和細(xì)菌覓食算法（BFA）。GA靈感來自于達(dá)爾文進(jìn)化論；SA利用熱力作用設(shè)計(jì)；ACO模擬螞蟻覓食行為；BFA來自于搜索(su su)和最佳覓食細(xì)菌；PSO模擬鳥群的行為。上述提到的啟發(fā)式算法都是隨機(jī)行為。然而，F(xiàn)ormato提出了基于引力運(yùn)動(dòng)的確定性的啟發(fā)式搜索算法，中心引力優(yōu)化（CFO）。中心引力優(yōu)化算法是根據(jù)物理運(yùn)動(dòng)學(xué)的模型建立的一個(gè)新型的優(yōu)化算法，通過初始化若干隨機(jī)質(zhì)點(diǎn)，進(jìn)行迭代，直至找到最優(yōu)解。共五十三頁7在一些隨機(jī)算法中，像模擬退火算法（SA）搜索開始于一個(gè)單一的初始點(diǎn)，并且以一個(gè)連續(xù)的方式繼續(xù)。然而，大多數(shù)啟發(fā)式搜索算法用多個(gè)初始點(diǎn)以

5、并行方式搜索。例如，群為基礎(chǔ)的算法使用類似于自然的鳥群或者魚群的一系列代理。在一個(gè)以群為基礎(chǔ)的算法，每一個(gè)體施行一系列的特殊運(yùn)算，并且分享這些信息給其他個(gè)體。這些操作大部分很簡(jiǎn)單，然而它們的集體效應(yīng)，稱為群體智能，會(huì)產(chǎn)生令人驚訝的結(jié)果。代理之間的局部相互作用提供了一個(gè)全局結(jié)果，它允許系統(tǒng)解決問題不需要應(yīng)用任何的中央控制器。這種情況下，個(gè)體操作包括隨機(jī)搜索、正反饋、負(fù)反饋和多元相互作用，進(jìn)行自組織。群體智能指許多簡(jiǎn)單個(gè)體通過相互合作產(chǎn)生復(fù)雜(fz)智能行為的特性。共五十三頁8我們可以在人群為基礎(chǔ)的啟發(fā)式算法(sun f)識(shí)別兩個(gè)常見問題：勘探和開采?？碧接袛U(kuò)大搜索空間的能力，開采有尋找最佳解決方

6、案能力。在第一次迭代中，啟發(fā)式搜索算法勘探搜索空間尋找新的解。為了避免陷入局部最優(yōu)的陷阱，該算法必須在前幾次迭代中使用勘探。因此，在以人群為基礎(chǔ)的啟發(fā)式算法，勘探是一個(gè)重要的問題。通過勘探和開采，算法調(diào)整自己的半最優(yōu)點(diǎn)。要有高性能的搜索，關(guān)鍵點(diǎn)是一個(gè)合適的勘探和開采之間的權(quán)衡。然而，所有的以人群為基礎(chǔ)的啟發(fā)式搜索算法采用的勘探和開采方面，他們使用不同的方法和操作。換句話說，所有的搜索算法有一個(gè)共同的框架。共五十三頁9從不同的角度來看，一個(gè)以群為基礎(chǔ)的搜索算法的個(gè)體在每次迭代中通過三個(gè)步驟來實(shí)現(xiàn)勘探和開采概念:自適應(yīng)，合作和競(jìng)爭(zhēng)。在自我調(diào)整的步驟，每個(gè)個(gè)體（代理）提高其性能。在合作中，個(gè)體彼此合

7、作形成(xngchng)的信息傳遞。最后，在競(jìng)爭(zhēng)的一步，個(gè)體競(jìng)爭(zhēng)生存。這些步驟通常隨機(jī)形成(xngchng)，可以用不同的方式來實(shí)現(xiàn)。這些步驟從自然的啟發(fā)，是以人群為基礎(chǔ)的啟發(fā)式算法的思想。這些概念，引導(dǎo)算法尋找全局最優(yōu)。然而，一個(gè)算法在解決一些問題是好的，在解決另外一些問題則不行。因此，提出高性能的新啟發(fā)式算法是非常受歡迎的。我們的目標(biāo)是建立一個(gè)新的考慮到所提到的方面和基于引力規(guī)則的以群為基礎(chǔ)的搜索算法。共五十三頁10. 萬有引力定律萬有引力定律是Newton于1687年在自然哲學(xué)的數(shù)學(xué)原理上提出的，萬有引力定律解釋物體之間相互作用關(guān)系的定律，是物體間由于它們的引力質(zhì)量而引起的相互吸引力所遵

8、循的規(guī)律。自然界中任何兩個(gè)物體都是相互吸引(xyn)的，萬有引力普遍存在于任意兩個(gè)有質(zhì)量的物體之間。萬有引力定律表示如下：自然界中任何兩個(gè)物體都是相互吸引的，引力的大小和這兩個(gè)物體的質(zhì)量的乘積成正比，和它們之間距離平方成反比。數(shù)學(xué)表達(dá)式為：（1）其中(qzhng)，F(xiàn)表示兩個(gè)物體間的引力大小，G表示萬有引力常數(shù)，M1，M2分別表示兩個(gè)物體的質(zhì)量，R表示兩個(gè)物體之間的距離。共五十三頁11牛頓第二定律：當(dāng)一個(gè)(y )力F作用在一個(gè)(y )質(zhì)子上，它的加速度依賴于力和它的質(zhì)量(zhling)M：（2）根據(jù)（1）和（2），增加兩個(gè)質(zhì)子之間的距離意味著減少他們之間的萬有引力。此外，由于引力減少的影響，引

9、力常數(shù)的實(shí)際值依賴于宇宙的實(shí)際時(shí)間，方程（3）給出了降低引力常數(shù)與時(shí)間關(guān)系：（3）其中G(t)是在時(shí)間t引力常數(shù)的值，G(t0)是在t0時(shí)萬有引力常數(shù)。共五十三頁12理論物理學(xué)中定義三種質(zhì)量(zhling)：主動(dòng)引力質(zhì)量，是對(duì)物體重力場(chǎng)的強(qiáng)度的測(cè)量(cling)，小的主動(dòng)物體的重力場(chǎng)比大的主動(dòng)引力質(zhì)量的重力場(chǎng)弱。小的被動(dòng)被動(dòng)引力質(zhì)量的物體比大的被動(dòng)引力質(zhì)量的物體改變快。引力質(zhì)量的被動(dòng)引力質(zhì)量，是對(duì)物體重力場(chǎng)中物體相互作用的強(qiáng)度的測(cè)量，受到的力小。慣性質(zhì)量是當(dāng)有一個(gè)力作用在物體，改變她位置的移動(dòng)的力的測(cè)量，大的慣性質(zhì)量的物體改變它移動(dòng)的更慢，小的慣性共五十三頁13考慮到以上提到(t do)的三種

10、質(zhì)量定義，我們重新定義牛頓定律。萬有引力Fij通過物體j作用在物體i，與j 的主動(dòng)引力質(zhì)量和i 被動(dòng)引力質(zhì)量乘積成正比，與它們之間距離成反比。與Fij成正比，與i 慣性質(zhì)量成反比，則（1）（2）式重新定義(dngy)如下：（4）（5）和分別代表質(zhì)子i 的主動(dòng)引力質(zhì)量，質(zhì)子j 的被動(dòng)引力質(zhì)量，代表質(zhì)子i 的慣性質(zhì)量。雖然，慣性質(zhì)量，主動(dòng)引力質(zhì)量，被動(dòng)引力質(zhì)量有概念上的區(qū)別，但是沒有實(shí)驗(yàn)可以清楚的證明它們之間的不同。追溯到廣義相對(duì)論上，假設(shè)慣性質(zhì)量和被動(dòng)引力質(zhì)量是等價(jià)的，這就是所知道的弱等價(jià)原理。斯坦-達(dá)爾德廣義相對(duì)論也假定慣性質(zhì)量和主動(dòng)引力質(zhì)量是等價(jià)的，這個(gè)等價(jià)有時(shí)稱為強(qiáng)等價(jià)原理。共五十三頁14

11、在圖1中，F(xiàn)1j是作用在M1到Mj的力，F(xiàn)1是作用在M1和產(chǎn)生(chnshng)加速度 的所有力。圖1共五十三頁15雖然(surn)，慣性質(zhì)量，主動(dòng)引力質(zhì)量，被動(dòng)引力質(zhì)量有概念上的區(qū)別，但是沒有實(shí)驗(yàn)可以清楚的證明它們之間的不同。追溯到廣義相對(duì)論上，假設(shè)慣性質(zhì)量和被動(dòng)引力質(zhì)量是等價(jià)的，這就是所知道的弱等價(jià)原理。斯坦-達(dá)爾德廣義相對(duì)論也假定慣性質(zhì)量和主動(dòng)引力質(zhì)量是等價(jià)的，這個(gè)等價(jià)有時(shí)稱為強(qiáng)等價(jià)原理。共五十三頁16.引力搜索算法（GSA）受萬有引力定律啟發(fā)，提出了一種新型群體智能優(yōu)化算法引力搜索算法。引力搜索算法在求解優(yōu)化問題時(shí)，搜索個(gè)體的位置和問題的解相對(duì)應(yīng)，并且還要考慮個(gè)體質(zhì)量。個(gè)體質(zhì)量用于評(píng)價(jià)

12、個(gè)體的優(yōu)劣，位置越好，質(zhì)量越大。由于引力的作用，個(gè)體之間相互吸引并且朝著質(zhì)量較大的個(gè)體方向移動(dòng)，個(gè)體運(yùn)動(dòng)遵循牛頓第二定律。隨著運(yùn)動(dòng)的不斷進(jìn)行，最終整個(gè)群體都會(huì)聚集在質(zhì)量最大個(gè)體的周圍，從而找到質(zhì)量最大的個(gè)體，而質(zhì)量最大個(gè)體占據(jù)最優(yōu)位置。因此，算法可以獲得問題的最優(yōu)解。在GSA，每個(gè)代理有4個(gè)規(guī)格：位置，慣性質(zhì)量，主動(dòng)引力質(zhì)量和被動(dòng)引力質(zhì)量。每個(gè)個(gè)體的位置對(duì)應(yīng)一個(gè)(y )問題的解決方法，它們的引力和慣性質(zhì)量確定應(yīng)用的適應(yīng)度函數(shù)。換句話說，每個(gè)個(gè)體呈現(xiàn)一個(gè)解決方法，并且算法通過適當(dāng)?shù)恼{(diào)節(jié)引力和慣性質(zhì)量。共五十三頁17引力搜索算法屬于群體智能優(yōu)化算法，而群體智能優(yōu)化算法最顯著的特點(diǎn)是強(qiáng)調(diào)個(gè)體之間的相

13、互作用。這里，相互作用可以是個(gè)體間直接或間接的通信。在引力搜索算法中，萬有引力相當(dāng)于是一種(y zhn)信息傳遞的工具，實(shí)現(xiàn)個(gè)體間的優(yōu)化信息共享，整個(gè)群體在引力的作用下進(jìn)行優(yōu)化搜索。信息的交互過程不僅在群體內(nèi)部傳播了信息，而且群體內(nèi)所有個(gè)體都能處理信息，并根據(jù)其所得到的信息改變自身的搜索行為，這樣就能使得整個(gè)群體涌現(xiàn)出一些單個(gè)個(gè)體所不具備的能力和特性，也就是說，在群體中，個(gè)體行為雖然簡(jiǎn)單，但是個(gè)體通過得到的信息相互作用以解決全局目標(biāo)，信息在整個(gè)群體的傳播使得問題能夠比由單個(gè)個(gè)體求解更加有效的獲得解決。共五十三頁183.1 算法(sun f)的模型引力搜索算法首先在解空間和速度空間分別對(duì)位置(w

14、i zhi)和速度進(jìn)行初始化，其中位置表示問題的解。例如，d維空間中的第i 個(gè)搜索個(gè)體的位置和速度分別表示為，分別表示個(gè)體i 在第d 維的位置分量和速度其中，和分量。通過評(píng)價(jià)各個(gè)個(gè)體的目標(biāo)函數(shù)值，確定每個(gè)個(gè)體的質(zhì)量和受到的引力，計(jì)算加速度，并更新速度和位置。共五十三頁19（1）計(jì)算(j sun)質(zhì)量個(gè)體i 的質(zhì)量定義(dngy)如下：（6）（7）其中，和分別表示在第t 次迭代時(shí)第i 個(gè)個(gè)體的best(t)和worst(t)表示在第t次迭代時(shí)所有個(gè)體中最優(yōu)適應(yīng)度函數(shù)值和最差適應(yīng)度函數(shù)值，對(duì)最小化問題，其定義如下：（8）（9）適應(yīng)度函數(shù)值和質(zhì)量。共五十三頁20（2）計(jì)算(j sun)引力算法(su

15、n f)源于對(duì)萬有引力定律的模擬，但不拘泥于物理學(xué)中的萬有引力公式的精確表達(dá)式。在第d 維上，個(gè)體j 對(duì)個(gè)體i 的引力定義如下：（10）其中，G(t)表示在t 次迭代時(shí)萬有引力常數(shù)的取值， G(t)=G(G0，t),Rij(t)表示個(gè)體i和j 之間的歐氏距離，是一常數(shù)，防止分母為零。共五十三頁21在第d維上，個(gè)體(gt)i 所受的合力為：（11）其中，randj表示在0,1之間服從均勻分布的一個(gè)(y )隨機(jī)變量kbest表示個(gè)體質(zhì)量按降序排在前k個(gè)的個(gè)體，并且k的取值隨迭代次數(shù)線性減小，初值為N，終值為1。共五十三頁22（3）計(jì)算(j sun)加速度根據(jù)牛頓第二定律，個(gè)體(gt)i 在第d維的

16、加速度方程為：（12）（4）更新速度和位置（13）（14）其中，r表示在0,1之間服從均勻分布的一個(gè)隨機(jī)變量。共五十三頁23引力(ynl)搜索算法的目的并不是為了模擬萬有引力(ynl)定律，而是利用萬有引力定律的特點(diǎn)去解決優(yōu)化問題。算法受萬有引力定律的啟發(fā)，但是不拘泥于萬有引力公式的原始表達(dá)式。在算法中引力與兩個(gè)個(gè)體質(zhì)量的乘積成正比和它們的距離成反比的優(yōu)化效果更好。此外，萬有引力常數(shù)不在固定不變，而是隨著迭代次數(shù)單調(diào)遞減，算法的優(yōu)化效果更好。在計(jì)算個(gè)體受到的萬有引力合力時(shí)，算法只考慮質(zhì)量較大的個(gè)體產(chǎn)生的引力。因?yàn)樵谝λ阉魉惴ㄖ?，?dāng)引力較大時(shí)，或者有質(zhì)量較大的個(gè)體，或者兩個(gè)個(gè)體間的距離較小。質(zhì)

17、量大的個(gè)體占據(jù)較優(yōu)的位置，并且代表較好的解。算法僅考慮來自質(zhì)量較大的個(gè)體的引力，可以消除因距離較小而引力較大的影響，引導(dǎo)其他個(gè)體向質(zhì)量較大的個(gè)體方向移動(dòng)。在引力的不斷作用下，整個(gè)群體逐漸向質(zhì)量較大的個(gè)體方向逼近，最終搜索到問題的最優(yōu)解。共五十三頁243.2 算法(sun f)的流程基本引力搜索算法主要包含三個(gè)組成部分：群體初始化、計(jì)算個(gè)體質(zhì)量和所受的引力以及個(gè)體運(yùn)動(dòng)更新。算法的主要實(shí)現(xiàn)步驟如下：步驟1 隨機(jī)初始化群體中各個(gè)體的位置，個(gè)體的初始速度為零步驟2 個(gè)體最適值（個(gè)體的適應(yīng)度函數(shù)值）步驟3 更新G(t),best(t),worst(t),Mi(t)步驟4 計(jì)算個(gè)體所受到的合力步驟5 計(jì)算

18、加速度和速度步驟6 更新個(gè)體位置步驟7 若滿足(mnz)終止條件，則輸出當(dāng)前結(jié)果并終止算法，否則轉(zhuǎn)向步驟2.共五十三頁25上述(shngsh)程序的結(jié)構(gòu)流程如圖2所示。圖2共五十三頁26對(duì)引力搜索算法的特點(diǎn)做如下總結(jié)：（1）每個(gè)搜索個(gè)體都賦予4個(gè)狀態(tài)變量，分別為位置、速度、加速度和質(zhì)量(zhling)。位置用于表示位置的解，速度用于更新位置，加速度用于更新速度質(zhì)量用于評(píng)價(jià)個(gè)體的優(yōu)劣。（2）整個(gè)群體總是尋找質(zhì)量最大的個(gè)體，無論是最大值優(yōu)化問題還是最小值優(yōu)化問題，都可以通過質(zhì)量函數(shù)的定義，將優(yōu)化目標(biāo)轉(zhuǎn)換為搜索質(zhì)量最大的個(gè)體。（3）從引力搜索算法設(shè)計(jì)的起源來看，算法主要是對(duì)萬有引力定律的模擬，是將物

19、理原理和優(yōu)化思想相結(jié)合而產(chǎn)生的。引力搜索算法最顯著的特點(diǎn)是整個(gè)群體依靠個(gè)體之間的引力作用進(jìn)行尋優(yōu)，引力相當(dāng)于一種優(yōu)化信息的傳遞工具，根據(jù)算法的設(shè)計(jì)，個(gè)體的質(zhì)量越大，引力也越大。因此，在引力作用下，整個(gè)群體能夠向質(zhì)量最大的個(gè)體方向移動(dòng)，從而能夠搜索到問題的最優(yōu)解。（4）引力搜索算法的流程簡(jiǎn)單，參數(shù)設(shè)置少，可以很好的和各種優(yōu)化問題相結(jié)合，易于(yy)實(shí)現(xiàn)。共五十三頁27除了上述這些特點(diǎn)之外，引力搜索算法也具有智能優(yōu)化算法一些共同的特點(diǎn)。例如，引力搜索算法對(duì)目標(biāo)函數(shù)沒有特別要求，不要求函數(shù)具有連續(xù)和可導(dǎo)等數(shù)學(xué)性質(zhì)，甚至有時(shí)連有沒有解析表達(dá)式都不做要求，而且對(duì)問題中不確定的信息具有一定的適應(yīng)能力，因此

20、，算法的通用性比較強(qiáng)。此外，從算法實(shí)現(xiàn)的方法來看，引力搜索算法可以采用(ciyng)串行或者并行的方法實(shí)現(xiàn)，可以根據(jù)具體問題，設(shè)計(jì)出合理的算法實(shí)現(xiàn)方法。共五十三頁284. 比較研究 4.1 粒子(lz)群算法（PSO）PSO啟發(fā)于模擬社會(huì)行為，這種優(yōu)化方法更新粒子群，通過操作者根據(jù)從環(huán)境中獲得的最適信息，為了群個(gè)體可以移向最優(yōu)解。在PSO中， 和 的計(jì)算如下：（15）（16）ri1,ri2是0,1范圍的隨機(jī)變量(su j bin lin)，c1,c2是位置常數(shù)，w是慣性權(quán)重。pbesti表示第i 個(gè)質(zhì)子的最佳位置，gbest表示群中所有質(zhì)子的最佳位置。共五十三頁29從（16）式，我們發(fā)現(xiàn)每個(gè)質(zhì)

21、子(zhz)嘗試更新它的位置（Xi），用當(dāng)前位置和第i 個(gè)質(zhì)子最佳位置pbesti之間的距離以及當(dāng)前位置與gbest之間的距離。共五十三頁30 GSA vs PSO GSA和PSO的優(yōu)化在搜索空間通過個(gè)體移動(dòng)獲得，然而移動(dòng)規(guī)則是不同，一些重要的不同如下：a. PSO代理的方向計(jì)算僅用兩個(gè)最佳位置pbesti和gbest，GSA的基于整體合力的所有其他代理獲得。b. PSO應(yīng)用一種存儲(chǔ)器來更新速度(sd)（pbesti,gbest）,然而，GSA無存儲(chǔ)，在更新中僅需要代理的當(dāng)前位置起作用。c. PSO執(zhí)行更新不需要考慮解之間的距離；GSA的力與解之間距離成反比。d. 兩個(gè)算法的搜索理念是不同的，

22、PSO模擬鳥的行為，GSA源于物理現(xiàn)象。共五十三頁314.2 CFO 算法 中心(zhngxn)引力優(yōu)化CFO是確定性多維搜索算法。它的模型是穿越搜索空間重力影響下的探針。在開始時(shí)，初始探位置用一個(gè)確定方式計(jì)算。對(duì)于初始化，根據(jù)式（17），在零時(shí)刻每一個(gè)坐標(biāo)軸的位置矢量排列充滿均勻分布的探針，d=1.n， p=1.（17），fiti 是探針(tn zhn)i 的適應(yīng)度函數(shù)，它必須最大化。n是維數(shù)，N是探針數(shù)量，在CFO，每一次迭代，探針進(jìn)行評(píng)估。M用適用度函數(shù)計(jì)算，即式（18）， 是t時(shí)刻探針i 的質(zhì)量。（18）共五十三頁32隨后，加速度更新應(yīng)用式（19），一個(gè)新位置(wi zhi)計(jì)算應(yīng)用式

23、（20），是時(shí)間(shjin)t探針i 的加速度是時(shí)間t探針i 的位置是兩個(gè)常數(shù)。（19）（20）G是引力常數(shù)，Rij(t)是t時(shí)刻探針i和j 之間的歐氏距離。U是單位階躍函數(shù)共五十三頁33GSA vs CFO兩者的探索位置和加速度都來源于在引力場(chǎng)中的質(zhì)點(diǎn)運(yùn)動(dòng)，但它們使用不同的構(gòu)想（1）其中一個(gè)(y )主要的不同是CFO是固有的確定性的并且沒有應(yīng)用任何隨機(jī)參數(shù)在它的構(gòu)想，GSA是隨機(jī)搜索算法。（2）加速度和運(yùn)動(dòng)表現(xiàn)以及群體計(jì)算，GSA不同于CFO。（3）CFO初始探針位置分布是系統(tǒng)的（基于確定性的規(guī)則），在算法收斂有很大影響。GSA初始分布是隨機(jī)的。（4）CFO的G是常數(shù)，GSA中是控制參數(shù)。

24、共五十三頁34. 實(shí)驗(yàn)結(jié)果 5.1 基準(zhǔn)函數(shù) 表1表3中的基準(zhǔn)函數(shù)是測(cè)試實(shí)驗(yàn)所用到的基準(zhǔn)函數(shù)。在這些表中，n代表函數(shù)的維數(shù)，S是 的子集。表1和表2中函數(shù)除了 之外最小值都是0， 的最小值為 并且除了 , 和 以外，它們(t men)的最優(yōu)位置 都為 ， 和 的最優(yōu)位置 為 ， 的最優(yōu)位置 為 表1，單峰測(cè)試函數(shù)共五十三頁35表2，高維多峰測(cè)試函數(shù)表3，多峰低維測(cè)試函數(shù)共五十三頁36 三個(gè)算法(sun f)應(yīng)用到基準(zhǔn)函數(shù)，結(jié)果如下： （1）單峰高維函數(shù) 到 是單峰高維函數(shù)，這種情況下，因?yàn)橛衅渌椒▉韺ｉT設(shè)計(jì)優(yōu)化單峰函數(shù)，因此單峰函數(shù)搜索算法的收斂速度比最終結(jié)果更重要。 在表4中顯示，GSA對(duì)

25、所有函數(shù)的運(yùn)行結(jié)果要比RGA和PSO要好，GSA的收斂速度可由圖3,4得出，根據(jù)這些圖表，GSA比其他算法更快的找到全局最優(yōu)，因此GSA有較高的收斂速度。從表4的結(jié)果顯示，除了F5之外，基于權(quán)值的引力優(yōu)化算法對(duì)其他的4個(gè)基準(zhǔn)函數(shù)的搜索結(jié)果明顯好于引力搜索算法的搜索結(jié)，仿真效果如圖3,4所示 共五十三頁37表4高維單峰函數(shù)最小值搜索結(jié)果(ji gu)（函數(shù)維數(shù)n為30，最大迭代次數(shù)為1000）共五十三頁38n=30時(shí)，GSA,PSO,RGA對(duì)最小化優(yōu)化結(jié)果(ji gu)的比較圖3，圖4n=30時(shí)，GSA,PSO,RGA對(duì)最小化優(yōu)化結(jié)果(ji gu)的比較共五十三頁39 （2）多峰高維函數(shù) 多峰函

26、數(shù)有很多局部極小點(diǎn)并且?guī)缀醵己茈y優(yōu)化，我們進(jìn)行了在 至 上的局部極小值以指數(shù)形式增加的實(shí)驗(yàn)，函數(shù)維數(shù)設(shè)置為30，平均(pngjn)適應(yīng)度函數(shù)是最佳解的中間值，最后一次迭代函數(shù)在表5中顯示，對(duì) ， 和 ，GSA的表現(xiàn)比其他的算法更好，而對(duì)函數(shù) ，GSA無法自身調(diào)整已取得理想的好的結(jié)果。 共五十三頁40表5測(cè)試(csh)高維多峰函數(shù)最小值搜索結(jié)果（函數(shù)的維數(shù)n為30，最大迭代次數(shù)為1000）共五十三頁41圖5n=30時(shí)，GSA,PSO,RGA對(duì)最小化優(yōu)化結(jié)果(ji gu)的比較圖6n=30時(shí)，GSA,PSO,RGA對(duì)最小化優(yōu)化結(jié)果(ji gu)的比較共五十三頁42（3）多峰低維函數(shù) 表6表示了表3

27、的GSA,RGA,PSO的多峰低維函數(shù)基準(zhǔn)函數(shù)建的比較，在圖7和圖8，結(jié)果表明RGA,PSO和GSA有相同(xin tn)解并且大部分性能相同(xin tn)表6，表3基準(zhǔn)(jzhn)函數(shù)的最小化結(jié)果，（函數(shù)的維數(shù)n為如表1中所示，最大迭代次數(shù)為1000）共五十三頁43圖7n=4時(shí)，GSA,PSO,RGA對(duì)最小化優(yōu)化結(jié)果(ji gu)的比較圖8n=4時(shí)，GSA,PSO,RGA對(duì)最小化優(yōu)化結(jié)果(ji gu)的比較共五十三頁445.3 與CFO比較(bjio) 先來比較GSA與CFO，在相同(xin tn)條件下是很難比較區(qū)分這兩種算法。 CFO是一個(gè)確定性的算法，有很多性質(zhì)并依賴于初始群的生成和

28、群的規(guī)模，特別是隨著問題的復(fù)雜性與維數(shù)增加,CFO對(duì)于群規(guī)模和初始條件更敏感。而且，在這種條件下，CFO必須以一個(gè)較大的群規(guī)模以獲得一個(gè)可接受的，合理的結(jié)果。這也就意味著，在用CFO解決問題前，我們應(yīng)知道一些先驗(yàn)信息來建立群數(shù)量或多次嘗試運(yùn)行算法來獲得合適的群值。 而GSA是一種隨機(jī)搜索算法，一種可以廣泛的應(yīng)用于一個(gè)固定的小規(guī)模人口問題的優(yōu)化算法。正是由于上述原因，在相同條件下不能比較GSA與CFO對(duì)高維函數(shù)的優(yōu)化。因此，我們?cè)诘途S問題上比較這兩種算法。共五十三頁45 在CFO，在步驟0位置矢量充滿了在，每個(gè)坐標(biāo)軸的探針均勻分布。在GSA，初始值是隨機(jī)的，代理(dil)數(shù)和迭代次數(shù)的最大值設(shè)置

29、分別為60和500，（因?yàn)镃FO需要一個(gè)大規(guī)模種群，故取代理(dil)次數(shù)為60）。GSA的參數(shù)設(shè)置在前一節(jié)已給出，對(duì)于CFO， 。注意到，我們?cè)诒容^GSA和CFO對(duì)Formato 提出的函數(shù)時(shí)，需要一些適用于CFO的先驗(yàn)函數(shù)信息來進(jìn)行函數(shù)的優(yōu)化。 表7表示(biosh)，CFO的隨機(jī)初始化結(jié)果（不是均勻分布的初始化）平均超過30分，如表7所示，CFO在所得結(jié)果不能呈現(xiàn)隨機(jī)初始化時(shí)好的結(jié)果，并對(duì)初始化條件有重要影響：對(duì)于三個(gè)函數(shù)每一個(gè)算法的性能在圖9-11中表示，這些結(jié)果顯示，除了函數(shù) ， 外，GSA比CFO有更好的解。共五十三頁46表7，表1-3的一些函數(shù)的最小化結(jié)果，最大迭代(di di)

30、次數(shù)為500圖9. n=5時(shí)，GSA,PSO,RGA對(duì)隨機(jī)(su j)最小化的比較共五十三頁47圖10，n=5時(shí)，GSA,PSO,RGA對(duì)隨機(jī)(su j)最小化的比較圖11，n=2時(shí)，GSA,PSO,RGA對(duì)隨機(jī)(su j)最小化的比較共五十三頁48 對(duì)于高維函數(shù)的優(yōu)化，CFO應(yīng)用大量的搜索來運(yùn)行，由于CFO的確定性，它在最初的幾個(gè)迭代收斂(shulin)。表8總結(jié)概括了對(duì)代理次數(shù)N不同的30維的研究結(jié)果，在表4-6，通過比較平均最值的結(jié)果，我們可以看出，除了 ， ， ，GSA提供更好的解法，CFO在前幾次迭代中收斂(shulin)，在局部最優(yōu)并不能自調(diào)整。表8 對(duì)表1-3的CFO運(yùn)行(ynx

31、ng)優(yōu)化結(jié)果共五十三頁495.4 結(jié)論(jiln) 近幾年，已經(jīng)研究了多種啟發(fā)式優(yōu)化方法(fngf)，有些優(yōu)化方法(fngf)的靈感來自于自然群集行為，本文中總結(jié)了一種新的優(yōu)化算法，即引力搜索算法（GSA），GSA的構(gòu)造是基于萬有引力定律和質(zhì)量相互作用的概念。對(duì)GSA，我們有獨(dú)立的群系統(tǒng)，利用重力引力作用，系統(tǒng)中每個(gè)質(zhì)量可以看到其他質(zhì)量的情況。因此，萬有引力是一種傳遞不同質(zhì)量之間信息的工具。 為了評(píng)價(jià)我們的算法，我們?cè)O(shè)置不同的標(biāo)準(zhǔn)基準(zhǔn)函數(shù)進(jìn)行研究。通過GSA在大多數(shù)情況下得到的結(jié)果提供了更好的結(jié)果，并與PSO，RGA及CFO進(jìn)行比較。共五十三頁50.引力搜索算法的研究展望 引力搜索算法有望成為繼遺傳算法，蟻群優(yōu)化算法和微粒群優(yōu)化算法等算法之后又一個(gè)優(yōu)秀的智能優(yōu)化算法，將會(huì)得到更多的國內(nèi)外研究者的關(guān)注。但算法自提出以來，至今也只有短短的幾年發(fā)展時(shí)間（2009年提出）。和幾個(gè)成熟的算法比較而言，引力搜索算法還很年輕，還有很多的工作需要進(jìn)一步研究和探討： 6.1算法的理論研究 雖然