數(shù)學建模優(yōu)秀論文

1、<p><b>　　問題重述</b></p><p>　　過孔是印刷線路板（也稱為印刷電路板）的重要組成部分之一，打孔機主要用于在制造印刷線路板流程中的打孔作業(yè)。目前，實際采用的打孔機普遍是單鉆頭作業(yè)，即一個鉆頭進行打孔。本問題旨在解決某類打孔機的生產(chǎn)效能問題。</p><p>　　打孔機的生產(chǎn)效能主要取決于：（1）單個過孔的鉆孔作業(yè)時間，由生產(chǎn)工藝決定；（

2、2）打孔機加工作業(yè)時，鉆頭的行進時間；（3）針對不同孔型加工作業(yè)時，刀具的轉(zhuǎn)換時間。</p><p>　　某種鉆頭裝有8種刀具，8種刀具的順序固定，不能調(diào)換。加工作業(yè)時，一種刀具使用完畢后，可轉(zhuǎn)換使用另一種刀具。相鄰兩刀具的轉(zhuǎn)換時間是18 s。作業(yè)時，可順時針旋轉(zhuǎn)轉(zhuǎn)換刀具，如刀具a刀具b；也可逆時針旋轉(zhuǎn)轉(zhuǎn)換刀具，如刀具a刀具h。將任兩個刀具轉(zhuǎn)換，所需時間是相應轉(zhuǎn)換時間的累加。假定鉆頭的行進速度相同，為180 mm

3、/s，行進成本為0.06元/mm，刀具轉(zhuǎn)換的時間成本為7元/min。刀具行進過程中可同時轉(zhuǎn)換刀具，但相應費用不減。</p><p>　　不同的刀具加工不同的孔型，有的只需一種刀具來完成，有的需要多種刀具及規(guī)定的加工次序來完成。表1為10種孔型所需加工刀具及加工次序（*表示該孔型不限制加工次序）。</p><p>　　表1：10種孔型所需加工刀具及加工次序</p><p&

4、gt;　　同一線路板上的過孔不要求加工完畢一個孔，再加工另一個孔，即對于須用多種刀具加工的過孔，只要保證所需刀具加工次序正確即可。</p><p>　　建立相應的數(shù)學模型，并完成以下問題：</p><p>　?。?）由附件1提供的某塊印刷線路板過孔中心坐標的數(shù)據(jù)，請給出單鉆頭作業(yè)的最優(yōu)作業(yè)線路（包括刀具轉(zhuǎn)換方案）、行進時間和作業(yè)成本。</p><p>　?。?）為提

5、高打孔機效能，現(xiàn)在設計一種雙鉆頭的打孔機（鉆頭形狀與單鉆頭相同），兩鉆頭可以同時作業(yè)，也可一個鉆頭打孔，另一個鉆頭行進或轉(zhuǎn)換刀具。為避免鉆頭間的觸碰和干擾，在過孔加工的任何時刻必須保持兩鉆頭間距不小于3cm的合作間距。</p><p>　?。╥）針對附件1的數(shù)據(jù)，給出雙鉆頭作業(yè)時的最優(yōu)作業(yè)線路、行進時間和作業(yè)成本，并與傳統(tǒng)單鉆頭打孔機進行比較，其生產(chǎn)效能提高多少？</p><p>　?。╥

6、i）研究打孔機的兩鉆頭合作間距對作業(yè)路線和生產(chǎn)效能產(chǎn)生的影響。</p><p><b>　　問題分析</b></p><p><b>　　問題1分析：</b></p><p>　　本問題可看作為動態(tài)規(guī)劃與圖論的組合問題，即求取由起始狀態(tài)到終點狀態(tài)的最優(yōu)單向路徑問題，主要是運用運籌學的排序理論、圖論中的路徑的相關理論知識解決

