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

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

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

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

4、看成是設(shè)計變量向量的端點 點取在坐標(biāo)原點），稱作設(shè)計點。也即：在設(shè)計空間中的一個點，對應(yīng)于一組設(shè)計變量的 值，代表一個設(shè)計方案。設(shè)計空間包含了該項設(shè)計所有可能的設(shè)計方案。 （ 2）向量表示法： 二維問題 二維向量 X x1, x2T三維問題三維向量 X x1,x2,x3Tn維問題n維向量X xX2, 幾丁設(shè)計變量的選取a、維數(shù)：設(shè)計變量的數(shù)目稱為最優(yōu)化問題的維數(shù)。如有 n個設(shè)計變量則稱為n維問題b、常選用的設(shè)計變量（1）結(jié)構(gòu)的總體布置尺寸，如中心距。（2）元件的幾何尺寸：長度，截面尺寸，某些點的坐標(biāo)值。（3）材料的力學(xué)和物理特性：重量、慣性矩、力或力矩等。通常選擇的設(shè)計變量都是構(gòu)件的幾個尺寸，

5、因為這不僅可使問題相對簡單些，而且由 于很多實際結(jié)構(gòu)的幾個關(guān)系和材料特性已決定的緣故。決定結(jié)構(gòu)布置情況的設(shè)計變量的選 取要復(fù)雜些。較困難的是選取表示材料特性的變量，因為通常所用材料的特性是離散值， 選擇這些變量時出現(xiàn)了設(shè)計變量不連續(xù)變化的這一特殊問題。c、設(shè)計變量的選擇原則（1）對設(shè)計影響較大的參數(shù)選為設(shè)計變量（2）盡量減少設(shè)計變量的個數(shù)2.2設(shè)計約束設(shè)計約束的種類a、定義：設(shè)計空間是所有設(shè)計方案的集合，但這些設(shè)計方案有些是工程上所不能接受的（例如 面積取負(fù)等）。如果一個設(shè)計滿足所有對它提出的要求，就稱為可行（或可接受）設(shè)計。 反之則稱為不可行（或不可接受）設(shè)計。在設(shè)計過程中，為了得到可行的設(shè)

6、計方案，必須根據(jù)實際要求，對設(shè)計變量的取值加 以種種限制，這種限制條件稱為約束條件。即：一個可行設(shè)計必須滿足的限制條件稱為約 束條件。b、分類法一"性能約束：針對性能要求而提出的限制條件稱為性能約束。例如：強(qiáng)度條件、剛度或穩(wěn)定性條件等等。匚邊界約束：對設(shè)計變量的取值圍加以限制的約束。例如允許選擇的尺寸圍。法二.等式約束：h( x) =0要求設(shè)計點在n維設(shè)計空間的約束曲面上不等式約束：g (x)要求設(shè)計點在約束曲面一側(cè)222可行域與非可行域設(shè)計可行域：凡滿足所有約束條件的設(shè)計點，它在設(shè)計空間中的活動圍稱作可行域。2.3目標(biāo)函數(shù)231目標(biāo)函數(shù)的定義：a、定義在設(shè)計中，設(shè)計者總是希望所設(shè)計

7、的產(chǎn)品或工程設(shè)施具有最好的使用性能，最小的質(zhì) 量或最緊湊的體積和最小的制造成本及最大的經(jīng)濟(jì)效益。在最優(yōu)設(shè)計中，可將所追求的設(shè) 計目標(biāo)(最優(yōu)指標(biāo))用設(shè)計變量的函數(shù)形式表達(dá)出來。目標(biāo)函數(shù)是設(shè)計中預(yù)期要達(dá)到的目標(biāo)，表達(dá)為各設(shè)計變量的函數(shù)表達(dá)式：f(X) f(Xi,X2, Xn)在優(yōu)化設(shè)計中，用目標(biāo)函數(shù)的大小來衡量設(shè)計方案的優(yōu)劣， 故目標(biāo)函數(shù)又叫評價函數(shù) 優(yōu)化設(shè)計中，通常對目標(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)的運動軌跡最準(zhǔn)確（6）滿足應(yīng)力要求

