解無約束非線性全局最優(yōu)化的一種新進化算法及其收斂性

1、解無約束非線性全局最優(yōu)化的一種新進化算法及其收斂性    核心提示：年 月電 學(xué) 報了 又 二 以二 解無約束非線性全局優(yōu)化的一種新進化算法及其收斂性王 宇平 , 焦永昌 , 張福順西安 電 了科技 大學(xué)理學(xué)院 , 陜 西 西安 川 西安電 子利技 人羊天線研究所 , 陜西西安摘 要 進化算法是解復(fù)雜非線性規(guī)劃問題的 一 種新型 有效方法 , 但現(xiàn)有方法.        年 月電 學(xué) 報了 又 二 以二 解無約束非線性全局優(yōu)化的一種新進化算法及其收斂性王 宇平 , 焦永昌 ,

2、 張福順西安 電 了科技 大學(xué)理學(xué)院 , 陜 西 西安 川 西安電 子利技 人羊天線研究所 , 陜西西安 摘 要 進化算法是解復(fù)雜非線性規(guī)劃問題的 一 種新型 有效方法 , 但現(xiàn)有方法的計算 髦通常較大 為減小計算 量 , 提高算法 的效率 , 本文利用均勻設(shè)計來構(gòu)造新的高效進化算法,新的進化算法本身具有類似于傳統(tǒng)優(yōu)化技術(shù) 中的局部搜索功能 , 因此它能非常有效地搜索解空問 , 保持種群的多樣性,減小 計算 量 文 中還證 明了新算法 的全局收斂性 最后 的模擬結(jié)果表明 , 新算法計算 墩小 且收斂速度快 關(guān)鍵詞 進化計算 均勻設(shè)計 非線性規(guī)劃 中圖分類號 文獻標識碼 文童編號 一 一 一 一

3、, 一擴,以一 、八。? 一了 。、, “ 釗 了, 、, ?！按?, , 夕腳 ,。 粉,姍以 了 “ 朋 靦 ,嶸, 刃叔認 , ,羊。 , , , 八“ “ , 以、 介 了記 瓜 、 瀏 叮?二 四?腳 , , 旗 羅 一 ” 玉 即蘭 , 了 即 羅 硯、 、 伴 詳 一 。門 叩巨。 , 卿 , 、, 羅 ,、, 舊 卿日企 , 砰 一 月卜二 。 四 , , 、 、? 洋司代 娜 、 邵引言在電子工程等領(lǐng)域有很 多復(fù)雜的全局 優(yōu)化問題 , 它們通常很難用 傳統(tǒng)的優(yōu)化方法求解 進化算法 是求解這些問題最有效的一類方法川 它通常能跳 出局部最優(yōu)解而求 出 全局最優(yōu)解 一 “ 但其計算

4、 量一般較大 為減少 汁算貴 , 提高算法效率 , 已有一些新的方法 出現(xiàn) 一 “ , 然 而 , 它們的效 果仍不 盡理想 均勻設(shè)計是統(tǒng)計和 數(shù)論結(jié)合而產(chǎn)生 的一種新的試驗設(shè)計方一法川 , 其主要思想是在所考慮的空 間用最少的計算 童設(shè)計一個均勻散布的點集 本文利用它來構(gòu)造新的高效進化算法 ,新的進化算法產(chǎn)生的后代均勻散布在其父母附近 , 因 而具有 類似于傳統(tǒng)優(yōu)化技術(shù)中的局部搜索功能 , 因此 , 新的進化算法能非常有效地搜索解空間 , 保持種群 的多樣 巴 另外 , 由于新算法本身具有局部搜索的功能 , 運行時不需再進行局部搜索,因而和其它方法相 比 , 不僅有效 , 而且 計算 錄小

