現(xiàn)代優(yōu)化方法綜述

1、1. 引言優(yōu)化設(shè)計(jì)英文名是optimization design，從多種方案中選擇最佳方案的設(shè)計(jì)方法。它以數(shù)學(xué)中的最優(yōu)化理論為基礎(chǔ)，以計(jì)算機(jī)為手段，根據(jù)設(shè)計(jì)所追求的性能目標(biāo)，建立目標(biāo)函數(shù)，在滿足給定的各種約束條件下，尋求最優(yōu)的設(shè)計(jì)方案。第二次世界大戰(zhàn)期間，在軍事上首先應(yīng)用了優(yōu)化技術(shù)。1967年，美國的R.L.?？怂沟劝l(fā)表了第一篇機(jī)構(gòu)最優(yōu)化論文。1970年，C.S.貝特勒等用幾何規(guī)劃解決了液體動(dòng)壓軸承的優(yōu)化設(shè)計(jì)問題后，優(yōu)化設(shè)計(jì)在機(jī)械設(shè)計(jì)中得到應(yīng)用和發(fā)展。隨著數(shù)學(xué)理論和電子計(jì)算機(jī)技術(shù)的進(jìn)一步發(fā)展，優(yōu)化設(shè)計(jì)已逐步形成為一門新興的獨(dú)立的工程學(xué)科，并在生產(chǎn)實(shí)踐中得到了廣泛的應(yīng)用。通常設(shè)計(jì)方案可以用一組參

2、數(shù)來表示，這些參數(shù)有些已經(jīng)給定，有些沒有給定，需要在設(shè)計(jì)中優(yōu)選，稱為設(shè)計(jì)變量。如何找到一組最合適的設(shè)計(jì)變量，在允許的范圍內(nèi)，能使所設(shè)計(jì)的產(chǎn)品結(jié)構(gòu)最合理、性能最好、質(zhì)量最高、成本最低（即技術(shù)經(jīng)濟(jì)指標(biāo)最佳），有市場競爭能力，同時(shí)設(shè)計(jì)的時(shí)間又不要太長，這就是優(yōu)化設(shè)計(jì)所要解決的問題。一般來說，優(yōu)化設(shè)計(jì)有以下幾個(gè)步驟：建立數(shù)學(xué)模型。選擇最優(yōu)化算法。程序設(shè)計(jì)。制定目標(biāo)要求。計(jì)算機(jī)自動(dòng)篩選最優(yōu)設(shè)計(jì)方案等。2. 數(shù)學(xué)模型優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型是對優(yōu)化設(shè)計(jì)工程問題的數(shù)學(xué)描述，它包含設(shè)計(jì)變量、目標(biāo)函數(shù)和設(shè)計(jì)約束三個(gè)基本要素。2.1設(shè)計(jì)變量基本參數(shù)a、定義：在設(shè)計(jì)過程中進(jìn)行選擇變化并最終確定的各項(xiàng)獨(dú)立參數(shù)稱為設(shè)計(jì)變量。

3、b、說明：在設(shè)計(jì)選擇過程中，這些設(shè)計(jì)變量是變量，但它們一旦被確定后，設(shè)計(jì)對象也就完全確定了。最優(yōu)化設(shè)計(jì)是研究怎樣合理地優(yōu)選這些設(shè)計(jì)變量的一種現(xiàn)代設(shè)計(jì)方法。在設(shè)計(jì)過程中，凡根據(jù)設(shè)計(jì)要求事先給定的，不是設(shè)計(jì)變量而是設(shè)計(jì)常量。設(shè)計(jì)方案的表現(xiàn)形式a、設(shè)計(jì)空間：由n個(gè)設(shè)計(jì)變量為坐標(biāo)所組成的時(shí)空間稱作設(shè)計(jì)空間。b、設(shè)計(jì)變量的表示法（1）坐標(biāo)表示法：一維問題一個(gè)設(shè)計(jì)變量數(shù)軸上的一個(gè)點(diǎn) 二維問題兩個(gè)設(shè)計(jì)變量平面直角坐標(biāo)系上的向量 三維問題三個(gè)設(shè)計(jì)變量空間直角坐標(biāo)系的向量n維問題n個(gè)設(shè)計(jì)變量n維超越空間的向量一個(gè)“設(shè)計(jì)”方案，可用設(shè)計(jì)空間中的一點(diǎn)表示，此點(diǎn)可看成是設(shè)計(jì)變量向量的端點(diǎn)（始點(diǎn)取在坐標(biāo)原點(diǎn)），稱作設(shè)計(jì)

