貪心算法遺傳算法流程圖遺傳算法實質(zhì)是通過種群搜索技術(shù)課件

打孔機生產(chǎn)效能的提高隊員：李倫

王旭查姍指導(dǎo)教師：屠良平學(xué)校：遼寧科技大學(xué)打孔機生產(chǎn)效能的提高隊員：李倫王旭查姍指導(dǎo)教1問題提出2問題分析3模型假設(shè)4模型的建立與求解5模型評價及改進(jìn)目錄目錄問題關(guān)鍵印刷線路板過孔加工費用占制版費用30%到40%，打孔機主要用于線路板打孔作業(yè)，提高打孔機生產(chǎn)效能可以降低制版費用，時間。

鉆頭上安有八種刀具，有些過孔需要多個工序且有次序要求。分別給出單鉆頭和雙鉆頭最優(yōu)加工作業(yè)線路，時間，成本，研究雙鉆頭合作間距對加工路線和效率影響問題重述問題關(guān)鍵印刷線路板過孔加工費用占制版費用30%到40%，打孔某些孔需多把刀具加工；某些孔加工時刀具有次序限制；鉆頭上有八把刀具，可順逆旋轉(zhuǎn)；共十種孔型，但孔數(shù)量大；不僅要研究單鉆頭打孔，還要研究雙鉆頭打孔；綜上分析可知：這道題與TSP問題類似，但不同之處是某些孔需多把刀具加工且加工有次序限制。因此我們要想辦法把本題轉(zhuǎn)化為TSP問題求解。問題分析問題特點某些孔需多把刀具加工；問題分析問題特點本文框架雙鉆頭單鉆頭最優(yōu)路徑最優(yōu)路徑、換刀方案換刀方案單鉆頭最優(yōu)路徑開始雙刀最優(yōu)路徑、換刀方案雙刀換刀方案雙鉆頭最優(yōu)路徑方案二方案三遺傳算法結(jié)合貪心算法分塊方案二方案二貪心算法貪心算法最優(yōu)路徑遺傳算法結(jié)合貪心算法聚類分塊分析合作間距影響結(jié)束對比分析生產(chǎn)效能對比對比成本矩陣方案一蟻群算法流程圖：成本矩陣蟻群算法方案一本文框架雙鉆頭單鉆頭最優(yōu)路徑最優(yōu)路徑、換刀方案單鉆頭最優(yōu)路徑不考慮單個過孔鉆孔作業(yè)成本。不考慮單個過孔鉆孔作業(yè)時間。鉆頭無損耗，不損壞。鉆頭移動速度恒定。鉆頭視為質(zhì)點。模型假設(shè)不考慮單個過孔鉆孔作業(yè)成本。模型假設(shè)孔型ABCDEFGHIJ所需刀具aba,cd,e*c,fg,h*d,g,fhe,cf,c已知線路板上各類孔型如表所示：我們對題目中所給的原始數(shù)據(jù)進(jìn)行處理，對需要多種刀具的孔型進(jìn)行拆分，把需多孔型的一點拆分成只需一刀具的多個孔，拆分成的多個孔的坐標(biāo)相同，但所需刀具不一樣，這樣一旦確定了一種加工次序，就把換刀方案確定了。模型建立與求解過孔轉(zhuǎn)換孔型ABCDEFGHIJ所需刀具aba,cd,e*c,上述10種孔型可轉(zhuǎn)化為：處理后孔的數(shù)量由2124個變?yōu)?814個單孔，分別對2814個孔坐標(biāo)進(jìn)行編號，即每一個孔都對應(yīng)一個確切編號，坐標(biāo)和所需刀具，這樣的話，我們轉(zhuǎn)換成TSP問題進(jìn)行求解。模型建立與求解轉(zhuǎn)換后的孔型上述10種孔型可轉(zhuǎn)化為：處理后孔的數(shù)量由2124個變?yōu)?81對刀具進(jìn)行編號，1—8每個空為三維坐標(biāo)，前兩維是位置，第三維是刀具編號。模型建立與求解孔型三維坐標(biāo)對刀具進(jìn)行編號，1—8每個空為三維坐標(biāo)，前兩維是位置，第三維總加工花費從i孔到j(luò)孔換刀次數(shù)總加工時間模型建立與求解符號約定、公式刀具編號：1，2，3……8總加工花費從i孔到j(luò)孔換刀次數(shù)總加工時間模型建立與求解符號約目標(biāo)函數(shù)模型建立與求解問題一：其中：（f:總成本，H：換刀成本，L：行進(jìn)成本，Xt：行進(jìn)時間，Ht:換刀時間。）目標(biāo)函數(shù)模型建立與求解問題一：其中：（f:總成本，H：換刀成目標(biāo)函數(shù)模型建立與求解問題二：其中：（f1：鉆頭一成本，f2：鉆頭二成本，T1

