本文選題：引力搜索算法 + 索引的非支配解��； 參考：《吉林大學》2016年博士論文

【摘要】：近年來,在信息處理、機器學習、機器視覺與模式識別、管理科學等諸多領域存在著許多待解決的NP類復雜最優(yōu)化問題。通過傳統(tǒng)優(yōu)化方法解決這類問題已變得十分困難,所以現(xiàn)在學者們一般通過仿生途徑來解決這類復雜的最優(yōu)化問題。仿生類優(yōu)化方法與傳統(tǒng)優(yōu)化方法相比可以更快地找到優(yōu)化問題的最優(yōu)解,所以這類方法具有更高的現(xiàn)實意義和應用價值。群智能優(yōu)化算法作為一類新興的仿生類方法,屬于智能優(yōu)化算法的一個分支。與傳統(tǒng)優(yōu)化方法相比其優(yōu)點在于:第一,在求解問題時通常對與問題相關先驗知識沒有要求;第二,對問題本身的數(shù)學性質(zhì)如可導性和連續(xù)性沒有任何要求;第三,不需根據(jù)問題本身創(chuàng)建精確的數(shù)學模型,因而可以用于求解那些不易構建形式化模型的問題;第四,求解結(jié)果不依賴于對知識的表示方式,而是直接處理輸入信息。群智能優(yōu)化算法之所以優(yōu)于傳統(tǒng)優(yōu)化方法的原因在于它是一種按照概率進行搜索的算法,具體而言是通過觀察自然界和生物界規(guī)律,模仿仿生學原理,在優(yōu)化過程中利用種群間個體的競爭機制尋找問題的最優(yōu)解。如上所述,與其他方法相比群智能優(yōu)化算法具有較強的魯棒性、并行性、自適應性、隨機性,并且可以有效地解決集中控制的復雜分布式問題和用傳統(tǒng)優(yōu)化方法很難解決或無法解決的問題。對仿生類群智能優(yōu)化算法的探索和研究具有重要的應用價值。目前智能優(yōu)化算法主要包括遺傳算法、引力搜索算法、模擬退火算法、人工神經(jīng)網(wǎng)絡、免疫算法、DNA計算、粒子群優(yōu)化算法、狼群優(yōu)化算法、蟻群優(yōu)化算法、細菌趨藥性算法和螢火蟲優(yōu)化算法等。其中群智能優(yōu)化算法屬于模仿動物群體智能的算法。智能優(yōu)化算法共分為兩大類,即隨機性搜索算法與確定性搜索算法。其中隨機性搜索算法又可分為基于單解的智能優(yōu)化算法和基于種群的優(yōu)化算法,基于種群的智能優(yōu)化算法與基于單解的智能優(yōu)化算法相比,具有可以并行搜索的特點。因此,近年來基于種群的智能優(yōu)化算法受到了眾多學者的高度關注。群智能的研究方向主要分為以下三種:一是群智能行為模擬研究,通過模擬種群的行為獲取新系統(tǒng)模型并對其進行實現(xiàn);二是分布式裝置研究,利用機器人等先進設備和群智能的分布式搜索特性,設計分布式裝置系統(tǒng)并對其進行實現(xiàn);三是群智能算法研究,即對群智能算法的設計、改進及其應用。其中,群智能算法的改進及其應用是群智能理論研究的重點。雖然群智能優(yōu)化算法取得了不少具有應用價值研究成果,但仍存在以下一些問題:(1)群智能算法的理論基礎比較薄弱,理論分析沒有普遍意義,如收斂性分析等。(2)算法中的參數(shù)通常依據(jù)經(jīng)驗設置,沒有理論依據(jù)。因此群智能算法對應用環(huán)境和具體問題的依賴性較大。(3)當利用群智能算法處理突發(fā)事件時,系統(tǒng)可能會出現(xiàn)不可預測的反應,從而導致應用風險增加�？傊�,群智能優(yōu)化算法具有較強的魯棒性,較廣的適用范圍且不依賴于函數(shù),但也有一些缺陷,如易早熟、后期算法收斂速度慢、尋優(yōu)結(jié)果不精確等。雖然國內(nèi)外學者提出了各種各樣的改進方法,但仍存在一些亟待解決的難題。針對上述問題,本文主要研究了引力搜索和粒子群等群智能算法的改進,并將圖像分類、圖像檢索作為一個新的應用領域。本文的主要貢獻和研究成果如下:(1)對群智能優(yōu)化算法的研究現(xiàn)狀進行了全面綜述,并分析和討論了該領域當前的發(fā)展趨勢和所存在的困難。同時重點分析和討論了引力搜索和粒子群等群智能優(yōu)化方法的研究現(xiàn)狀和存在的缺陷。這些內(nèi)容的討論和分析是開展下一步研究工作的基礎;(2)針對現(xiàn)有引力搜索算法迭代速度較慢且容易陷入局部最優(yōu)等問題,我們提出一種新的混合引力搜索優(yōu)化模型,并應用于圖像分類領域。在該模型中,集成量化粒子思想和GSA搜索方法,幾乎在圖像特征提取的同時,進行特征選擇,大大的簡化了整個分類框架的特征提取與優(yōu)化速度。后續(xù)結(jié)合SVM分類器,進一步提高了圖像分類精度。實驗結(jié)果表明,我們所提出的混合引力搜索優(yōu)化算法在場景數(shù)據(jù)庫中,如Scene-8和RGB-NIR數(shù)據(jù)庫,取得優(yōu)于現(xiàn)有的群智能算法。(3)基于向心加速的粒子群優(yōu)化算法(Centripetal Accelerated Particle Swarm Optimization,CAPSO)作為一種改進的PSO算法,在優(yōu)化學習與收斂速度方面有較大提升。但是,其未對搜索過程陷入局部最優(yōu)的逃離速度加以控制,使得浪費了許多無效的停留時間,針對此,我們在CAPSO優(yōu)化過程中增加旋轉(zhuǎn)角度和旋轉(zhuǎn)半徑兩個參數(shù),使得其在向心加速過程中探索的時間最少,進而使得陷入局部最優(yōu)的逃離速度大大加快。此外,我們進一步將該CAPSO的改進方法,應用于圖像檢索領域的相關反饋中。實驗結(jié)果表明,我們的改進方法在醫(yī)學圖像檢索中獲得優(yōu)于其他的群智能方法檢索精度。(4)現(xiàn)有大多數(shù)的特征選擇方法是針對單一目標,然而在需要實際應用中存在基于多目標的特征選擇問題。鑒于此,我們提出一種基于多目標引力搜索的特征選擇方法�；诙嗄繕说乃枷氩皇菃我坏膬�(yōu)化問題,而是對所有優(yōu)化結(jié)果的子集進行分組,以獲得非劣解和非支配解。實驗結(jié)果表明,我們所提出的方法在UCI系列數(shù)據(jù)庫中獲得優(yōu)于其他多目標優(yōu)化算法的性能。下面就幾項具體的創(chuàng)新性工作進行詳細介紹。(1)改進的引力搜索算法及在圖像分類中的應用。本文主要研究的引力搜索算法是一種新型的啟發(fā)式群智能優(yōu)化算法,它是由伊朗克曼大學的Esmat Rashedi等人在2009年所提出。引力搜索算法的基本思想源于對物理學的萬有引力進行模擬而產(chǎn)生的群智能優(yōu)化算法,即將搜索的個體看成一組在空間運行的物體,個體間通過萬有引力相互作用吸引,引力作用的大小與個體的質(zhì)量成正比,與個體之間的距離成反比,因此萬有引力會促使個體們朝著質(zhì)量最大的個體移動,從而逐漸逼近求出優(yōu)化問題的最優(yōu)解。在引力搜索算法中,每個搜索粒子的質(zhì)量有四種屬性,即位置、慣性質(zhì)量、主動引力質(zhì)量以及被動引力質(zhì)量。粒子的位置代表著問題的解,它們的作用力和質(zhì)量取決于對象的適應度函數(shù)值,算法通過調(diào)整引力和慣性質(zhì)量來運行。在算法迭代過程中,期望粒子被慣性質(zhì)量大的粒子所吸引,在整個搜索空間中,慣性質(zhì)量最大的粒子代表問題的最優(yōu)解。引力搜索算法的流程一般分為如下幾個步驟:(i)識別搜索空間;(ii)隨機初始化搜索群體,即初始化所有粒子的位置和加速度,并設置迭代次數(shù)和算法中所采用的參數(shù);(iii)為每一個搜索粒子計算適應度值;(iv)更新萬有引力系數(shù);(v)計算各個不同方向的力,并計算其合力;(vi)計算加速度和速度;(vii)更新粒子的位置;(viii)循環(huán)步驟3-7,直到滿足最優(yōu)化問題的終止條件。從上述的步驟流程不難發(fā)現(xiàn),與其他基于種群的啟發(fā)式搜索算法一樣,引力搜索算法的迭代循環(huán)中同樣具有三個基本環(huán)節(jié)來實現(xiàn)優(yōu)化算法的搜索與學習能力,即粒子本身的調(diào)整,粒子之間的互相作用,粒子的選擇與更新。在第一個環(huán)節(jié),粒子通過調(diào)整完成自身性能的提升;在第二個環(huán)節(jié),粒子依靠相互作用完成信息的相互傳遞;在第三個環(huán)節(jié),粒子之間通過對比適應值完成更新與選擇。這三個環(huán)節(jié)都是啟發(fā)式的,不同的群智能算法依據(jù)不同的種群特性制定不同的運算機制,并通過多次迭代搜索找到全局最優(yōu)解。然而,相比其他群智能算法,引力搜索算法具有如下獨特的機理特點:(i)引力搜索算法是一種基于交互機制的算法,在最優(yōu)解的迭代搜索過程中,粒子搜索解是由質(zhì)量的大小來確定的,質(zhì)量小的粒子趨向質(zhì)量大的粒子;(ii)粒子受到的合力來自于周圍其他粒子對它的作用,即粒子可感應周圍的環(huán)境;(iii)根據(jù)萬有引力定律,質(zhì)量大的粒子其萬有引力也大,并對應著較好的解,從而其他粒子會向著質(zhì)量大的粒子方向運動;(iv)慣性質(zhì)量在一定程度上阻止粒子的運動改變,使得質(zhì)量大的粒子運動速度較為緩慢。這種特性一方面使粒子的搜索解空間受到一定限制,但另一方面也使局部搜索更為精細。這種慣性質(zhì)量可理解為自適應學習因子;(v)引力搜索算法是非記憶式的啟發(fā)式算法,即引力搜索算法的每次迭代循環(huán)都是獨立的,不受之前的尋優(yōu)結(jié)果的影響,某粒子的運動只決定于當前狀態(tài)下該粒子所受的合力。而粒子群算法相反,它是記憶式的。粒子算算法中的每次迭代均受到先前最優(yōu)解的影響,這也是粒子群較易陷入局部最優(yōu)的一個原因;(vi)引力搜索算法在高維問題的優(yōu)化問題中表現(xiàn)更為優(yōu)異,這歸因于搜索粒子運動的特性。粒子之間引力的大小受粒子之間距離的影響,于是粒子在運動中,搜索空間的各個維數(shù)之間是互相聯(lián)系的。引力搜索算法基于粒子之間的引力交互作用來完成尋找最優(yōu)解的過程,而萬有引力不需要借助任何傳播介質(zhì),處于搜索空間的粒子可獲知全局環(huán)境的信息,這使得粒子具有很強的全局搜索能力。然而,像其他全局搜索算法一樣,引力搜索算法也容易陷入局部最優(yōu)�，F(xiàn)階段,國內(nèi)外研究工作者對引力搜索算法的改進主要集中在加強該算法的局部搜索能力、提高種群的收斂速度和尋優(yōu)精度等方面,如增加搜索粒子的記憶性、基于混沌搜索、為質(zhì)量計算引入權重等方法。由于引力搜索算法在處理優(yōu)化問題上的優(yōu)異表現(xiàn),它在越來越多的領域得到應用,如決策函數(shù)的估計、混沌系統(tǒng)中的參數(shù)識別問題、機器人路徑規(guī)劃問題、聚類算法等等。截止目前,應用引力搜索算法在圖像分類、圖像檢索領域應用相對較少,而該領域的特征選擇、參數(shù)優(yōu)化、用戶相關反饋等問題都可通過應用引力搜索算法來解決。本文在以下三個方面對引力搜索算法進行了改進,進行了應用:1、通過分析引力搜索算法自身的機理和在尋優(yōu)過程中存在的缺陷,試圖引入某種解決方法來改進引力搜索算法,以提高尋優(yōu)速度和尋優(yōu)精度;2、將其他優(yōu)化算法的思想與引力搜索算法相結(jié)合,進一步改進引力搜索算法;3、將引力搜索算法應用于機器視覺領域,以解決圖像分類、圖像檢索領域中特征選擇、參數(shù)優(yōu)化、相關反饋等具體問題。(2)改進的向心加速的粒子群優(yōu)化算法及在圖像檢索相關反饋中的應用將引力搜索思想應用在粒子群優(yōu)化算法中,提出了一種新的群智能算法,即向心加速粒子群優(yōu)化算法。本文從改進引力搜索算法的思想出發(fā),對向心加速粒子群優(yōu)化算法進一步改進,并應用到圖像檢索相關反饋中。粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法是一種最重要的群智能技術之一。粒子群優(yōu)化算法對問題解的搜索是通過模擬自然界中的生物群體的社會行為實現(xiàn)的,例如鳥群和魚群,種群個體之間相互協(xié)作,利用個體信息和群體信息尋找食物。粒子群優(yōu)化算法將種群中的個體抽象為沒有體積和質(zhì)量但具有速度和位置的粒子,同時每個粒子還具有一個評判粒子位置好壞的適應度值。粒子群優(yōu)化算法以進化代表候選解的粒子群的方式求解問題。粒子的位置對應解空間的決策向量,表示粒子在決策空間中的位置;粒子的速度對應粒子在前一代進化中位置的改變,表示粒子在決策空間中移動的長度和方向;粒子的適應度值對應粒子的目標向量,表示粒子的優(yōu)劣。每個粒子具有一個個體最優(yōu)位置,該位置是其所經(jīng)歷的所有位置中具有最高適應度值的位置,同時每個種群具有一個全局最優(yōu)位置,該位置是全部粒子的個體最優(yōu)位置中適應度值最高的位置。種群中的粒子在進化過程中向粒子的個體最優(yōu)位置和種群的全局最優(yōu)位置移動,使粒子收斂到問題的最優(yōu)解。粒子群優(yōu)化算法作為一種新型的啟發(fā)式搜索算法,能夠在可接受的時間內(nèi)尋找到最優(yōu)解,卻不能保證最優(yōu)解的精確性,粒子群算法求得的最優(yōu)解只是近似解。粒子群優(yōu)化算法首先以隨機生成種群中粒子的初始位置和速度,然后對每個粒子進行進化操作,在進化過程中種群粒子利用個體最優(yōu)位置和全局最優(yōu)位置在解空間上更新自己的位置和速度,更新后計算出新位置的適應度值,如果更新后的位置的適應度值優(yōu)于個體最優(yōu)的適應度值,則更新個體最優(yōu),同理,如果新更新的位置的適應度值優(yōu)于全局最優(yōu),更新全局最優(yōu)位置的信息。與其他優(yōu)化算法相比,粒子群優(yōu)化算法的優(yōu)點主要體現(xiàn)在一下幾個方面:概念易于理解,算法實現(xiàn)簡單,對領域知識沒有要求,僅涉及一些簡單的初等數(shù)學知識;對待求解問題本身的結(jié)構,組織形式等要求不高,可以是黑盒問題;算法求解速度快,能夠在可接受的時間內(nèi)找到最優(yōu)解;算法具有靈活的全局搜索能力和局部搜索能力,同時可以使二者保持平衡,收斂速度快。然而粒子群優(yōu)化算法也有一些缺點:理論基礎薄弱,在搜索前期收斂速度很快,但當粒子趨近極值點時對算法的局部搜索調(diào)整比較慢,最終導致算法求解精度不高,不能夠確保算法收斂到局部最優(yōu)點;粒子群優(yōu)化算法作為啟發(fā)式算法,不能保證最優(yōu)解的精確性,粒子群算法求得的最優(yōu)解只是近似解;算法的局部搜索能力有限;當利用粒子群優(yōu)化算法求解多峰問題時,算法易陷入局部最優(yōu),無法保證算法求解的精度;在算法迭代過程中種群多樣性損失過快,使算法早熟。CAPSO算法主要探討了向心加速度以及它如何影響粒子在解空間中的搜索。因此問題的關鍵在于如何有效的調(diào)節(jié)粒子向心加速度的參數(shù)。這樣能夠使CAPSO在特征提取和特征選擇方面的效率得到加強,從而進一步地提高分類精度。此算法的第一步是初始化一組隨機解對搜索空間進行搜索。搜索的目標是經(jīng)過幾次迭代后能夠找到滿足目標函數(shù)的粒子[158]。由于一些被公認優(yōu)化方法都不能很好地解決高維度的問題,所以CAPSO算法也不例外。正是出于到這樣的考慮,所以在CAPSO的基礎上引入了其他參數(shù)使得算法在面對高維搜索空間的尋優(yōu)問題時能夠在局部開采和全局搜索方面做的更好。為了改進CAPSO算法,我們有必要提一下下面的這些問題:i.快速地從局部最優(yōu)中跳出ii.可調(diào)節(jié)參數(shù)的缺失iii.對隨機性的監(jiān)管iv.搜索停止v.不一致性問題vi.運行速度慢vii.過早收斂viii.二進制和實數(shù)的轉(zhuǎn)換問題本文改進了向心加速的粒子群優(yōu)化算法,在CAPSO優(yōu)化過程中增加旋轉(zhuǎn)角度和旋轉(zhuǎn)半徑兩個參數(shù),使得其在向心加速過程中探索的時間最少,進而使得陷入局部最優(yōu)的逃離速度大大加快。將改進的CAPSO,應用于醫(yī)學圖像檢索領域的相關反饋中。實驗結(jié)果顯示,該改進方法優(yōu)于其他的群智能方法。(3)基于多目標優(yōu)化引力搜索算法的特征選擇雖然多目標優(yōu)化問題是被認為是復雜的問題,但是它在科研中非常有用。多目標優(yōu)化問題和單目標優(yōu)化問題的區(qū)別在于多目標優(yōu)化問題要達到多個目標,但是這多個目標彼此之間可能存在沖突。在優(yōu)化的過程中多個相關的目標被同時優(yōu)化從而確定一組帕累托非支配解集。與單目標優(yōu)化問題的解不同,帕累托解集是利用支配的思想從解空間集合當中選取的一組解。帕累托最優(yōu)解的選擇主要基于帕累托前沿,它們是那些處于支配地位的解集。特征選擇是在對數(shù)據(jù)進行降維處理時常用的方法。特征選擇是指在某種特定的評估準則指導下,從初始的特征空間中選擇出滿足該準則的最佳特征子集,使得該子集可以提高算法的泛化能力,降低特征空間的維數(shù),并能在處理未知樣本時增強模型的預測能力。當前已經(jīng)有一些基于群智能算法的特征選擇研究工作,但是都是針對單一目標的優(yōu)化。然而在需要實際應用中存在基于多目標的特征選擇問題。本文提出一種基于多目標引力搜索的特征選擇方法。通過對所有優(yōu)化結(jié)果的子集進行分組,進行多目標優(yōu)化,獲得非劣解和非支配解。最后在UCI數(shù)據(jù)庫中進行了測試,結(jié)果表明效果優(yōu)于其他多目標優(yōu)化算法。
[Abstract]:......
【學位授予單位】：吉林大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP18
，

本文編號：1862919