4、點(diǎn)。也即：在設(shè)計(jì)空間中的一個(gè)點(diǎn)，對應(yīng)于一組設(shè)計(jì)變量的值，代表一個(gè)設(shè)計(jì)方案。設(shè)計(jì)空間包含了該項(xiàng)設(shè)計(jì)所有可能的設(shè)計(jì)方案。（2）向量表示法：二維問題二維向量 三維問題三維向量 n維問題n維向量設(shè)計(jì)變量的選取a、維數(shù)：設(shè)計(jì)變量的數(shù)目稱為最優(yōu)化問題的維數(shù)。如有n個(gè)設(shè)計(jì)變量則稱為n維問題。b、常選用的設(shè)計(jì)變量（1）結(jié)構(gòu)的總體布置尺寸，如中心距。（2）元件的幾何尺寸：長度，截面尺寸，某些點(diǎn)的坐標(biāo)值。（3）材料的力學(xué)和物理特性：重量、慣性矩、力或力矩等。通常選擇的設(shè)計(jì)變量都是構(gòu)件的幾個(gè)尺寸，因?yàn)檫@不僅可使問題相對簡單些，而且由于很多實(shí)際結(jié)構(gòu)的幾個(gè)關(guān)系和材料特性已決定的緣故。決定結(jié)構(gòu)布置情況的設(shè)計(jì)變量的選取要復(fù)

5、雜些。較困難的是選取表示材料特性的變量，因?yàn)橥ǔＫ貌牧系奶匦允请x散值，選擇這些變量時(shí)出現(xiàn)了設(shè)計(jì)變量不連續(xù)變化的這一特殊問題。c、設(shè)計(jì)變量的選擇原則（1）對設(shè)計(jì)影響較大的參數(shù)選為設(shè)計(jì)變量（2）盡量減少設(shè)計(jì)變量的個(gè)數(shù)2.2設(shè)計(jì)約束設(shè)計(jì)約束的種類a、定義：設(shè)計(jì)空間是所有設(shè)計(jì)方案的集合，但這些設(shè)計(jì)方案有些是工程上所不能接受的（例如面積取負(fù)等）。如果一個(gè)設(shè)計(jì)滿足所有對它提出的要求，就稱為可行（或可接受）設(shè)計(jì)。反之則稱為不可行（或不可接受）設(shè)計(jì)。在設(shè)計(jì)過程中，為了得到可行的設(shè)計(jì)方案，必須根據(jù)實(shí)際要求，對設(shè)計(jì)變量的取值加以種種限制，這種限制條件稱為約束條件。即：一個(gè)可行設(shè)計(jì)必須滿足的限制條件稱為約束條件。

6、b、分類法一 性能約束：針對性能要求而提出的限制條件稱為性能約束。例如：強(qiáng)度條件、剛度或穩(wěn)定性條件等等。邊界約束：對設(shè)計(jì)變量的取值范圍加以限制的約束。例如允許選擇的尺寸范圍。法二 等式約束：h（x）=0要求設(shè)計(jì)點(diǎn)在n維設(shè)計(jì)空間的約束曲面上不等式約束：g（x）0要求設(shè)計(jì)點(diǎn)在約束曲面一側(cè)2.2.2可行域與非可行域設(shè)計(jì)可行域：凡滿足所有約束條件的設(shè)計(jì)點(diǎn)，它在設(shè)計(jì)空間中的活動(dòng)范圍稱作可行域。2.3目標(biāo)函數(shù)2.3.1目標(biāo)函數(shù)的定義：a、定義在設(shè)計(jì)中，設(shè)計(jì)者總是希望所設(shè)計(jì)的產(chǎn)品或工程設(shè)施具有最好的使用性能，最小的質(zhì)量或最緊湊的體積和最小的制造成本及最大的經(jīng)濟(jì)效益。在最優(yōu)設(shè)計(jì)中，可將所追求的設(shè)計(jì)目標(biāo)（最優(yōu)指