8、（材料利用最好）（7）振動或噪聲最?。X輪振動，由側(cè)隙產(chǎn)生，尋找一周期嚙合點加速度平方根值最小）（8）平均壽命最長（軸承的壽命計算）。（9）冷卻效果最好（軸承的熱平衡計算）。（10）可靠性最高。2.4優(yōu)化設(shè)計數(shù)學(xué)模型的幾何意義優(yōu)化設(shè)計數(shù)學(xué)模型的一般形式a、模型形式選取設(shè)計變量，列出目標(biāo)函數(shù)，給定約束條件后，便可構(gòu)造最優(yōu)化設(shè)計的數(shù)學(xué)模型。任何一個最優(yōu)化問題均可歸結(jié)為如下描述：在給定的約束條件下，選取適當(dāng)?shù)脑O(shè)計變量 X，使其目標(biāo)函數(shù)f （X）達(dá)到最優(yōu)值，其 數(shù)學(xué)表達(dá)式（數(shù)學(xué)模型）為：min f（X） f（Xi,X2, ,Xn）X XM,曲丁st. gu （X）0 （u 1,2,m）hv（x）0 （

9、v 1,2, p n）b、模型分類：（1）法一 -有約束無約束（2）法二一-線性：目標(biāo)函數(shù)和約束函數(shù)都是線性的。非線性：目標(biāo)函數(shù)和約束函數(shù)至少有一個為非線性最優(yōu)化問題的幾何描述a、約束條件與可行域b、目標(biāo)函數(shù)等值線（1）定義：目標(biāo)函數(shù)是n為變量的函數(shù)，它的圖象只能在n+1維空間中描述出來。給定一 組設(shè)計變量的值就相應(yīng)有一個函數(shù)值（并相應(yīng)在設(shè)計空間對應(yīng)于一個設(shè)計點）， 具有相同函數(shù)值的點集在設(shè)計空間形成一個曲線或曲面，就是目標(biāo)函數(shù)的等值面 或等值線。（C、無約束最優(yōu)解和約束最優(yōu)解（1）無約束優(yōu)化問題：在沒有限制條件下，對設(shè)計變量求目標(biāo)函數(shù)的極小點， 即求等值面 中心。（2）約束優(yōu)化問題：在設(shè)計可

10、行域?qū)で竽繕?biāo)函數(shù)的極小點。243局部最優(yōu)解和全局最優(yōu)解一、單谷函數(shù)和多股函數(shù)只有一個極值點的函數(shù)稱為單谷函數(shù)；具有兩個以上局部極值點的函數(shù)稱為多谷函數(shù)。二、局部最優(yōu)解和全局最優(yōu)解2.5優(yōu)化設(shè)計數(shù)學(xué)模型大小的分類：n > 50大型10< nW50 中型v 10小型3. 經(jīng)典優(yōu)化算法小結(jié)：3.1無約束優(yōu)化方法工程優(yōu)化問題通常都是多維有約束優(yōu)化問題，但需從一維無約束問題到多維無約束優(yōu) 化問題再到多維約束優(yōu)化問題的由簡單到復(fù)雜的循序漸進(jìn)的研究過程。無約束優(yōu)化問題數(shù)學(xué)模型：min f（X）, X Rn分類，從是否利用目標(biāo)函數(shù)的導(dǎo)數(shù)信息，分直接法和間接法直接法：坐標(biāo)輪換法、共軛方向法、鮑威爾法

11、（略）i |間接法：梯度法、牛頓法（略）、變尺度法（略）坐標(biāo)輪換法3.1.1.1 坐標(biāo)輪換法基本原理將多維無約束優(yōu)化問題分解、轉(zhuǎn)化為一系列一維優(yōu)化問題，輪換沿各個坐標(biāo)軸一維搜 索，直到求得最優(yōu)點。在每次迭代部，要依次沿各坐標(biāo)軸進(jìn)行 2次（N為優(yōu)化問題的維數(shù)）一維搜索。這種一 維搜索是固定其它N-1維變量，視為常量，然后進(jìn)行一維搜索，X： X：!：ej,（j1,2,N），對于第k輪迭代，須重復(fù)N次該式的一維搜索，搜索的參數(shù)為ak （即要優(yōu)化的參數(shù)是ak），為相對第j維變量的搜索步長，搜索方向為第j維空間坐 標(biāo)的方向。當(dāng)k輪迭代結(jié)束后，本輪搜索的重點作為下一輪的起點，即Xok1 XN，然后投入下一

