周耿烈 馮無恙 胡赤兵②

(①蘭州理工大學(xué)機(jī)電工程學(xué)院，甘肅蘭州 730050;②蘭州理工大學(xué)數(shù)字制造技術(shù)與應(yīng)用省部共建教育部重點(diǎn)實(shí)驗(yàn)室，甘肅蘭州 730050)

成本、質(zhì)量、生產(chǎn)率和產(chǎn)量、交貨期是衡量機(jī)床制造企業(yè)生產(chǎn)能力和巿場競爭能力的4個(gè)要素［1］。機(jī)床零部件加工后要經(jīng)過嚴(yán)格的檢驗(yàn)進(jìn)入全自動(dòng)化立體倉庫存放，再由立體倉庫送至裝配作業(yè)線進(jìn)行部件裝配，裝配完成的部件經(jīng)過嚴(yán)格的部裝檢驗(yàn)后進(jìn)入立體倉庫。立體倉庫根據(jù)生產(chǎn)需要將零部件送到裝配作業(yè)線進(jìn)行總裝。如何在保證機(jī)床質(zhì)量的前提下降低生產(chǎn)成本包括物流成本，同時(shí)提高機(jī)床的生產(chǎn)率和產(chǎn)量，并依據(jù)客戶要求按時(shí)交貨是機(jī)床制造企業(yè)關(guān)注的重點(diǎn)。

立體倉庫是現(xiàn)代物流系統(tǒng)中迅速發(fā)展的一個(gè)重要組成部分，在制造自動(dòng)化中也占有非常重要的地位。在機(jī)床制造企業(yè)建立立體倉庫及其信息管理系統(tǒng)其目的不僅是為了進(jìn)行毛坯、半成品、成品、工裝夾具等的自動(dòng)存儲和自動(dòng)檢索，更是密切配合企業(yè)的產(chǎn)銷計(jì)劃與物料需求計(jì)劃。由于機(jī)床不同零部件的制造周期不一樣，為保證產(chǎn)品成套既要按期交貨，又要盡可能減少由于產(chǎn)品積壓所導(dǎo)致的生產(chǎn)管理混亂現(xiàn)象，立體倉庫管理系統(tǒng)是現(xiàn)代化立體倉庫不可或缺的一部分。

隨著自動(dòng)化立體倉庫在生產(chǎn)線當(dāng)中的應(yīng)用，形成了以自動(dòng)化立體倉庫為核心的物流配送系統(tǒng)，從采購、外協(xié)到貨、檢驗(yàn)入庫、毛坯出庫、加工、零件入庫、裝配及產(chǎn)品生成，都要與自動(dòng)化立體倉庫協(xié)調(diào)。

自動(dòng)化立體倉庫要求作業(yè)迅速、準(zhǔn)確、穩(wěn)定等特點(diǎn)。其作業(yè)周期由出入庫臺的時(shí)間、貨物登記時(shí)間和堆垛機(jī)在倉庫存取貨物時(shí)間等組成。由于現(xiàn)代化立體倉庫規(guī)模越來越大，其高度達(dá)50多m，長度也達(dá)150 m，所以在整個(gè)物流周期中堆垛機(jī)的行駛時(shí)間占到整個(gè)倉庫作業(yè)周期的50%。如果堆垛機(jī)調(diào)度不當(dāng)或選用效率較低的調(diào)度模式，會嚴(yán)重影響堆垛機(jī)的工作效率，進(jìn)而影響整個(gè)倉庫的作業(yè)效率。所以選擇一種較為合理的揀選路徑是提高堆垛機(jī)作業(yè)效率的方法。

在對堆垛機(jī)的路徑進(jìn)行分析時(shí)，國內(nèi)外學(xué)者已對倉庫中的貨位存取優(yōu)化，單復(fù)合作業(yè)的優(yōu)化、堆垛機(jī)揀選作業(yè)的優(yōu)化及輸送系統(tǒng)的調(diào)度優(yōu)化進(jìn)行了廣泛的研究。自動(dòng)化立體倉庫堆垛機(jī)路徑優(yōu)化的算法研究，包括蟻群算法、模擬退火算法、啟發(fā)式算法、禁忌搜索算法［2－5］及遺傳算法等。其中遺傳算法能夠得出較好的全局最優(yōu)解，具有搜索速度快、精度高等優(yōu)點(diǎn)。

1 自動(dòng)化立體倉庫模型的建立