7、標(biāo)）用設(shè)計(jì)變量的函數(shù)形式表達(dá)出來。l 目標(biāo)函數(shù)是設(shè)計(jì)中預(yù)期要達(dá)到的目標(biāo)，表達(dá)為各設(shè)計(jì)變量的函數(shù)表達(dá)式：l 在優(yōu)化設(shè)計(jì)中，用目標(biāo)函數(shù)的大小來衡量設(shè)計(jì)方案的優(yōu)劣，故目標(biāo)函數(shù)又叫評價(jià)函數(shù)。 l 優(yōu)化設(shè)計(jì)中，通常對目標(biāo)函數(shù)求極小值。b、常用的目標(biāo)函數(shù)（1）以成本最低構(gòu)造目標(biāo)函數(shù)。（2）按最小重量構(gòu)造目標(biāo)函數(shù)。（3）按幾何要求：如最小體積，最小尺寸構(gòu)造目標(biāo)函數(shù)。（4）按機(jī)構(gòu)的工作精度要求構(gòu)造（5）按機(jī)構(gòu)的運(yùn)動(dòng)軌跡最準(zhǔn)確（6）滿足應(yīng)力要求（材料利用最好）（7）振動(dòng)或噪聲最?。X輪振動(dòng)，由側(cè)隙產(chǎn)生，尋找一周期內(nèi)嚙合點(diǎn)加速度平方根值最?。＃?）平均壽命最長（軸承的壽命計(jì)算）。（9）冷卻效果最好（軸承的熱平衡

8、計(jì)算）。（10）可靠性最高。2.4 優(yōu)化設(shè)計(jì)數(shù)學(xué)模型的幾何意義 優(yōu)化設(shè)計(jì)數(shù)學(xué)模型的一般形式a、模型形式選取設(shè)計(jì)變量，列出目標(biāo)函數(shù)，給定約束條件后，便可構(gòu)造最優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型。任何一個(gè)最優(yōu)化問題均可歸結(jié)為如下描述：在給定的約束條件下，選取適當(dāng)?shù)脑O(shè)計(jì)變量X，使其目標(biāo)函數(shù)f（X）達(dá)到最優(yōu)值，其數(shù)學(xué)表達(dá)式（數(shù)學(xué)模型）為： b、模型分類：（1）法一 有約束 無約束（2）法二 線性：目標(biāo)函數(shù)和約束函數(shù)都是線性的。 非線性：目標(biāo)函數(shù)和約束函數(shù)至少有一個(gè)為非線性最優(yōu)化問題的幾何描述a、約束條件與可行域b、目標(biāo)函數(shù)等值線（1）定義：目標(biāo)函數(shù)是n為變量的函數(shù)，它的圖象只能在n+1維空間中描述出來。給定一組設(shè)計(jì)變

9、量的值就相應(yīng)有一個(gè)函數(shù)值（并相應(yīng)在設(shè)計(jì)空間對應(yīng)于一個(gè)設(shè)計(jì)點(diǎn)），具有相同函數(shù)值的點(diǎn)集在設(shè)計(jì)空間內(nèi)形成一個(gè)曲線或曲面，就是目標(biāo)函數(shù)的等值面或等值線。（c、無約束最優(yōu)解和約束最優(yōu)解（1）無約束優(yōu)化問題：在沒有限制條件下，對設(shè)計(jì)變量求目標(biāo)函數(shù)的極小點(diǎn)，即求等值面中心。（2）約束優(yōu)化問題：在設(shè)計(jì)可行域內(nèi)尋求目標(biāo)函數(shù)的極小點(diǎn)。局部最優(yōu)解和全局最優(yōu)解一、單谷函數(shù)和多股函數(shù)只有一個(gè)極值點(diǎn)的函數(shù)稱為單谷函數(shù)；具有兩個(gè)以上局部極值點(diǎn)的函數(shù)稱為多谷函數(shù)。二、局部最優(yōu)解和全局最優(yōu)解2.5優(yōu)化設(shè)計(jì)數(shù)學(xué)模型大小的分類: n50大型 10n50中型n10小型 3. 經(jīng)典優(yōu)化算法小結(jié)：3.1無約束優(yōu)化方法 工程優(yōu)化問題通常都

