周耿烈 馮無恙 胡赤兵②
(①蘭州理工大學(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)。
假設(shè)堆垛機(jī)的工作空間(立體倉庫)用二維平面圖形來表示。堆垛機(jī)執(zhí)行一次任務(wù)時(shí)所不能通過的貨格的位置已知。用尺寸相同的柵格對立體倉庫進(jìn)行劃分。若某一柵格內(nèi)不含任何障礙物,則稱此柵格為自由柵格;反之,稱之為障礙柵格[6]。如圖1所示。
遺傳算法是一種借鑒生物界自然選擇和自然選擇機(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)象。
采用序號法?;卷樞蚴菑淖蟮接?,從下到上。將立體倉庫分為若干個(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)。
在選取初始種群時(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ī)劃出最短路徑。
在這里選取如下所示的個(gè)體適應(yīng)度函數(shù):
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),直至符合要求。
采用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)生了。
本文提出改進(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.