數(shù)學建模論文基于改進的遺傳算法的打孔機最優(yōu)作業(yè)方案設計

1、2012“深圳杯”全國大學生數(shù)學建模競賽承 諾 書我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從a/b/c/d中選擇一項填寫）： d 我們的參賽報名號為（如果賽區(qū)設

2、置報名號的話）： 10038 所屬學校（請?zhí)顚懲暾娜?西安交通大學 參賽隊員 (打印并簽名) ：1. 2. 3. 指導教師或指導教師組負責人 (打印并簽名)： 日期： 2012 年 5 月 7 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：2012“深圳杯”全國大學生數(shù)學建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：基于改進的遺傳算法的打孔機最優(yōu)作業(yè)方案設計摘要本文的背景是印刷電路板過孔孔群的加工問題。通過建立單孔模型成功將具

3、有復雜加工要求的電路板加工路徑規(guī)劃問題轉(zhuǎn)化為常見的循環(huán)旅行商問題（）和多旅行商問題（），我們研究了使用單鉆頭加工和多鉆頭加工時的加工路線優(yōu)化問題。我們首先根據(jù)孔的加工要求和孔的類型對所給待加工孔群進行了重新定義，將孔的孔型和所需加工刀具都作為孔的特征，把需要多把刀加工的孔拆分為由孔型和加工刀具共同區(qū)分的多個孔，并使用邏輯值對孔是否已打進行標記，從而對孔進行擴展，使復雜孔群成為只需單一刀具一次加工的孔群，得到了單孔孔群模型。在單孔模型中，鉆頭在孔間的可達與否受加工刀序的控制，這在單孔孔群模型中成為孔間加工的關(guān)聯(lián)問題，可以通過訪問標記進行。單鉆頭對線路板加工時，使用單孔模型后，孔的相異性變得清晰，

4、孔與孔間的關(guān)系我們建立了權(quán)值計算函數(shù)模型，把單孔孔群看成了點間關(guān)聯(lián)的尋找最優(yōu)加工路徑的問題成為具有訪問順序的。對孔擴展后單孔的規(guī)模為，屬于大規(guī)模的最優(yōu)路徑問題單純遺傳算法的搜索效率較低，我們將模擬退火算法與遺傳算法相結(jié)合，并在其選擇的方式上進行了時間節(jié)約化的改進，使計算時間復雜度有所下降，有效提高了最優(yōu)解的求解效率，在計算機上對所有點全部搜索，約為半個小時，表明其有較高的求解效率。多鉆頭打孔時的路徑規(guī)劃成為多旅行商的最優(yōu)旅行線路問題，在對路徑的規(guī)劃上，對了第一問的遺傳算法中的染色體產(chǎn)生形式和適應度函數(shù)進行修改，通過插入虛擬點的方法，使多鉆頭的影響變成單一路徑求解，在相應的限制下找到最好的合作路

5、線。關(guān)鍵字：單孔孔群模型問題遺傳算法模擬退火算法最優(yōu)化1 問題重述現(xiàn)有一類給印刷電路板打過孔的打孔機，現(xiàn)在普遍采用單鉆頭作業(yè)。它的某種鉆頭，上面裝有8種刀具a，b，c， , h，依次排列呈圓環(huán)狀，并且8種刀具的順序固定，不能調(diào)換。不同的刀具加工不同的孔型。作業(yè)時，不同刀具之間的轉(zhuǎn)換（可順時針也可逆時針）需要時間成本；打不同孔時，鉆頭的行進需要行進成本，過孔的打孔時間成本（這是由生產(chǎn)工藝決定，為了簡化問題，這里假定對于同一孔型鉆孔作業(yè)時間都是相同的）決定著打孔機的生產(chǎn)效能。現(xiàn)在提供有10種孔型所需加工刀具及加工次序。為了提高這類打孔機的生產(chǎn)效能，對于某種給定過孔中心坐標和孔型的印刷電路板，對其過