10、是多維有約束優(yōu)化問題，但需從一維無約束問題到多維無約束優(yōu)化問題再到多維約束優(yōu)化問題的由簡單到復(fù)雜的循序漸進(jìn)的研究過程。 無約束優(yōu)化問題數(shù)學(xué)模型： 分類，從是否利用目標(biāo)函數(shù)的導(dǎo)數(shù)信息，分直接法和間接法直接法：坐標(biāo)輪換法、共軛方向法、鮑威爾法(略)間接法：梯度法、牛頓法(略)、變尺度法(略)3.1.1 坐標(biāo)輪換法.1 坐標(biāo)輪換法基本原理將多維無約束優(yōu)化問題分解、轉(zhuǎn)化為一系列一維優(yōu)化問題，輪換沿各個(gè)坐標(biāo)軸一維搜索，直到求得最優(yōu)點(diǎn)。在每次迭代內(nèi)部，要依次沿各坐標(biāo)軸進(jìn)行N次（N為優(yōu)化問題的維數(shù)）一維搜索。這種一維搜索是固定其它N-1維變量，視為常量，然后進(jìn)行一維搜索，對于第k輪迭代，須重復(fù)N次該式的一維

11、搜索，搜索的參數(shù)為ajk（即要優(yōu)化的參數(shù)是ajk），為相對第j維變量的搜索步長，搜索方向?yàn)榈趈維空間坐標(biāo)的方向。當(dāng)k輪迭代結(jié)束后，本輪搜索的重點(diǎn)作為下一輪的起點(diǎn)，即，然后投入下一輪迭代。.2 該方法特點(diǎn) 不考慮目標(biāo)函數(shù)本身的變化情況（函數(shù)特點(diǎn)），簡單、效率低、收斂速度慢。3.1.2 共軛方向法.1 共軛方向?qū)τ贜維正定二次函數(shù) (當(dāng)N=2，為同心橢圓族)，H為函數(shù)f的黑塞矩陣(正定對稱陣)。若存在兩個(gè)方向向量，滿足，則稱與為共軛方向。如何構(gòu)造共軛方向（二維）？對于某兩點(diǎn)，沿方向（不平行）一維搜索得到兩個(gè)最優(yōu)點(diǎn)，構(gòu)成方向，則可以證明與為共軛方向，即當(dāng)然，這個(gè)結(jié)論可以從2維推廣到N維。同樣，說明對

12、于N維函數(shù)，有N個(gè)共軛方向。對于二次函數(shù)，只要經(jīng)過N個(gè)一維搜索即可到達(dá)最優(yōu)點(diǎn)（即N維空間內(nèi)完成一輪迭代）。對于大于二次的函數(shù)，則可能需要將上一輪迭代的終點(diǎn)作為新一輪迭代的起點(diǎn)。在構(gòu)造迭代方程式時(shí)，可以用二次泰勒展開式來近似目標(biāo)函數(shù)的等值面。.2 共軛方向法基本原理第一輪迭代與坐標(biāo)輪換法相同。將起點(diǎn)和N次一維搜索的末點(diǎn)組成一個(gè)新的方向，沿這個(gè)方向一維搜索，得到本輪迭代的終點(diǎn)。從第二輪起，舍去前一輪的第一個(gè)一維搜索方向，將前一輪的后N個(gè)一維搜索方向作為本輪迭代的前N個(gè)方向，這N個(gè)方向的一維搜索終點(diǎn)與本輪搜索的起點(diǎn)構(gòu)成第N+1個(gè)一維搜索方向，沿這個(gè)方向做一維搜索，得到本輪搜索的終點(diǎn)。若不滿足精度要求