假設(shè)堆垛機(jī)的工作空間(立體倉庫)用二維平面圖形來表示。堆垛機(jī)執(zhí)行一次任務(wù)時(shí)所不能通過的貨格的位置已知。用尺寸相同的柵格對立體倉庫進(jìn)行劃分。若某一柵格內(nèi)不含任何障礙物，則稱此柵格為自由柵格;反之，稱之為障礙柵格［6］。如圖1所示。

2 改進(jìn)的自適應(yīng)遺傳算法

遺傳算法是一種借鑒生物界自然選擇和自然選擇機(jī)制的隨機(jī)化搜索算法，對于用傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性問題具有良好的適應(yīng)性。但還有很多不足，如早熟收斂、易陷入局部最優(yōu)和收斂速度慢等。本文采用改進(jìn)的自適應(yīng)遺傳算法對堆垛機(jī)的工作環(huán)境進(jìn)行建模，找到堆垛機(jī)路徑優(yōu)化的最佳路徑。

當(dāng)今改進(jìn)遺傳算法的措施主要集中于對交叉概率和遺傳概率的選擇與確定上，因?yàn)樗鼈儠绊戇z傳算法的收斂性和搜索速度。針對不同的優(yōu)化目標(biāo)需要反復(fù)試驗(yàn)來確定交叉概率和遺傳概率，而傳統(tǒng)的遺傳算法采用的是固定數(shù)值來代替交叉概率和遺傳概率，這樣很難找到最佳優(yōu)化目標(biāo)。

自適應(yīng)遺傳算法(AGA)［7］是由 Srinivas提出來的，它的基本思想是交叉概率和變異概率能夠隨著適應(yīng)度的變化而變化。當(dāng)種群各個(gè)體適應(yīng)度處于趨于一致或者局部最優(yōu)時(shí)，使交叉概率和變異概率增加，從而避免陷入局部最優(yōu)，繼而引發(fā)早熟現(xiàn)象;當(dāng)群體各個(gè)體適應(yīng)度比較分散時(shí)，使交叉概率和變異概率減少，從而不易破壞優(yōu)良個(gè)體，以利于優(yōu)良個(gè)體保存下來。同時(shí)，對適應(yīng)度高于群體平均適應(yīng)度的個(gè)體選擇較小的交叉概率和變異概率，使得個(gè)體保存下來;那些低于群體平均適應(yīng)度的個(gè)體，選擇較大的交叉概率和變異概率，一方面將一部分差的個(gè)體淘汰，另一方面增加新個(gè)體［8］。在自適應(yīng)遺傳算法中，交叉概率pc和變異概率pm按如下公式進(jìn)行調(diào)整:

式中:fmax為種群的最大適應(yīng)度;favg為種群的平均適應(yīng)度;f′為參與交叉的2個(gè)個(gè)體中較大的個(gè)體的適應(yīng)度;f為變異個(gè)體的適應(yīng)度。

AGA算法是有缺陷的。從公式中可以看出，當(dāng)個(gè)體適應(yīng)度越接近于最大適應(yīng)度(fmax－f′≈0)時(shí)，交叉概率和變異概率越小，到接近為零，這種調(diào)整方法在群體優(yōu)化后期較為合適，因?yàn)樵诤笃?，要將?yōu)良個(gè)體保存下來，即為全局最優(yōu)解。但是在進(jìn)化初期不利，因?yàn)樵谶M(jìn)化初期群體中的較優(yōu)個(gè)體幾乎處于一種不發(fā)生變化的狀態(tài)，而此時(shí)的優(yōu)良個(gè)體不一定是全局最優(yōu)解，增加了進(jìn)化走向局部最優(yōu)解的可能性，就是所謂的早熟現(xiàn)象。

任子武等人在AGA的基礎(chǔ)上，提出了一種改進(jìn)的自適應(yīng)遺傳算法(IAGA)。它除了有AGA的一系列優(yōu)點(diǎn)之外，還彌補(bǔ)了AGA的缺陷。為了保證每一代的優(yōu)良個(gè)體不被破壞，采取了精英保留策略:如果下一代的最佳個(gè)體適應(yīng)度小于當(dāng)前種群的最佳個(gè)體適應(yīng)度，那么將當(dāng)前種群的最佳個(gè)體或者多個(gè)個(gè)體直接復(fù)制到下一代，從而不會被當(dāng)代種群的交叉和變異等遺傳操作破壞［8］。IAGA 公式如下:

式中:pc1、pc2分別為交叉概率的最大值和最小值;pm1、pm2分別為變異概率的最大值和最小值。