6、孔進行加工前需要對其作業(yè)的線路進行優(yōu)化。問題一中要求在單鉆頭作業(yè)的情況下，根據(jù)提供了某塊印刷線路板過孔中心坐標的數(shù)據(jù)，建立相應的數(shù)學模型，給出單鉆頭作業(yè)的最優(yōu)作業(yè)線路（包括刀具轉(zhuǎn)換方案）、行進時間和作業(yè)成本。問題二中，為提高打孔機效能，現(xiàn)在設計一種雙鉆頭的打孔機（每個鉆頭的形狀與單鉆頭相同），兩鉆頭可以同時作業(yè)，且作業(yè)是獨立的，即可以兩個鉆頭同時進行打孔，也可以一個鉆頭打孔，另一個鉆頭行進或轉(zhuǎn)換刀具。為避免鉆頭間的觸碰和干擾，在過孔加工的任何時刻必須保持兩鉆頭間距不小于3cm（稱為兩鉆頭合作間距）。為使問題簡化，可以將鉆頭看作質(zhì)點。（1）針對問題一中提供的數(shù)據(jù)，建立模型，給出雙鉆頭作業(yè)時的最優(yōu)

7、作業(yè)線路、行進時間和作業(yè)成本，并與傳統(tǒng)單鉆頭打孔機進行比較，其生產(chǎn)效能提高多少？（2）研究打孔機的兩鉆頭合作間距對作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。2 符號說明表一：本文使用的主要符號及說明單孔編號數(shù)組工作時間目標時間適應度函數(shù)名線路板的平面區(qū)域刀具編號集合孔類型集合單孔孔群集合刀具編號孔型編號訪問標記邏輯值孔間行進時間孔間換刀時間打孔鉆頭升降時間打所有孔鉆頭升降時間加工費用函數(shù)名3 基本假設1. 為了使求解問題的方便，模型中假定鉆頭在兩孔之間的行進為直線運動，并且在整個打孔過程中，鉆頭的運動速度是相同的。2. 雙鉆頭打孔時，同一時刻兩鉆頭的合作間距有一定的要求，兩鉆頭的間距與時間有關(guān)系，因此鉆頭

8、的打孔時間忽略不計。4 問題分析 本題要求根據(jù)提供的線路板的過孔的加工中心坐標規(guī)劃出一個優(yōu)化的加工方法，用以提高鉆孔機的生產(chǎn)效能，在第一問中，對于單鉆頭的加工問題，求最優(yōu)加工路線是tsp問題。而在這個問題中，有些類型的過孔需要不同刀具加工，并且有些孔型的加工刀具順序固定，因此這樣的過孔就會被重復經(jīng)過，并且其中幾類重復經(jīng)過的順序是固定的，我們把需重復經(jīng)過的每點拆分為相當?shù)膬H打孔一次的多個點來看，這樣被抽象化擴展的點便可以構(gòu)成一個非靜態(tài)有向圖，把所有的點遍歷一次時的兩點可達與否與已經(jīng)經(jīng)過了的點相關(guān)聯(lián)，因此我們定義點類時，添加了標記函數(shù)，用以了解幾何上的此點是否已經(jīng)過。遍歷路徑總長由遍歷時動態(tài)函數(shù)

9、(為一個點的排列序)計算，作為路徑的總長，將在可行解的搜索中作為選擇算子的參數(shù)。對于第一問的求解，由于所給的數(shù)據(jù)量較大，進行擴展后變得更大，要找出最優(yōu)的加工路線，并計算出所用的加工費用，是np-hard問題，為了在允許的時間內(nèi)找出最優(yōu)解，考慮使用改進后的遺傳算法-模擬退火算法與遺傳算法結(jié)合的現(xiàn)代優(yōu)化算法，以使收斂速度更快，在算法中的適應度函數(shù)需要動態(tài)計算。 5 模型的建立與求解5.1 數(shù)據(jù)點的模型5.1.1擴展單孔模型問題中的電路板過孔分為a到j10種不同的類型，共有2124個孔，并且其中的c，d，e，f，g，i,j類孔都需要多種不同的刀具進行加工，這幾類點中，除了d，f類，其他類的點都需要固