13、，則重復(fù)迭代。.3 共軛方向法的特點(diǎn)收斂速度比坐標(biāo)輪換法有明顯的提高，但前提是每次迭代所產(chǎn)生的新的方向與原來的N-1個(gè)方向之間要保持線性無關(guān)，若這些方向之間線性相關(guān)，則降低了搜索空間的維數(shù)，導(dǎo)致不能完全窮盡對設(shè)計(jì)空間每個(gè)方向的搜索，從而不能收斂于真正的最優(yōu)解。3.1.3 梯度法（最速下降法）.1 梯度法基本原理無約束優(yōu)化的直接法（坐標(biāo)輪換法和共軛方向法、鮑威爾法）沒有考慮無約束優(yōu)化最優(yōu)解存在的必要條件（梯度為零），使用這一條件，可以設(shè)計(jì)出更為高效的算法，所謂間接法（梯度法、牛頓法、變尺度法）。梯度方向是函數(shù)值變化最快的方向，那么負(fù)梯度方向便是函數(shù)值下降最快的方向。從這一點(diǎn)受啟發(fā)，可以使迭代方向

14、沿梯度方向進(jìn)行一維搜索來再多維空間尋優(yōu)。即搜索方向?yàn)樘荻确较颍?，或，則迭代公式為。.2 梯度法的特點(diǎn)前提是梯度存在。優(yōu)點(diǎn)是算法簡單。相鄰兩次迭代的搜索方向垂直。即證明：，即k輪迭代經(jīng)過一次一維搜索由k點(diǎn)到達(dá)k+1點(diǎn)，那么，對于一維優(yōu)化有，所以可見，相鄰兩輪迭代的搜索方向并不一致，為相互垂直的鋸齒形過程。剃度法對于迭代出發(fā)點(diǎn)目標(biāo)函數(shù)等值面偏心率為零時(shí)很有效，但對于有偏心的其效率就低了，隨偏心率的增加，迭代終止的難度也在增加。可見這種搜索在接近目標(biāo)時(shí)的收斂是比較慢（缺點(diǎn)）的，效率也就不會高了。剃度法一般并不作為工程中實(shí)際應(yīng)用的方法，常用于其他方法的初始迭代（類似于坐標(biāo)輪換法）。3.2約束優(yōu)化方法實(shí)

15、際工程優(yōu)化問題大多數(shù)為設(shè)計(jì)空間多維且?guī)в屑s束條件的非線性優(yōu)化問題。其數(shù)學(xué)模型為根據(jù)對約束條件處理方法的不同：直接法（約束坐標(biāo)輪換法、隨機(jī)方向法、復(fù)合形法、可行方向法）間接法（簡約梯度法、懲罰函數(shù)法等）。直接法可以直接從可行域中找到最優(yōu)解；將問題分解為一系列比較簡單的子問題，用子問題的解逼近原問題的解。直接法簡單直觀、對目標(biāo)函數(shù)要求不高；計(jì)算量大、收斂慢，因此效率低。 約束隨機(jī)方向搜索法（隨機(jī)方向法）3.2.1.1 基本原理從可行域內(nèi)某一點(diǎn)出發(fā)，沿某一給定步長，并隨機(jī)產(chǎn)生搜索方向，直到該方向同時(shí)滿足可行性和下降性要求，沿著這個(gè)方向以該步長繼續(xù)搜索，直到不滿足可行性及下降性條件為止。把上述滿足要求

16、的終點(diǎn)作為新的起點(diǎn)，重新產(chǎn)生隨機(jī)方向，如果能夠找到一個(gè)合適的方向，同時(shí)滿足條件，則沿該方向以原步長繼續(xù)搜索；如若找不到適合的方向，則將步長減半，仍以該點(diǎn)為起點(diǎn)隨機(jī)搜索，如果能找到新的方向，則沿該方向繼續(xù)，如果不能，步長再減半。直到找不到新的搜索方向，且步長滿足精度要求，則以該起點(diǎn)為最優(yōu)點(diǎn)。一個(gè)需要說明的問題：從某一點(diǎn)出發(fā)，如何判斷沿某一給定步長找不到可行的方向呢？如果不靠目標(biāo)函數(shù)和約束條件中隱含的指引信息，那么只有對搜索空間進(jìn)行機(jī)械的排查，對隨機(jī)方向搜索法而言，就是在產(chǎn)生并搜索了足夠多方向之后，認(rèn)為可以近似的得出這個(gè)結(jié)論。那么，到底隨機(jī)搜索了多少個(gè)方向才能得出結(jié)論呢？一般取50500個(gè)方向，當(dāng)

