萬有引力搜索算法PPT課件.ppt

1 5 2比較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)用算法交叉算子 高斯交換以及輪盤算法 交叉和變異的概率分別為0 3和0 1 在GSA G用 21 式表示 為100 是所有迭代次數(shù) 21 引力搜索算法GSA AGravitationalSearchAlgorithm 2 3 近幾年 多種啟發(fā)式優(yōu)化方法得到發(fā)展 這些方法中很多是根據(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ā)式算法回顧 萬有引力定律 引力搜索算法 GSA 比較研究 實(shí)驗(yàn)結(jié)果 引力搜索算法的研究展望 5 Heuristic 是希臘語 意為 啟發(fā)式 啟發(fā)式是尋找好的 近似最佳 解的技術(shù) 對于那些受大自然的運(yùn)行規(guī)律或者面向具體問題的經(jīng)驗(yàn) 規(guī)則啟發(fā)出來的方法 人們常常稱為啟發(fā)式算法 啟發(fā)式算法是相對于最優(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è)可行解該可行解與最優(yōu)解的偏離程度一般不能被預(yù)計(jì) Heuristicalgorithms 啟發(fā)式算法 6 啟發(fā)式算法模擬物理或生物過程 例如一些著名的算法 遺傳算法 GA 模擬退火算法 SA 蟻群算法 ACO 粒子群優(yōu)化算法 PSO 和細(xì)菌覓食算法 BFA GA靈感來自于達(dá)爾文進(jìn)化論 SA利用熱力作用設(shè)計(jì) ACO模擬螞蟻覓食行為 BFA來自于搜索和最佳覓食細(xì)菌 PSO模擬鳥群的行為 上述提到的啟發(fā)式算法都是隨機(jī)行為 然而 Formato提出了基于引力運(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)以并行方式搜索 例如 群為基礎(chǔ)的算法使用類似于自然的鳥群或者魚群的一系列代理 在一個(gè)以群為基礎(chǔ)的算法 每一個(gè)體施行一系列的特殊運(yùn)算 并且分享這些信息給其他個(gè)體 這些操作大部分很簡單 然而它們的集體效應(yīng) 稱為群體智能 會產(chǎn)生令人驚訝的結(jié)果 代理之間的局部相互作用提供了一個(gè)全局結(jié)果 它允許系統(tǒng)解決問題不需要應(yīng)用任何的中央控制器 這種情況下 個(gè)體操作包括隨機(jī)搜索 正反饋 負(fù)反饋和多元相互作用 進(jìn)行自組織 群體智能指許多簡單個(gè)體通過相互合作產(chǎn)生復(fù)雜智能行為的特性 8 我們可以在人群為基礎(chǔ)的啟發(fā)式算法識別兩個(gè)常見問題 勘探和開采 勘探有擴(kuò)大搜索空間的能力 開采有尋找最佳解決方案能力 在第一次迭代中 啟發(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) 合作和競爭 在自我調(diào)整的步驟 每個(gè)個(gè)體 代理 提高其性能 在合作中 個(gè)體彼此合作形成的信息傳遞 最后 在競爭的一步 個(gè)體競爭生存 這些步驟通常隨機(jī)形成 可以用不同的方式來實(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ì)量而引起的相互吸引力所遵循的規(guī)律 自然界中任何兩個(gè)物體都是相互吸引的 萬有引力普遍存在于任意兩個(gè)有質(zhì)量的物體之間 萬有引力定律表示如下 自然界中任何兩個(gè)物體都是相互吸引的 引力的大小和這兩個(gè)物體的質(zhì)量的乘積成正比 和它們之間距離平方成反比 數(shù)學(xué)表達(dá)式為 1 其中 F表示兩個(gè)物體間的引力大小 G表示萬有引力常數(shù) M1 M2分別表示兩個(gè)物體的質(zhì)量 R表示兩個(gè)物體之間的距離 11 牛頓第二定律 當(dāng)一個(gè)力F作用在一個(gè)質(zhì)子上 它的加速度 依賴于力和它的質(zhì)量M 2 根據(jù) 1 和 2 增加兩個(gè)質(zhì)子之間的距離意味著減少他們之間的萬有引力 此外 由于引力減少的影響 引力常數(shù)的實(shí)際值依賴于宇宙的實(shí)際時(shí)間 方程 3 給出了降低引力常數(shù)與時(shí)間關(guān)系 3 其中G t 是在時(shí)間t引力常數(shù)的值 G t0 是在t0時(shí)萬有引力常數(shù) 12 理論物理學(xué)中定義三種質(zhì)量 主動(dòng)引力質(zhì)量 是對物體重力場的強(qiáng)度的測量 小的主動(dòng) 物體的重力場比大的主動(dòng)引力質(zhì)量的重力場弱 小的被動(dòng) 被動(dòng)引力質(zhì)量的物體比大的被動(dòng)引力質(zhì)量的物體 改變快 引力質(zhì)量的 被動(dòng)引力質(zhì)量 是對物體重力場中物體相互作用的強(qiáng)度的測量 受到的力小 慣性質(zhì)量 是當(dāng)有一個(gè)力作用在物體 改變她位置的移動(dòng)的 力的測量 大的 慣性質(zhì)量的物體改變它移動(dòng)的更慢 小的慣性 13 考慮到以上提到的三種質(zhì)量定義 我們重新定義牛頓定律 萬有引力Fij通過物體j作用在物體i 與j的主動(dòng)引力質(zhì)量和i被動(dòng)引力質(zhì)量乘積成正比 與它們之間距離成反比 與Fij成正比 與i慣性質(zhì)量成反比 則 1 2 式重新定義如下 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)可以清楚的證明它們之間的不同 追溯到廣義相對論上 假設(shè)慣性質(zhì)量和被動(dòng)引力質(zhì)量是等價(jià)的 這就是所知道的弱等價(jià)原理 斯坦 達(dá)爾德廣義相對論也假定慣性質(zhì)量和主動(dòng)引力質(zhì)量是等價(jià)的 這個(gè)等價(jià)有時(shí)稱為強(qiáng)等價(jià)原理 14 在圖1中 F1j是作用在M1到Mj的力 F1是作用在M1和產(chǎn)生加速度的所有力 圖1 15 雖然 慣性質(zhì)量 主動(dòng)引力質(zhì)量 被動(dòng)引力質(zhì)量有概念上的區(qū)別 但是沒有實(shí)驗(yàn)可以清楚的證明它們之間的不同 追溯到廣義相對論上 假設(shè)慣性質(zhì)量和被動(dòng)引力質(zhì)量是等價(jià)的 這就是所知道的弱等價(jià)原理 斯坦 達(dá)爾德廣義相對論也假定慣性質(zhì)量和主動(dòng)引力質(zhì)量是等價(jià)的 這個(gè)等價(jià)有時(shí)稱為強(qiáng)等價(jià)原理 16 引力搜索算法 GSA 受萬有引力定律啟發(fā) 提出了一種新型群體智能優(yōu)化算法 引力搜索算法 引力搜索算法在求解優(yōu)化問題時(shí) 搜索個(gè)體的位置和問題的解相對應(yīng) 并且還要考慮個(gè)體質(zhì)量 個(gè)體質(zhì)量用于評價(jià)個(gè)體的優(yōu)劣 位置越好 質(zhì)量越大 由于引力的作用 個(gè)體之間相互吸引并且朝著質(zhì)量較大的個(gè)體方向移動(dòng) 個(gè)體運(yùn)動(dòng)遵循牛頓第二定律 隨著運(yùn)動(dòng)的不斷進(jìn)行 最終整個(gè)群體都會聚集在質(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è)體的位置對應(yīng)一個(gè)問題的解決方法 它們的引力和慣性質(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è)體之間的相互作用 這里 相互作用可以是個(gè)體間直接或間接的通信 在引力搜索算法中 萬有引力相當(dāng)于是一種信息傳遞的工具 實(shí)現(xiàn)個(gè)體間的優(yōu)化信息共享 整個(gè)群體在引力的作用下進(jìn)行優(yōu)化搜索 信息的交互過程不僅在群體內(nèi)部傳播了信息 而且群體內(nèi)所有個(gè)體都能處理信息 并根據(jù)其所得到的信息改變自身的搜索行為 這樣就能使得整個(gè)群體涌現(xiàn)出一些單個(gè)個(gè)體所不具備的能力和特性 也就是說 在群體中 個(gè)體行為雖然簡單 但是個(gè)體通過得到的信息相互作用以解決全局目標(biāo) 信息在整個(gè)群體的傳播使得問題能夠比由單個(gè)個(gè)體求解更加有效的獲得解決 18 3 1算法的模型 引力搜索算法首先在解空間和速度空間分別對位置和速度進(jìn)行初始化 其中位置表示問題的解 例如 d維空間中的第i個(gè)搜索個(gè)體的位置和速度分別表示為 分別表示個(gè)體i在第d維的位置分量和速度 其中 和 分量 通過評價(jià)各個(gè)個(gè)體的目標(biāo)函數(shù)值 確定每個(gè)個(gè)體的質(zhì)量和受到的引力 計(jì)算加速度 并更新速度和位置 19 1 計(jì)算質(zhì)量 個(gè)體i的質(zhì)量定義如下 6 7 其中 和 分別表示在第t次迭代時(shí)第i個(gè)個(gè)體的 best t 和worst t 表示在第t次迭代時(shí)所有個(gè)體中最優(yōu)適應(yīng)度函數(shù)值和最差適應(yīng)度函數(shù)值 對最小化問題 其定義如下 8 9 適應(yīng)度函數(shù)值和質(zhì)量 20 2 計(jì)算引力 算法源于對萬有引力定律的模擬 但不拘泥于物理學(xué)中的萬有引力公式的精確表達(dá)式 在第d維上 個(gè)體j對個(gè)體i的引力定義如下 10 其中 G t 表示在t次迭代時(shí)萬有引力常數(shù)的取值 G t G G0 t Rij t 表示個(gè)體i和j之間的歐氏距離 是一常數(shù) 防止分母為零 21 在第d維上 個(gè)體i所受的合力為 11 其中 randj表示在 0 1 之間服從均勻分布的一個(gè)隨機(jī)變量 kbest表示個(gè)體質(zhì)量按降序排在前k個(gè)的個(gè)體 并且k的取值隨迭代次數(shù)線性減小 初值為N 終值為1 22 3 計(jì)算加速度 根據(jù)牛頓第二定律 個(gè)體i在第d維的加速度方程為 12 4 更新速度和位置 13 14 其中 r表示在 0 1 之間服從均勻分布的一個(gè)隨機(jī)變量 23 引力搜索算法的目的并不是為了模擬萬有引力定律 而是利用萬有引力定律的特點(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ì)量大的個(gè)體占據(jù)較優(yōu)的位置 并且代表較好的解 算法僅考慮來自質(zhì)量較大的個(gè)體的引力 可以消除因距離較小而引力較大的影響 引導(dǎo)其他個(gè)體向質(zhì)量較大的個(gè)體方向移動(dòng) 在引力的不斷作用下 整個(gè)群體逐漸向質(zhì)量較大的個(gè)體方向逼近 最終搜索到問題的最優(yōu)解 24 3 2算法的流程 基本引力搜索算法主要包含三個(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ì)算加速度和速度步驟6更新個(gè)體位置步驟7若滿足終止條件 則輸出當(dāng)前結(jié)果并終止算法 否則轉(zhuǎn)向步驟2 25 上述程序的結(jié)構(gòu)流程如圖2所示 圖2 26 對引力搜索算法的特點(diǎn)做如下總結(jié) 1 每個(gè)搜索個(gè)體都賦予4個(gè)狀態(tài)變量 分別為位置 速度 加速度和質(zhì)量 位置用于表示位置的解 速度用于更新位置 加速度用于更新速度質(zhì)量用于評價(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ì)的起源來看 算法主要是對萬有引力定律的模擬 是將物理原理和優(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 引力搜索算法的流程簡單 參數(shù)設(shè)置少 可以很好的和各種優(yōu)化問題相結(jié)合 易于實(shí)現(xiàn) 2020 2 5 27 28 除了上述這些特點(diǎn)之外 引力搜索算法也具有智能優(yōu)化算法一些共同的特點(diǎn) 例如 引力搜索算法對目標(biāo)函數(shù)沒有特別要求 不要求函數(shù)具有連續(xù)和可導(dǎo)等數(shù)學(xué)性質(zhì) 甚至有時(shí)連有沒有解析表達(dá)式都不做要求 而且對問題中不確定的信息具有一定的適應(yīng)能力 因此 算法的通用性比較強(qiáng) 此外 從算法實(shí)現(xiàn)的方法來看 引力搜索算法可以采用串行或者并行的方法實(shí)現(xiàn) 可以根據(jù)具體問題 設(shè)計(jì)出合理的算法實(shí)現(xiàn)方法 29 4 比較研究4 1粒子群算法 PSO PSO啟發(fā)于模擬社會行為 這種優(yōu)化方法更新粒子群 通過操作者根據(jù)從環(huán)境中獲得的最適信息 為了群個(gè)體可以移向最優(yōu)解 在PSO中 和的計(jì)算如下 15 16 ri1 ri2是 0 1 范圍的隨機(jī)變量 c1 c2是位置常數(shù) w是慣性權(quán)重 pbesti表示第i個(gè)質(zhì)子的最佳位置 gbest表示群中所有質(zhì)子的最佳位置 30 從 16 式 我們發(fā)現(xiàn)每個(gè)質(zhì)子嘗試更新它的位置 Xi 用當(dāng)前位置和第i個(gè)質(zhì)子最佳位置pbesti之間的距離以及當(dāng)前位置與gbest之間的距離 31 GSAvsPSOGSA和PSO的優(yōu)化在搜索空間通過個(gè)體移動(dòng)獲得 然而移動(dòng)規(guī)則是不同 一些重要的不同如下 a PSO代理的方向計(jì)算僅用兩個(gè)最佳位置pbesti和gbest GSA的基于整體合力的所有其他代理獲得 b PSO應(yīng)用一種存儲器來更新速度 pbesti gbest 然而 GSA無存儲 在更新中僅需要代理的當(dāng)前位置起作用 c PSO執(zhí)行更新不需要考慮解之間的距離 GSA的力與解之間距離成反比 d 兩個(gè)算法的搜索理念是不同的 PSO模擬鳥的行為 GSA源于物理現(xiàn)象 32 4 2CFO算法中心引力優(yōu)化CFO是確定性多維搜索算法 它的模型是穿越搜索空間重力影響下的探針 在開始時(shí) 初始探位置用一個(gè)確定方式計(jì)算 對于初始化 根據(jù)式 17 在零時(shí)刻每一個(gè)坐標(biāo)軸的位置矢量排列充滿均勻分布的探針 d 1 n p 1 17 fiti是探針i的適應(yīng)度函數(shù) 它必須最大化 n是維數(shù) N是探針數(shù)量 在CFO 每一次迭代 探針進(jìn)行評估 M用適用度函數(shù)計(jì)算 即式 18 是t時(shí)刻探針i的質(zhì)量 18 33 隨后 加速度更新應(yīng)用式 19 一個(gè)新位置計(jì)算應(yīng)用式 20 是時(shí)間t探針i的加速度 是時(shí)間t探針i的位置 是兩個(gè)常數(shù) 19 20 G是引力常數(shù) Rij t 是t時(shí)刻探針i和j之間的歐氏距離 U是單位階躍函數(shù) 34 GSAvsCFO 兩者的探索位置和加速度都來源于在引力場中的質(zhì)點(diǎn)運(yùn)動(dòng) 但它們使用不同的構(gòu)想 1 其中一個(gè)主要的不同是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ù) 35 實(shí)驗(yàn)結(jié)果5 1基準(zhǔn)函數(shù)表1 表3中的基準(zhǔn)函數(shù)是測試實(shí)驗(yàn)所用到的基準(zhǔn)函數(shù) 在這些表中 n代表函數(shù)的維數(shù) S是的子集 表1和表2中函數(shù)除了之外最小值都是0 的最小值為并且除了 和以外 它們的最優(yōu)位置都為 和的最優(yōu)位置為 的最優(yōu)位置為 表1 單峰測試函數(shù) 36 表2 高維多峰測試函數(shù) 表3 多峰低維測試函數(shù) 37 三個(gè)算法應(yīng)用到基準(zhǔn)函數(shù) 結(jié)果如下 1 單峰高維函數(shù)到是單峰高維函數(shù) 這種情況下 因?yàn)橛衅渌椒▉韺ｉT設(shè)計(jì)優(yōu)化單峰函數(shù) 因此單峰函數(shù)搜索算法的收斂速度比最終結(jié)果更重要 在表4中顯示 GSA對所有函數(shù)的運(yùn)行結(jié)果要比RGA和PSO要好 GSA的收斂速度可由圖3 4得出 根據(jù)這些圖表 GSA比其他算法更快的找到全局最優(yōu) 因此GSA有較高的收斂速度 從表4的結(jié)果顯示 除了F5之外 基于權(quán)值的引力優(yōu)化算法對其他的4個(gè)基準(zhǔn)函數(shù)的搜索結(jié)果明顯好于引力搜索算法的搜索結(jié) 仿真效果如圖3 4所示 38 表4高維單峰函數(shù)最小值搜索結(jié)果 函數(shù)維數(shù)n為30 最大迭代次數(shù)為1000 39 n 30時(shí) GSA PSO RGA對最小化優(yōu)化結(jié)果的比較 圖3 圖4 n 30時(shí) GSA PSO RGA對最小化優(yōu)化結(jié)果的比較 40 2 多峰高維函數(shù)多峰函數(shù)有很多局部極小點(diǎn)并且?guī)缀醵己茈y優(yōu)化 我們進(jìn)行了在至上的局部極小值以指數(shù)形式增加的實(shí)驗(yàn) 函數(shù)維數(shù)設(shè)置為30 平均適應(yīng)度函數(shù)是最佳解的中間值 最后一次迭代函數(shù)在表5中顯示 對 和 GSA的表現(xiàn)比其他的算法更好 而對函數(shù) GSA無法自身調(diào)整已取得理想的好的結(jié)果 41 表5測試高維多峰函數(shù)最小值搜索結(jié)果 函數(shù)的維數(shù)n為30 最大迭代次數(shù)為1000 42 圖5n 30時(shí) GSA PSO RGA對最小化優(yōu)化結(jié)果的比較 圖6n 30時(shí) GSA PSO RGA對最小化優(yōu)化結(jié)果的比較 43 3 多峰低維函數(shù)表6表示了表3的GSA RGA PSO的多峰低維函數(shù)基準(zhǔn)函數(shù)建的比較 在圖7和圖8 結(jié)果表明RGA PSO和GSA有相同解并且大部分性能相同 表6 表3基準(zhǔn)函數(shù)的最小化結(jié)果 函數(shù)的維數(shù)n為如表1中所示 最大迭代次數(shù)為1000 44 圖7n 4時(shí) GSA PSO RGA對最小化優(yōu)化結(jié)果的比較 圖8n 4時(shí) GSA PSO RGA對最小化優(yōu)化結(jié)果的比較 45 5 3與CFO比較 先來比較GSA與CFO 在相同條件下是很難比較區(qū)分這兩種算法 CFO是一個(gè)確定性的算法 有很多性質(zhì)并依賴于初始群的生成和群的規(guī)模 特別是隨著問題的復(fù)雜性與維數(shù)增加 CFO對于群規(guī)模和初始條件更敏感 而且 在這種條件下 CFO必須以一個(gè)較大的群規(guī)模以獲得一個(gè)可接受的 合理的結(jié)果 這也就意味著 在用CFO解決問題前 我們應(yīng)知道一些先驗(yàn)信息來建立群數(shù)量或多次嘗試運(yùn)行算法來獲得合適的群值 而GSA是一種隨機(jī)搜索算法 一種可以廣泛的應(yīng)用于一個(gè)固定的小規(guī)模人口問題的優(yōu)化算法 正是由于上述原因 在相同條件下不能比較GSA與CFO對高維函數(shù)的優(yōu)化 因此 我們在低維問題上比較這兩種算法 46 在CFO 在步驟0位置矢量充滿了在 每個(gè)坐標(biāo)軸的探針均勻分布 在GSA 初始值是隨機(jī)的 代理數(shù)和迭代次數(shù)的最大值設(shè)置分別為60和500 因?yàn)镃FO需要一個(gè)大規(guī)模種群 故取代理次數(shù)為60 GSA的參數(shù)設(shè)置在前一節(jié)已給出 對于CFO 注意到 我們在比較GSA和CFO對Formato提出的函數(shù)時(shí) 需要一些適用于CFO的先驗(yàn)函數(shù)信息來進(jìn)行函數(shù)的優(yōu)化 表7表示 CFO的隨機(jī)初始化結(jié)果 不是均勻分布的初始化 平均超過30分 如表7所示 CFO在所得結(jié)果不能呈現(xiàn)隨機(jī)初始化時(shí)好的結(jié)果 并對初始化條件有重要影響 對于三個(gè)函數(shù)每一個(gè)算法的性能在圖9 11中表示 這些結(jié)果顯示 除了函數(shù) 外 GSA比CFO有更好的解 47 表7 表1 3的一些函數(shù)的最小化結(jié)果 最大迭代次數(shù)為500 圖9 n 5時(shí) GSA PSO RGA對隨機(jī)最小化的比較 48 圖10 n 5時(shí) GSA PSO RGA對隨機(jī)最小化的比較 圖11 n 2時(shí) GSA PSO RGA對隨機(jī)最小化的比較 49 對于高維函數(shù)的優(yōu)化 CFO應(yīng)用大量的搜索來運(yùn)行 由于CFO的確定性 它在最初的幾個(gè)迭代收斂 表8總結(jié)概括了對代理次數(shù)N不同的30維的研究結(jié)果 在表4 6 通過比較平均最值的結(jié)果 我們可以看出 除了 GSA提供更好的解法 CFO在前幾次迭代中收斂 在局部最優(yōu)并不能自調(diào)整 表8對表1 3的CFO運(yùn)行優(yōu)化結(jié)果 50 5 4結(jié)論 近幾年 已經(jīng)研究了多種啟發(fā)式優(yōu)化方法 有些優(yōu)化方法的靈感來自于自然群集行為 本文中總結(jié)了一種新的優(yōu)化算法 即引力搜索算法 GSA GSA的構(gòu)造是基于萬有引力定律和質(zhì)量相互作用的概念 對GSA 我們有獨(dú)立的群系統(tǒng) 利用重力引力作用 系統(tǒng)中每個(gè)質(zhì)量可以看到其他