生物地理學優(yōu)化算法的改進及在聚類優(yōu)化問題上的應用
發(fā)布時間:2020-07-07 15:17
【摘要】:優(yōu)化問題無處不在,與人們的生活息息相關。為了高效地處理優(yōu)化問題,群智能優(yōu)化算法應運而生。生物地理學優(yōu)化(Biogeography-Based Optimization,BBO)算法是群智能優(yōu)化算法之一,其模擬了物種在不同棲息地之間的遷移行為和生態(tài)環(huán)境的變異現(xiàn)象。BBO算法結構簡單易實現(xiàn),吸引了大量學者關注,并在數(shù)據(jù)挖掘、圖像處理、機械設計等諸多領域得到應用。然而,隨著社會的發(fā)展和科技的進步,科學和工程領域中所面臨的優(yōu)化問題越來越復雜,對算法性能的要求也越來越高。目前,BBO算法的性能依然有著較大的提升空間。聚類優(yōu)化是數(shù)據(jù)挖掘領域的一個重要分支,K-means算法是一種經(jīng)典的聚類算法,其原理簡單,具有較好的可伸縮性和高效性,但也存在K的個數(shù)無法確定,對初始點敏感等問題。為此,一些學者嘗試用群智能算法解決K-means算法存在的問題。BBO算法性能良好,應用廣泛,有潛力更好地處理聚類優(yōu)化問題,但目前相關研究甚少,因此,BBO算法在K-means聚類優(yōu)化上的應用有著較大的研究價值。本文介紹了BBO算法和聚類優(yōu)化的研究背景及意義,描述了BBO算法的步驟,分析了BBO算法存在的主要缺陷,對BBO算法的國內外研究現(xiàn)狀進行了簡單綜述。為了進一步提升BBO算法的性能并拓展其應用,本文針對BBO算法在處理高維和實際復雜問題時性能不強,效率不高和普適性不好的問題,提出了三種BBO改進算法,并應用改進算法處理K-means聚類優(yōu)化問題。本文主要研究工作如下:(1)為了增強BBO算法的優(yōu)化性能,提出了一種差分遷移和趨優(yōu)變異的生物地理學優(yōu)化算法(DGBBO)。對BBO算法的遷出棲息地選擇方法,遷移算子和變異算子分別進行改進,克服了輪賭選擇法可能選出較差的棲息地并將其信息分享給較優(yōu)的棲息地,遷移算子在解空間中可搜索到的位置局限和變異算子可能破壞優(yōu)質解的缺陷,又從多個角度降低計算復雜度,最終得到改進算法DGBBO。對DGBBO算法進行了計算復雜度分析,并在16個基準函數(shù)上進行了仿真實驗,對比了其它state-of-the-art算法,實驗結果表明,DGBBO算法具有較好的優(yōu)化性能。(2)為了提升BBO算法的優(yōu)化效率,提出了一種高效融合的生物地理學優(yōu)化算法(EMBBO)。首先去掉BBO算法的變異算子,大幅度降低計算復雜度,又對BBO算法的遷移算子進行改進,彌補變異算子的缺失并增強局部搜索能力,然后在改進的遷移算子中融入單維全維交叉更新策略,平衡了探索和開采并進一步降低計算復雜度,接著在算法中融入反向學習機制,一定程度上避免算法陷入局部最優(yōu),最終得到高效算法EMBBO。對EMBBO算法進行了穩(wěn)定性分析,并在21個基準函數(shù)和CEC2017測試集上進行了仿真實驗,對比了其它state-of-the-art算法,實驗結果表明,EMBBO算法具有較高的優(yōu)化效率。(3)為了更好地處理K-means聚類優(yōu)化問題,提出了一種生物地理學優(yōu)化和灰狼優(yōu)化(GWO)的混合算法(HBBOG)。將BBO算法和GWO算法分別進行改進,增強它們的性能,然后將兩種改進算法采用單維全維交叉更新策略進行混合,使它們優(yōu)勢互補,整體上平衡探索和開采,最終得到混合算法HBBOG。對HBBOG算法進行了全局收斂性分析,并在30個基準函數(shù)和9個聚類數(shù)據(jù)集上進行了仿真實驗,對比了其它有競爭力的算法,實驗結果驗證了HBBOG算法的普適性,表明HBBOG算法在處理K-means聚類優(yōu)化問題上整體表現(xiàn)最佳。3項研究在算法設計方面:第一項研究是在BBO算法的基礎上提出的創(chuàng)新性改進,重點強調算法性能的提升;第二項研究是在第一項研究的基礎上,借鑒了部分創(chuàng)新性改進,又提出了新的改進,不僅強調算法性能的提升,還強調了計算復雜度的大幅度降低,從而達到算法優(yōu)化效率高,可操作性強的目的;第三項研究是在第二項研究的基礎上,借鑒了部分創(chuàng)新性改進,又提出了新的改進,除了強調算法性能的提升外,還要求算法能處理更多類型的優(yōu)化問題,最終達到普適性強的目的。3項研究在實驗設計方面:第一項研究在一組常用的基準函數(shù)上進行了實驗;第二項研究在更多基準函數(shù)上進行了實驗;第三項研究不僅在基準函數(shù)上進行了實驗,還測試了聚類數(shù)據(jù)集。整體上,3項研究遵從由算法的簡單改進到復雜改進,由單一改進研究到改進和應用綜合研究的邏輯關系,后者較前者的改進更加完善,算法性能更加優(yōu)秀,實驗內容也更加豐富,這也對應了本文研究由淺入深的過程。
【學位授予單位】:河南師范大學
【學位級別】:碩士
【學位授予年份】:2018
【分類號】:TP18
【圖文】:
DGBBO算法與其不完整變體的收斂曲線
圖 4-2 共享操作優(yōu)概率 ps的計算如下所示。/= t MaxDT策略源自遺傳算法,被廣泛應用于優(yōu)化領域[54-55]。受交叉策略交叉策略,其表示如下。( ) ( ) ( 0.5 ) *( ( ) ( ))j SI j SI j i jSIV ← H SIV + rand H SIV H SIVSI是通過榜樣學習法選出的棲息地。(4-2)可知,(0.5-rand)可以得到一個-0.5 和 0.5 之間的權重,(H一個交叉值。權重乘以交叉值再加 HSI(SIVj),實現(xiàn)了在解空間中心的小范圍內擾動,其實質是在 HSI(SIVj)附近區(qū)域進行局部樣棲息地,擁有更優(yōu)的 HSI,故這種局部搜索更可能搜索到
代策略和趨優(yōu)引導策略主要用于局部搜索,相對來說,趨優(yōu)引選取的,具有更高的種群多樣性。由式(4-1)可知,t 的值增加,前期,ps的值較小,執(zhí)行趨優(yōu)引導策略的概率更大,在迭代接取代策略的概率更大。這樣的設置符合算法前期對種群多避免多樣性破壞優(yōu)質候選解。使 Hi(SIVj)有機會通過三種不同的策略進行更新,可以在局克服原遷移操作可搜索位置局限的缺陷,大幅度增強了局部的遷移算子 BBO 算法變異算子中的缺陷,直接去掉了該算子。為了彌算子中融入了基于平均選擇概率的兩種差分擾動操作,其詳改進的遷移算子流程如下所示。
【學位授予單位】:河南師范大學
【學位級別】:碩士
【學位授予年份】:2018
【分類號】:TP18
【圖文】:
DGBBO算法與其不完整變體的收斂曲線
圖 4-2 共享操作優(yōu)概率 ps的計算如下所示。/= t MaxDT策略源自遺傳算法,被廣泛應用于優(yōu)化領域[54-55]。受交叉策略交叉策略,其表示如下。( ) ( ) ( 0.5 ) *( ( ) ( ))j SI j SI j i jSIV ← H SIV + rand H SIV H SIVSI是通過榜樣學習法選出的棲息地。(4-2)可知,(0.5-rand)可以得到一個-0.5 和 0.5 之間的權重,(H一個交叉值。權重乘以交叉值再加 HSI(SIVj),實現(xiàn)了在解空間中心的小范圍內擾動,其實質是在 HSI(SIVj)附近區(qū)域進行局部樣棲息地,擁有更優(yōu)的 HSI,故這種局部搜索更可能搜索到
代策略和趨優(yōu)引導策略主要用于局部搜索,相對來說,趨優(yōu)引選取的,具有更高的種群多樣性。由式(4-1)可知,t 的值增加,前期,ps的值較小,執(zhí)行趨優(yōu)引導策略的概率更大,在迭代接取代策略的概率更大。這樣的設置符合算法前期對種群多避免多樣性破壞優(yōu)質候選解。使 Hi(SIVj)有機會通過三種不同的策略進行更新,可以在局克服原遷移操作可搜索位置局限的缺陷,大幅度增強了局部的遷移算子 BBO 算法變異算子中的缺陷,直接去掉了該算子。為了彌算子中融入了基于平均選擇概率的兩種差分擾動操作,其詳改進的遷移算子流程如下所示。
【相似文獻】
相關期刊論文 前10條
1 張宏哲;;FFT算法的一種改進[J];長安大學學報(自然科學版);1988年01期
2 苑寶生,俞鐵城;連呼漢語識別研究[J];聲學學報;1989年06期
3 孫楊模;;操作系統(tǒng)常見的幾種算法舉例分析[J];湖北三峽職業(yè)技術學院學報;2010年02期
4 吳天行;郭鍵;;基于“反學習”理論的人工蜂群算法在訂單分批問題中的應用[J];物流技術;2017年12期
5 肖海軍;成金華;何凡;;雙核因素蝙蝠算法[J];中南民族大學學報(自然科學版);2018年01期
6 張進;;一種快速雙對分邏輯運算算法[J];情報學報;1992年03期
7 陳廣江;用MUSIC算法處理非均勻間隔采樣數(shù)據(jù)[J];系統(tǒng)工程與電子技術;1998年09期
8 于浩;王芳;;ROHC算法在LWIP上的仿真與實現(xiàn)[J];計算機仿真;2017年12期
9 高廣尚;蔣泰;;ISO 18000-6 Type C中的防沖突機制分析[J];廣西科學院學報;2008年04期
10 劉津霖;付光遠;李海龍;汪洪橋;;基于改進投票專家算法的專有協(xié)議模糊測試方法[J];計算機工程與應用;2018年12期
相關會議論文 前6條
1 李孟霖;余祥;巫岱s
本文編號:2745277
本文鏈接:http://sikaile.net/kejilunwen/sousuoyinqinglunwen/2745277.html
最近更新
教材專著