17、然，如果不考慮計(jì)算的速度和效率，這個(gè)最大的方向數(shù)大一些更好，而且設(shè)計(jì)空間維數(shù)越大，這個(gè)數(shù)也應(yīng)越大。3.2.1.2 初始點(diǎn)的選取其中ri為隨機(jī)數(shù)，對C語言，有函數(shù)rand()產(chǎn)生一個(gè)0到RAND_MAX的偽隨機(jī)整數(shù)，則3.2.1.3隨機(jī)搜索方向的產(chǎn)生。通過該變換，使搜索方向的每個(gè)分量為-1到1之間的隨機(jī)值，從而確保對每個(gè)坐標(biāo)方向的正負(fù)兩方向的搜索。之后可以進(jìn)行標(biāo)準(zhǔn)化處理3.2.1.4 隨機(jī)法的特點(diǎn)算法簡單，對目標(biāo)函數(shù)要求不高；由于隨機(jī)搜索帶有盲目性，效率低，速度慢，可能不收斂。 復(fù)合形法3.2.2.1 基本原理（1） 在設(shè)計(jì)空間找到K個(gè)可行點(diǎn)構(gòu)成多面體（復(fù)合形），一般N+1K2N。（2） 不斷使

18、復(fù)合形向著約束內(nèi)最優(yōu)點(diǎn)移動(dòng)和收縮。更具體一些，根據(jù)目標(biāo)函數(shù)值的大小找出這K個(gè)點(diǎn)中的最壞點(diǎn)（函數(shù)值最大），除最壞點(diǎn)之外的其它K-1個(gè)點(diǎn)的形心為映射中點(diǎn)，找到最壞點(diǎn)的映射點(diǎn)（對稱點(diǎn)），最壞點(diǎn)之外其余K-1個(gè)點(diǎn)以及這個(gè)映射點(diǎn)構(gòu)成新的復(fù)合形。（3） 檢驗(yàn)復(fù)合形中各個(gè)點(diǎn)與最好點(diǎn)是否滿足重合,或這些點(diǎn)收斂于某個(gè)精度構(gòu)成的最好點(diǎn)的臨域之內(nèi)。若滿足，則算法成功結(jié)束；否則，重復(fù)(2)。3.2.2.2 幾個(gè)關(guān)鍵問題（一）初始復(fù)合形的產(chǎn)生1 確定第一個(gè)可行點(diǎn)作為復(fù)合形的第一個(gè)頂點(diǎn)。如果不滿足可行性，反復(fù)進(jìn)行隨機(jī)搜索，直到找到可行點(diǎn)。公式2 再隨機(jī)產(chǎn)生其余K-1個(gè)頂點(diǎn)。3 對2.中產(chǎn)生的K-1個(gè)點(diǎn)逐一檢驗(yàn)可行性，并將

19、不滿足的點(diǎn)調(diào)入可行域。具體的方法：1） 從第一個(gè)點(diǎn)起，找到滿足可行性的q個(gè)點(diǎn)，第q+1個(gè)點(diǎn)不滿足。求前q個(gè)點(diǎn)的形心。2） 將q+1點(diǎn)向這個(gè)形心按兩點(diǎn)長度的一半移動(dòng)，如此反復(fù)，直到將該點(diǎn)移入可行域。3） 之后其它不可行的點(diǎn)按1）、2）的步驟重復(fù)，直到K個(gè)點(diǎn)均滿足可行性。（二） 映射點(diǎn)不滿足可行性和下降性的處理1） 如果映射點(diǎn)不滿足可行性和下降性，將映射系數(shù)減半，產(chǎn)生新的映射點(diǎn)，如此反復(fù)，直到滿足；否則2）2） 以次壞點(diǎn)取代最壞點(diǎn)，求新的形心和形心的映射點(diǎn)。（三） 可行域?yàn)榉峭辜奶幚砣绻顗狞c(diǎn)外其它K-1個(gè)點(diǎn)的形心不在可行域內(nèi)，則可行域可能是非凸集。這時(shí)在以最好點(diǎn)和該形心構(gòu)成的超立方體中重新構(gòu)

