1、第七章 現(xiàn)代優(yōu)化方法第二節(jié) 遺傳算法第三節(jié) 蟻群算法第四節(jié) 基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化方法第一節(jié) 緒論1.現(xiàn)代機(jī)械產(chǎn)品的系統(tǒng)性,綜合性、復(fù)雜性和規(guī)?；瘜?dǎo)致設(shè)計模型的橫向擴(kuò)展.例如,由零件的優(yōu)化發(fā)展到部件,整機(jī)、系列和組合產(chǎn)品的優(yōu)化,由單學(xué)科領(lǐng)域的優(yōu)化發(fā)展到機(jī)、液、光、電、信息的集成優(yōu)化；2.對產(chǎn)品壽命周期優(yōu)化的市場需求導(dǎo)致設(shè)計模型的縱向擴(kuò)展,例如從功能優(yōu)化、原理方案設(shè)計優(yōu)化到技術(shù)設(shè)計優(yōu)化;從性能參數(shù)優(yōu)化、結(jié)構(gòu)參數(shù)優(yōu)化到面向制造的優(yōu)化;從設(shè)計參數(shù)優(yōu)化到加工方案和工藝參數(shù),也即的優(yōu)化;最終直至考慮產(chǎn)品可裝配性、可使用性,可維修性和可回用性等的全壽命周期優(yōu)化；3. 對產(chǎn)品的要求由技術(shù)性擴(kuò)展到經(jīng)濟(jì)性和社會性,

2、導(dǎo)致基于全性能的多目標(biāo)優(yōu)化。第一節(jié) 緒論廣義優(yōu)化設(shè)計方法產(chǎn)生的背景工程優(yōu)化的發(fā)展歷程傳統(tǒng)優(yōu)化往往只適用于簡單零部件，廣義優(yōu)化把對象由此擴(kuò)展到復(fù)雜零部件、整機(jī)、系列產(chǎn)品和組合產(chǎn)品的整體優(yōu)化，可統(tǒng)稱為全系統(tǒng)優(yōu)化?，F(xiàn)代優(yōu)化是全系統(tǒng)優(yōu)化傳統(tǒng)優(yōu)化往往只側(cè)重于某一方面性能的優(yōu)化，處理不同類性能時一般分先后而優(yōu)之。廣義優(yōu)化把優(yōu)化準(zhǔn)則由某方面性能擴(kuò)展到各方面性能，要實現(xiàn)技術(shù)性、經(jīng)濟(jì)性和社會性的綜合評估和優(yōu)化?，F(xiàn)代優(yōu)化是全性能協(xié)調(diào)優(yōu)化傳統(tǒng)優(yōu)化往往局限于產(chǎn)品技術(shù)設(shè)計階段的優(yōu)化，廣義優(yōu)化則把優(yōu)化的范圍擴(kuò)展到包含功能、原理方案和原理參數(shù)、結(jié)構(gòu)方案、結(jié)構(gòu)參數(shù)、結(jié)構(gòu)形狀和公差優(yōu)化的全設(shè)計過程，進(jìn)而面向制造、經(jīng)銷、使用和用

3、后處置的壽命周期設(shè)計過程?，F(xiàn)代優(yōu)化是全設(shè)計過程優(yōu)化傳統(tǒng)優(yōu)化的搜索策略以數(shù)學(xué)規(guī)劃方法為主，對模型數(shù)學(xué)形態(tài)的要求苛刻。廣義優(yōu)化設(shè)計注重開發(fā)、綜合運(yùn)用人類智能、人工智能和各種數(shù)學(xué)工具的新一代搜索策略，處理大規(guī)模復(fù)雜形態(tài)模型的能力顯著提高，從而為全系統(tǒng)、全性能和全壽命周期優(yōu)化模型的綜合求解提供了可能?，F(xiàn)代優(yōu)化是智能優(yōu)化傳統(tǒng)優(yōu)化一般是單學(xué)科、單方面性能、單計算機(jī)串行優(yōu)化的過程，不但費(fèi)時，而且難以得到綜合優(yōu)化解。廣義優(yōu)化實現(xiàn)了多學(xué)科、多方面性能、多計算機(jī)分布式并行協(xié)同優(yōu)化,以追求綜合優(yōu)化解?，F(xiàn)代優(yōu)化是多學(xué)科優(yōu)化 航天、航空、通訊設(shè)備等的快速發(fā)展，提出了大量的復(fù)雜優(yōu)化設(shè)計問題，為現(xiàn)代優(yōu)化方法的產(chǎn)生提供了動力