：鉆頭一時間，T2:鉆頭二時間。）目標(biāo)函數(shù)模型建立與求解問題二：其中：（f1：鉆頭一成本，f2模型建立與求解問題一：1.蟻群算法：隨著時間的推進(jìn)，路徑上累積的信息素濃度逐漸增高，選擇該路徑的螞蟻個數(shù)也愈來愈多。最終，整個螞蟻會在正反饋的作用下集中到最佳的路徑上，此時的便是待優(yōu)化問題的最佳解。模型建立與求解問題一：1.蟻群算法：隨著時間的推進(jìn)，路徑上累模型建立與求解問題一：1.蟻群算法(一)、將三維坐標(biāo)形成成本矩陣，即孔孔之間的刀具轉(zhuǎn)換成本和行進(jìn)成本之和。(二)、采用蟻群算法進(jìn)行計算。模型建立與求解問題一：1.蟻群算法(一)、將三維坐標(biāo)形成成本模型建立與求解問題一：1.蟻群算法初始化隨機放置螞蟻以每一只螞蟻所在孔，作為起始城市選擇選下一個城市返回到初始城市還有可選城市？更新信息素矩陣，即更新每路徑上的信息素的量滿足停止條件？輸出最好的路徑Y(jié)esNoNo模型建立與求解問題一：1.蟻群算法初始化隨機放置螞蟻以每一只模型建立與求解問題一：1.蟻群算法成本：1197.2元時間：1382.2秒模型建立與求解問題一：1.蟻群算法成本：1197.2元模型建立與求解問題一：2.貪心算法(一)、換刀方案：d,e,f,g,h,a,b,c,f(二)、換刀時間：180秒(三)、權(quán)值：距離模型建立與求解問題一：2.貪心算法(一)、換刀方案：d,e,模型建立與求解問題一：2.貪心算法算法流程圖模型建立與求解問題一：2.貪心算法算法流程圖模型建立與求解問題一：2.貪心算法作業(yè)時間：267.68秒成本：932.19元d刀具加工圖(單位：mil)模型建立與求解問題一：2.貪心算法作業(yè)時間：267.68秒d模型建立與求解問題一：2.貪心算法537(465)->522->525->518->514->510->506->503->507->511->515->516->512->508->504->523->528->531->533->536->524->517->513->509->505->520->521->527->530->532->535->534->529->526->519->498->492->497->485->486->487->493->500->499->488->489->494->502->501->490->484->491->496->495->483->換h刀具g刀具走刀路線：模型建立與求解問題一：2.貪心算法537(465)->522模型建立與求解問題一：2.貪心算法權(quán)重系數(shù)cst10.90.80.70.60.50.40.30.20.10csf00.10.20.30.40.50.60.70.80.91費用(元)965.12965.12965.12965.12965.12965.12965.12956.38960.48932.27944.27時間(秒)2142142142142142142143203734951084最終選擇cst=0.6,csf=0.4計算出總費用為965.12元，加工時間為214秒模型建立與求解問題一：2.貪心算法權(quán)重系數(shù)cst10.90.模型建立與求解問題一：2.貪心算法模型建立與求解問題一：2.貪心算法遺傳算法流程圖遺傳算法實質(zhì)是通過種群搜索技術(shù)，根據(jù)適者生存原則逐代進(jìn)化，最終得到最優(yōu)解或準(zhǔn)最優(yōu)解。采用“改良圈”算法得到優(yōu)良父代開始對父代進(jìn)行交叉，變異，形成新種群計算種群中個體的適應(yīng)度值，并選擇優(yōu)良子代1滿足遺傳代輸出結(jié)果結(jié)束1模型建立與求解問題一：3.遺傳結(jié)合貪心算法遺傳算法流程圖遺傳算法實質(zhì)是通過種群搜索技術(shù)，根據(jù)適者生存原改良圈算法：（以m=233）為例改良圈算法是一種經(jīng)典的近似算法，用于優(yōu)化遺傳算法的初始種群，令i=1，第一步：隨機生成初始圈（初始解）：第二步：交換u，v之間的順序，則得到新路徑：C=C’=uvvu?模型建立與求解問題一：3.遺傳結(jié)合貪心算法改良圈算法：（以m=233）為例改良圈算法是一種經(jīng)典的近似算改良圈算法：評判標(biāo)準(zhǔn)為兩次相鄰路徑的差值：若f<0,則以新路徑替換舊路徑，直到不能修改為止。第三步：令i=i+1，若i=POP（種群規(guī)模）,算法結(jié)束，否則轉(zhuǎn)向第一步C=C’=uvvu模型建立與求解問題一：3.遺傳結(jié)合貪心算法改良圈算法：評判標(biāo)準(zhǔn)為兩次相鄰路徑的差值：若f<0,則以新遺傳算法的實現(xiàn)：編碼策略采用十進(jìn)制編碼，用隨機數(shù)列作為染色體(個體)，其中為避免在交叉后產(chǎn)生的染色體出現(xiàn)重復(fù)的基因（孔編號），限定

