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

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