10、定的刀具加工順序，因此我們將需要用不同的幾種刀具加工的孔按不同刀具擴展成不同的新類型如下圖：acac進行如上擴展后孔的規(guī)模變大，產(chǎn)生了新的不同的孔群結(jié)構(gòu)，這樣的新類孔被認為是只需單刀加工的孔。對于附件孔中心的幾何位置點數(shù)據(jù)，需要進行擴展處理，并用枚舉型對刀具（到）進行編號（1到8），對孔進行的重新分類后的結(jié)果如下刀號編號點類a1a cb2b c3c e i jd4d ge5d if6e g jg7f gh8h 被擴展后的點有18類，在這18類孔中，幾何位置相同的孔有相同的位置坐標，而屬于不同的孔類型，因此需要重新對孔的數(shù)據(jù)結(jié)構(gòu)進行定義，然后對孔進行編號，對擴展后的孔進行重新定義時。按照以下規(guī)則

11、進行：1） 使用了孔型和加工刀具兩重特征將孔分類，本題中的電路板過孔孔型有10類，加工刀具有8種類型；2） 對于孔型相同的孔，單個孔的需要用孔中心位置坐標加以區(qū)別；3） 本題中有幾類過孔需要用不同的刀具并以一定的刀具使用順序重復加工，擴展后的的點在需要按照以下邏輯關(guān)系對孔的加工順序進行限制只有孔的加工刀序是正確的，鉆頭才可移動到下一孔。定義1：僅使用一把刀就可加工完成的孔稱為單孔。線路板的區(qū)域為不同刀具的枚舉編號集合為不同孔型的編號集合為 對于每個點需要有訪問標記量對點是否已被訪問進行標記，初始狀態(tài)下，所有的點置為，被訪問之后置為。此時定義的新的孔群為在本題中經(jīng)擴展后的孔群規(guī)模為=2814。此

12、孔群中的每一孔都只需一種刀具加工一次就可加工完成，因此此孔群是一個單孔孔群。5.1.2單孔間移動時間計算 打孔機在打孔時，打孔的效能受打孔的鉆頭在兩孔和（和為單孔的編號）間的行進時間，兩孔間的換刀時間和打孔鉆頭的升降時間的影響，在行進過程中，為使問題簡化，鉆頭在兩孔間的行進為直線運動，并且行進的速度是恒定的，于是鉆頭上的刀具排布如下圖所示換刀時，可以順時針轉(zhuǎn)動換刀，也可逆時針換刀，設定相鄰刀具轉(zhuǎn)化的時間為恒定的，于是打孔機的升降時間由生產(chǎn)工藝所決定，打所有孔的鉆頭升降時間在打孔時鉆頭的行進與換刀可以同時進行，因此兩單孔間的鉆頭工作時間為對于一條給定的路徑，鉆頭總的工作時間為在工藝條件不變時，打

13、孔鉆頭升降總時間是固定的。因此打孔機的效能由工作時間決定，尋求最優(yōu)路徑滿足目標即為求使工作時間取最小值，目標函數(shù)為的路徑。設置動態(tài)函數(shù)表示加工過程中的行進或換刀時間，以此作為評價加工路線優(yōu)劣的標準。設加工費用函數(shù)為則為鉆頭的單位距離行進成本，為換刀的單位時間成本。我們把孔群單孔作為一個圖的節(jié)點，兩點之間的工作時間作為點與點之間的邊，即權(quán)重函數(shù)，因此此單孔群及其孔間關(guān)系可表示為一個圖，圖的含義為：為圖的邊的權(quán)重的集合即兩單孔間的工作時間，為圖的節(jié)點集合即孔的集合， 。由于兩單孔之間是否可達不能預先確定，此圖并不是一個靜態(tài)的完全有向圖，單純靜態(tài)圖的鄰接矩陣是確定的，在對圖進行使用時可以認為是圖的常

