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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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