12、輪迭代。3.1.1.2 該方法特點不考慮目標(biāo)函數(shù)本身的變化情況（函數(shù)特點），簡單、效率低、收斂速度慢。共軛方向法3.1.2.1 共軛方向1對于N維正定二次函數(shù)f（X） XtAX bTX c （當(dāng)N=2,為同心橢圓族），H為函2數(shù)f的黑塞矩陣（正定對稱陣）。若存在兩個方向向量S1，S2，滿足S1T H S20，則稱S1與S2為共軛方向。如何構(gòu)造共軛方向（二維）？對于某兩點 X10.X20，沿方向S1（ X10 X20,S1不平行） 一維搜索得到兩個最優(yōu)點X1, X2，構(gòu)成方向S2 X2 X1，則可以證明S1與S2為共軛方向， 即 S1T H S20當(dāng)然，這個結(jié)論可以從2維推廣到N維。同樣，說明對

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

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

15、的方向。從這一點受啟發(fā)，可以使迭代方向沿梯度方向進(jìn)行一維搜索來再多維空間尋優(yōu)。即搜索方向為梯度方向：kkskf(Xk)，或 Skf；X*，則迭代公式為 Xk1 Xk kV。3.1.3 .2梯度法的特點前提是梯度存在。優(yōu)點是算法簡單。相鄰兩次迭代的搜索方向垂直。即f(Xk1)T f(Xk) 0證明：Xk1 Xk k f (Xk)，即k輪迭代經(jīng)過一次一維搜索由k點到達(dá)k+1點，那么mi n f(Xk k f(Xk)，對于一維優(yōu)化有f k 0,所以")T X k/E)f (Xk 1)T f(Xk) 0可見，相鄰兩輪迭代的搜索方向并不一致，為相互垂直的鋸齒形過程。剃度法對于迭 代出發(fā)點目標(biāo)函

16、數(shù)等值面偏心率為零時很有效，但對于有偏心的其效率就低了，隨偏心率 的增加，迭代終止的難度也在增加?？梢娺@種搜索在接近目標(biāo)時的收斂是比較慢(缺點) 的，效率也就不會高了。剃度法一般并不作為工程中實際應(yīng)用的方法，常用于其他方法的 初始迭代(類似于坐標(biāo)輪換法)。3.2約束優(yōu)化方法實際工程優(yōu)化問題大多數(shù)為設(shè)計空間多維且?guī)в屑s束條件的非線性優(yōu)化問題。其數(shù)學(xué)模型 為mi nf(X),X Rnst. gu(X)0,u1,2, ,mhv(X)0,v 1,2, p n根據(jù)對約束條件處理方法的不同:直接法(約束坐標(biāo)輪換法、隨機(jī)方向法、復(fù)合形法、可行方向法)間接法(簡約梯度法、懲罰函數(shù)法等)。直接法可以直接從可行域

17、中找到最優(yōu)解；將問題分解為一系列比較簡單的子問題，用子問 題的解逼近原問題的解。直接法簡單直觀、對目標(biāo)函數(shù)要求不高；計算量大、收斂慢，因此效率低。321約束隨機(jī)方向搜索法(隨機(jī)方向法)321.1 基本原理從可行域某一點出發(fā)，沿某一給定步長，并隨機(jī)產(chǎn)生搜索方向，直到該方向同時滿足 可行性和下降性要求，沿著這個方向以該步長繼續(xù)搜索，直到不滿足可行性及下降性條件 為止。把上述滿足要求的終點作為新的起點，重新產(chǎn)生隨機(jī)方向，如果能夠找到一個合適 的方向，同時滿足條件，貝U沿該方向以原步長繼續(xù)搜索；如若找不到適合的方向，貝U將步 長減半，仍以該點為起點隨機(jī)搜索，如果能找到新的方向，貝U沿該方向繼續(xù)，如果不