4、。 生物技術(shù)、并行計算技術(shù)和人工智能技術(shù)以及商用軟件等的發(fā)展為現(xiàn)代優(yōu)化方法提供了技術(shù)支撐?，F(xiàn)代優(yōu)化設(shè)計方法遺傳算法神經(jīng)網(wǎng)絡(luò)拓?fù)鋬?yōu)化蟻群算法模擬退火混沌優(yōu)化禁忌算法常用現(xiàn)代優(yōu)化方法遺傳算法(Genetic Algorithm) 是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型，是自然遺傳學(xué)和計算機(jī)科學(xué)相互結(jié)合與滲透而形成的新的計算方法。 該方法最早是由美國Michigan大學(xué)的Holland教授于1975年提出。生物進(jìn)化遺傳算法基因染色體種群環(huán)境適應(yīng)性進(jìn)化字符字符串解集目標(biāo)函數(shù)值算子關(guān)鍵技術(shù)編碼適應(yīng)度遺傳算子第二節(jié) 遺傳算法遺傳算法的二進(jìn)制編碼過程對設(shè)計變量進(jìn)行離散化處理，得出每一個分量

5、的離散值和離散值個數(shù)：確定每一個設(shè)計變量的編碼長度 (二進(jìn)制位數(shù))：對每一個設(shè)計變量進(jìn)行編碼：將所有設(shè)計變量編碼按順序排列在一起，變形成一個染色體。染色體長度為二進(jìn)制編碼選例在直齒圓柱齒輪減速器優(yōu)化設(shè)計中，設(shè)計變量為： 0 0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 適應(yīng)度函數(shù)的確定遺傳算子選擇(Selection)交叉(Crossover)變異(Mutation)移民(Immigrant)遺傳算子遺傳算法的流程框圖開 始輸入種群數(shù)、交叉概率、變異概率隨機(jī)產(chǎn)生一組初始種群依據(jù)個體的適應(yīng)度，隨機(jī)進(jìn)行選擇依據(jù)交叉概率，隨機(jī)進(jìn)行交叉依據(jù)變異概率，隨機(jī)進(jìn)行變異達(dá)到進(jìn)化代數(shù)NY結(jié) 束確定

6、種群規(guī)模n（一般=40-300) 、交叉概率pc（0.6到1.0之間)、交叉概率pm（0.001到0.01之間) 和迭代代數(shù)，令k=0；隨機(jī)產(chǎn)生的一組初始種群；計算種群中每個解(個體)相應(yīng)的目標(biāo)函數(shù)值(適應(yīng)度)，按每個個體的適應(yīng)度占種群適應(yīng)度的百分?jǐn)?shù)分配選擇率；在所有個體中，選出適應(yīng)度較大的個個體(有些個體是重復(fù)的)，這個過程稱為選擇；在選擇后的種群中，按交叉概率隨機(jī)選取一對個體，進(jìn)行交叉運(yùn)算，產(chǎn)生一對新的個體，重復(fù)該過程；在交叉后的種群中，按變異概率隨機(jī)選取一個個體，進(jìn)行變異運(yùn)算，產(chǎn)生一個新的個體，重復(fù)該過程；K=k+1，若達(dá)到預(yù)定的迭代代數(shù)，則將種群中適應(yīng)度最大的個體作為最優(yōu)解輸出，停止迭

7、代；否則，轉(zhuǎn)(3)。遺傳算法實現(xiàn)遺傳算法收斂判據(jù)達(dá)到規(guī)定迭代的次數(shù);設(shè)定連續(xù)幾次得到的解群中最好的解沒有變化;解群中最好的解的適應(yīng)值與平均值之差占平均適應(yīng)值的百分?jǐn)?shù)小于某一設(shè)定值.遺傳算法理論研究Holland (1975)的模式理論模式：具有部分相同字符的字符串組合如模式： 0*10 表示 0010, 0110Number of instance ofschema s at time tAverage fitness ofindividuals in schema s at time tProbabilityof mutationNumber ofdefined bitsin schema

8、sProbabilityof crossoverDistance betweendefined bits in s選擇算子父輩群體個體編碼個體譯碼適應(yīng)度值10100111001101011101010100111111011011011010011030, 5, 25.7645.711101100001101001111110001001110.19, 4, 21.028, 6, 22.539, 7, 25.027, 3, 24.5735.1545.1724.4656.9父輩群體為選擇算子與運(yùn)算對象，作為選擇池。10100111001101011001010100111011110101010