7、問題。經(jīng)分析，—鉆頭的行進時間、—加工不同孔型的刀具的轉(zhuǎn)換時間，是本題的目標規(guī)劃量。行進速度恒定，故目標規(guī)劃量可轉(zhuǎn)化為等效最短路徑。</p><p>　　首先，由分析，異型孔中最遠兩點距離小于等效換刀距離，故我們建立換刀、路線分立優(yōu)化原則，鄰近換刀原則。在該兩個原則下，我們確定了運用工序優(yōu)化算法總體優(yōu)化換刀次序，同型孔中計算路徑最優(yōu)的問題的思路，將問題分成兩部分進行求解。其次，為解決在同型孔中求解最優(yōu)路徑，由優(yōu)化

8、的最鄰近算法我們求解出初始的回路，通過二邊逐次修正算法對其進行優(yōu)化，而后刪去虛擬點得最優(yōu)單向路徑。最后，通過與最小生成樹計算所得下界進行比較，對結果進行驗證。</p><p><b>　　問題2分析</b></p><p>　　問題二中，雙鉆頭對孔群進行加工的互相干擾，使本問題的時序性更突出，故不能簡單使用求回路法，即使用動態(tài)規(guī)劃的思想，該問題這也是個典型的NP-難問

9、題，故我們將采用改進的蟻群算法進行近似求解。我們將采取建立于蟻群算法的蟻對群算法，全局搜索出兩條最短路徑，以達到目標時間最短，使生產(chǎn)效能最高。</p><p>　　對于（i），由于其他條件不變，故決定性條件仍為換刀時間，對此我們沿用問題一的兩個原則。為使目標時間最小，基于兩刀加工時間的一致性，對總換刀次數(shù)，令，并使兩鉆頭換刀次數(shù)盡可能相同。在優(yōu)化問題上，由于存在合作間距的約束條件，問題變?yōu)樵谶B續(xù)時間內(nèi)，時刻加入兩

10、鉆孔間距離的判斷。對于（ii），將在統(tǒng)一模型算法下，通過改變合作間距，定量研究其對生產(chǎn)效能的影響。</p><p>　　在模型驗證中，將所求的路徑與基于最小生成樹的路徑做誤差分析。同時，單純對于提高生產(chǎn)效能而言，與問題一結果相較，若單孔作業(yè)總時間，為雙孔作業(yè)時間，則該模型的建立是失敗的。</p><p><b>　　模型假設</b></p><p&

11、gt;　　忽略鉆頭的形狀、材料、加工工藝等因素對鉆孔作業(yè)的影響，將鉆頭視為質(zhì)點；</p><p>　　忽略所打孔的大小，將孔視為質(zhì)點，以圓心坐標表示；</p><p>　　假定打孔機8種刀具單獨鉆孔作業(yè)時間相同；</p><p>　　假定對于同一孔型鉆孔作業(yè)時間都是相同的；</p><p>　　在問題一中，假定所有孔型的鉆孔作業(yè)時間相同，經(jīng)查

12、閱資料，取該時間為；</p><p>　　在問題二的(i)中，假定合作距離為3cm。</p><p><b>　　符號說明</b></p><p><b>　　模型準備</b></p><p>　　路徑（回路）與TSP問題</p><p>　　定義 在無向圖中，穿程于的每

13、個節(jié)點依次且僅一次的路徑稱為路徑。穿程于的每個節(jié)點依次且僅一次的回路稱為回路。</p><p>　　TSP(旅行商問題)</p><p>　　有n個城市，其相互間距離,為已知，求合理的路線使得每個城市都被經(jīng)過一次，且總路徑為最短。TSP的數(shù)學模型為：</p><p><b>　　(7)</b></p><p><b

14、>　　(8)</b></p><p><b>　　(9)</b></p><p><b>　　(10)</b></p><p><b>　　(11)</b></p><p>　　式(8)中表示旅行商經(jīng)歷的路徑，表示不經(jīng)過該路徑；式(5)(6)要求旅行商經(jīng)過點有

15、且僅有一次；(8)在任何一個城市的子集中不行成圈。</p><p><b>　　最鄰近算法</b></p><p>　　定理1 是個頂點的無向完全圖，為從到正實數(shù)集的函數(shù)，對在中任意三點，滿足</p><p><b>　　(1)</b></p><p>　　則可將實際問題轉(zhuǎn)化為求取賦權圖上的回路