在IAGA算法中，根據(jù)公式，個(gè)體的交叉概率和變異概率應(yīng)根據(jù)個(gè)體的適應(yīng)度在平均適應(yīng)度和最大適應(yīng)度之間進(jìn)行線性變換。如果種群中存在較大規(guī)模的適應(yīng)度接近平均適應(yīng)度的個(gè)體，它的交叉概率最大，幾乎為pc1和pm1，若個(gè)體適應(yīng)度接近于最大適應(yīng)度，那么它的交叉概率和變異概率很小，為pc2和pm2，即IAGA的自適應(yīng)交叉概率和變異概率曲線非常陡峭，導(dǎo)致一部分個(gè)體只能擁有較低的交叉概率和變異概率，使進(jìn)化停滯不前，造成局部收斂［9］。

本文所要提出的新的改進(jìn)自適應(yīng)遺傳算法是根據(jù)種群的大小、適應(yīng)值的分布情況、自適應(yīng)變化整個(gè)種群的交叉概率和變異概率，使它們的變化曲線為一個(gè)從振蕩而逐漸穩(wěn)定的形勢。設(shè)計(jì)進(jìn)化前期具有較大的交叉概率和變異概率，以增強(qiáng)搜索能力，在進(jìn)化后期采取相對較低的交叉概率和變異概率，以確定最佳個(gè)體。本文將采用正弦形式的自適應(yīng)遺傳算法(SAGA)，其公式如下:

圖2和圖3為兩個(gè)公式所表示的圖像，均為正弦式圖像，從而保證了交叉概率和變異概率呈一種穩(wěn)定式變化，而不會出現(xiàn)過度陡峭曲線，因?yàn)椋?＜sina＜1，它可以弱化由于適應(yīng)度接近平均適應(yīng)度或者接近最大適應(yīng)度而造成的交叉概率和變異概率的過大或者過小，也克服了由于種群停滯不前而陷入局部最優(yōu)的現(xiàn)象。

3 路徑規(guī)劃方法

3.1 編碼

采用序號法?；卷樞蚴菑淖蟮接?，從下到上。將立體倉庫分為若干個(gè)空格，從立體倉庫的左下角的第一個(gè)格開始，給每一個(gè)空格一個(gè)序號N，依次延續(xù)，這樣序號N與立體倉庫的每一個(gè)空格一一對應(yīng)。

我們將堆垛機(jī)在立體倉庫的一條運(yùn)動(dòng)路徑稱之為一個(gè)個(gè)體，在這里假設(shè)堆垛機(jī)由起始位置A經(jīng)過這一條路徑最終到達(dá)終點(diǎn)位置B，那么這條路徑可以表示為一個(gè)個(gè)體。采用序號法，則表示為以下所示:(0，1，11，13，22，32，34，45，56，66，77，87，88，99)，我們從中可以看出，每條路徑采用序號法具有編碼長度短、簡明、直觀的優(yōu)點(diǎn)。

3.2 初始種群

在選取初始種群時(shí)，為了使堆垛機(jī)行駛的路徑最短，在起始點(diǎn)與終點(diǎn)連線的兩側(cè)分布初始點(diǎn)，把這些點(diǎn)稱之為過渡點(diǎn)。把上一點(diǎn)與下一點(diǎn)的選取作為一個(gè)周期，每個(gè)周期選擇與當(dāng)前堆垛機(jī)的位置距離最小的點(diǎn)作為當(dāng)前時(shí)刻的規(guī)劃子目標(biāo)點(diǎn)。如果子目標(biāo)點(diǎn)不是障礙物，則此點(diǎn)為最佳點(diǎn);若是障礙物，則選取此點(diǎn)周圍的過渡點(diǎn)為候選點(diǎn)。這樣規(guī)劃出的路徑都是圍繞起點(diǎn)和終點(diǎn)連線的，確保點(diǎn)的分布不會太分散，這樣可以規(guī)劃出最短路徑。

3.3 個(gè)體適應(yīng)度函數(shù)

在這里選取如下所示的個(gè)體適應(yīng)度函數(shù):

3.4 遺傳算子設(shè)計(jì)

3.4.1 選擇算子

采用輪盤賭選擇和精英保留相結(jié)合的方法，是個(gè)體按照與適應(yīng)度成正比例的概率向下一代群體繁殖。

3.4.2 交叉算子

