1. 萬(wàn)有引力算法簡(jiǎn)介
（以下描述，均不是學(xué)術(shù)用語(yǔ)霞幅，僅供大家快樂的閱讀）
萬(wàn)有引力算法（Gravitational Search Algorithm）是受物體之間的萬(wàn)有引力啟發(fā)而提出的算法。算法提出于2008（2009）年，時(shí)間不長(zhǎng)，不過相關(guān)的文章和應(yīng)用已經(jīng)相對(duì)較多温圆，也有不少的優(yōu)化改進(jìn)方案。
萬(wàn)有引力算法中孩革，每一個(gè)物體的位置代表了一個(gè)可行解岁歉，而物體的質(zhì)量則反映了該位置的好壞，位置越好的物體的質(zhì)量越大膝蜈，反之物體的質(zhì)量越泄啤（質(zhì)量由適應(yīng)度值計(jì)算出，不是直接相等）饱搏。物體在解空間中的運(yùn)動(dòng)方式由其他物體的引力決定非剃，質(zhì)量越大的物體，在同等引力作用下的加速度較小推沸，所以單位時(shí)間內(nèi)的速度也相對(duì)較小备绽，位移距離較短券坞，反之加速度和速度都較大，位移距離較長(zhǎng)肺素。故可以簡(jiǎn)單的認(rèn)為恨锚，位置越優(yōu)的個(gè)體的移動(dòng)速度越慢，位置越差的個(gè)體的移動(dòng)速度越快倍靡。
2. 算法流程
萬(wàn)物之間皆有萬(wàn)有引力猴伶，不過在我們談到萬(wàn)有引力之時(shí)，對(duì)象大多是天體塌西，否則萬(wàn)有引力太小可以忽略不計(jì)他挎。所有這次我們的主角就是天體了。（總不可能是蘋果吧）雨让。
每一個(gè)天體都有個(gè)屬性：位置X雇盖，質(zhì)量M忿等，加速度A栖忠，以及速度V，還有適應(yīng)度值F贸街。
在D維空間內(nèi)有N個(gè)天體庵寞，其位置為
，加速度
薛匪，速度
捐川，其適應(yīng)度值為
。
2.1計(jì)算天體的質(zhì)量
第i個(gè)天體的質(zhì)量則是根據(jù)其適應(yīng)度值計(jì)算得出：
其中M為天體的質(zhì)量在群體重質(zhì)量中的占比逸尖， 分別表示全局最差天體的適應(yīng)度值和全局最優(yōu)個(gè)體的適應(yīng)度值古沥。
可以看出，處于最優(yōu)位置的天體的質(zhì)量m為1娇跟，最差位置的天體的質(zhì)量m為0岩齿。當(dāng)最優(yōu)天體和最差天體重合時(shí)，所有的天體的質(zhì)量m都為1苞俘。
2.2計(jì)算天體的加速度
由萬(wàn)有引力計(jì)算公式和加速度公式可以計(jì)算出當(dāng)前天體收到另一個(gè)天體萬(wàn)有引力而產(chǎn)生的加速度：
其中R表示第i個(gè)天體和第j個(gè)天體之間的歐式距離盹沈，aij為天體i在第d維上受到天體j的萬(wàn)有引力而產(chǎn)生的加速度,ai為第i個(gè)天體受到的其他所有天體萬(wàn)有引力的合力產(chǎn)生的加速度。G為萬(wàn)有引力常量吃谣，可以根據(jù)一下公式計(jì)算：
其中G0為初始值乞封，T為最大迭代次數(shù)。
2.3計(jì)算天體的速度并更新位置
計(jì)算出了天體的加速度岗憋，則可以根據(jù)當(dāng)前速度計(jì)算出下一步天體的運(yùn)行速度以及天體下一步的位置肃晚。
這一步比較簡(jiǎn)單與粒子群、蝙蝠等有速度的算法一致仔戈。
可以看出萬(wàn)有引力算法的流程異常的簡(jiǎn)單关串，與經(jīng)典的粒子群差不多惋鸥。萬(wàn)有引力算法也可以看做是一個(gè)優(yōu)化改進(jìn)版的粒子群，不過設(shè)計(jì)比較巧妙悍缠，引入的質(zhì)量卦绣、加速度等概念，但實(shí)現(xiàn)仍然很簡(jiǎn)單飞蚓。萬(wàn)有引力算法的效果如何滤港，在下一節(jié)將會(huì)進(jìn)行實(shí)驗(yàn)測(cè)試。
3. 實(shí)驗(yàn)
適應(yīng)度函數(shù)趴拧。
實(shí)驗(yàn)一：
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 搜索次數(shù)(最大迭代次數(shù)) | 100 |
| G0 | 100 |
| 取值范圍 | （-100溅漾，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| 值 | |
|---|---|
| 最優(yōu)值 | 2.3541929659476212E-18 |
| 最差值 | 0.12702092417237046 |
| 平均值 | 0.012796260245792387 |
從圖像中可以看出，各個(gè)天體都在不停的運(yùn)動(dòng)著榴，由于沒有貪心算法（優(yōu)于當(dāng)前值才改變位置）的加入添履，所以個(gè)天體有可能運(yùn)動(dòng)到比原先位置更差的地方，而且其收斂速度也比較快脑又。
從結(jié)果上看暮胧，似乎還不錯(cuò)，受到最差值的影響均值也相對(duì)較大问麸，算法結(jié)果的穩(wěn)定性不是太好往衷。
直覺上感覺算法有點(diǎn)問題。根據(jù)物理得來(lái)的直覺告訴我严卖，這些天體會(huì)相互靠近席舍，所以，它們不會(huì)集中到它們所構(gòu)成的凸包之外哮笆，凸實(shí)心物體的質(zhì)心不會(huì)跑到該物體的外部来颤。做個(gè)試驗(yàn)驗(yàn)證一下，將測(cè)試函數(shù)的最優(yōu)解設(shè)置到一個(gè)極端的位置稠肘。
實(shí)驗(yàn)二： 適應(yīng)度函數(shù)
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 搜索次數(shù)(最大迭代次數(shù)) | 100 |
| G0 | 100 |
| 取值范圍 | （-100福铅，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
這次最優(yōu)解位置在（90,90）處，該點(diǎn)有很大概率出現(xiàn)在初始天體所圍成的凸多邊形外启具。
| 值 | |
|---|---|
| 最優(yōu)值 | 23.0992211557913 |
| 最差值 | 1267.97543843818 |
| 平均值 | 417.19208443999185 |
從圖像中可以看出本讥，在天體們還沒有到達(dá)最優(yōu)位置附近（右下角的紅點(diǎn)）時(shí)，它們已經(jīng)收斂于一個(gè)點(diǎn)鲁冯，之后則很難再次向最優(yōu)解靠經(jīng)拷沸。看結(jié)果可以發(fā)現(xiàn)幾乎每一次實(shí)驗(yàn)的結(jié)果都不太好薯演，算法果然有點(diǎn)問題撞芍，不過問題不大。
萬(wàn)有引力出現(xiàn)這種現(xiàn)象可能有兩個(gè)原因：1.算法收斂的太快跨扮，還未對(duì)全局進(jìn)行充分搜索之時(shí)就收斂到了一點(diǎn)序无，收斂到一點(diǎn)后無(wú)法再運(yùn)到验毡。2.算法沒有跳出局部最優(yōu)的策略，萬(wàn)有引力作用下的天體慢慢聚集到奇點(diǎn)帝嗡，形成黑洞晶通，無(wú)法從中逃離。
那接下來(lái)哟玷，對(duì)萬(wàn)有引力算法的改進(jìn)方向也比較明確了：1.減緩其收斂速度狮辽，2增加跳出局部最優(yōu)操作，使之逃離黑洞巢寡。
看看萬(wàn)有引力常量G的函數(shù)圖像
幾乎在x/Xmax=1/5時(shí)已經(jīng)收斂到接近0喉脖。
實(shí)驗(yàn)三：修改
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 搜索次數(shù)(最大迭代次數(shù)) | 100 |
| G0 | 100 |
| 取值范圍 | （-100，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| 值 | |
|---|---|
| 最優(yōu)值 | 1.3110161211294625E-5 |
| 最差值 | 0.27745689480499086 |
| 平均值 | 0.033094478518038435 |
將萬(wàn)有引力常量的值修改為隨著迭代次數(shù)線性下降抑月，從圖像中可以看出树叽，效果還是比較明顯的，天體在不斷的運(yùn)動(dòng)谦絮，最后才收斂题诵、聚集于一起。從實(shí)驗(yàn)結(jié)果也可以看出挨稿，算法相對(duì)穩(wěn)定仇轻。結(jié)合圖像可以知道，改進(jìn)后奶甘，算法的收斂性下降，但全局搜索能力有較大的提升祭椰，算法的結(jié)果不會(huì)很差但是精度較低臭家。
| 值 | |
|---|---|
| 最優(yōu)值 | 2.828223575285611E-9 |
| 最差值 | 0.11880965981395 |
| 平均值 | 0.013540748540427833 |
將萬(wàn)有引力常量的下降趨勢(shì)放緩為原來(lái)的1/4，從圖像中可以看出方淤，算法的收斂速度非扯ち蓿快，也得到了較好的結(jié)果携茂，相比線性下降你踩，算法有著更好的精度，不足之處則是沒有跳出局部最優(yōu)的操作讳苦，收斂過快也容易陷入局部最優(yōu)带膜。
不知道原文為什么讓萬(wàn)有引力常量G的如此快的降到0，明明降的更慢能有更好的全局搜索能力鸳谜，但精度可能較差膝藕。猜測(cè)如果精度較差則在測(cè)試函數(shù)結(jié)果和曲線上比不贏對(duì)比的其他算法，論文沒法發(fā)了咐扭。其使用的測(cè)試函數(shù)的最優(yōu)解大多處于解空間的中心位置附近芭挽，即很少出現(xiàn)最優(yōu)解在天體所圍成的凸多面體之外的情況滑废，而實(shí)際問題中我們是無(wú)法預(yù)知最優(yōu)解在個(gè)位置的。
接下來(lái)袜爪，將試著為萬(wàn)有引力算法加入一點(diǎn)跳出局部最優(yōu)的操作蠕趁。
實(shí)驗(yàn)四：改進(jìn),新增以下規(guī)則及操作
在實(shí)驗(yàn)二的條件下
1. 處于最優(yōu)位置的天體保持自己的位置不動(dòng).
2. 如果某一個(gè)天體的運(yùn)動(dòng)后的位置優(yōu)于當(dāng)前全局最優(yōu)個(gè)體的位置則將當(dāng)前的最優(yōu)個(gè)體初始化到解空間的隨機(jī)位置.(將被自己干掉的大哥流放)。
3. 如果觸發(fā)了規(guī)則2辛馆，將所有的個(gè)體的以迭代次數(shù)重置為0妻导，即計(jì)算G=G0*e^(-20t/T)中的t置為0，重新計(jì)算萬(wàn)有引力常量怀各，若未觸發(fā)條件2則t=t+1倔韭。
| 值 | |
|---|---|
| 問題維度(維度) | 2 |
| 總?cè)簲?shù)量(種群數(shù)) | 20 |
| 搜索次數(shù)(最大迭代次數(shù)) | 100 |
| G0 | 100 |
| 取值范圍 | （-100，100） |
| 實(shí)驗(yàn)次數(shù) | 10 |
| 值 | |
|---|---|
| 最優(yōu)值 | 0.002865626046584871 |
| 最差值 | 0.34315942017305623 |
| 平均值 | 0.051625935063410844 |
從圖像上看瓢对，算法的全局搜索能力有大幅的增強(qiáng)寿酌，并且已經(jīng)集中到了最優(yōu)解的附近，而且由于加入了“流放”這一跳出局部最優(yōu)的操作硕蛹，可以看出醇疼，不斷的有新的個(gè)體出現(xiàn)在距最優(yōu)位置較遠(yuǎn)的位置。不過收斂速度有所下降法焰，因此局部搜索能力有一定減弱秧荆。
看結(jié)果，好像沒有實(shí)驗(yàn)三那么好埃仪，但與實(shí)驗(yàn)二相比乙濒，已經(jīng)有了很大的提升，而且有了跳出局部最優(yōu)的操作卵蛉，結(jié)果也相對(duì)穩(wěn)定颁股。
上述的實(shí)驗(yàn)僅僅是對(duì)直觀猜想的實(shí)現(xiàn)，如果想以此為改進(jìn)點(diǎn)傻丝，還要對(duì)其進(jìn)行大量的調(diào)優(yōu)忱嘹，相信會(huì)有不錯(cuò)的結(jié)果箱吕。
4. 總結(jié)
萬(wàn)有引力算法根據(jù)萬(wàn)有引力提出，結(jié)合了牛頓第二定律，可以說其操作步驟與真實(shí)的物理規(guī)律非常的貼切医寿。不過就像前文說過铺遂，受物理現(xiàn)象啟發(fā)而來(lái)的優(yōu)化算法其性能是未知的胳嘲，因?yàn)樗鼈儾痪邆渲悄苌醮挥兄?guī)律，有規(guī)律就會(huì)存在弱點(diǎn)胁澳，就會(huì)有搜索盲區(qū)该互。宇宙那么大，肯定存在沒有任何天體到達(dá)過的空間韭畸。
不過由于萬(wàn)有引力算法流程簡(jiǎn)單宇智，理解方便蔓搞，其優(yōu)化方案和能改進(jìn)的地方相對(duì)較多。萬(wàn)有引力算法的收斂速度過快随橘，導(dǎo)致其全局搜索能力較弱而局部搜索能力很強(qiáng)喂分，容易陷入局部最優(yōu)。根據(jù)其特點(diǎn)机蔗，我們可以降低其收斂速度或者增加跳出局部最優(yōu)操作蒲祈，來(lái)平衡算法的各個(gè)性能。
參考文獻(xiàn)
Rashedi E , Nezamabadi-Pour H , Saryazdi S . GSA: A Gravitational Search Algorithm[J]. Information Sciences, 2009, 179(13):2232-2248. 提取碼：xhpa
以下指標(biāo)純屬個(gè)人yy,僅供參考
| 指標(biāo) | 星數(shù) |
|---|---|
| 復(fù)雜度 | ★★☆☆☆☆☆☆☆☆ |
| 收斂速度 | ★★★★★★★☆☆☆ |
| 全局搜索 | ★★☆☆☆☆☆☆☆☆ |
| 局部搜索 | ★★★★★★★☆☆☆ |
| 優(yōu)化性能 | ★★★☆☆☆☆☆☆☆ |
| 跳出局部最優(yōu) | ★★☆☆☆☆☆☆☆☆ |
| 改進(jìn)點(diǎn) | ★★★★★★★☆☆☆ |
目錄
上一篇 優(yōu)化算法筆記（十六）混合蛙跳算法
下一篇 優(yōu)化算法筆記（十八）灰狼算法
優(yōu)化算法matlab實(shí)現(xiàn)（十七）萬(wàn)有引力算法matlab實(shí)現(xiàn)