14、量參數(shù)，在圖中尋找最短h路（或h圈）時對路徑總權(quán)重的計算是在路徑尋找完成之后直接調(diào)用常量參數(shù)計算。本文中所要討論的孔群相關(guān)圖的點是有順序訪問關(guān)聯(lián)的，因此需要對孔群中的點間權(quán)重計算進行改進，改進的時候。5.1.3 改進的單孔間時間成本計算模型經(jīng)擴展后的單孔孔群不能用一個靜態(tài)的完全有向圖來表達，它的鄰接矩陣是動態(tài)的，每一個點的序列都對應有不同的鄰接矩陣。因此鄰接矩陣需要動態(tài)定義。對于節(jié)點的集合 有點，從（作為單孔的標號）接著訪問的下一,此點的幾何位置，特征區(qū)分量,（下面僅以特征區(qū)分量來區(qū)分幾何位置相同的不同點）需要不同的刀打孔，設打孔的刀具順序為，若，則從到是可達的，從到的權(quán)重為，若，此時需要了解

15、的另一點，若，從到的權(quán)重為，否則置為，需要更多種刀具加工的孔的用相同的方法可以得出相應權(quán)重計算函數(shù)。這樣來計算兩個孔之間的時間成本對點的操作是靜態(tài)的，兩點之間是否可達的信息全部包含在點的自身屬性中。在這個圖中找一條最優(yōu)路為一個（traveling salesman problem）問題，需要對圖中的點進行遍歷尋求最優(yōu)解，這與問題一所要求的最優(yōu)加工路線有相同的目標函數(shù)。因此題目一中的問題是一個tsp問題，我們對單孔孔群中的2084個孔依次進行編號為1,2，2814，則第一問的問題是求鉆頭從某一孔出發(fā)，打完所有的孔的一條加工路徑使得加工時間最短，第二問的求兩條加工路徑，使得兩個鉆頭利用兩條加工路徑

16、將所有的點加工完的時間最短。5.2 單鉆頭打孔的tsp模型5.2.1傳統(tǒng)線路板孔群加工tsp模型表示一個線路板的過孔孔群，其中表示孔的集合，（為孔之間的權(quán)值）表示孔與孔之間的權(quán)重集合，其與孔群建構(gòu)的圖的鄰接矩陣相對應。模型中，為從孔到孔有向邊權(quán)重，它的值在未進行遍歷之前是完全確定的。對于孔的數(shù)量不大時，使用中的模擬退火算法可以較快的找到最優(yōu)解（或準最優(yōu)解），數(shù)據(jù)量適中時可以使用中的遺傳算法進行全局搜索找到比較滿意的解，對于含有多次不同刀有固定順序打同一幾何位置的孔的線路板，兩點之間是否可達與已經(jīng)訪問過的點有關(guān)，計算兩點之間的權(quán)重時必須受制與已經(jīng)訪問了的點。5.2.3 改進的模擬退火算法與遺傳算

17、法結(jié)合的tsp求解模型模擬退火算法和遺傳算法都是能解決圖中最優(yōu)h路（或h圈的）的現(xiàn)代優(yōu)化算法（tsp求解問題），他們各有優(yōu)缺點，先對他們的算法思想描述如下：（1）模擬退火算法模擬退火算法來源于材料的統(tǒng)計力學的研究成果。對于解決一個尋求最小值的優(yōu)化問題，為了使對可行解的搜索不致陷入局部最優(yōu)的情況，需要使搜索具有概率性，將物理學中的模擬退火的思想運用在最優(yōu)過程中，就使新解的接受具有了概率性，這樣就可避免局部收斂的情況，使搜索具有全局能力。給定優(yōu)化函數(shù)，其中，它表示優(yōu)化問題的一個可行解，表示函數(shù)的定義域。表示的一個鄰域集合，即下一個解的存在集合。 首先給定一個初始溫度和一個可行初始解，并由生成下一個