16、問題。</p><p><b>　　具體算法如下：</b></p><p>　　在中取一點為起始點，找出一個與始點最近的點，形成一條邊的初始路徑。</p><p>　　設表示最新加到這條路徑上的點，從不在路徑上的所有點中，選一個與最鄰近的點，把連接與此點邊加到這條路徑中。重復直至中的所有頂點包含在路徑中</p><p>

17、　　把始點和最后加入的頂點之間的邊放入，即得出一個回路。</p><p><b>　　蟻群算法：</b></p><p><b>　　狀態(tài)轉(zhuǎn)移規(guī)則</b></p><p><b>　　(2)</b></p><p>　　式中一在時刻螞蟻由元素轉(zhuǎn)移到元素的概率；——表示螞蟻下一步

18、允許選擇的城市；——信息啟發(fā)式因子，表示軌跡的相對重要性；一期望啟發(fā)式因子，表示能見度的相對重要性；——啟發(fā)函數(shù)，；——殘留信息量。</p><p><b>　　信息素修正規(guī)則</b></p><p><b>　　(3)</b></p><p><b>　　(4)</b></p><

19、;p>　　式中,——信息素揮發(fā)系數(shù)；一表示第只螞蟻在本次循環(huán)中留在路徑上的信息量；——信息素強度，設為常數(shù)；——第后只螞蟻在本次循環(huán)中所走過的路徑的長度。</p><p>　　禁忌表的修改和表螞蟻數(shù)后有一個表和表。初始時可以把中的元素都設為0，把的元素都設為l。如果螞蟻第1次選擇了城市，則把tabu表中第1元素賦值為，并把表總第個元素賦值為0，表示此城市已經(jīng)走過。</p><p>&

20、lt;b>　　算法實現(xiàn)步驟如下：</b></p><p>　　參數(shù)初始化。令循環(huán)次數(shù)，將只螞蟻隨機放在個元素(城市)上，；</p><p><b>　　循環(huán)次數(shù)</b></p><p><b>　　螞蟻數(shù)；</b></p><p>　　對第只螞蟻，根據(jù)公式(1)選擇城市，并前進；&

21、lt;/p><p>　　把選擇的城市加入到第屜只螞蟻的表中，并修改表；</p><p>　　對于第只螞蟻若沒有游歷完所有個城市，則轉(zhuǎn)到第4步，若游歷完所有城市，則執(zhí)行第7步；</p><p>　　若螞蟻數(shù)k小于螞蟻總數(shù)，則轉(zhuǎn)到第3步，直到只螞蟻都游歷完個城市，再執(zhí)行第8步；</p><p>　　根據(jù)式(2)、式(3)更新每條路上的信息量，并找出只

22、螞蟻中，所走的最短路徑的值，并保存；</p><p>　　若循環(huán)次數(shù)未達到最大循環(huán)次數(shù)，則轉(zhuǎn)到第2步，若滿足結束條件則結束循環(huán)，并輸出計算結果。</p><p><b>　　數(shù)據(jù)處理</b></p><p>　　將10種孔型按所需刀具重新編號，其中分別代表8種刀具、10種孔型中某一種，故得18類孔（共2814個）如下表。</p>

23、<p>　　表格 1 18種新孔分類列表</p><p>　　另外，為敘述簡便，將新的18種孔型做統(tǒng)一再命名，對應表格如下</p><p>　　表格 2 18種新孔識記表</p><p>　　同時我們作出了相應的18種新孔的刀具分布情況，如下圖。</p><p>　　圖 1 18種新型孔的刀具分布情況</p>

24、<p>　　由公式，將題目中縮短行進、換刀時間問題，轉(zhuǎn)化為求解最短距離問題。</p><p>　　首先，將5.3數(shù)據(jù)處理中所得到的2814個點，，記作賦權圖中點集，其中。</p><p>　　針對上步中的2814個點，依次求出兩點間最短距離；</p><p>　　不同的孔型需換刀具，兩點間的換刀等效距離</p><p><b&