2331模型建立與求解問題一：3.遺傳結(jié)合貪心算法遺傳算法的實現(xiàn)：編碼策略采用十進(jìn)制編碼，用隨機數(shù)列作為染色體遺傳算法的實現(xiàn)：（2）種群初始化：

本文利用改良圈算法得到一個規(guī)模為50的種群。（3）交叉

根據(jù)孔數(shù)的規(guī)模，本文采用單點交叉方案，取交叉概率pc=1。先從種群中隨機選取兩個父代（兩個初始解）Ω1和Ω2：用Logistic混沌序列產(chǎn)生一個2到232之間的正整數(shù)，例如得到隨機數(shù)21，則對相應(yīng)基因進(jìn)行交叉得到新染色體。23312331模型建立與求解問題一：3.遺傳結(jié)合貪心算法遺傳算法的實現(xiàn)：（2）種群初始化：用Logistic混沌序遺傳算法的實現(xiàn)：(4)變異是實現(xiàn)群體多樣性的一種手段，是跳出局部最優(yōu)，全局尋優(yōu)的重要保證。本模型中具體變異算子設(shè)計如下，首先根據(jù)給定的變異率(本模型選為0.02)，隨機地取兩個在2到232之間的整數(shù)，對這兩個數(shù)對應(yīng)位置的基因進(jìn)行變異，具體變異以當(dāng)前的基因值為初值利用Logistic混沌序列進(jìn)行適當(dāng)次數(shù)的迭代，得到變異后新的基因值，從而得到新的染色體。模型建立與求解問題一：3.遺傳結(jié)合貪心算法遺傳算法的實現(xiàn)：(4)變異模型建立與求解問題一：3.遺傳結(jié)合遺傳算法的實現(xiàn)：（5）選擇

本文選取目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，選擇上述所有個體中適應(yīng)度函數(shù)最小的50個個體作為下一代個體。采用圓盤賭法：

計算適應(yīng)度函數(shù)值Fitness模型建立與求解問題一：3.遺傳結(jié)合貪心算法遺傳算法的實現(xiàn)：（5）選擇采用圓盤賭法：模型建立與求解問題一