18、能， 步長再減半。直到找不到新的搜索方向，且步長滿足精度要求，則以該起點為最優(yōu)點。 一個需要說明的問題：從某一點出發(fā)，如何判斷沿某一給定步長找不到可行的方向呢？如 果不靠目標(biāo)函數(shù)和約束條件中隱含的指引信息，那么只有對搜索空間進(jìn)行機(jī)械的排查，對 隨機(jī)方向搜索法而言，就是在產(chǎn)生并搜索了足夠多方向之后，認(rèn)為可以近似的得出這個結(jié) 論。那么，到底隨機(jī)搜索了多少個方向才能得出結(jié)論呢？ 一般取50500個方向，當(dāng)然，如果不考慮計算的速度和效率，這個最大的方向數(shù)大一些更好，而且設(shè)計空間維數(shù)越大，這 個數(shù)也應(yīng)越大。初始點的選取才 a, nQ aj其中門為隨機(jī)數(shù)，對C語言，有函數(shù)rand()產(chǎn)生一個0到RAND_

19、MAX偽隨機(jī)整數(shù)，則rand ()r,RAND _ MAX隨機(jī)搜索方向的產(chǎn)生y 2r (1,1,1)T。通過該變換，使搜索方向的每個分量為-1到1之間的隨機(jī)值，從而確保對每個坐標(biāo)方向的正負(fù)兩方向的搜索。之后可以進(jìn)行標(biāo)準(zhǔn)化處理e -yhll隨機(jī)法的特點算法簡單，對目標(biāo)函數(shù)要求不高；由于隨機(jī)搜索帶有盲目性，效率低，速度慢，可能不 收斂。復(fù)合形法3.2.2.1 基本原理（1） 在設(shè)計空間找到K個可行點構(gòu)成多面體（復(fù)合形），一般 N+1W KW 2N。（2）不斷使復(fù)合形向著約束最優(yōu)點移動和收縮。更具體一些，根據(jù)目標(biāo)函數(shù)值的大小找出這K個點中的最壞點（函數(shù)值最大），除最壞點之外的其它K-1個點的形心為映

20、射中點，找到最壞點的映射點（對稱點），最壞點之外其余K-1個點以及這個映射點構(gòu)成新的復(fù)合形。（3）檢驗復(fù)合形中各個點與最好點是否滿足重合，或這些點收斂于某個精度構(gòu)成的最好 點的臨域之。若滿足，貝U算法成功結(jié)束；否則，重復(fù) 。322.2 幾個關(guān)鍵問題（一）初始復(fù)合形的產(chǎn)生1 確定第一個可行點作為復(fù)合形的第一個頂點。如果不滿足可行性，反復(fù)進(jìn)行隨機(jī)搜索， 直到找到可行點。公式x1 ai（bi aj2再隨機(jī)產(chǎn)生其余K-1個頂點。xij ai rij（bi ai）, j 2,3, ,k3對2.中產(chǎn)生的K-1個點逐一檢驗可行性，并將不滿足的點調(diào)入可行域。具體的方法：1）從第一個點起，找到滿足可行性的q個點

21、，第q+1個點不滿足。求前q個點的形心。2）將q+1點向這個形心按兩點長度的一半移動，如此反復(fù)，直到將該點移入可行域。3）之后其它不可行的點按1）、2）的步驟重復(fù)，直到K個點均滿足可行性。（二）映射點不滿足可行性和下降性的處理1）如果映射點不滿足可行性和下降性，將映射系數(shù)減半，產(chǎn)生新的映射點，如此反 復(fù)，直到滿足；否則2）2）以次壞點取代最壞點，求新的形心和形心的映射點。（三）可行域為非凸集的處理如果除最壞點外其它K-1個點的形心不在可行域，則可行域可能是非凸集。這時在以最好點和該形心構(gòu)成的超立方體中重新構(gòu)造復(fù)合形。如果xiL xC，則 aixL, bixC（四）迭代終止條件：各頂點與最好點目

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

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

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

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

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

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

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

29、隱函數(shù)， 因而應(yīng)用圍較廣（7）遺傳算法具有并行計算的特點，因而可通過大規(guī)模并行計算來提高計算速度，適 合大規(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)行性能評價的常用算例。尤 其是對非線性、多模型、多目標(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) 實生產(chǎn)中多采用一些經(jīng)驗進(jìn)行調(diào)度。遺傳算法是解決復(fù)雜調(diào)度問題的有效工具，在單件生 產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到