25、gt;　　(5)</b></p><p><b>　　其中</b></p><p><b>　　(6)</b></p><p>　　為兩刀具之間所需的換刀時間，為點與點換刀次數(shù)。</p><p><b>　　模型的建立與求解</b></p><p

26、>　　兩個原則下的單向路徑的圖論模型</p><p><b>　　模型建立</b></p><p>　　基于TSP(旅行商問題)的最短路程模型：</p><p><b>　　最短等效路徑：</b></p><p><b>　　刀具行進路徑：</b></p>

27、<p>　　從先前位置移動到當前位置的成本。設兩個位置之間的實際距離為單位長度的刀具行進成本為n，則完成個孔加工的刀具行進成本為：</p><p><b>　　(12)</b></p><p>　　——孔和孔之間距離；——該路徑在優(yōu)化路徑上。</p><p><b>　　換刀等效路徑：</b></p&g

28、t;<p>　　設打孔機為加工孔后再加工不同孔型所需的等效換刀距離，為單位路徑的換刀成本，則完成個孔加工的換刀成本為：</p><p><b>　　(13)</b></p><p>　　——兩點間的等效換刀路徑 （處理方法，見數(shù)據(jù)處理5.3）；</p><p>　　——兩點之間的換刀次數(shù)。</p><p>

29、;<b>　　則最小化總目標：</b></p><p><b>　　(14)</b></p><p><b>　　模型求解思路：</b></p><p>　　在換刀、路線分立優(yōu)化原則，鄰近換刀原則下，我們將用語言編寫工序優(yōu)化算法實現(xiàn)總體工序優(yōu)化，通過優(yōu)化的最鄰近算法求得初始回路，而后用二邊逐次修正算法

30、對路徑進行優(yōu)化，并將虛擬點刪去得單向路徑。解決步驟如圖2。</p><p><b>　　圖 2模型一流程圖</b></p><p>　　兩個原則下的工序、路徑優(yōu)化</p><p><b>　　兩個原則：</b></p><p>　　換刀、路線分立優(yōu)化原則：</p><p>　

31、　換刀情況下，最小等效換刀距離</p><p><b>　　(17)</b></p><p><b>　　(18)</b></p><p>　　其中，——對行進距離的平均值。</p><p>　　故需將同一類型的孔打完再換刀，則本問題轉(zhuǎn)化為——異類點工序（換刀）優(yōu)化、同類點之內(nèi)的路徑優(yōu)化問題。<

32、;/p><p><b>　　鄰近換刀原則：</b></p><p>　　為減小等效，換刀時應盡量進行臨近刀具轉(zhuǎn)換進行打孔作業(yè)，如，，或孔作業(yè)完畢，則優(yōu)先或孔的作業(yè)，在鄰近換刀條件下，最大程度上減少。</p><p><b>　　工序優(yōu)化算法：</b></p><p>　　對于已有18類孔，必然有，其中表

33、示步驟總數(shù)，18步之內(nèi)總能打完所有的點。故對工序進行優(yōu)化時，我們引入步驟矩陣，激活矩陣，狀態(tài)矩陣，以總次數(shù)最小為目標，</p><p><b>　　(19) </b></p><p>　　其中，為要打第類孔時，所需的換刀次數(shù)。</p><p><b>　　初始化步驟矩陣，；</b></p><p>

34、<b>　　激活矩陣，；</b></p><p><b>　　狀態(tài)矩陣，；</b></p><p>　　其中，代表相應的新型孔。</p><p>　　根據(jù)圖4 ,18類新型孔的刀具分布情況，步驟矩陣，由某確定起始孔型開始，，若，則向左尋找最近的的孔型，并將對應的關系矩陣尋找下線孔型，并使，。</p><

35、p>　　根據(jù)，的值，重復對的操作。并判斷是否，。 若滿足則結束，若不滿足則重復3)的操作。則可得工序的最優(yōu)解。</p><p>　　最鄰近算法求初始回路</p><p><b>　　具體步驟如下：</b></p><p>　　建立等效距離矩陣，其中第行、第列的元素，為點到點的等效距離；</p><p>　　建立激活