5、文 中還 對維數(shù)均為 的 個 困難的標準試驗 函數(shù)進行 廠計算 , 與文獻 中已有結(jié)果 一 “ 的比較表 明 , 新算法不僅能找 出全局最優(yōu)解 或更好的近似全局最優(yōu)解 , 而且計算量 比已 有方法小得多新的雜交算子下面介紹如何用均勻設(shè) 計一 構(gòu)造高效 的雜交算子 均勻設(shè)計 可產(chǎn)生 個 維整數(shù)點、 , 、 , ? , 。卜, , ? , 一 瀏 、 一二 一, 其中 為素數(shù) , 為適 當(dāng)正整數(shù) 可 由 中給出的表查 出 滿足 。 三 一 , 。, 且 , 護 , ? , ” 一 側(cè) 婦是 不 同的數(shù) 假設(shè)被選定進 行雜交 的兩點為 二 , , ? ,戈 了 和 二 , , ? , 兒 ” , 新

6、的雜交算子步驟為步 令 。 , , 少 , 二 , , 關(guān) , , , ? , ,定 義。, , 。, , ? , , 。 , , , ? , 。 了步 選適 當(dāng)大小的素數(shù) , 查文仁 中表可得對應(yīng)的 ,用式 求 今 個點步 與 的 , 個后代 , , ? , 尸 可 由下面兩種情形產(chǎn)生情形 若 三 叮一 , 則 刃 二 , 、, ? , 式 丁 的分量可定義為,。 。 弓一 。 , , , , , ? ,情形 若 。一 , 將任一 維 向量 二 , , ? ,氣 不 分成 一 子向量 , , , 礦, ? , 尸 一 尹, 其中 , 押, ? , 氣一,一州是 一一 維子向量 , 二 , ,

7、 ? ,。一 , 廠 , , ? , 。一 是在 , 。 中隨機產(chǎn)生 的互不相 同的整數(shù) , 二 。 , ? 島 一 二 類似地 , 將、 、 和 也按如卜方式分成 一 個子 向量 , 它們的第 個子向量分別記為, 尸 , 和 刀 , 二 一 一 , 則 二 科 , 牲 , 二 , 硯一 丁 可定收稿 期 伽 一 一 修回 期 一以一從金項 國家 自然科學(xué)基金 燦 印 以 陜西省 自然科學(xué)研究計劃項 川 、 偽轉(zhuǎn)載 龍 年義為 丫二 。 。 一 甲 , , , , ? , 。一?新的變異算子定義 假設(shè)解的精度要求是 。 , 若點 滿足 一 , 。 , 則稱 為一個 。一 精度的最優(yōu)解 其中 。

8、 是一個非常小的正數(shù) , 是問題的一個全局最優(yōu)解設(shè)搜索空間為 乙 , , , ? , 。 , “ , 。 , 則對 二 , ? , 二。 護 進行變異的方法如下步 將 , 分成若干子區(qū)間叨 , 叨玉, 、玉, 頭, ?,氣一 卜 氣, 使得 可 一 可一 , 、 , 其中 , 氣二 乙 ,步 對 的每個分量 二 、, 隨機產(chǎn)生一個數(shù) 任 , , 若。 , 隨機在 、, 一 氣中選一個 喊代替 否則, 保持不變 , 其中 。 為變異概率 經(jīng)過這樣的變異后 , 變?yōu)? ? , 。一 。一 任 無 , 日 證明 先證對任兩個點 廠 二 了 , , ?丫 。 下 和 二 , ?。 了 , , 是從 通

9、過雜交和變異為 。一 精度可達 的 ,即 徹 一 , 。, 其中 夕 是 通過雜交和變異產(chǎn)生的點 事實上 , 設(shè) 滅 是 通過雜交產(chǎn)生 的任一點 , 即 二 無 , 則只要證 叉 是從 通過變異為 。一 精度可達的即可 , 即 而 材 叉 一 矛 。 注意到, 對了 的每個分量 , 記 , 一 、 , 而 ” 討一 一,則叨之一 , 。, 其中 , 由變異算子確定?記 無 切 , 屯,二 , 叨獷 丁 , 則 戈一 , 。 因此 , 若能證 而 無 無, 則 而占 材 無 一 、 。 成立 設(shè) 對 無 和 無的 加 距離為 , 不失一般性 , 設(shè) 無 和 無的后 。個分量相同 , 于是有而 無