18、解，是否接受該解的概率表示如下：也就是說，如果生成的解的函數(shù)值比前一解的函數(shù)值小，則接受作為下一解，否則以概率 接受 作為新解。 依次進行，對于某一溫度和該優(yōu)化問題的一個解，可以生成。接受作為下一個新解的概率為：這樣在一定溫度下依次轉(zhuǎn)移尋求最優(yōu)解，然后降低溫度在次尋找最優(yōu)解。在每個下，所得的新解依賴于前一解，和前面的0到k-1個可行解無關(guān)，因此是一個馬兒可夫過程。使用馬爾可夫過程對模擬退火過程進行分析，可知當溫度下降的足夠緩慢時，則全局最優(yōu)解將以概率為1被找到。模擬退火算法在解決小規(guī)模的tsp問題，可由單一初始解逐步進行模擬退火轉(zhuǎn)移得到最優(yōu)解。本文中，所要考察的線路板過孔的擴展單孔規(guī)模有近30

19、00個，使用模擬退火算法解決時必然會出現(xiàn)局部收斂的問題，并且計算量也相當龐大。 （2）遺傳算法遺傳算法是一種基于自然選擇原理和自然遺傳機制的搜索尋優(yōu)算法，它模擬自然界中的生物進化過程，運用于人工系統(tǒng)實行特定目標的優(yōu)化，遺傳算法的實質(zhì)是通過對群體的搜索技術(shù)，根據(jù)適者生存的原則進行逐代優(yōu)化，最后得到最優(yōu)解或準最優(yōu)解，它的實現(xiàn)需要做以下工作：產(chǎn)生初始種群；求每一個體的適應度；根據(jù)適應度依照適者生存的原則選擇優(yōu)良個體；選擇出的優(yōu)良個體進行兩兩雜交，按一定概率兩兩隨機交叉其染色體和一定概率變異某些染色體后產(chǎn)生下一代群體，以此方法使群體逐代優(yōu)化，直到滿足進化的終止條件，它的具體實現(xiàn)方法如下：根據(jù)具體問題確

20、定求解的可行解域，確定一種編碼具體問題的染色體方法，使問題的解可用編碼表示。：尋找一個非負的適應度函數(shù)作為度量解的好壞的依據(jù)。：確定進化的群體規(guī)模，交叉概率，變異概率和進化終止條件。為方便計算，通常將每一代的群體規(guī)模m設為相同，群體的規(guī)模越大，找到全局最優(yōu)解的概率就越大，然而由于計算機的運算能力有限，群體規(guī)模的增大會使運算的時間增加。遺傳算法對于解決規(guī)模較大的搜索求最優(yōu)問題能夠綜合考慮全局，使每一代種群都分布的均勻，但到了搜索后期，由于種群中個體的差異性減小，使它的搜索效率會變得比較低，收斂速度降低；同時，遺傳算算法在對可行解的接受上不具有概率性，容易造成搜索的早熟。模擬退后算法的全局搜索能力

21、較弱，容易陷入局部最優(yōu)的狀況，而在個體的在個體差異較小時模擬退火算法具有較高的搜索效率，因此可以將兩個算法相結(jié)合，各取其長，使搜索時即考慮全局性又可加快收斂速度，使遺傳算法具有更好的爬山能力，因此我們結(jié)合了這兩種算法的優(yōu)點，采用下面所描述的模擬退火算法與遺傳算法相結(jié)合的算法來對單鉆頭加工單孔的加工作業(yè)路徑進行合理搜索，在全局范圍內(nèi)找到滿意解。（3）模擬退火與遺傳算法的結(jié)合算法結(jié)合前面的對模擬退火算法和遺傳算法的描述，通過改變遺傳算法中的選擇算子的選擇操作，使其對種群的選擇優(yōu)化過程按照模擬退火算法思想進行，使可行解能以較大概率向最優(yōu)解收斂。具體按如下步驟實現(xiàn)：（a） 遺傳算法的；（b） 遺傳算法