36、矩陣，其中；</p><p>　　建立關系矩陣，其中；</p><p>　　建立狀態(tài)矩陣，其中；</p><p>　　確a定點（時為起始點），對應將，，若，則由值查找下線點，跳轉(zhuǎn)至步驟3；若，則繼續(xù)對點重復對的操作，直至轉(zhuǎn)至步驟3。</p><p>　　由第二步所確定的點對于除外的所有點滿足相應的點，并在等效距離矩陣中的第行中，對于滿足要求的

37、點對應的值尋找最小值，并對點重復步驟二，直至所有元素為零，故所得路徑為優(yōu)化的有向回路。</p><p>　　在路徑中加入虛擬點，令任一點到得距離=0，則與路徑中所有的點都相連接，則最終去掉邊權最大的兩點中間的路徑，則得到有向路徑。</p><p><b>　　具體算法流程如下：</b></p><p><b>　　二邊逐次修正算法&l

38、t;/b></p><p>　　對所得圈，對所有適合的，判斷對某一對和，是否有</p><p><b>　　(20)</b></p><p>　　若有，刪去邊和,添加邊和得;</p><p>　　重復1)2)兩步，直至不可再用此方法繼續(xù)進行，則求得一個較優(yōu)的圈</p><p>　　為了得到更

39、高的精度，該程序可以重復幾次，每次都以不同的圈開始。</p><p><b>　　模型求解</b></p><p><b>　　總路徑示意圖：</b></p><p><b>　　打孔路徑圖：</b></p><p><b>　　打孔路徑圖：</b><

40、;/p><p><b>　　打孔路徑圖：</b></p><p><b>　　打孔路徑圖</b></p><p><b>　　打孔路徑圖：</b></p><p><b>　　打孔路徑圖：</b></p><p><b>　　

41、打孔路徑圖：</b></p><p><b>　　打孔路徑圖：</b></p><p><b>　　打孔路徑圖：</b></p><p>　　工序流程表及對應路徑長度：</p><p><b>　　工序流程為：</b></p><p>　　該

42、流程實際為刀具轉(zhuǎn)換的流程，也即工序圖，其中表示某一種刀具，表示換刀。該流程為，由刀具開始，將所有用到刀具的孔全部打完后，刀具換轉(zhuǎn)，將即需刀具的型所有孔打完，再轉(zhuǎn)換。同理，以該流程打完所有孔。</p><p>　　工序流程表及對應長度如下：</p><p><b>　　總時間計算：</b></p><p><b>　　(21)</

43、b></p><p><b>　　總費用計算：</b></p><p><b>　　(22)</b></p><p><b>　　模型檢驗</b></p><p>　　有向圈的求解并不能找到確定的最優(yōu)解，但可以用最佳圈的權的下界與其比較。利用最小生成樹可以得到最佳圈的一個

44、下界，方法如下。</p><p>　　設是的一個最佳圈，則對的任一頂點，是的路，也是的生成樹。如果是的最小生成樹，且和是與關聯(lián)的邊中權最小的兩條邊，則將是的一個下界。</p><p><b>　　問題二</b></p><p><b>　　模型建立</b></p><p>　　在問題一的基礎上，我們

45、由雙鉆頭工序優(yōu)化算法優(yōu)化出雙鉆頭的換刀方案，在兩個原則下，我們可認為雙鉆頭在滿足的約束條件下在兩塊獨立且重合的板上進行獨立打孔作業(yè)。針對此問題，我們將平面問題轉(zhuǎn)化加入時間軸為空間問題，軸為坐標軸，軸為時間軸，并提出了基于蟻群算法的蟻對群算法。</p><p><b>　　蟻對群算法：</b></p><p>　　在蟻群算法的基礎上，為解決雙打孔機的作業(yè)線路設計問題，我

46、們提出了蟻群對算法。具體步驟如下：</p><p>　　隨機產(chǎn)生對螞蟻，將該對中的螞蟻平均分別置于將行路線上；</p><p>　　對于螞蟻對的起始孔加入到禁忌表； </p><p>　　計算，其中為螞蟻到剩余點的概率，為螞蟻到剩余點的概率；</p><p>　　用賭輪方法選擇螞蟻各自在該次行進中將要到達的孔；</p><