10、 戈?一個新的進化算法算法 給定雜交概率 。 , 變異概率 。 及種群大小隨機產(chǎn)生初始種群 尸 卜, ? , 刀即 , 令雜交 對每一代 , 產(chǎn)生 個隨機數(shù) , ? , 倆 任, 若 尹。 , 則 中 刃 參加雜交 , 一 仰 對參加雜交的點隨機配對 , 每一對用新的雜交算子進行雜交產(chǎn)生臨時后代變異 對上步中產(chǎn)生的每個臨時后代用新的變異算子進行變異產(chǎn)生 的后代選擇 從 和步 產(chǎn)生的其所有后代中選擇最好的 產(chǎn)塑 個點作為下一代的種群 , 令 左十 , 轉(zhuǎn)若終止條件滿足 , 停止全局收斂性定義 稱 是從 通過雜交和變異可達的 , 若 可由通過雜交和變異產(chǎn)生 , 即而州 金 二 卜 , 表示 由 通

11、過雜交和變異算子產(chǎn)生的點 從引 表示隨機事件 的概率定義 若 而占 幾 一 , 。, 則稱 廠 是從 通過雜交和變異為 。一 精度可達的 考慮極小化問題而 , 幾 為可行域 勘 已經(jīng)證明 任, 若一個進化算法滿足下面兩個條件 , 則其以概率收斂到全局最優(yōu)解對可行域中任兩個點 和 , 是從 通過雜交和變異可達的種群序列 尸 , 尸 , ? , , ?是單調(diào) 的 , 即 對, 有 一 無 而 一 無下證 將第 個條件 中的“ 可達 ”改為 “ 。一 精度可達 ” , 本 文進化算法以概率 收斂到 。一 精度的最優(yōu)解 定理 設(shè) 。 充分小 , 若 在搜索空間 , 衛(wèi)日上連續(xù) , 則算法 以概率 收斂

12、到 分精度的最優(yōu)解 , 即而石 尸 一 尸, 。 二 , 其 中 是全局最優(yōu)解蓋一集 , 一 日, 。 表示立于 卜 ,、 一二 , “ 少二 人 青,“? ”, 即 是從 通過雜交和變異為 。一 精度可達的由算法步 知 , 對每一代 , 算法總是保持 個最好的點作為種群 尸 , 故種群序列 , , ? , 無 , ?是單調(diào)的 因為 在 , 上連續(xù) , 故對充分小的 。 , 當(dāng) 。 一 , 。 , 凡 樣 。 時 , 有, 其中 是任一全局最優(yōu)解算法 產(chǎn)生的種群可看成是具有兩個狀態(tài)的 鏈狀態(tài) 種群滿足 。 狀態(tài) 種群不滿足幼 一 。 由種群序列 的單調(diào)性知 , 從狀態(tài) 轉(zhuǎn)移到狀態(tài) 的概率為 ,

13、 因此狀態(tài) 為吸收態(tài) 由任兩點的 。一 精度可達性知 , 從狀態(tài) 轉(zhuǎn)移到狀態(tài) 的概率恒大于 , 因此狀態(tài) 為瞬時態(tài) 訪 。 由 鏈理論閉 即知結(jié)論成立?表 和 王萬對計算結(jié)果的比較田 耐飛妞 正鄉(xiāng)抖 如印 一 一一一及 、 一一 一一 一硯 加叨扣 一一印 印 一 一一 一儀 一 一一 一數(shù)值模擬本文選了 個困難的標準試驗函數(shù)關(guān) 一 , 它們依次對應(yīng)于文仁 中的 介 一 ,無 , ,介 , 五 一 介 我們用本文 的算法簡記為 隊 對它們進行了計算 , 并和 飛 , , 第 期 王宇平 解無約束非線性全局優(yōu)化的一種新進化算法及其收斂性及 , 對這些函數(shù)計算的結(jié)果進行了比較 在運行時 , 各參數(shù)

