【正文】 nditions, and always could receive the optimal solution or approximate optimal solution. Its convergence results are more reasonable, the performance is more stable. Key Words: Nonlinear Programming。與傳統(tǒng)的非線性規(guī)劃算法 —— 外點(diǎn)罰函數(shù)法的比較結(jié)果表明該算法在一定程度上有效地克服了傳統(tǒng)的非線性規(guī)劃算法 穩(wěn)定性差， 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高， 且容易陷入局部最優(yōu)解 的缺陷，收斂更合理，性能更穩(wěn)定。 本文在分析傳統(tǒng)的非線性規(guī)劃算法的不足和遺傳算法的優(yōu)越性的基礎(chǔ)上，將遺傳算法應(yīng)用于非線性規(guī)劃。 遺傳算法 是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型 。 摘 要 非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用。 傳統(tǒng)的解決非線性規(guī)劃問題的方法，如 梯度法、罰函數(shù)法、拉格朗日乘子法 等， 穩(wěn)定性差， 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高， 且容易陷入局部最優(yōu)解 。遺傳算法是一種全局搜索算法，簡(jiǎn)單、通用、魯棒性強(qiáng)， 對(duì)目標(biāo)函數(shù)既不要求連續(xù)，也不要求可 導(dǎo) ，適用于并行分布處理，應(yīng)用范圍廣。算法引進(jìn)懲罰函數(shù)的概念，構(gòu) 造帶有懲罰項(xiàng)的適應(yīng)度函數(shù)；通過實(shí)數(shù)編碼，轉(zhuǎn)輪法選擇，雙點(diǎn)交叉，均勻變異，形成了求解非線性規(guī)劃問題的遺傳算法。 關(guān)鍵詞： 非線性規(guī)劃；遺傳算法； 罰函數(shù)法 ABSTRACT Nonlinear programming has a wide range of applications in engineering, management, economic, scientific, and military aspects. Traditional methods to solve the nonlinear programming problem, such as the gradient method, penalty method, Lagrange multiplier method, have poor stability. They are sensitive to the function initial value and request the objective function to be continuous and differential. The results are also easily trapped into local optimal solution. Geic algorithm is a kind of calculate model which simulates Darwin39。 Geic Algorithm。 非線性規(guī)劃是 20世紀(jì) 50 年代才開始形成的一門新興學(xué)科。在 50 年代還得出了可分離規(guī)劃和二次規(guī)劃的 n 種解法 ， 它們大都是以 .丹齊克提出的解線性規(guī)劃的單純形法為基礎(chǔ)的。 非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用，為最優(yōu)化設(shè)計(jì)提供了有力的工具。在非線性規(guī)劃理論研究的 基礎(chǔ)上，人們?nèi)找嬷匾暦蔷€性規(guī)劃問題求解方法的研究。 遺傳算法簡(jiǎn)介 遺傳算法（ Geic Algorithm） ， 是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法 ， 它是 由 美國(guó) Michigan大學(xué) 教授于 1975 年首先提出來的，并出版了頗 有影響的專著《 Adaptation in Natural and Artificial Systems》， GA 這個(gè)名稱才逐漸為人所知 ， 教授所提出的GA 通常為簡(jiǎn)單遺傳算法（ SGA）。它的主要特點(diǎn)是簡(jiǎn)單、通用、魯棒性強(qiáng)，對(duì)目標(biāo)函數(shù)既不要求連續(xù)，也不要求可 導(dǎo) ，適用于并行分布處理，應(yīng)用范圍廣。并且取得了令人矚目的成果。 而遺傳算法是一種魯棒性很強(qiáng)的 種全局搜索算法，理論上可以克服傳統(tǒng) 非線性規(guī)劃 算法的缺陷。具體內(nèi)容包括編碼方法設(shè)計(jì)，適應(yīng)度函數(shù)設(shè)計(jì)，選擇算子、交叉算子、變異算子等遺傳算子設(shè)計(jì)，算法流程設(shè)計(jì)，并在設(shè)計(jì)的基礎(chǔ)上用 MATLAB 語言實(shí)現(xiàn)該算法的程序，運(yùn)行并調(diào)試程序，直至得到正確的結(jié)果。 3 2 非線性規(guī)劃 非線性規(guī)劃的概念 具有非線性約束條件或目標(biāo)函數(shù)的 數(shù)學(xué)規(guī)劃 ， 稱為非線性規(guī)劃 。目標(biāo)函數(shù)和約束條件都是線性函數(shù)的情形則屬于 線性規(guī)劃 。建立數(shù)學(xué)模型首先要選定適當(dāng)?shù)哪繕?biāo)變量和決策變量 ， 并建立起目標(biāo)變量與決策變量之間的函數(shù)關(guān)系 ， 稱之為 目標(biāo)函數(shù) 。 非線性規(guī)劃問題的一般數(shù)學(xué)模型可表述為求未知量 nxxx ,..., 21 ， 使?jié)M足約束條件： ? ?? ???? ?? ?? pjxxh mixxgnjni ,...,1,0,..., ,...,1,0,...,11 （ ） 并使目標(biāo)函數(shù) ? ?nxxf ,...,1 達(dá)到最小值 (或最大值 )。 上述模型可簡(jiǎn)記為： ? ?xfmin （ ） ? ?? ???? ?? ?? pjxh mixgts ,...,1,0 ,...,1,0.. （ ） 其中 ? ?nxx ,...,x 1? 屬于定義域 D ，符號(hào) min 表示“求最小值”，符號(hào) “受約束于”。全體可行解所成的集合稱為問題的可行集。如果 ? ?*xf 優(yōu)于一切可行解處的目標(biāo)函數(shù)值 ， 則稱 x*為問題的整體最優(yōu)解（簡(jiǎn)稱整體解）。 4 非線性規(guī)劃的求解方法 一維最優(yōu)化方法 指尋求一元函數(shù)在某區(qū)間上的最優(yōu)值點(diǎn)的方法。常用的一維最優(yōu)化方法有黃金分割法、切線法和插值法 [1]。它適用于單峰函數(shù)。 ② 切線法 ，又稱牛頓法。其基本思想是：在一個(gè)猜測(cè)點(diǎn)附近將目標(biāo)函數(shù)的導(dǎo)函數(shù)線性化，用此線性函數(shù)的零點(diǎn)作為新的猜測(cè)點(diǎn)，逐步迭代去逼近最優(yōu)點(diǎn)。其基本思想是用多項(xiàng)式（通常用二次或三次多項(xiàng)式）去擬合目標(biāo)函數(shù)。 無約束最優(yōu)化方法 指尋求 n 元實(shí)函數(shù) f 在整個(gè) n 維向量空間 nR 上的最優(yōu)值點(diǎn)的方法。 無約束最優(yōu)化方法 大多是逐次一維搜索的迭代算法。一類需要用目標(biāo)函數(shù)的導(dǎo)函數(shù) ， 稱為解析法。這些迭代算法的基本思想是：在一個(gè)近似點(diǎn)處選定一個(gè)有利搜索方向 ， 沿這個(gè)方向進(jìn)行一維尋查 ， 得出新的近似點(diǎn)。根據(jù)搜索方向的取法不同 ， 可以有各種算法。這是早期的解析法，收斂速度較慢。 ③ 共軛梯度法 ：收斂較快，效果較好。其中達(dá)維登 弗萊徹 鮑威爾變尺度法，簡(jiǎn)稱DFP 法，是最常用的方法。 5 約束最優(yōu)化方法 指前述一般非線性規(guī)劃模型的求解方法。 ② 制約函數(shù)法 ：又稱系列無約束最小化方法，簡(jiǎn)稱 SUMT 法 。它們都是將原問題轉(zhuǎn)化為一系列無約束問題來求解。如佐坦迪克法、弗蘭克－沃爾夫法、投影梯度法和簡(jiǎn)約梯度法都屬于此類算法。前者將原問題化為一系列線性規(guī)劃問題求解，后者將原問題化為一系列二次規(guī)劃問題求解。例如：如何在現(xiàn)有人力、物力、財(cái)力條件下合理安排產(chǎn)品生產(chǎn)，以取得最高的利潤(rùn)；如何設(shè)計(jì)某種產(chǎn)品，在滿足規(guī)格、性能要求的前提下，達(dá)到最低的成本；如何確定一個(gè)自動(dòng)控制系統(tǒng)的某些參數(shù)，使系統(tǒng)的工作狀態(tài)最佳；如何分配一個(gè)動(dòng)力系統(tǒng)中各電站的負(fù)荷，在保證一定指標(biāo)要求的前提下，使總耗費(fèi)最小；如何安排庫存儲(chǔ)量，既能保證供應(yīng)，又使儲(chǔ)存費(fèi)用最低；如何組織貨源，既能滿足顧客需要，又使資金周轉(zhuǎn)最快等。 6 3 傳統(tǒng)非線性規(guī)劃算法 —— 外點(diǎn)罰函數(shù)法 算法概述 罰函數(shù)法求解非線性規(guī)劃問題的思想是，利用問題中的約束函數(shù) 做 出適當(dāng)?shù)牧P函數(shù)，由此構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把問題轉(zhuǎn)化為無約束非線性規(guī)劃問題。 主要有兩種形式，一種叫 外 點(diǎn) 罰函數(shù)法 ，另一種叫 內(nèi) 點(diǎn) 罰函數(shù)法 。內(nèi) 點(diǎn) 罰函數(shù)法也稱為障礙罰函數(shù)法，這種方法是在可行域內(nèi)部進(jìn)行搜索，約束邊界起到類似圍墻的作用，如果當(dāng)前解遠(yuǎn)離約束邊界時(shí)，則罰函數(shù)值是非常小的，否則罰函數(shù)值接近無窮大的方法。 極小點(diǎn)或者無限地向可行域靠近，或者一直保持 在可行集內(nèi)移動(dòng)，直到收斂于原來約束最優(yōu)化問題極小點(diǎn)。 ),( kMXF 又稱為 問題 （ ） 的增廣目標(biāo)函數(shù)。由增廣目標(biāo)函數(shù)),( kMXF 的構(gòu)造知當(dāng) DX? 時(shí) )(),( XfMXF k ? （ ） 此時(shí) ),( kMXF 的最優(yōu)解就是問題 （ ） 的最優(yōu)解；而當(dāng) DX? 時(shí)， ),( kMXF 的最優(yōu)解就不一定是問題 （ ） 的最優(yōu)解。為此規(guī)定，當(dāng) DX? 時(shí)， ),( kMXF 在 X 點(diǎn)處的函數(shù)值迅速變大，換而言之，可行域外的任一點(diǎn) X 處的函數(shù)值 ),( kMXF 都相當(dāng)大。 當(dāng) DX? 時(shí)， ),( kMXF 迅速變大的原因是通過懲罰因子 kM 來實(shí)現(xiàn)。 在用外點(diǎn)罰函數(shù)法求解問題 （ ） 時(shí)，首先構(gòu)造增廣目標(biāo)函數(shù) ),( kMXF ，然后按照無約束優(yōu)化方法求解。如果 DXM? ，則 MX 是問題 （ ） 的最優(yōu)解 ；如果 DXM? ，則 MX 不 是問題 （ ） 的最優(yōu)解，此時(shí)說明原來的懲罰因子給的太小了，需要加大懲罰因子，使得 kk MM ??1 ，然后再重新計(jì)算 ),( 1?kMXF 的最優(yōu)值。 （ 2） 計(jì)算效率高 ，穩(wěn)定性較好。 （ 2） 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高。 在搜索過程開始的時(shí)候 ， 一個(gè)較大的罰因子將會(huì)阻礙非可行域的搜索 。這對(duì)于進(jìn)化算法來說非常致命的。 程序步驟 對(duì)于問題 （ ） ，構(gòu)造一函數(shù)為 )()(),( XMXfMXF kk ??? （ ） 其中，懲罰函數(shù) )(X? 按照式 （ ） 構(gòu)造，給定終止限 ? （ 可取 610??? ）。懲罰因子放大系數(shù) 10?C ，置 1?k 。 （ 3） 若 ?? ?)(XMk ，則 kX 就是所要求問題的最優(yōu)解，打印 ? ?)(, kk XfX ， 結(jié)束；否則轉(zhuǎn) （ 4）。 程序流程圖 外點(diǎn)罰函數(shù)法 程序流程圖如 圖 31 所示。自然選擇學(xué)說認(rèn)為，生物要生存下去，就必須進(jìn)行生存斗爭(zhēng)。達(dá)爾文把這種在生存斗爭(zhēng)中適者生存，不適者淘汰的過程叫做自然選擇。遺傳能使生物的性狀不斷地傳遞給后代，因而保持了物種的特性，變異 能夠使生物的性狀發(fā)生改變，從而適應(yīng)新的環(huán)境而不斷地向前發(fā)展 [2]。和傳統(tǒng)算法不同，遺傳算法從一組隨機(jī)產(chǎn)生的初始解，稱為“種群”，開始搜索過程。染色體是一串符號(hào)，比如一個(gè)二進(jìn)制字符串。在每一代中用“適值”來測(cè)量染色體的好壞。后代是由前一代染色體通過交叉或變異運(yùn)算形成的。適值高的染色體被選中的概率較高。 設(shè) ??tP 和 ??tC 分別表示第 t 代的雙親和后代，遺傳算法的一般結(jié)構(gòu)可描述如下 [3]： 遺傳算法過程 ： begin 0?t ； 初始化 ??tP ； 評(píng)估 ??tP ； while 不 滿足終止條件 do begin 重組 ??tp 獲得 ??tC ； 評(píng)估 ??tC ； 11 從 ??tP 和 ??tC 中選擇 ? ?1?tP ； 1??tt ； end end 圖 41 遺傳算法的一般結(jié)構(gòu) 通常初始化是隨機(jī)產(chǎn)生的。實(shí)際上，遺傳算法中有兩類運(yùn)算： （ 1）遺傳運(yùn)算：交叉和變異； （ 2）進(jìn)化運(yùn)算：選擇。 12 遺傳算法的特點(diǎn) 遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比 ， 主要有以下特點(diǎn) [3]： （ 1） 遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象。 （ 2） 遺傳算法直接以適應(yīng)度作為搜索信息，無需導(dǎo)數(shù)等其它輔助信息。 （ 4） 遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域 [2][5]： （ 1）函數(shù)優(yōu)化。 （ 2）組合優(yōu)化。遺傳算法是解決這類問題的最佳工具之一。 （ 3）生產(chǎn)調(diào)度問題?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。在自動(dòng)控制領(lǐng) 域中有許多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示出了良好的效果。機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對(duì)人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人智能控制理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。在圖像處理過程中，不可避免地會(huì)產(chǎn)生一些誤差，這些誤差會(huì)影響圖像處理的效果。目前遺傳算法已在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。人工生命與遺 傳算法有著密切的關(guān)系，基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。 （ 8）遺傳編程。 （ 9）機(jī)器學(xué)習(xí)。 遺傳算法實(shí)現(xiàn)的關(guān)鍵技術(shù) 編碼方法 在遺傳算法的運(yùn)行過程中，它不對(duì)所求解問題的實(shí)際決策變量直接 進(jìn)行操作，而是對(duì)表示可行解的個(gè)體編碼施加選擇、交叉、變異等遺傳運(yùn)算，通過這種遺傳操作來達(dá)到優(yōu)化的目的，這是遺傳算法的特點(diǎn)之一。 常用 的 編碼方法 有 ： （ 1） 二進(jìn)制編碼：使用由二進(jìn)制符號(hào) 0 和 1 所組成的二值符號(hào)集 {0， 1}進(jìn)行編碼，它所構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào)串