20、造復(fù)合形。如果，則（四）迭代終止條件：各頂點(diǎn)與最好點(diǎn)目標(biāo)函數(shù)值之差的均方根小于設(shè)計(jì)精度3.2.2.3 復(fù)合形法的特點(diǎn)搜索具有方向性，收斂速度較快 懲罰函數(shù)法罰函數(shù)法基本思想：約束條件構(gòu)造罰函數(shù)項(xiàng)，并入目標(biāo)函數(shù)，化為無約束優(yōu)化問題。所謂“懲罰”，既是給不滿足約束條件的懲罰項(xiàng)以很大的值，使目標(biāo)函數(shù)的總值增大（就是懲罰），那么無約束優(yōu)化方法就會使搜索向著總值減小的方向前進(jìn)，從而使不滿足的約束的點(diǎn)（或遠(yuǎn)離約束邊界的點(diǎn)）向滿足約束的方向靠攏。4. 現(xiàn)代優(yōu)化算法小結(jié)遺傳算法遺傳算法簡稱GA（Genetic Algorithm），最早由美國Michigan大學(xué)的J. Holland教授提出（于上世紀(jì)60-7

21、0年代，以1975年出版的一本著作為代表）,模擬自然界遺傳機(jī)制和生物進(jìn)化論而成的一種并行隨機(jī)搜索最優(yōu)化方法。 遺傳算法是以達(dá)爾文的自然選擇學(xué)說為基礎(chǔ)發(fā)展起來的。自然選擇學(xué)說包括以下三個(gè)方面：（1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個(gè)特征，物種才能穩(wěn)定存在。（2）變異：親代和子代之間以及子代的不同個(gè)體之間的差異，稱為變異。變異是隨機(jī)發(fā)生的，變異的選擇和積累是生命多樣性的根源。（3）生存斗爭和適者生存：具有適應(yīng)性變異的個(gè)體被保留下來，不具有適應(yīng)性變異的個(gè)體被淘汰，通過一代代的生存環(huán)境的選擇作用，性狀逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。遺

22、傳算法將“優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入優(yōu)化參數(shù)形成的編碼串聯(lián)群體中，按所選擇的適應(yīng)度函數(shù)并通過遺傳中的選擇、交叉及變異對個(gè)體進(jìn)行篩選，使適應(yīng)度高的個(gè)體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的條件。遺傳算法的算法簡單，可并行處理，并能到全局最優(yōu)解。4.1 遺傳算法的基本操作（算子）有（1）選擇（Selection Operator） 選擇是從一個(gè)舊種群中選擇生命力強(qiáng)的個(gè)體位串產(chǎn)生新種群的過程。具有高適應(yīng)度的位串更有可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。 選擇操作可以通過隨機(jī)方法來實(shí)現(xiàn)。首先產(chǎn)生01之間均勻分