22、的；（c） 隨機產(chǎn)生一個在可行解域內(nèi)的規(guī)模為m的初始種群；（d） 對初始種群中的每一個體使用模擬退后算法進行優(yōu)化，得到第一批優(yōu)良的父代a；（e） 使用隨機交叉和變異的方法由父代a各產(chǎn)生一批子代b和子代c；（f） 根據(jù)適應度函數(shù)，從子代和父代中選擇適應度最好的m個個體作為下一個父代；（g） 判斷進化終止條件是否滿足，不滿足則循環(huán)執(zhí)行步驟（d）到（g）直至滿足循環(huán)終止條件。用以上算法對全部的單孔遍歷路徑進行搜索可以較快收斂速度找到全局最優(yōu)解或準最優(yōu)解。5.3 雙鉆頭打孔組合模型的建立5.3.1 第二問的分析在現(xiàn)有工藝條件下，現(xiàn)代計算方法的不斷改進和智能算法的引進對單鉆頭的加工路徑的優(yōu)化提高了生產(chǎn)的

23、效率，而加工時打孔的時間由于受生產(chǎn)工藝的限制并沒有縮短，引入雙鉆頭后，使用雙鉆頭同時加工同一孔群的孔時，通過合理優(yōu)化加工路線，在完成相同加工任務時，所用時間會減少很多?；谇懊娴谝粏柕那蠼夂蛦慰啄Ｐ偷慕Y(jié)構(gòu)特征，通過對單鉆頭的染色體表達和適應度函數(shù)計算的修改，對雙鉆頭的路徑進行約束限制，也可將第二問的雙鉆頭加工路徑問題轉(zhuǎn)化為多旅行商的mtsp問題。5.3.2 約束限制關(guān)系雙鉆頭進行打孔操作時，兩鉆頭從各自的對刀點同步出發(fā)，打完一塊電路板的所有單孔后鉆頭按照一定的路線回到各自的對刀點，在此過程中完成已加工電路板的取走與待加工電路板的放置。在單孔模型的基礎上，兩鉆頭合作間距需要滿足一定距離限制即在雙

24、鉆頭相互獨立加工的任何時刻，其間距離有一下限以防止相互碰撞。雙鉆頭在加工點的次序上還要滿足在加工有加工刀序時需要滿足時間上的限制如果加工一個需兩種刀型加工點時兩刀要在加工時間上要滿足先后次序。而此時在抽象圖中兩頂點之間的權(quán)重將會隨兩刀加工次序的影響，因此該圖部分頂點的權(quán)重本身受到遍歷該圖頂點的次序的影響。5.3.3在第一問的改進基礎用模擬退火法求解mtsp問題在第一問的啟發(fā)下，雙鉆頭加工路徑可以合并為一條路徑,將兩條路徑合為一條路徑則該路徑順序就對應遺傳退火算法中的一個個體，該個體的適應度為合并雙路徑前路徑長度中較大者。在進行路徑計算時需要動態(tài)計算路徑的長度，雙鉆頭各自路徑長度需要混合交叉計算

25、。該mtsp問題要滿足多個限制條件，無法建立靜態(tài)的權(quán)重鄰接矩陣，導致無法像常規(guī)的mtsp問題那樣直接運用模擬退火算法求解，由此我們建立了動態(tài)權(quán)重計算函數(shù)可以再路徑的生成過程中計算任一條路徑的總權(quán)重。我們在最后選擇階段將通過任意一條路徑的時間函數(shù)判斷兩鉆頭在同一時刻是否滿足距離約束條件 5.4 模型的求解5.4.1 單鉆頭打孔的最優(yōu)路線求解使用單鉆頭tsp問題模型尋找最優(yōu)加工路線，問題中要求通過合理的優(yōu)化找到能使打孔機生產(chǎn)效能提高的孔群加工路徑，我們以加工時間最少作為優(yōu)化的目標函數(shù)。對問題一中所給的孔擴展后的單孔規(guī)模為n=2814，于是對模型中的參數(shù)作如下設定：種群大小最大進化代數(shù),退火初始溫度