采用部分匹配交叉法:先隨機(jī)產(chǎn)生兩個(gè) ，定義這兩點(diǎn)間的區(qū)域?yàn)槠ヅ鋮^(qū)域，并用位置操作交換兩個(gè)父代的匹配區(qū)域。如:交叉點(diǎn)為3、6父代A872 130 9546父代B983 567 1420，先交換130與567，得出來的兩個(gè)過渡代為A′872 567 9546父代B′983 130 1420，對于A′、B′中的匹配區(qū)域以外出現(xiàn)的數(shù)碼重復(fù)，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進(jìn)行交換。即5和1進(jìn)行交換，6和3進(jìn)行交換，7和0進(jìn)行交換。這樣經(jīng)過交叉之后，子代A為 8025679143，同理，子代B為9861305427。

3.4.3 變異算子

其變異算子采用逆轉(zhuǎn)變異算子，方法如下:在個(gè)體中隨機(jī)挑選兩個(gè)逆轉(zhuǎn)點(diǎn)，再將兩個(gè)逆轉(zhuǎn)點(diǎn)間的基因反序插入原位置。如個(gè)體A:987654321，在第4號位與第6號位采用逆轉(zhuǎn)變異算子。新生成的個(gè)體為987456321。

3.4.4 平滑算子

堆垛機(jī)采用導(dǎo)軌式行走裝置，所以在行駛到轉(zhuǎn)彎路徑時(shí)要求拐彎處角度大，從而引出路徑平滑度問題。平滑度是指路徑段之間偏轉(zhuǎn)角度的大小。如果轉(zhuǎn)角過小，則會增加堆垛機(jī)行走過程的復(fù)雜性，其消耗時(shí)間過長，甚至?xí)?dǎo)致堆垛機(jī)因轉(zhuǎn)角過小而無法通過。

平滑算子是在路徑段之間的轉(zhuǎn)角處兩端添加兩個(gè)或多個(gè)節(jié)點(diǎn)，替代原有的節(jié)點(diǎn)，使得路徑轉(zhuǎn)角處更加平滑，使堆垛機(jī)順利通過此處。

設(shè)堆垛機(jī)的轉(zhuǎn)彎最小角度為α，如圖4所示.當(dāng)判斷出兩個(gè)相連路徑的拐角偏轉(zhuǎn)角度β＜α?xí)r，則分別在拐角附近的兩端可行域附近隨機(jī)選取兩個(gè)新節(jié)點(diǎn)，這樣就形成了兩個(gè)拐角處，這時(shí)分別判斷兩個(gè)拐角處的偏轉(zhuǎn)角度是否大于α，若大于則替代原節(jié)點(diǎn)，否則在兩節(jié)點(diǎn)處的兩端可行域再選擇兩個(gè)新節(jié)點(diǎn)，直至符合要求。

4 仿真分析

采用Matlab遺傳算法工具箱對此進(jìn)行仿真測試。設(shè)種群規(guī)模為40，每個(gè)種群的長度為20，交叉概率pc=0.9，變異概率為pm=0.01，然后利用SAGA對每一代的交叉概率和變異概率進(jìn)行計(jì)算。在Matlab窗口中輸入Gatool，打開、進(jìn)入遺傳算法工具箱。之前必須將適應(yīng)度函數(shù)寫成M文件。

決定遺傳算法的一個(gè)重要性能是種群的多樣性。個(gè)體間的距離越大，則多樣性越高;反之，個(gè)體間的距離越小，則多樣性越小。

設(shè)置“initial range”為［0;1］，其顯示圖形如圖 5所示。

圖5的上圖中較為密集的點(diǎn)為每一代的最佳適應(yīng)度值(Fitness value)，而在密集點(diǎn)周圍的較為分散的點(diǎn)為每一代的平均適應(yīng)度值，它可以很好地用來衡量種群的多樣性。對于初始范圍的設(shè)置，由于多樣性太小，算法進(jìn)展很小。設(shè)置“initial range”為［0;100］，運(yùn)行算法，如圖6所示。

這次算法進(jìn)展較快。但是，由于個(gè)體之間的平均距離較大，最佳個(gè)體原理最優(yōu)解。

設(shè)置“initial range”為［0;20］，運(yùn)行算法，如圖7所示。

這次由于多樣性比較適合，所以算法得到的結(jié)果比前兩次都好。