23、布的隨機(jī)數(shù)，若某串的選擇概率為40%，則當(dāng)產(chǎn)生的隨機(jī)數(shù)在0.401.0之間時(shí)，該串被選擇，否則被淘汰。（2）交叉（Crossover Operator） 選擇操作能從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體。而交叉模擬了生物進(jìn)化過程中的繁殖現(xiàn)象，通過兩個(gè)染色體的交換組合，來產(chǎn)生新的優(yōu)良品種。 交叉的過程為：在匹配池中任選兩個(gè)染色體，隨機(jī)選擇一點(diǎn)或多點(diǎn)交換點(diǎn)位置；交換雙親染色體交換點(diǎn)右邊的部分，即可得到兩個(gè)新的染色體數(shù)字串。交叉體現(xiàn)了自然界中信息交換的思想。交叉有單點(diǎn)交叉、多點(diǎn)交叉、還有一致交叉、順序交叉和周期交叉。單點(diǎn)交叉是最基本的方法，應(yīng)用較廣。它是指染色體切斷點(diǎn)有一處。（3）變異 (Mu

24、tation Operator) 變異運(yùn)算用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)地改變遺傳基因（表示染色體的符號串的某一位）的值。在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個(gè)基因由1變?yōu)?，或由0變?yōu)?。若只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進(jìn)行搜索，使進(jìn)化過程在早期就陷入局部解而進(jìn)入終止過程，從而影響解的質(zhì)量。為了在盡可能大的空間中獲得質(zhì)量較高的優(yōu)化解，必須采用變異操作。4.2 遺傳算法的特點(diǎn) （1）遺傳算法是對參數(shù)的編碼進(jìn)行操作，而非對參數(shù)本身，這就是使得我們在優(yōu)化計(jì)算過程中可以借鑒生物學(xué)中染色體和基因等概念，模仿自

25、然界中生物的遺傳和進(jìn)化等機(jī)理（2）遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息。傳統(tǒng)的優(yōu)化方法往往是從解空間的單個(gè)初始點(diǎn)開始最優(yōu)解的迭代搜索過程，單個(gè)搜索點(diǎn)所提供的信息不多，搜索效率不高，有時(shí)甚至使搜索過程局限于局部最優(yōu)解而停滯不前。遺傳算法從由很多個(gè)體組成的一個(gè)初始群體開始最優(yōu)解的搜索過程，而不是從一個(gè)單一的個(gè)體開始搜索，這是遺傳算法所特有的一種隱含并行性，因此遺傳算法的搜索效率較高（3）遺傳算法直接以目標(biāo)函數(shù)作為搜索信息。傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值，而且需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等輔助信息才能確定搜索方向。而遺傳算法僅使用由目標(biāo)函數(shù)值變換來的適應(yīng)度函數(shù)值，就可以確定進(jìn)一步的搜索方向和搜索范圍，

26、無需目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。遺傳算法可應(yīng)用于目標(biāo)函數(shù)無法求導(dǎo)數(shù)或?qū)?shù)不存在的函數(shù)的優(yōu)化問題，以及組合優(yōu)化問題等（4）遺傳算法使用概率搜索技術(shù)。遺傳算法的選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，因而遺傳算法的搜索過程具有很好的靈活性。隨著進(jìn)化過程的進(jìn)行，遺傳算法新的群體會更多地產(chǎn)生出許多新的優(yōu)良的個(gè)體（5）遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機(jī)搜索（6）遺傳算法對于待尋優(yōu)的函數(shù)基本無限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，又可以是映射矩陣甚至是神經(jīng)網(wǎng)絡(luò)的隱函數(shù)，因而應(yīng)用范圍較廣（7）遺傳算法具有并行計(jì)算的特點(diǎn)，因

27、而可通過大規(guī)模并行計(jì)算來提高計(jì)算速度，適合大規(guī)模復(fù)雜問題的優(yōu)化。 4.3 遺傳算法的應(yīng)用領(lǐng)域（1）函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評價(jià)的常用算例。尤其是對非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，采用其他優(yōu)化方法較難求解，而遺傳算法卻可以得到較好的結(jié)果。（2）組合優(yōu)化 隨著問題的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，采用傳統(tǒng)的優(yōu)化方法很難得到最優(yōu)解。遺傳算法是尋求這種滿意解的最佳工具。例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用。（3）生產(chǎn)調(diào)度問題 在很多情況下，采用建立數(shù)學(xué)模型的方法難以對生產(chǎn)調(diào)度問題進(jìn)行精確求解。在現(xiàn)實(shí)生產(chǎn)中多采用一些經(jīng)驗(yàn)進(jìn)行調(diào)度。遺傳算法是解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。（4）自動(dòng)控制 在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已經(jīng)在其中得