集值向量優(yōu)化中精確罰函數(shù)穩(wěn)定性研究

吳功躍

集值向量優(yōu)化問題作為約束優(yōu)化問題之一，在工程、管理、科學、經(jīng)濟以及軍事等眾多領(lǐng)域中發(fā)揮極其重要的作用，因此對集值向量優(yōu)化問題進行求解一直是國內(nèi)外相關(guān)專家和學者研究的重點項目。經(jīng)過多年的研究，目前常用的求解方法有可行點法，Lagrange 乘子法，共軛梯度法，罰函數(shù)法和信賴域法等幾種。本次就對其中的罰函數(shù)法進行研究。罰函數(shù)求解的主要思路是將一個約束優(yōu)化問題轉(zhuǎn)化為一系列易于求解的無約束優(yōu)化問題。在罰函數(shù)中又包括精確罰函數(shù)和序列罰函數(shù)兩種，而所謂精確罰函數(shù)法是當罰參數(shù)足夠大時，求得的罰問題的解就是原問題的解或原問題的解是罰問題的解，精確罰函數(shù)概念是由Zangwill第一個提出來的，由于其在求解集值向量優(yōu)化問題上， 不需要罰因子無窮大， 即可以通過求解有限個罰問題來得到原問題的最優(yōu)解，因此與上述幾種其余求解方法相比， 是簡單的、精確的，但是也因此是非穩(wěn)定和非平靜的，所以精確罰函數(shù)中的三個關(guān)鍵問題：平靜、穩(wěn)定和精確就成為近幾年來被廣泛研究的對象。經(jīng)過研究得出一種結(jié)論，如果懲罰函數(shù)滿足平靜或穩(wěn)定條件，就可以認定它是精確的，反推理，如果它是精確的，那么它一定是精確的。在此背景下，研究精確罰函數(shù)的平靜性、穩(wěn)定性具有十分重要的意義，但由于目前對平靜性研究的比較多，而穩(wěn)定性研究比較少，因此本文就僅對其中的穩(wěn)定性進行研究，彌補精確罰函數(shù)研究中的不足，強化其中的薄弱環(huán)節(jié)，為集值向量優(yōu)化求解問題的解決提供參考。

1 精確罰函數(shù)穩(wěn)定性研究

精確罰函數(shù)的主要功能是將難解決或無法解決的約束化問題轉(zhuǎn)換成易于解決的無約束化問題，從而通過求解無約束化問題解決集值向量優(yōu)化問題。精確罰函數(shù)不需要求解多個罰優(yōu)化問題，只需要在一個規(guī)定的區(qū)間內(nèi)選取幾個罰參數(shù)就可以得到想要求得的最優(yōu)解，從而解決原集值向量優(yōu)化問題。精確罰函數(shù)是罰函數(shù)的改進和優(yōu)化，能極大減少計算量，但是有利就有弊，少量罰參數(shù)，無法確定得出的解是最優(yōu)解，降低了罰函數(shù)的穩(wěn)定，因此如何增強罰函數(shù)的穩(wěn)定性成為研究的重點。

1.1 精確罰函數(shù)

罰函數(shù)的精髓是通過尋找一個容易求解的問題代替原問題，使得求解變得簡單、容易。

首先構(gòu)造一個具有罰性質(zhì)的函數(shù)，如下：

在精確罰函數(shù)的概念下，轉(zhuǎn)化為相應(yīng)無約束化問題，其求得的解需要滿足一下條件：求得最優(yōu)解是原問題（集值向量優(yōu)化問題）的最優(yōu)解，實現(xiàn)精確罰函數(shù)的穩(wěn)定。

1.2 求取滿足穩(wěn)定性條件的最優(yōu)解

假定：r是無約束化問題的最優(yōu)解，且迭代次數(shù)滿足達到最小值，認為精確罰函數(shù)是穩(wěn)定的。

求取滿足穩(wěn)定性條件的最優(yōu)解的方法有很多，如遺傳算法、神經(jīng)網(wǎng)絡(luò)算法等。下面就這針對這兩種方法進行穩(wěn)定性求解研究。