47、p>　　計算螞蟻第次行進時間，螞蟻第次行進時間，</p><p><b>　　(23)</b></p><p><b>　　(24)</b></p><p><b>　　(25)</b></p><p>　　其中為從螞蟻從到的等效行進時 間，為的實際行進時間，為兩個孔之間

48、是否要換刀的標記變量，對于平行存在;</p><p>　　若，并且，則螞蟻移至孔處，返回步驟4）；若，，則螞蟻均不可移動，直接返回4）；</p><p>　　對螞蟻均完成1次行進，則根據(jù)修正信息素規(guī)則，修改信息素（見模型準備5.4）；</p><p>　　當循環(huán)次數(shù)時，結束。</p><p><b>　　具體流程圖如圖3：</

49、b></p><p>　　圖 3蟻對群算法流程圖</p><p>　　其中目標點確定方法為蟻對群算法中的（3）（4）（5）（6）。</p><p><b>　　模型求解</b></p><p><b>　　最優(yōu)作業(yè)線路圖</b></p><p>　　在雙鉆頭按照，其中，

50、道具僅打型孔，對道具所打型孔，對兩鉆頭進行近似平均分配。</p><p><b>　　點分布路線圖：</b></p><p><b>　　1~100點</b></p><p><b>　　101~200點</b></p><p><b>　　201~300點</

51、b></p><p><b>　　301~350點</b></p><p><b>　　351~480點</b></p><p><b>　　481~680點</b></p><p><b>　　681~800點</b></p><

52、;p><b>　　801~900點</b></p><p><b>　　901~1180點</b></p><p>　　1181~1300點</p><p>　　1301~1350點</p><p>　　1351~1410點</p><p><b>　　軸路線

53、圖</b></p><p><b>　　軸路線圖</b></p><p>　　行進時間（單個空作業(yè)時間為）</p><p>　　鉆頭路徑中共1407個頂點，b點數(shù)為268 個，</p><p><b>　　，（含作業(yè)時間）</b></p><p>　　鉆頭路徑中共

54、1407個頂點，</p><p><b>　　，（含作業(yè)時間）</b></p><p>　　行進總時間：，（含作業(yè)時間）</p><p><b>　　作業(yè)成本</b></p><p><b>　　模型評價</b></p><p>　　對模型一，考慮到所需

55、作業(yè)的孔的數(shù)據(jù)龐大，鄰近換刀條件、刀具轉(zhuǎn)換次序限制條件混合，問題復雜性較高。首先，我們通過優(yōu)化的最鄰近算法下，求出新分類的18種孔型下的所有孔的近似最短回路問題。其次，在已有的結果的基礎上，對問題進行分析。同時，基于結果分析后提出的兩個原則，運用二邊逐次修正算法、工序優(yōu)化算法，分別對同類孔之間行進路徑、工序進行優(yōu)化。該模型的建立中，我們對問題逐層求解，所提出的求解有向回路的算法——即在最鄰近算法的基礎上引入激活、狀態(tài)、關系矩陣，運算量相

56、對圖論的經(jīng)典算法較小，應用范圍廣。</p><p>　　在問題二的解答中延續(xù)了問題一的思想，兩處基礎算法都是基于問題一已實現(xiàn)的程序，即由最鄰近算法求解同型孔之內(nèi)的最優(yōu)路徑問題。故而在已有的基礎上減少了運行時間，提高了效率。</p><p><b>　　靈敏度分析</b></p><p><b>　　單個孔的作業(yè)時間：</b>

57、;</p><p>　　考慮到單個孔的的作業(yè)時間若置為變量，使問題更加復雜。經(jīng)查閱資料，我們將打孔時間設為。實際，在問題二中，由于兩個打孔機獨立作業(yè)，由于有合作間距的限制，單個孔打孔時間，會對的作業(yè)情況有較大的影響。如，若在某時刻打孔，而按預定路程本應向的孔行進，但，故需等待作業(yè)完畢后進行。則對雙打孔機作業(yè)的影響可能較大，下面我們將對的取值對整體結果的影響進行具體討論。</p><p>　

