萬有引力搜索算法要點教學課件

5.2比較PS0與RGA我們應用GSA到這些最小化函數(shù),并且比較RGA與PS0所得出的結(jié)果,在這些情況,群體大小設置為N=50。維數(shù)n=3表1,2的函數(shù)最大迭代次數(shù)為1000,表3為500,在PSO中C1=C2=2,慣性因素Q從0.9到0.2線性下降,在RGA應用算法交叉算子,高斯交換以及輪盤算法,交叉和變異的概率分別為0.3和0.1.在GSA,G用(21)式表示,G為100,a=20。T是所有迭代次數(shù)G(t=goeT(21)引力搜索算法GSA.AGravitationalsearchAlgorithm近幾年,多種啟發(fā)式優(yōu)化方法得到發(fā)展,這些方法中很多是根據(jù)自然中群體行為得到啟示本節(jié)課介紹一種基于萬有引力定律和質(zhì)量相互作用的新的優(yōu)化算法一引力搜索算法。引力搜索算法在2009年被首次提出,是一種基于萬有引力定律和牛頓第二定律的種群優(yōu)化算法。該算法通過種群的粒子位置移動來尋找最優(yōu)解,即隨著算法的循環(huán),粒子靠它們之間的萬有引力在搜索空間內(nèi)不斷運動,當粒子移動到最優(yōu)位置時,最優(yōu)解便找到了。Ⅰ.啟發(fā)式算法回顧工.萬有引力定律Ⅲ.引力搜索算法(GSA)ⅠV.比較研究V.實驗結(jié)果ⅥⅠ.引力搜索算法的研究展望I.啟發(fā)式算法(Heuristicalgorithms)"Heuristic"是希臘語,意為“啟發(fā)式”。啟發(fā)式是尋找好的(近似最佳)解的技術(shù)。對于那些受大自然的運行規(guī)律或者面向具體問題的經(jīng)驗、規(guī)則啟發(fā)出來的方法,人們常常稱為啟發(fā)式算法。啟發(fā)式算法是相對于最優(yōu)化算法提出的。很多實際的最優(yōu)化問題的計算是復雜的。因此,解決這樣問題的實際方法是運用啟發(fā)式算法,這樣可以在合理的計算時間內(nèi)找到一個近似最優(yōu)解。啟發(fā)式算法可以這樣定義:一個基于直觀或經(jīng)驗構(gòu)造的算法在可接受的花費(計算時間和空間)下給出解決組合優(yōu)化題每一個實例的一個可行解該可行解與最優(yōu)解的偏離程度一般不能被預計。啟發(fā)式算法模擬物理或生物過程,例如一些著名的算法,遺傳算法(GA)、模擬退火算法(SA)、蟻群算法(ACO)粒子群優(yōu)化算法(PSO)和細菌覓食算法(BFA)。GA靈感來自于達爾文進化論;SA利用熱力作用設計;ACO模擬螞蟻覓食行為;BFA來自于搜索和最佳覓食細菌;PSO模擬鳥群的行為上述提到的啟發(fā)式算法都是隨機行為。然而,Formato提出了基于引力運動的確定性的啟發(fā)式搜索算法,中心引力優(yōu)化(CFO)。中心引力優(yōu)化算法是根據(jù)物理運動學的模型建立的一個新型的優(yōu)化算法,通過初始化若干隨機質(zhì)點,進行迭代,直至找到最優(yōu)解。在一些隨機算法中,像模擬退火算法(SA)搜索開始于個單一的初始點,并且以一個連續(xù)的方式繼續(xù)。然而,大多數(shù)啟發(fā)式搜索算法用多個初始點以并行方式搜索。例如,群為基礎(chǔ)的算法使用類似于自然的鳥群或者魚群的一系列代理。在一個以群為基礎(chǔ)的算法,每一個體施行一系列的特殊運算并且分享這些信息給其他個體。這些操作大部分很簡單,然而它們的集體效應,稱為群體智能,會產(chǎn)生令人驚訝的結(jié)果。代理之間的局部相互作用提供了一個全局結(jié)果,它允許系統(tǒng)解決問題不需要應用任何的中央控制器。這種情況下,個體操作包括隨機搜索、正反饋、負反饋和多元相互作用,進行自組織。群體智能指許多簡單個體通過相互合作產(chǎn)生復雜智能行為的特性。我們可以在人群為基礎(chǔ)的啟發(fā)式算法識別兩個常見問題:勘探和開采?？碧接袛U大搜索空間的能力,開采有尋找最佳解決方案能力。在第一次迭代中,啟發(fā)式搜索算法勘探搜索空間尋找新的解。為了避免陷入局部最優(yōu)的陷阱,該算法必須在前幾次迭代中使用勘探。因此,在以人群為基礎(chǔ)的啟發(fā)式算法,勘探是一個重要的問題。通過勘探和開采,算法調(diào)整自己的半最優(yōu)點。要有高性能的搜索,關(guān)鍵點是一個合適的勘探和開采之間的權(quán)衡。然而,所有的以人群為基礎(chǔ)的啟發(fā)式搜索算法采用的勘探和開采方面,他們使用不同的方法和操作。換句話說,所有的搜索算法有一個共同的框架從不同的角度來看,一個以群為基礎(chǔ)的搜索算法的個體在每次迭代中通過三個步驟來實現(xiàn)勘探和開采概念自適應,合作和競爭。在自我調(diào)整的步驟,每個個體(代理)提高其性能。在合作中,個體彼此合作形成的信息傳遞。最后,在競爭的一步,個體競爭生存。這些步驟通常隨機形成,可以用不同的方式來實現(xiàn)。這些步驟從自然的啟發(fā),是以人群為基礎(chǔ)的啟發(fā)式算法的思想。這些概念,引導算法尋找全局最優(yōu)。然而,一個算法在解決一些問題是好的,在解決另外一些問題則不行。因此,提出高性能的新啟發(fā)式算法是非常受歡迎的。我們的目標是建立一個新的考慮到所提到的方面和基于引力規(guī)則的以群為基礎(chǔ)的搜索算法。工.萬有引力定律萬有引力定律是Newton于1687年在《自然哲學的數(shù)學原理》上提出的,萬有引力定律解釋物體之間相互作用關(guān)系的定律是物體間由于它們的引力質(zhì)量而引起的相互吸引力所遵循的規(guī)律。自然界中任何兩個物體都是相互吸引的,萬有引力普遍存在于任意兩個有質(zhì)量的物體之間。萬有引力定律表示如下自然界中任何兩個物體都是相互