1.2.1 遺傳算法

遺傳算法，簡稱GA，最早是在1975年由美國密歇根州立大學J.Holland教授提出來的，其最大的優(yōu)點是計算簡單、適用性廣、功能強，已被廣泛應(yīng)用于各個優(yōu)化求解領(lǐng)域。其具體過程如下：

1）設(shè)置初始子群。子群是影響是遺傳算法求取最優(yōu)解的關(guān)鍵因素，子群規(guī)模越大，最優(yōu)解求取效率越高，但與此同時也增加了計算量，因此只要以精確罰函數(shù)的規(guī)定區(qū)間內(nèi)所有罰參數(shù)作為初始子群即可。為方便計算，對子群的所有罰參數(shù)進行標準化處理，計算與中間值的標準差值，然后對以上得到的標準化罰參數(shù)結(jié)果進行隨機采樣，即得到初始化子群，也就是多條染色體，每條染色體代表一個罰參數(shù)。

2）編碼。在這里采用一種新的編碼方式對每個染色體進行編碼，即讓每條染色體都有一個相對應(yīng)的配置結(jié)構(gòu)，然后利用M×N 的二維布爾矩陣對其進行表示，以此省略每條染色體的解碼過程，直接就可以進行費用值評估，然后進行適應(yīng)值計算。

3）計算適應(yīng)值。適應(yīng)值是衡量子群中每條染色體的生存能力的標準，適應(yīng)值越高，該條染色體就越有可能是無約束化問題的最優(yōu)解，但是在精確函數(shù)中，由于目標函數(shù)是不確定的，因此為了計算出每條染色體的的數(shù)值，需要先設(shè)定染色體適應(yīng)值為非負數(shù)，然后在映射關(guān)系規(guī)則下，得出映射后的染色體適應(yīng)值。

4）遺傳算子。在遺傳算子環(huán)節(jié)，主要由三個步驟：選擇、交叉好變異。選擇：遺傳算法是根據(jù)達爾文的進化論提出的，因此其中心思想就是優(yōu)勝劣汰，適者生存，剩到最后的就是最優(yōu)的，這正是求取最優(yōu)解的目的。選擇，即從已經(jīng)存在的子群中選擇適應(yīng)值高的個體作為基體，然后將該基體與子群中的其它個體進行交叉和變異操作。交叉：將選出的適應(yīng)值高的染色體與其它染色體進行換組操作，其過程如下：選取固定一個點，每次兩個染色體進行交叉操作時都以這個點為原點，按照一定的交叉概率進行操作，以此來避免出現(xiàn)重復情況。變異：為保證最優(yōu)解質(zhì)量，需要從交叉后的染色體子群中任意選取出若干個變異染色體進行變異操作，例如原染色體的位置數(shù)值為0 ，變異后的位置數(shù)值就應(yīng)該是1，而原為1，變異后則為0。這樣做的目的是增加子群多樣性，從而增強精確罰函數(shù)求解過程的穩(wěn)定性的。變異操作的關(guān)鍵是如何選擇變異概率，變異概率的大小直接關(guān)系著變異得次數(shù)量，過小，求取的的解就有可能達不到最優(yōu)，過大就有可能增加迭代次數(shù)，加大計算量，因此為保證結(jié)果最優(yōu)，可以根據(jù)精確罰函數(shù)的規(guī)定區(qū)間進行確定，一般選擇其中間數(shù)量所對應(yīng)的概率。

利用遺傳算法求取精確罰函數(shù)最大優(yōu)勢在于精度較高，能最大程度保證結(jié)果的準確性，而最大劣勢在于計算量相比后面的神經(jīng)網(wǎng)絡(luò)較大，迭代次數(shù)較高。

