【正文】 {1， 2， 3， 4， 5， …} ；還可以是一個代碼表，如 {A1,A2,A3,A4,…} 等等。基于遺傳算法的機(jī)器學(xué)習(xí)，在很多領(lǐng)域中都得到了應(yīng)用。如何使這些誤差最小是使計算機(jī)視覺達(dá)到實(shí)用化的重要要求。生產(chǎn)調(diào)度問題在許多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解，也會因簡化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。 遺傳算法的應(yīng)用 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。重組包括交叉和變異來獲得后代。這些染色體在后續(xù)迭代中不斷進(jìn)化，稱為遺傳。在生存斗爭中，具有有利變異 （ mutation） 的個體容易存活下來，并且有更多的機(jī)會將有利的變異傳給后代；具有不利變異的個體就容易被淘汰，產(chǎn)生后代的機(jī)會也少得多。 具體過 程描述如下： （ 1） 選定初始點(diǎn) 0X ， 初始懲罰因子 01?M （ 可取 11?M ） 。 缺點(diǎn)有： （ 1） 罰函數(shù)法對于有些問題只能求出局部最優(yōu)解，而不能求出全局最優(yōu)。此時要求 ),( kMXF 在 nR 中的最優(yōu)解，只能讓點(diǎn) X 回到 D 內(nèi)才 有 可能，然而一旦點(diǎn) X 回到 D 內(nèi)，即 DX? ，此時 ),( kMXF就與問題 （ ） 有相同的最優(yōu)解。 算法描述 對于問題 （ ） ，本文所述的基本策略是，根據(jù)約束特點(diǎn) （ 等式或不等式 ） 構(gòu)造某種“罰函數(shù)”，然后把它加到目標(biāo)函數(shù)中去，使得對約束最優(yōu)化問題的求解轉(zhuǎn)化為一系列無約束問題 。 非線性規(guī)劃的應(yīng)用 在 經(jīng)營管理 、 工程設(shè)計 、 科學(xué)研究 、 軍事指揮 等方面普遍地存在著最優(yōu)化問題。常用的 約束最優(yōu)化方 法有 4 種 [1]： ① 拉格朗日乘子法 ：它是將原問題轉(zhuǎn)化為求拉格朗日函數(shù)的駐點(diǎn)。 屬于解析型的算法有： ① 梯度法 ：又稱最速下降法。這類方法的意義在于 ： 雖然實(shí)用規(guī)劃問題大多是有約束的，但許多約束最優(yōu)化方法可將有約束問題轉(zhuǎn)化為若干無約束問題來求解 [1]。其基本思想是：在初始尋查區(qū)間中設(shè)計一列點(diǎn)，通過逐次比較其函數(shù)值，逐步縮小尋查區(qū)間，以得出近似最優(yōu)值點(diǎn)。對于一個可行解 *x ， 如果存在 *x 的一個鄰域，使目標(biāo)函數(shù)在 *x 處的值 ? ?*xf 優(yōu)于 (指不大于或不小于 )該鄰域中任何其他可行解處的函數(shù)值，則稱 *x 為問題的局部最優(yōu)解（簡稱 局部解）。 非線性 規(guī)劃的數(shù)學(xué)模型 對實(shí)際 規(guī)劃問題 作 定量分析 ，必須建立 數(shù)學(xué)模型 。 2 研究內(nèi)容 傳統(tǒng)的非線性規(guī)劃 算 法的缺陷是 計算煩瑣且精度不高 ， 穩(wěn)定性差， 對函數(shù)初值和函數(shù)性態(tài)要求較高， 且容易陷入局部最優(yōu)解 。 隨著計算機(jī)的產(chǎn)生與發(fā)展，非線性規(guī)劃作為一門獨(dú)立的學(xué)科越來越受到人們的重視。s geic selection and biological evolution of natural selection. Geic algorithm is a global search algorithm. It has simple, universal, robust features, and does not request the objective function to be continuous and differential, and is suitable in parallel distribution processing. Geic algorithm is widely applied in many areas. Based on the analysis of the disadvantage of traditional nonlinear programming algorithm and the advantage of geic algorithm, geic algorithm is applied to nonlinear programming in this paper. The introduction of the concept of penalty function is used to construct the fitness function with punishment. By using realcoded, Roulette Wheel selection method, twopoint crossover, uniform mutation, we formed a geic algorithm to solve the nonlinear programming problem. Compared with the most classical and widely used traditional nonlinear programming problem algorithm –SUMT algorithm, the results show that the new algorithm could effectively overe the defect of the traditional algorithm in a certain extent. The new algorithm is more stable, less sensitive to the function initial value and conditions, 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。 摘 要 非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用。 關(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。 非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用，為最優(yōu)化設(shè)計提供了有力的工具。并且取得了令人矚目的成果。目標(biāo)函數(shù)和約束條件都是線性函數(shù)的情形則屬于 線性規(guī)劃 。全體可行解所成的集合稱為問題的可行集。它適用于單峰函數(shù)。 無約束最優(yōu)化方法 指尋求 n 元實(shí)函數(shù) f 在整個 n 維向量空間 nR 上的最優(yōu)值點(diǎn)的方法。根據(jù)搜索方向的取法不同 ， 可以有各種算法。 5 約束最優(yōu)化方法 指前述一般非線性規(guī)劃模型的求解方法。前者將原問題化為一系列線性規(guī)劃問題求解，后者將原問題化為一系列二次規(guī)劃問題求解。內(nèi) 點(diǎn) 罰函數(shù)法也稱為障礙罰函數(shù)法，這種方法是在可行域內(nèi)部進(jìn)行搜索，約束邊界起到類似圍墻的作用，如果當(dāng)前解遠(yuǎn)離約束邊界時，則罰函數(shù)值是非常小的，否則罰函數(shù)值接近無窮大的方法。為此規(guī)定，當(dāng) DX? 時， ),( kMXF 在 X 點(diǎn)處的函數(shù)值迅速變大，換而言之，可行域外的任一點(diǎn) X 處的函數(shù)值 ),( kMXF 都相當(dāng)大。 （ 2） 計算效率高 ，穩(wěn)定性較好。 程序步驟 對于問題 （ ） ，構(gòu)造一函數(shù)為 )()(),( XMXfMXF kk ??? （ ） 其中，懲罰函數(shù) )(X? 按照式 （ ） 構(gòu)造，給定終止限 ? （ 可取 610??? ）。自然選擇學(xué)說認(rèn)為，生物要生存下去，就必須進(jìn)行生存斗爭。染色體是一串符號，比如一個二進(jìn)制字符串。 設(shè) ??tP 和 ??tC 分別表示第 t 代的雙親和后代，遺傳算法的一般結(jié)構(gòu)可描述如下 [3]： 遺傳算法過程 ： begin 0?t ； 初始化 ??tP ； 評估 ??tP ； while 不 滿足終止條件 do begin 重組 ??tp 獲得 ??tC ； 評估 ??tC ； 11 從 ??tP 和 ??tC 中選擇 ? ?1?tP ； 1??tt ； end end 圖 41 遺傳算法的一般結(jié)構(gòu) 通常初始化是隨機(jī)產(chǎn)生的。 （ 4） 遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。 （ 3）生產(chǎn)調(diào)度問題。在圖像處理過程中，不可避免地會產(chǎn)生一些誤差，這些誤差會影響圖像處理的效果。 （ 9）機(jī)器學(xué)習(xí)。 （ 3） 符號編碼：個體染色體編碼串中的基因值取自一個無數(shù)值含義、而只有代碼含義的符號集。 選擇算子 遺傳算法使用遺傳算子（或稱為復(fù)制算子， Reproduction Operator）來對群體中的個 14 體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度較高的個體被遺傳到下一代群體中的概率較大；適應(yīng)度較低的個體被遺傳到下一代群體中的概率較小。 交叉算子 遺傳算法中的交叉運(yùn)算是指對兩個相互配對的染色體按某種方式相互交換其部分基因， 從而形成兩個新的個體。遺傳算法導(dǎo)入變異的目的有兩個：一是使遺傳算法具有局部的隨機(jī)搜索能力。使用二進(jìn)制編碼時， L 與問題所要求的求解精度有關(guān)；使用浮點(diǎn)數(shù)編碼時， L 與決策變量的個數(shù) n 相等；使用符號編碼是， L 由問題的編碼方式確定。 （ 4）變異概率 Pm。因此，將遺傳算法應(yīng)用于非線性規(guī)劃，是改善收斂效果，提高最優(yōu)化質(zhì)量的有效途徑。而且采用二進(jìn)制編碼，又要牽涉到 十進(jìn)制與二進(jìn)制的轉(zhuǎn)換， 在實(shí)際操作過程中要頻繁進(jìn)行編碼和解碼操作，費(fèi)時 費(fèi)力。例如，對許多約束優(yōu)化問題初始種群可能全由非可行染色體構(gòu)成，這就需要對他們進(jìn)行修補(bǔ)。 修復(fù)后的染色體可以只用來作評估，也可用來替代原染色體進(jìn)入種群。 （ 4）懲罰策略 上面三種策略的 共同優(yōu)點(diǎn)是都不會產(chǎn)生不可行解，缺點(diǎn)則是無法考慮可行域外的點(diǎn)。 18 一般，解空間包含兩部分：可行域和不可行域。設(shè)計懲罰函數(shù)沒有一般規(guī)則，這仍要依賴于待解的問題。 當(dāng) ??xg 不滿 足約束時，也就是 ??xg 小于 0時，括號里的邏輯運(yùn)算結(jié)果為 1，由于約束是要求 ??xg 大于等于 0，則要對其進(jìn)行懲罰，乘以 1 相當(dāng)于對 ??xg 取絕對值，再乘以一個較大的數(shù) 1e+3， 則此時 ??xp 為一個較大的實(shí)數(shù)，實(shí)現(xiàn)了其懲罰作用。 它是一種 正比選擇策略，能夠根據(jù)與適值成正比的概率選擇出新的種群。 若隨機(jī)生成 的 交叉點(diǎn)為 2 和 5， 則將 第 2 號 和第 5 號位置 之間 的基因值互換，交叉后產(chǎn)生的新染色體為： NewChromosome1=[1， 2， 8， 9， 5]，NewChromosome2=[6， 7， 3， 4， 10]。 （ 2） 種群 大小 pop_size。 （ 4）變異概率 Pm。步驟如下： （ 1）初始化遺傳算法的運(yùn)行參數(shù)：種群大小 pop_size，每條染色體基因串長度 length，交叉概率 Pc，變異概率 Pm，算法迭代次數(shù) T，當(dāng)前迭代次數(shù) t。 種群由 A 進(jìn)化為 A1。 （ 13） 對每代最小適值 M 排序， me 為排序后的向量。 （ 3）上取整函數(shù) ceil。具體過程如下： ① 利用 rand 函數(shù)產(chǎn)生一個 0～ 1 之間的隨機(jī)數(shù) r。 為了充分比較兩種算法收斂效果，我們 對遺傳算法 分別采用 大小為 300 和 200 的兩個種群 ，懲罰函數(shù)法分別取初始懲罰因子 M 為 10 和 1，兩種算法分別 執(zhí)行算法 10 次 ，得到結(jié)果如表61 所示。 表 63 運(yùn)行時間比較 表 遺傳算法 懲罰函數(shù)法 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 最大值 最小值 均 值 從表中可以看出，懲罰函數(shù)法在運(yùn)行時間上明顯優(yōu)于遺傳算法，說 明 傳統(tǒng)算法也有其 可取 優(yōu)勢，不可能被完全取代。 通過理論分析以及對測試數(shù)據(jù)的統(tǒng)計分析，我們可以看到 求解非線性規(guī)劃問題的遺傳算法 與 傳統(tǒng)的非線性規(guī)劃算法 相比， 收斂 結(jié)果更 優(yōu) ，性能更穩(wěn)定，魯棒性強(qiáng)， 對目標(biāo)函數(shù)既不要求連續(xù)，也不要求可 導(dǎo)，有效地克服了傳統(tǒng)算法對函數(shù)初值和函數(shù)性態(tài)要求高 ，容易陷入局部最優(yōu)解的缺陷。在論文的選題、研究以及撰寫過程中，自始至終得到了導(dǎo)師的精心指導(dǎo)和熱情幫助，其中無不凝聚著導(dǎo)師的心血和汗水