[發明專利]非對稱負相關搜索方法

有效

• 申請號: 201910559830.0
• 申請日: 2019-06-24
• 公開（公告）號: CN110263906B
• 公開（公告）日: 2022-09-06
• 發明（設計）人: 陳恩紅;劉淇;于潤龍;葉雨揚
• 申請（專利權）人: 中國科學技術大學
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 北京凱特來知識產權代理有限公司 11260
• 代理人: 鄭立明;鄭哲

本發明公開了一種非對稱負相關搜索方法，將每一個搜索進程的搜索行為建模為概率分布，利用搜索進程搜索范圍的相對大小，將搜索行為進一步劃分為全局搜索行為和局部搜索行為。然后提出一種新的元啟發式搜索算法，即非對稱負相關搜索，它假設具有全局搜索行為的搜索進程應盡可能遠離具有局部搜索行為的搜索進程。得益于搜索進程之間非對稱的負相關的搜索趨勢，本發明提出的算法為元啟發式搜索提供了更優的探索與利用的平衡策略，擁有更好的搜索效率及更佳的整體性能。

技術領域

本發明涉及復雜實值優化和元啟發式搜索領域，尤其涉及一種非對稱負相關搜索方法。

背景技術

在現實世界中存在許多復雜的優化問題，例如，最小化汽車流體設計的空氣阻力，最小化天線陣列中的峰值傍瓣電平(Peak Side-Lobe Levels,PSLLs)，以及最優經濟調度問題中電力設備的折損，等等。這些復雜優化問題都涉及實值參數空間的許多局部極值解。通常，研究人員設計專門的模擬軟件來擬合復雜的優化場景，也就是說顯式的優化函數和梯度信息是很難被獲取的。這類優化問題被統稱為多模態(非凸)實值優化問題或黑盒優化問題，由于在大多數場景下，缺少對優化函數的有效信息，因此需要采取一般的啟發式假設來指導搜索解空間，所有的這些算法被歸納為元啟發式搜索。研究表明，元啟發式搜索在求解復雜實值優化問題時，展現了比一般遍歷方法和其他近似方法更好的優化性能。其中具有代表性的元啟發式搜索包括：爬山算法(Hill Climbing,HC)，模擬退火算法(SimulatedAnnealing,SA)，禁忌搜索(Tabu Search,TS)，遺傳算法(Genetic Algorithms,GA)，粒子群算法(Particle Swarm Optimizer,PSO)，演化策略(Evolution Strategies,ES)，差分演化(Differential Evolution,DE)，等等。

元啟發式搜索是基于一個或多個隨機搜索進程以及個體或種群的迭代實現的，種群中的每個個體代表了實值優化問題的一個可行候選解。為了衡量這些解的優劣，需要通過計算實值優化問題的函數值來評估這些候選解，稱得到的函數值為個體或解的適應度。適應度的大小通常被用于指導元啟發式搜索的搜索方向。對于復雜實值優化問題，一方面，由于解空間的維度高、規模大，存在大量的局部極值點，任何包含有限數量搜索進程的元啟發式搜索都不能保證發現全局最優解；另一方面，由于解空間的連續性和缺乏優化函數的梯度信息，采用任何隨機搜索算子的搜索進程都只能在有限的搜索步驟盡可能接近局部極值點，而不能到達極值點。因此，一個元啟發式搜索方法是注重解空間的探索，即探尋更多的局部極值點以發現全局更優的解，還是注重解的利用，即驅使適應度更優的解逼近周圍的某個局部極值點，是設計元啟發式搜索最為關鍵的問題之一，相關問題也被稱作探索與利用問題，或多樣化與集約化問題。許多元啟發式搜索提出了平衡探索與利用的方法或假設，研究表明這些元啟發式假設直接影響了搜索算法的性能。

特別地，基于種群的元啟發式搜索算法不僅在理論方面取得了成功，而且在應用方面被認為是經驗上更好的元啟發式搜索。盡管有許多工作討論了基于種群的探索與利用的平衡策略，但是可以從整體上把它們分為兩類：(1)小生境技術(Niching Techniques)。諸如適應度共享和擁擠方法的小生境技術旨在選擇解空間中彼此距離較遠的一組候選解，然后利用這些解產生新的候選解(一般通過雜交算子)。適應度共享方法試圖與鄰域的個體共享適應度，并通過犧牲部分候選解的適應度來維持種群的多樣化。而擁擠方法依賴于后代與其近代父母之間的競爭機制，允許調整選擇壓力以偏向選擇相隔距離很遠的個體，從而增進種群的多樣化。這種方法的問題是，多樣性的父母并不一定能夠產生多樣性的個體，小生境技術需要對父母之間的雜交策略提出嚴苛的要求。(2)自適應搜索步長(AdaptiveSearch Step-Size)。一方面，可以采用具有小搜索步長的搜索進程來發現更接近當前候選解的新的解，這有助于利用適應度更優的候選解。另一方面，可以采用具有大搜索步長的搜索進程來發現更遠離當前候選解的新的解，這有助于解空間的探索。許多元啟發式假設基于解空間的屬性提出了自適應搜索步長的策略。但是，這種方法會引入另一個算法設計問題，即，應該使用何種搜索進程，以及在迭代期間何時切換具有不同搜索步長的進程以實現探索與利用之間的良好折中。