1.2.2 神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)，顧名思義就是根據(jù)人體大腦神經(jīng)網(wǎng)絡(luò)構(gòu)而模擬出的一種智能算法，主要作用是模擬大腦功能進行復雜信息處理。神經(jīng)網(wǎng)絡(luò)實際上是一個非線性動力學數(shù)學模型，在求取最優(yōu)解中具有重要作用。神經(jīng)網(wǎng)絡(luò)最大的優(yōu)點在于具有極強的魯棒性、容錯性、自適應(yīng)性以及學習能力，所以本次研究利用神經(jīng)網(wǎng)絡(luò)對精確罰函數(shù)進行求解，以規(guī)定區(qū)間內(nèi)罰參數(shù)為輸入項輸入到神經(jīng)網(wǎng)絡(luò)組織中，之后通過學習訓練獲得最優(yōu)解，保證精確罰函數(shù)的穩(wěn)定性。利用神經(jīng)網(wǎng)絡(luò)求取最優(yōu)解的基本思路：遵循一定的法則，選擇合適的網(wǎng)絡(luò)結(jié)構(gòu)以及精確罰函數(shù)的權(quán)值，使得求得的解達到最優(yōu)。在這一過程中，最困難的部分在于能量函數(shù)的構(gòu)造，使得構(gòu)造出來的神經(jīng)網(wǎng)絡(luò)能最大限度的保證精確罰函數(shù)的穩(wěn)定。這里的能量函數(shù)不具有任何的物理意義，只是在表達形式上與物理意義上的能量概念一致，所以需要依靠Hopfield提出的工作運行規(guī)則完成模型迭代，使得能量函數(shù)達到極小值。

神經(jīng)網(wǎng)絡(luò)求取最優(yōu)解流程如下：

1）從各種神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中選取一個合適的運行結(jié)構(gòu)，使神經(jīng)元輸出與精確罰函數(shù)的最優(yōu)解相對應(yīng);

2）建立一個能量函數(shù)，使其求得的最小值對應(yīng)精確罰函數(shù)的最優(yōu)解;

3）通過能量函數(shù)推理出神經(jīng)網(wǎng)絡(luò)與精確罰函數(shù)之間的聯(lián)系權(quán)重;

4）根據(jù)權(quán)重計算出精確罰函數(shù)中所有解;

5）由解建立一組以穩(wěn)定性為約束條件的方程;

6）求解方程組，得出精確罰函數(shù)的最優(yōu)解。

從上述過程中可以看出利用神經(jīng)網(wǎng)絡(luò)解決優(yōu)化問題的過程實質(zhì)上就是通過引進一個神經(jīng)網(wǎng)絡(luò)，這個網(wǎng)絡(luò)對應(yīng)一個精確罰函數(shù)和一個能量函數(shù)，當這兩個函數(shù)的解相對性，二者就達到了相對平衡，從而保持精確罰函數(shù)穩(wěn)定的過程。其重點是如何構(gòu)造一個準確有效的能量函數(shù)。下面為一個典型的能量函數(shù)，其定義如下：

2 結(jié)束語

在約束優(yōu)化問題中集值向量優(yōu)化問題是其中最常見的，對于其解決方法有很多種，本次就其中的罰函數(shù)法進行深入研究。在罰函數(shù)中，精確罰函數(shù)作為其中的一類，如何保證其平靜性、穩(wěn)定性一直是未解決的重點問題之一，缺乏穩(wěn)定行動精確罰函數(shù)是無法有效解決集值向量優(yōu)化問題的，所以本次研究從求取精確罰函數(shù)最優(yōu)解的角度入手，最大程度的確保其穩(wěn)定性，主要介紹了兩種方法，一是遺傳算法;一是神經(jīng)網(wǎng)絡(luò)算法。這兩種算法哪一種性能最佳或者如何將兩種算法結(jié)合在一起使用，成為下一步研究的重點工作。通過本次研究期望為以上眾多領(lǐng)域中約束優(yōu)化問題的解決提供一些借鑒。

基金項目：國家自然科學基金（10461007）， 江西省自然科學基金（0611081）。

（作者單位：南昌大學科學技術(shù)學院基礎(chǔ)部）