[發明專利]子空間淘汰式隨機搜索優化方法

在審

• 申請號: 201810536617.3
• 申請日: 2018-05-30
• 公開（公告）號: CN108875894A
• 公開（公告）日: 2018-11-23
• 發明（設計）人: 秦俊;黃玥;王楚婷;陳海鵬;申鉉京;秦貴和
• 申請（專利權）人: 吉林大學
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 吉林長春新紀元專利代理有限責任公司 22100
• 代理人: 王怡敏

本發明涉及一種子空間淘汰式隨機搜索優化方法，屬于隨機優化領域。把決策變量空間劃分成一些子空間塊，先在子空間中分別由某種搜尋方法對局部最優值進行初步的搜索，根據初步搜索結果進行擇優，按照已經找到的局部優化解的情況，留下有潛力的子空間塊，淘汰掉“沒有潛力”的子塊，對有潛力的子塊繼續下一輪搜尋，這樣不斷淘汰，最后搜索出最優解。因此在搜索中，能盡早淘汰不大可能存在最優點的部分，而把更多的搜索資源投入到最優閾值可能存在的區域，有利于提高搜索效率，包括速度和準確度。優點在于：搜尋效率高，有效降低計算復雜度，提高實時性的有點。具有通過參數調整，在優化指標與計算復雜度之間靈活選擇的優點。

技術領域

本發明涉及隨機優化領域，特別涉及一種面向有限決策變量空間單目標函數優化的最優解快速搜尋方法，尤指一種子空間淘汰式隨機搜索優化方法。適用于由數字變量構成的決策變量空間的情況，如數字圖像處理及計算機視覺等系統中的優化問題快速求解。本方法可廣泛應用于圖像處理，目標跟蹤、智能系統中的離散系統單目標優化等領域。

背景技術

尋找使某個函數(適應度函數)最優的解是優化的典型問題，也是應用型很強的一個研究領域。隨著基于計算機技術方法的發展，基于計算機數字計算方法和基于數字量的優化方法使用越來越多。尤其是基于群智能隨機優化方法不斷被提出，通過與強大的數字計算結合，與傳統方法比較體現出明顯的優勢。一個問題的最優解是很多規劃需要面對的問題。在人工智能領域，最有優化是一個基本問題，應用領域廣泛，如機器人的行為規劃、機器視覺、數字圖像處理等方面很多問題，都存在尋找最優解的問題。對于復雜問題尋找最優解的方法，基于群智能隨機搜索的策略相對傳統方法被認為是效率和效果綜合最好的方法。隨著計算智能的不斷發展，基于群智能的優化算法大量涌現。這些方法幾乎都是基于對自然模擬的方法。

這些群智能方法都有計算量大，較容易陷入局部最優解，實時性較差等問題。尤其是決策變量空間維數和尺度范圍大目標函數復雜的情況。但一般其在較小決策變量空間搜索效率更高。隨機搜索式優化方法，在決策變量空間中尋找最優解，可以看成是在一個空間范圍尋找某個目標的過程，如考古挖掘探測，尋找礦藏的探測。在這些過程中往往采用一種劃定一些局部區域(探方)先進行探測式挖掘(隨機搜索)，如果有某種跡象，則進一步發掘，否則停止(淘汰這個局部)。相當于在決策變量空間中化成子空間，對子空間進行按層次搜索，不斷淘汰不具潛力的子空間。只在具有潛力的子空間中進行進一步的搜索，直到找到最優解。這樣可以提高搜索群體的工作效率，減少計算量，提高搜尋速度。基于這樣的對比，急需一種模擬這種搜尋方式的隨機優化方法。

發明內容

本發明的目的在于提供一種子空間淘汰式隨機搜索優化方法，是一種局部分層隨機尋優的優化方法，解決了現有技術存在的上述問題。對優化問題的解空間劃分為均勻子空間塊，通過小粒子群對子空間塊探查，不斷淘汰劣塊，實現快速搜索最優解的方法。本發明是一個在n維決策變量X在一個有限可行域D中求解目標函數f(X)最優值(最大或最小值)的方法。即：

Min/Max f(X)

X∈D

D＝[0,M₀]×[0,M₁]…[0,M_n-1] (1)

M_j為一個有限數，j＝0,1,2…n-1；[0,M_i]范圍內的取值可以是連續的或離散的。

X是一個n維變量，X＝(x₀,x₁，…x_n-1)^T，x_j∈[0,M_j]。 (2)

當可行域空間的某維取值范圍不是從“0”點開始的有限范圍時，通過坐標平移，可以把其映射到從“0”點開始的一個有限區域。在當前基于數字量的計算中，很多優化問題的決策變量空間都是一個已知的有限域，如數字圖像及機器視覺領域的優化問題。