集值向量優化中精確罰函數穩定性研究

吳功躍

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

1 精確罰函數穩定性研究

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

1.1 精確罰函數

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

首先構造一個具有罰性質的函數，如下：

在精確罰函數的概念下，轉化為相應無約束化問題，其求得的解需要滿足一下條件：求得最優解是原問題（集值向量優化問題）的最優解，實現精確罰函數的穩定。

1.2 求取滿足穩定性條件的最優解

假定：r是無約束化問題的最優解，且迭代次數滿足達到最小值，認為精確罰函數是穩定的。

求取滿足穩定性條件的最優解的方法有很多，如遺傳算法、神經網絡算法等。下面就這針對這兩種方法進行穩定性求解研究。

1.2.1 遺傳算法

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

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

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

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

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

利用遺傳算法求取精確罰函數最大優勢在于精度較高，能最大程度保證結果的準確性，而最大劣勢在于計算量相比后面的神經網絡較大，迭代次數較高。

1.2.2 神經網絡

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

神經網絡求取最優解流程如下：

1）從各種神經網絡結構中選取一個合適的運行結構，使神經元輸出與精確罰函數的最優解相對應;

2）建立一個能量函數，使其求得的最小值對應精確罰函數的最優解;

3）通過能量函數推理出神經網絡與精確罰函數之間的聯系權重;

4）根據權重計算出精確罰函數中所有解;

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

6）求解方程組，得出精確罰函數的最優解。

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

2 結束語

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

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

（作者單位：南昌大學科學技術學院基礎部）