圖7上圖為遺傳算法過程中群體中每一代個(gè)體最佳適應(yīng)度隨進(jìn)化代數(shù)(Generation)的變化情況。可以看出，改進(jìn)后的遺傳算法收斂較快，進(jìn)化到約34代就已經(jīng)接近搜索到了全局最優(yōu)解。在早期各代中，當(dāng)個(gè)體離理想值較遠(yuǎn)時(shí)，最佳值會迅速得到改進(jìn);在后來各代中，種群越接近最佳點(diǎn)，最佳值改進(jìn)的越慢，正好順應(yīng)了SAGA的要求，圖7的下圖很好地解釋了這些情況。它為每一代中(每一代中會產(chǎn)生一定數(shù)量的點(diǎn)，各點(diǎn)所對應(yīng)的適應(yīng)度值不一樣)各點(diǎn)之間的平均距離。當(dāng)變異數(shù)減小時(shí)，個(gè)體之間的平均距離也減小，逐漸向零靠近?？梢钥闯觯?dāng)進(jìn)化代數(shù)在40代之前，個(gè)體之間的平均距離較大，這符合了SAGA的要求，即在進(jìn)化前期，不要一味地將適應(yīng)度值差的個(gè)體淘汰掉，而是要通過交叉和變異將個(gè)體改良，這樣既增加了種群的多樣性，又不至于產(chǎn)生局部最優(yōu)化，導(dǎo)致引起的早期收斂現(xiàn)象。而從第40代往后，個(gè)體之間的平均距離減小，這意味著代與代之間的差異性較小，全局最優(yōu)解基本產(chǎn)生了。

通過圖8所示可以清晰地看到自適應(yīng)算法在算完100代之后，這其中的每一代的具體情況，圖8中每一條的垂直線表示每一代中各點(diǎn)適應(yīng)度值由最小到最大的范圍，在圖形的下方所看到的一條曲折的線是遺傳算法在完成進(jìn)化100代之后平均適應(yīng)度值演化趨勢。40代之前，每一代的種群之間適應(yīng)度差異較大，所以線條長度較長;而40代之后，差異性迅速縮小并趨于穩(wěn)定化，所以線條長度較短。與此相對應(yīng)的是平均適應(yīng)度也由較大范圍的變化逐漸縮小并最終趨于穩(wěn)定。這說明當(dāng)變異數(shù)減小時(shí)，適應(yīng)度值的范圍也減小，這些圖形顯示減小變異數(shù)，也就減小了子輩的多樣性，加快了收斂速度，這說明全局最優(yōu)解接近產(chǎn)生了。

5 結(jié)語

本文提出改進(jìn)的自適應(yīng)遺傳算法(SAGA)，不僅克服了傳統(tǒng)遺傳算法的早熟和收斂速度慢問題，而且大幅度提高遺傳算法的工作效率。此方法應(yīng)用于堆垛機(jī)的路徑規(guī)劃，可提高堆垛機(jī)的路徑規(guī)劃質(zhì)量和工作效率。通過Matlab遺傳算法工具箱的仿真，進(jìn)一步驗(yàn)證了此方法的有效性和可行性。通過自動(dòng)化立體倉庫技術(shù)和軟件技術(shù)實(shí)現(xiàn)對物料的智能化管理，減少產(chǎn)品積壓，提高機(jī)床制造企業(yè)在激烈市場中的競爭能力。

［1］馬千里.機(jī)床制造企業(yè)立體倉庫信息管理系統(tǒng)研究［J］.控制管理，2008，4(3):5 －7.

［2］華紅艷，張丹.基于蟻群算法的自動(dòng)化立體倉庫路徑優(yōu)化［J］.計(jì)算機(jī)技術(shù)與自動(dòng)化，2010，29(1):51 －54.

［3］杜宗宗，劉國棟.基于混合模擬退火算法求解TSP問題［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(29):40 －42.

［4］陸文，郭延濤，李文杰.基于改進(jìn)遺傳算法的車間調(diào)度問題求解［J］.現(xiàn)代制造工程，2010(10):35－37.

［5］王清校，郎茂祥，彭永昭，等.基于禁忌搜索算法的貨物運(yùn)輸路徑和方式選擇問題研究［J］.物流技術(shù)，2010(12):96－98.

［6］孫樹棟，曲彥賓.遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用研究［J］.西北工業(yè)大學(xué)學(xué)報(bào)，1998，16(1):79 －83.

［7］SRINVAS M，PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithms［J］.IEEE Trans on Systems，Man and Cybernetics，1992，24(6):656 －667.

［8］張京釗，江濤.改進(jìn)的自適應(yīng)遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(11):53 －55.

［9］任子武，傘冶.自適應(yīng)遺傳算法的改進(jìn)及在系統(tǒng)辨識中應(yīng)用研究［J］.系統(tǒng)仿真學(xué)報(bào)，2006，18(1):41 －46.

［10］張國強(qiáng)，彭曉明.自適應(yīng)遺傳算法的改進(jìn)與應(yīng)用［J］.艦船電子工程，2010(1):83－84.