26、初始溫度設定與降溫關(guān)系，需要根據(jù)單孔加工的動態(tài)函數(shù)確定，以此作為對路徑變化的敏感度量。降溫關(guān)系交叉概率=1，可以保證種群充分的進化變異概率=0.2，種群的變異概率較?。?）用十進制對染色體進行編碼。用隨機數(shù)列,01（）作為染色體，每一染色體都和種群中的一個個體相對應，編碼的位置代表單孔，編碼的數(shù)值代表單孔的加工順序，即按升序排列時按編碼的大小順序打孔，編碼按數(shù)值大小順序排列的孔序用數(shù)組 保存，例如對于有4個孔的染色體編碼為，則孔的加工順序為（2）第一批優(yōu)良父代的產(chǎn)生用。根據(jù)（1）的方法隨機產(chǎn)生規(guī)模為2000的初始種群，用模擬退火算法對每一個個體進行局部優(yōu)化，例如對一個個體 ， ，其路徑的目標函

27、數(shù)值為，交換與之間的順序，得到新路徑為：，在這里，我們進行了的搜索的節(jié)約改進，對此路徑的目標函數(shù)的計算時，一旦出現(xiàn)兩孔間不可達的狀況時對此路目標函數(shù)的計算立即終止，否則路徑的目標函數(shù)為為計，若，則用新的路徑替代舊的路徑，否則隨機產(chǎn)生一個0,1之間的隨機數(shù)，若，就用新路徑替代舊路徑，即以概率接受下一個可行解，從式可以知道，越小，新路徑被接受的概率就越大，溫度影響子代的更新率，溫度越低，子代就越容易更新，對這2000個初始種群都進行如上操作，就獲得一個優(yōu)良的后代種群。（3） 交叉變異產(chǎn)生子代。我們用單點交叉和三點變異方法分別產(chǎn)生子代b和c我們是這樣設計的：1）交叉操作：對于選取的兩個父代染色體和，

28、由交叉概率我們隨機選取第（）個基因處為交叉點，經(jīng)交叉后的產(chǎn)生兩子代染色體和，由的前個基因和的后2814-個基因組成，由的前個基因和的后2814-個基因組成，即，由此對應兩個新的打孔順序，利用單點交叉的方法產(chǎn)生子代的速度較快并且當基因數(shù)量較大時，由此產(chǎn)生的新染色體仍是豐富的，本文中所研究的孔的數(shù)量較大，用此交叉方法產(chǎn)生子代更利于收斂加快；2）變異操作：對于選定的一個父代染色體，隨機的取三個數(shù)，滿足,把之間的基因段插入到的后面，由此產(chǎn)生新的變異個體，對于單孔的遍歷路徑由此得到變化，根據(jù)新路徑的目標函數(shù)值決定新路徑的取舍，優(yōu)化得到下一批父代。（4）從步驟（3）中產(chǎn)生的子代和步驟（2）中的父代總種群，的規(guī)模為中得到新的一批父代。每一批的父代的數(shù)據(jù)規(guī)模都為2000，規(guī)模比較大，變異產(chǎn)生的數(shù)據(jù)量同樣很龐大，使用確定的篩選方法對進行篩選，本文中的求解目標為找到使目標函數(shù)值最小或準最小的路徑，由于孔的規(guī)模較大，我們采用輪盤賭的方式對個體進行篩選，此時的適應度函數(shù)這樣定義適應度函數(shù)值就是