58、　由于實際工程中條件約束，，分別故取將，代入問題的程序求解，則結果如表格3：</p><p>　　表格 3單孔作業(yè)時間對比表格</p><p>　　由表格3可知，當分別取，，，說明取值不同時，差異不大?？倳r間包含了作業(yè)時間，故取值不同時，變化較大。故的取值對本問題影響不大，且問題二的模型有較好的彈性，可以滿足咋一定范圍內(nèi)的波動。</p><p><b>　

59、　算法分析：</b></p><p>　　由于尋找回路問題為問題，并沒有成熟的算法解決該問題。為解決尋找有向路徑，我們將最鄰近算法進行改進，具體分析如下。</p><p><b>　　優(yōu)化的最鄰近算法：</b></p><p>　　由起始點進行路徑的擴充，基于最鄰近的思想，只添加最小的邊。同時我們引入的等效距離矩陣，的激活矩陣，關系

60、矩陣，狀態(tài)矩陣，其計算時間復雜度為，其中為總節(jié)點數(shù)。算法優(yōu)勢在于，在時間復雜度較低的情況下求解出近似的有向最優(yōu)回路。同時，沒有矩陣的迭代，則不會產(chǎn)生由迭代深度引起的空間復雜度過大的問題。</p><p><b>　　模型推廣</b></p><p><b>　　拓展一：遺傳算法</b></p><p>　　遺傳算法是模擬生

61、物在自然界中遺傳和進化過程而形成的一種向適應全局優(yōu)化概率搜索算法。遺傳算法在優(yōu)化孔群的加工路徑中，染色體一般為一個代加工孔的序列，所以染色體的長度與孔的數(shù)量相等。直接采用孔的標號編碼在運算中可能出現(xiàn)某些孔未加工的情況，因此可采用編碼方式如下：</p><p>　　每加工一個孔，就將其從未加工列表中刪除，則列表作為一個染色體表示代加工孔的序列。假設某個待加工孔的序列為，則按照上述方法編碼得到的染色體為（112141

62、311）。而對于雙鉆頭孔群加工路徑問題，每個孔的加工序列都是兩條加工路徑之間斷開后都可形成兩個子序列，根據(jù)鉆頭行走時間和鉆頭所需時間可算出對應加工時間為和。比較不通斷電的值，值最小的兩個子序列就是這一染色體代表的雙鉆頭的群加工方案。</p><p>　　合作距離的判斷間距算法：</p><p>　　若在某時刻，若螞蟻分別在點處，若通過目標點確定算法確定出分別將行至點。比較線段，之間的最短距

63、離與合作間距之間的大小，若滿足該條件則螞蟻分別可達，若否，則由目標點確定算法重新確定。</p><p><b>　　參考文獻</b></p><p>　　姜啟源,謝金星,葉俊,《數(shù)學模型》,北京,高等教育出版社. 2004年4月.</p><p>　　胡運權,《運籌學教程》, 北京：清華大學出版社，1998: 405 ~ 410.</p&

64、gt;<p>　　盧開澄, 盧華明,《組合數(shù)學》，第3 版, 北京：清華大學出版社，2002: 473 ~ 478.</p><p>　　《運籌學》教材編寫組,《運籌學》, 北京：清華大學出版社. 2005年6月.</p><p>　　張銀明，單向最優(yōu)通路的求解新方法及其算法設計，華僑大學學報(自然科學版)，2003，24(3).</p><p>　　

65、周培德, 一種快速求解貨郎擔問題的方法，計算機理論通信，1984(03).</p><p>　　潘金直、顧鐵成等編譯．現(xiàn)代計算機常用數(shù)據(jù)結構與算法，南京大學出版社．1994.</p><p>　　曲晶，肖世德，熊鷹，基于蟻群算法的PCB孔加工路徑優(yōu)化，機電工程，2007（24）.</p><p>　　張毅華，鄭長江，丁金學. 基于螞蟻尋徑原理的最優(yōu)路徑選擇算法，系統(tǒng)