【正文】 式，稱之為約束條件[4]。非線性規(guī)劃問題的一般數(shù)學(xué)模型可表述為求未知量，使?jié)M足約束條件： （）并使目標(biāo)函數(shù)達(dá)到最小值(或最大值)。其中，諸和諸都是定義在n維向量空間的某子集(定義域)上的實值函數(shù)，且至少有一個是非線性函數(shù)。 上述模型可簡記為： （） （）其中屬于定義域，符號min表示“求最小值”，“受約束于”。定義域中滿足約束條件的點稱為問題的可行解。全體可行解所成的集合稱為問題的可行集。對于一個可行解，如果存在的一個鄰域，使目標(biāo)函數(shù)在處的值優(yōu)于(指不大于或不小于)該鄰域中任何其他可行解處的函數(shù)值，則稱為問題的局部最優(yōu)解（簡稱局部解）。如果優(yōu)于一切可行解處的目標(biāo)函數(shù)值，則稱x*為問題的整體最優(yōu)解（簡稱整體解）。實用非線性規(guī)劃問題要求整體解，而現(xiàn)有解法大多只是求出局部解。 非線性規(guī)劃的求解方法 一維最優(yōu)化方法指尋求一元函數(shù)在某區(qū)間上的最優(yōu)值點的方法。這類方法不僅有實用價值，而且大量多維最優(yōu)化方法都依賴于一系列的一維最優(yōu)化。常用的一維最優(yōu)化方法有黃金分割法、切線法和插值法[1]。①黃金分割法。它適用于單峰函數(shù)。其基本思想是：在初始尋查區(qū)間中設(shè)計一列點，通過逐次比較其函數(shù)值，逐步縮小尋查區(qū)間，以得出近似最優(yōu)值點。 ②切線法，又稱牛頓法。它也是針對單峰函數(shù)的。其基本思想是：在一個猜測點附近將目標(biāo)函數(shù)的導(dǎo)函數(shù)線性化，用此線性函數(shù)的零點作為新的猜測點，逐步迭代去逼近最優(yōu)點。③插值法，又稱多項式逼近法。其基本思想是用多項式（通常用二次或三次多項式）去擬合目標(biāo)函數(shù)。 此外，還有斐波那契法、割線法、有理插值法、分批搜索法等。 無約束最優(yōu)化方法指尋求n元實函數(shù)在整個n維向量空間上的最優(yōu)值點的方法。這類方法的意義在于：雖然實用規(guī)劃問題大多是有約束的，但許多約束最優(yōu)化方法可將有約束問題轉(zhuǎn)化為若干無約束問題來求解[1]。 無約束最優(yōu)化方法大多是逐次一維搜索的迭代算法。這類迭代算法可分為兩類。一類需要用目標(biāo)函數(shù)的導(dǎo)函數(shù)，稱為解析法。另一類不涉及導(dǎo)數(shù)，只用到函數(shù)值，稱為直接法。這些迭代算法的基本思想是：在一個近似點處選定一個有利搜索方向，沿這個方向進行一維尋查，得出新的近似點。然后對新點施行同樣手續(xù)，如此反復(fù)迭代，直到滿足預(yù)定的精度要求為止。根據(jù)搜索方向的取法不同，可以有各種算法。屬于解析型的算法有：①梯度法：又稱最速下降法。這是早期的解析法，收斂速度較慢。②牛頓法：收斂速度快，但不穩(wěn)定，計算也較困難。③共軛梯度法：收斂較快，效果較好。④變尺度法：這是一類效率較高的方法。其中達(dá)維登弗萊徹鮑威爾變尺度法，簡稱DFP法，是最常用的方法。屬于直接型的算法有交替方向法（又稱坐標(biāo)輪換法）、模式搜索法、旋轉(zhuǎn)方向法、鮑威爾共軛方向法和單純形加速法等。 約束最優(yōu)化方法指前述一般非線性規(guī)劃模型的求解方法。常用的約束最優(yōu)化方法有4種[1]：①拉格朗日乘子法：它是將原問題轉(zhuǎn)化為求拉格朗日函數(shù)的駐點。②制約函數(shù)法：又稱系列無約束最小化方法，簡稱SUMT法。它又分兩類，一類叫懲罰函數(shù)法，或稱外點法；另一類叫障礙函數(shù)法，或稱內(nèi)點法。它們都是將原問題轉(zhuǎn)化為一系列無約束問題來求解。③可行方向法：這是一類通過逐次選取可行下降方向去逼近最優(yōu)點的迭代算法。如佐坦迪克法、弗蘭克－沃爾夫法、投影梯度法和簡約梯度法都屬于此類算法。④近似型算法：這類算法包括序貫線性規(guī)劃法和序貫二次規(guī)劃法。前者將原問題化為一系列線性規(guī)劃問題求解，后者將原問題化為一系列二次規(guī)劃問題求解。 非線性規(guī)劃的應(yīng)用在經(jīng)營管理、工程設(shè)計、科學(xué)研究、軍事指揮等方面普遍地存在著最優(yōu)化問題。例如：如何在現(xiàn)有人力、物力、財力條件下合理安排產(chǎn)品生產(chǎn)，以取得最高的利潤；如何設(shè)計某種產(chǎn)品，在滿足規(guī)格、性能要求的前提下，達(dá)到最低的成本；如何確定一個自動控制系統(tǒng)的某些參數(shù)，使系統(tǒng)的工作狀態(tài)最佳；如何分配一個動力系統(tǒng)中各電站的負(fù)荷，在保證一定指標(biāo)要求的前提下，使總耗費最?。蝗绾伟才艓齑鎯α?，既能保證供應(yīng)，又使儲存費用最低；如何組織貨源，既能滿足顧客需要，又使資金周轉(zhuǎn)最快等。對于靜態(tài)的最優(yōu)化問題，當(dāng)目標(biāo)函數(shù)或約束條件出現(xiàn)未知量的非線性函數(shù)，且不便于線性化，或勉強線性化后會招致較大誤差時，就可應(yīng)用非線性規(guī)劃的方法去處理。3 傳統(tǒng)非線性規(guī)劃算法——外點罰函數(shù)法 算法概述罰函數(shù)法求解非線性規(guī)劃問題的思想是，利用問題中的約束函數(shù)做出適當(dāng)?shù)牧P函數(shù)，由此構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把問題轉(zhuǎn)化為無約束非線性規(guī)劃問題。利用罰函數(shù)法，可將非線性規(guī)劃問題的求解，轉(zhuǎn)化為求解一系列無約束極值問題，因而也稱這種方法為序列無約束最小化技術(shù)，簡記為SUMT(Sequential Unconstrained Minimization Technique)。主要有兩種形式，一種叫外點罰函數(shù)法，另一種叫內(nèi)點罰函數(shù)法。外點罰函數(shù)法是從非可行解出發(fā)逐漸移動到可行區(qū)域的方法。內(nèi)點罰函數(shù)法也稱為障礙罰函數(shù)法，這種方法是在可行域內(nèi)部進行搜索，約束邊界起到類似圍墻的作用，如果當(dāng)前解遠(yuǎn)離約束邊界時，則罰函數(shù)值是非常小的，否則罰函數(shù)值接近無窮大的方法。 算法描述對于問題（），本文所述的基本策略是，根據(jù)約束特點（等式或不等式）構(gòu)造某種“罰函數(shù)”，然后把它加到目標(biāo)函數(shù)中去，使得對約束最優(yōu)化問題的求解轉(zhuǎn)化為一系列無約束問題。極小點或者無限地向可行域靠近，或者一直保持在可行集內(nèi)移動，直到收斂于原來約束最優(yōu)化問題極小點。對于問題（），構(gòu)造一函數(shù)為 （）其中， （）在（）中，又稱為懲罰函數(shù)， （） （）是一個逐漸增大的參數(shù)，稱為懲罰因子。又稱為問題（）的增廣目標(biāo)函數(shù)。顯然，增廣目標(biāo)函數(shù)是定義在上的一個無約束函數(shù)。由增廣目標(biāo)函數(shù)的構(gòu)造知當(dāng)時 （）此時的最優(yōu)解就是問題（）的最優(yōu)解；而當(dāng)時，的最優(yōu)解就不一定是問題（）的最優(yōu)解。但是研究時，的最優(yōu)解不是我們所需要的。為此規(guī)定，當(dāng)時，在點處的函數(shù)值迅速變大，換而言之，可行域外的任一點處的函數(shù)值都相當(dāng)大。此時要求在中的最優(yōu)解，只能讓點回到內(nèi)才有可能，然而一旦點回到內(nèi)，即，此時就與問題（）有相同的最優(yōu)解。當(dāng)時，迅速變大的原因是通過懲罰因子來實現(xiàn)。簡言之，外點罰函數(shù)法的思想是：當(dāng)點時，設(shè)法加大不可行點處的函數(shù)值，使不可行點不能成為在中的最優(yōu)解。在用外點罰函數(shù)法求解問題（）時，首先構(gòu)造增廣目標(biāo)函數(shù)，然后按照無約束優(yōu)化方法求解。如果求出的最優(yōu)解為，則判斷是否屬于。如果，則是問題（）的最優(yōu)解；如果，則不是問題（）的最優(yōu)解，此時說明原來的懲罰因子給的太小了，需要加大懲罰因子，使得，然后再重新計算的最優(yōu)值。 算法性能分析通過長期的理論研究和實驗結(jié)果，人們總結(jié)出懲罰函數(shù)的優(yōu)點有：（1）罰函數(shù)法是解決非線性規(guī)劃問題的一種經(jīng)典算法，這種算法簡單易行、熟練數(shù)度快，在很多實際問題的求解中得到了應(yīng)用。（2）計算效率高，穩(wěn)定性較好。缺點有：（1）罰函數(shù)法對于有些問題只能求出局部最優(yōu)解，而不能求出全局最優(yōu)。（2）對函數(shù)初值和函數(shù)性態(tài)要求較高。（3）罰函數(shù)法在實際計算中的缺點是罰因子的取值難于把握，太小起不到懲罰作用；太大則由于誤差的影響會導(dǎo)致錯誤。在搜索過程開始的時候，一個較大的罰因子將會阻礙非可行域的搜索。另一方面，如果罰因子太小，這樣相對于目標(biāo)函數(shù)罰函數(shù)項是可以忽略的，則大量的搜索時間將花費在非可行域。這對于進化算法來說非常致命的。 外點罰函數(shù)法的程序設(shè)計為了能和求解非線性規(guī)劃問題的遺傳算法進行比較，我們同時實現(xiàn)最經(jīng)典的，也是得到最廣泛應(yīng)用的傳統(tǒng)的非線性規(guī)劃算法——外點罰函數(shù)法，通過對二者的結(jié)果，比較二者性能的差別。對于問題（），構(gòu)造一函數(shù)為 （）其中，懲罰函數(shù)按照式（）構(gòu)造，給定終止限（可取）。具體過程描述如下：（1）選定初始點，初始懲罰因子（可?。土P因子放大系數(shù)，置。（2）假設(shè)已獲得迭代點，以為初始點，求解無約束問題 （）設(shè)其最優(yōu)點為。（3）若，則就是所要求問題的最優(yōu)解，打印，結(jié)束；否則轉(zhuǎn)（4）。（4）置，轉(zhuǎn)（2）。外點罰函數(shù)法程序流程圖如圖31所示。圖31 外點罰函數(shù)法程序流程圖4 遺傳算法 遺傳算法概述 遺傳算法的生物學(xué)基礎(chǔ)遺傳算法的生物學(xué)基礎(chǔ)是達(dá)爾文的自然選擇學(xué)說。自然選擇學(xué)說認(rèn)為，生物要生存下去，就必須進行生存斗爭。在生存斗爭中，具有有利變異（mutation）的個體容易存活下來，并且有更多的機會將有利的變異傳給后代；具有不利變異的個體就容易被淘汰，產(chǎn)生后代的機會也少得多。達(dá)爾文把這種在生存斗爭中適者生存，不適者淘汰的過程叫做自然選擇。達(dá)爾文的自然選擇學(xué)說表明，遺傳和變異是決定生物進化的內(nèi)在因素。遺傳能使生物的性狀不斷地傳遞給后代，因而保持了物種的特性，變異能夠使生物的性狀發(fā)生改變，從而適應(yīng)新的環(huán)境而不斷地向前發(fā)展[2]。 遺傳算法的一般結(jié)構(gòu)遺傳算法是一種基于生物自然選擇與遺傳機理的隨機搜索算法。和傳統(tǒng)算法不同，遺傳算法從一組隨機產(chǎn)生的初始解，稱為“種群”，開始搜索過程。種群中的每個個體是問題的一個解，稱為“染色體”。染色體是一串符號，比如一個二進制字符串。這些染色體在后續(xù)迭代中不斷進化，稱為遺傳。在每一代中用“適值”來測量染色體的好壞。生成的下一代染色體稱為后代。后代是由前一代染色體通過交叉或變異運算形成的。新一代形成中，根據(jù)適值的大小選擇部分后代，淘汰部分之后，從而保持種群大小是常數(shù)。適值高的染色體被選中的概率較高。這樣，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或者次優(yōu)解。設(shè)和分別表示第t代的雙親和后代，遺傳算法的一般結(jié)構(gòu)可描述如下[3]：遺傳算法過程：begin；初始化