9、0111111110101010011111111010101001111111010011100110101101001110011010110100111001101011010011100110101子輩群體1個體編碼個體譯碼適應(yīng)度值1010011100110101011011011010011030, 5, 25.7645.711101100001101001101010100111111.19, 4, 21.028, 6, 22.527, 3, 24.527, 3, 24.5735.1545.1724.4735.11101010100111111選擇算子執(zhí)行過程交叉算子執(zhí)行過程011

10、0110101110111隨機(jī)選取一對染色體1110110100101010隨機(jī)選擇交叉位置01101101011101111110110100101010子輩群體1個體編碼1010011100110101111011010010101001101101011101111110111000110000.交換后部基因串子輩群體2個體編碼11101101011101110110110100101010.各種交叉算子1010011100110101隨機(jī)選取一個染色體隨機(jī)選擇變異位置1010011100110101子輩群體2個體編碼11100011001101110101011100111000101

11、0011100110101111000111000101.對基因進(jìn)行變異變異算子執(zhí)行過程子輩群體3個體編碼1010011100110111.第三節(jié) 蟻群算法(Ant colony algorithm)1991年，Mdorigo等人首先開始了對蟻群行為進(jìn)行研究。深入考察了相對弱小，功能并不強(qiáng)大的個體是如何完成復(fù)雜的工作的(如尋找到食物的最佳路徑并返回等)。在此基礎(chǔ)上形成了一種很好的優(yōu)化算法。特別是對于離散規(guī)劃問題更為有效。研究中發(fā)現(xiàn)，螞蟻在行進(jìn)中會沿途留下一種叫信息素的揮發(fā)性物質(zhì)，其他螞蟻能根據(jù)這種物質(zhì)濃度的大小選擇路徑前進(jìn)，并且沿途又留下這種信息素，使這種濃度加強(qiáng)，于是又吸引更多的螞蟻沿此路前

12、進(jìn)。在一段時間后，較短路徑上信息素由于揮發(fā)的少，同時訪問的螞蟻多，使其濃度遠(yuǎn)遠(yuǎn)超過較長路徑上的信息素，此過程持續(xù)進(jìn)行，直到所有螞蟻都選擇最短路徑為止。受此啟發(fā)而提出的ACA，能通過功能相對簡單的人工螞蟻之間的協(xié)作，解決復(fù)雜的問題。1. 概述 基于螞蟻覓食建立最短路徑的機(jī)理，是一種自然算法；具有本質(zhì)并行性。所有螞蟻獨立、無監(jiān)督的同時搜索解空間中許多點而不是一個點，因而能夠快速全局收斂；協(xié)同工作機(jī)制。螞蟻選擇路徑時，根據(jù)以前螞蟻留下的信息素進(jìn)行搜索，能以很大的概率找到優(yōu)化問題的最優(yōu)解；魯棒性。使用概率規(guī)則而不是確定性規(guī)則指導(dǎo)搜索，不必知道其他輔助信息，有極好的魯棒性和廣泛的適應(yīng)性；易于與其他啟發(fā)式

13、算法結(jié)合，以改進(jìn)算法的性能。2. 蟻群算法的特點3. 人工蟻群算法原理螞蟻在尋找食物源時，能在其走過的路徑上釋放一種螞蟻特有的分泌物信息素；螞蟻在運(yùn)動過程中能夠感知信息素的存在及其強(qiáng)度，并以此指導(dǎo)自己的運(yùn)動方向，使螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象；某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大，螞蟻這種選擇路徑的過程被稱之為螞蟻的自催化行為，也可將螞蟻行為理解成所謂的增強(qiáng)型學(xué)習(xí)系統(tǒng)。現(xiàn)以旅行商(Traveling Salesman Problem)問題的求解為例說明蟻群系統(tǒng)模型。4. 人工蟻群系統(tǒng)模型及算法實現(xiàn)TSP

14、: 一個商人欲到n個城市推銷商品，每兩個城市i和j間的距離為dij，如何選擇一條道路，使得商人每個城市走一遍后回到起點，且所走路徑最短。計變量xij : 當(dāng)商人選擇走城市i和j間的距離時xij1； 當(dāng)商人不選擇走城市i和j間的距離時xij0。由城市i出發(fā)1次TSP的數(shù)學(xué)模型：進(jìn)入城市j1次在城市子集中不形成回路m蟻群中螞蟻的數(shù)量;dij兩城市i和j之間距離;bi(t)t時刻位于城市i的螞蟻的個數(shù),m=ni=1 bi(t) ;ij(t)t時刻邊弧(i,j)的軌跡強(qiáng)度(即ij連線上殘留的信息量)，且設(shè)ij(0) =C(C為常數(shù))，i,j=0,1,n-1; ij(t)t時刻邊弧(i,j)的能見度，反