14、取值如下 仰, , 。 二 , 。 , 。一 對每個試驗函數(shù)獨立運行 次 , 每次運行 , 若連續(xù)代最好解沒有改進 , 則算法停止 記錄最優(yōu)值的平均值 、標準差和函數(shù)值的平均計算次數(shù) 在表 一 中記為 , 并和文 一 中記錄的結(jié)果比較 , 結(jié)果見表 一 , 表中第 列數(shù)字為 函數(shù)編號 , 表示此量文獻中未提供表 和 玲。、 對 個函數(shù)計算結(jié)果的比較加舊 耐 西刊 玲 咫燈 一 取詔一必 以刃 胡 叨田犯 叫 一一 一 偽印 一一 今抖表 人和 、 對 , 個函數(shù)計算結(jié)果的比較切舊 西地二 一 二 一耳 一 卯一傭朋 又 一 一 一一 醉 儀以 卯 一 能 一 洲 胡 一一巧 以 一 一 一一創(chuàng)

15、 舊 一 醉一 洲 一 一 卯 一一 “跳 叮祠 乃田傭 一 一一 側(cè) 一 一一 結(jié)論本文結(jié)合均勻設(shè)計構(gòu)造了一個新的進化算法 , 從理論上證明了其收斂性 , 模擬結(jié)果也表明算法非常有效 由于篇幅所限 , 文中沒有包含該算法的應(yīng)用實例 實際上 , 它適合于 電子工程領(lǐng)域 , 特別是電磁學(xué)領(lǐng)域中的復(fù)雜優(yōu)化設(shè)計問題 參考文獻 隴 砒訊 七 。 哈示山 招 十 田舊 二 功孚也拙 面 記 燦, 羅 , 慚仁 磕 們田甲 川卿 叮 氏 腸面記 理翩 , 哭巧 既川 , 噸 腳 腳 即 誡 甲朋石刀蚊 目 山 叩血五叼 旅 。田甲 腸呷 石 , , 一 , 舫羅 , 以婦 羅 川 瀏 此 叮孚 淺 腸 石

16、 , 卿 巧 一 叩 。莊山 閉。 別 川 翅 , 哪,一 田山甲 叩石而皿 , 耐叩石而涵。 叩 徹 氏 。 , 說忱山 羅 偽 此柳 , 訓(xùn)畫昭 致劃訪 戶哪 略 , 男印 一, 明 山過祀 印 以 運 犯即 皿 , 望科 , 即叮 誡 。州四妙 曰, ,擬 而,以作者簡介王宇平 教授 , 博士 生導(dǎo)師 , 年生 于甘肅蘭州 , 卯 年獲博士學(xué)位 , 主要從事優(yōu)化理論 、方法及應(yīng)用 , 進化算法及應(yīng)用的研究 , 曾應(yīng)邀赴香港中文大學(xué)和香港浸會大學(xué)做訪問學(xué)者 , 已在國內(nèi)外刊物發(fā)表論文 多篇 , 主持和參加多項科研項 目 , 曾獲省部級科技進步獎 項從表 可看出 , 對 一 幾 中每個 函數(shù)都能求出非常接近全局 最優(yōu)解 的解 而 對 , 幾 不 能求 出滿意 的解對 一 五求出的解遠遠好于 求出的解 雖然 對乃 ,幾求出的解比 求出的稍差 , 但 所需的函數(shù)值的平均計算次數(shù)比 要少得多 從表 、 可看出洲 對 比較的每個函數(shù)都能求出非常接近全局最優(yōu)解的解 , 且 對所 比較的函數(shù)求出的解遠遠好于 班邁, 和 , , 求出的解 , 更進一步 , 所需的函數(shù)值的平