模型建立與求解問題一：3.遺傳結(jié)合貪心算法(一)、換刀方案：d.c.b.a.b.g.f.e.d.c(二)、換刀時間：162秒(三)、權(quán)值：距離模型建立與求解問題一：3.遺傳結(jié)合貪心算法(一)、換刀方（1）用遺傳算法進(jìn)行計算。（2）采用貪心算法進(jìn)行搜索。模型建立與求解問題一：3.遺傳結(jié)合貪心算法成本： 892.97元；時間： 242.9s（1）用遺傳算法進(jìn)行計算。模型建立與求解問題一：3.遺傳結(jié)合換刀路徑圖打孔路徑圖模型建立與求解問題一：3.遺傳結(jié)合貪心算法換刀路徑圖打孔路徑圖模型建立與求解問題一：3.遺傳結(jié)合貪心算成本：892.97元；時間：242.9s成本：1197.2元，時間為1382.2秒蟻群算法：貪心算法：成本：932.19元；成本：267.6754秒遺傳結(jié)合貪心算法：模型建立與求解問題一：結(jié)論：成本：892.97元；時間：242.9s成本：1197.2元模型建立與求解問題二：鉆頭一：642.3秒

成本：450.83元鉆頭二：1021.5秒

成本：738.32元1.蟻群算法總成本：1189.2元時間：1021.5秒模型建立與求解問題二：鉆頭一：642.3秒 成本：45模型建立與求解問題二：2.貪心算法

鉆頭一鉆頭二，d刀具的加工圖模型建立與求解問題二：2.貪心算法

鉆頭一鉆頭二，d刀具模型建立與求解問題二：鉆頭一：

總時間：213.909秒，總花費：360.66元 (其中換刀時間為：180秒,行進(jìn)時間：33.91秒)鉆頭二：

總時間：234.28秒，總花費：577.26元 (其中換刀時間為：180秒，行進(jìn)時間：54.28秒)則雙鉆頭：

總時間：234.28秒

總花費：937.92元2.貪心算法模型建立與求解問題二：鉆頭一：2.貪心算法模型建立與求解問題二：2.貪心算法

鉆頭二966(a)967(a)968(a)1974(b)2411(c)2412(c)2413(c)2414(c)2728(f)鉆頭一坐標(biāo)

962(a)1751.16671691981158.111751.16671691988084.018084.01963(a)1701.16666691481108.121701.16666691488034.018034.01964(a)533.1445498798060.8276533.1445498798068666866965(a)1466.86349859802060.021466.86349859804866.014866.012409(c)1751.16671691981158.111751.16671691988084.018084.012410(c)1701.16666691481108.121701.16666691488034.018034.01可能沖突的點形成的距離矩陣（以x=-50000mil劃分）模型建立與求解問題二：2.貪心算法鉆頭二966(a)96模型建立與求解問題二：2.貪心算法合作間距1cm2cm3cm3.5cm4cm4.5cm5cm總加工費用(元)1257.51248.231248.231248.231248.221248.221248.22加工時間（秒）256255255255255255255

雙鉆頭和鉆間距與加工費用和時間的關(guān)系模型建立與求解問題二：2.貪心算法合作1cm2cm3cm3.模型建立與求解問題二：2.貪心算法

x:是合作間距y:是加工費用合作間距函數(shù)：x:是合作間距

y:是加工時間費用函數(shù)：模型建立與求解問題二：2.貪心算法x:是合作間距y:是加鉆頭同時工作時的生產(chǎn)效能，提出以下兩種分配方案：首先采用K-means聚類分析方法，以合作間距為依據(jù)將所有孔分為兩大類，采用遺傳結(jié)合貪心算法對兩大類分別計算得到最優(yōu)路徑。第一類初始類中心為：（-325400,554800）第二類初始類中心為：（88800,919800）模型建立與求解問題二：聚類分析3.遺傳結(jié)合貪心算法鉆頭同時工作時的生產(chǎn)效能，提出以下兩種分配方案：模型建立與求模型建立與求解問題二：3.遺傳結(jié)合貪心算法聚類結(jié)果：模型建立與求解問題二：3.遺傳結(jié)合貪心算法聚類結(jié)果：雙鉆頭打孔算法流程圖開始聚類為兩類輸出下一起點結(jié)束按方案三，對兩類分別計算模型建立與求解問題二：3.遺傳結(jié)合貪心算法雙鉆頭打孔算法流程圖開始聚類為兩類輸出下一起點結(jié)束按方案三，其中第一個鉆頭路徑圖模型建立與求解