15、映由城市i轉(zhuǎn)移到城市j的期望程度；首先引進(jìn)如下記號:螞蟻k(k=1,2,m)在運(yùn)動過程中根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向。與真實蟻群系統(tǒng)不同，人工蟻群系統(tǒng)具有一定的記憶功能，隨著時間的推移，以前留下的信息逐漸消逝，經(jīng)n個時刻，螞蟻完成一次循環(huán)，各路徑上信息量要作調(diào)整。由此得到下述的人工蟻群系統(tǒng)模型:5. 蟻群算法步驟設(shè)人工蟻群在并行地搜索TSP的解，并通過一種信息素做媒介相互通信，在每個結(jié)點上且和該結(jié)點相連的邊的長度以信息素量做搜索下一結(jié)點的試探依據(jù)，直到找到一個TSP的可行解。在時刻t人工蟻k由位置i 轉(zhuǎn)移至位置j (即從一個結(jié)點轉(zhuǎn)移到下一個結(jié)點)的轉(zhuǎn)移概率為pkij(t)=ij(t)ij

16、(t)sSis(t)is(t),sS0,s S 其中參數(shù)軌跡的相對重要性( 0); 能見度的相對重要性( 0); S可行頂點集，即螞蟻k下一步允許選擇的城市。,分別反映了螞蟻在運(yùn)動過程中所積累的信息及啟發(fā)式因子在螞蟻選擇路徑中所起的不同作用。當(dāng)m個人工蟻按(1)式找到了可行解，則將各邊的信息量用下式修改，即調(diào)整信息量的軌跡強(qiáng)度，更新方程為 ij(t+n)=.ij(t)+ij,(0,1) ij=mk=1kij其中kij第k只螞蟻在本次循環(huán)中留在路徑(i,j)上的信息量;ij本次循環(huán)中路徑ij上的信息量的增量;參數(shù)軌跡的持久性;1-軌跡衰減度,表示信息消逝程度.對上述系統(tǒng)模型,采用人工蟻群方法求解

17、的算法步驟可歸結(jié)為:Step1: NC0(NC為迭代步數(shù)或搜索次數(shù))；各ij和ij的初始化；將m個螞蟻置于n個頂點上；Step2: 將各螞蟻的初始出發(fā)點置于當(dāng)前解集中；對每個螞蟻k(k=1,m)按概率pkij移至下一頂點j；將頂點j置于當(dāng)前解集；Step3: 計算各螞蟻的目標(biāo)函數(shù)值zk(k=1,m)，記錄當(dāng)前的最好解；Step4: 按更新方程修改軌跡強(qiáng)度；Step5: 對各邊弧(i，j)(即路徑ij)，置ij0；NCNC+1.Step6: 若NC預(yù)定的迭代次數(shù)且無退化行為(即找到的都是相同解),則轉(zhuǎn)Step2.6. 蟻群算法框圖 人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Network

18、s)的早期工作可以追溯到1943年McCulloch和 Pitts建立的第一個用于分類的認(rèn)知模型。20世紀(jì)80年代，Hopfield將人工神經(jīng)網(wǎng)絡(luò)成功地應(yīng)用在組合優(yōu)化問題。 人工神經(jīng)網(wǎng)絡(luò)模型是基于生物學(xué)中的神經(jīng)網(wǎng)絡(luò)的基本原理而建立的。生物學(xué)中的神經(jīng)網(wǎng)絡(luò)簡圖如下：第四節(jié) 基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化方法人工神經(jīng)元x1x2xnw1w2wny軸突突觸晶枝內(nèi)核 軸突輸入輸出稱為閾值轉(zhuǎn)移函數(shù)或輸出函數(shù)其中F(x)x01F(x)x011/2常用轉(zhuǎn)移函數(shù)符號函數(shù)S形函數(shù)神經(jīng)網(wǎng)絡(luò)的工作原理神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程：神經(jīng)網(wǎng)絡(luò)工作過程：輸入自變量值神經(jīng)網(wǎng)絡(luò)模型確定權(quán)系數(shù)輸出因變量值輸出因變量值與預(yù)期輸出比較調(diào)整權(quán)系數(shù)輸入自變量值神經(jīng)網(wǎng)絡(luò)模型確定權(quán)系數(shù) 常用網(wǎng)絡(luò)模型 前向網(wǎng)絡(luò) 反饋網(wǎng)絡(luò)層狀結(jié)構(gòu)同層單元間無信息交流信息向前傳遞環(huán)狀結(jié)構(gòu)單元間