基于粒子群算法的鋼板倒垛優(yōu)化

朱 軍，王 躍，卓 杰

（連云港杰瑞深軟科技有限公司，連云港 222006）

鋼板堆場(chǎng)是船廠鋼板原材料進(jìn)料、分類堆放、保管、預(yù)處理和出料的場(chǎng)地，是整個(gè)總裝化生產(chǎn)系統(tǒng)的物流和信息流的源頭，與船廠所有工程及生產(chǎn)工程有聯(lián)系，確保鋼板的穩(wěn)定物流是至關(guān)重要的，其信息化和自動(dòng)化程度的高低對(duì)整個(gè)生產(chǎn)效率的提高有重要影響。

由于目前國(guó)內(nèi)各大船廠的鋼板堆場(chǎng)管理處在手工作業(yè)或半手工作業(yè)狀態(tài)，鋼板堆場(chǎng)存放的鋼板品種多、量大、周期長(zhǎng)；堆場(chǎng)的環(huán)境惡劣，鋼板的標(biāo)識(shí)、跟蹤困難，并且大部分船廠沒有對(duì)堆場(chǎng)進(jìn)行科學(xué)、合理的規(guī)劃，鋼板的堆放隨意性大，不能及時(shí)地將鋼板進(jìn)行定位以及不能快速地將鋼板從堆場(chǎng)中按照最優(yōu)化的路徑進(jìn)行出入庫操作，因此亟需一種優(yōu)化手段對(duì)其進(jìn)行優(yōu)化改善[1]。

工程實(shí)踐中有很多目標(biāo)優(yōu)化問題，多目標(biāo)優(yōu)化問題中各目標(biāo)之間通常相互制約，對(duì)其中一個(gè)目標(biāo)優(yōu)化經(jīng)常以犧牲其它目標(biāo)為代價(jià)，因此很難評(píng)價(jià)多目標(biāo)問題解的優(yōu)劣性。一般來說，多目標(biāo)優(yōu)化問題并不存在唯一最優(yōu)解，其多個(gè)目標(biāo)不可能同時(shí)達(dá)到最優(yōu)。與傳統(tǒng)的優(yōu)化算法相比較，粒子群算法是一種簡(jiǎn)單有效的仿生算法，具有基于多點(diǎn)并行搜索的特性。

1 粒子群算法原理

粒子群算法，也稱粒子群優(yōu)化算法PSO，是近年來由J.Kennedy和R.C.Eberhart等開發(fā)的一種新的進(jìn)化算法。PSO算法屬于進(jìn)化算法的一種，和模擬退火算法相似，它也是從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解，通過適應(yīng)度來評(píng)價(jià)解的品質(zhì)，但它比遺傳算法規(guī)則更為簡(jiǎn)單，它沒有遺傳算法交叉和變異操作，它通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)。這種算法以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實(shí)際問題中展示了其優(yōu)越性。

PSO同遺傳算法類似，是一種基于迭代的優(yōu)化算法。系統(tǒng)初始化為一組隨機(jī)解，通過迭代搜尋最優(yōu)值。同遺傳算法比較，PSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒有許多參數(shù)需要調(diào)整。目前已廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。

2 鋼板倒垛問題描述

船廠鋼板管理系統(tǒng)針對(duì)造船廠鋼板的出入庫開發(fā)的系統(tǒng)軟件，主要由系統(tǒng)管理、鋼板管理以及工控網(wǎng)絡(luò)安全等模塊組成，通過掃描終端設(shè)備與外部交互，實(shí)現(xiàn)鋼板的數(shù)據(jù)采集、傳輸與更新。系統(tǒng)架構(gòu)如圖1所示。

根據(jù)訂單中鋼板的規(guī)格和數(shù)量，從堆場(chǎng)中選取合適的鋼板，由于堆場(chǎng)面積大，對(duì)位數(shù)量大，在鋼板出入庫過程中難免會(huì)出現(xiàn)所需要的鋼板不在當(dāng)前鋼板堆垛的頂端，在此過程中首先需要先對(duì)上方的鋼板進(jìn)行倒垛作業(yè)?？紤]到倒垛耗費(fèi)能量大和時(shí)間等因素，采用基于規(guī)則的知識(shí)推理方法為倒垛鋼板指定倒放堆位。鋼板堆垛狀態(tài)如圖2所示。在鋼板出庫優(yōu)化算法得到一組優(yōu)化出庫鋼板集合，根據(jù)計(jì)算公式得到相應(yīng)倒垛鋼板集合和倒垛鋼板的可選垛位集合為輸入?yún)?shù)[2]，通過離散粒子群優(yōu)化算法對(duì)倒垛問題空間進(jìn)行優(yōu)化，得到倒垛方案。

3 鋼板倒垛模型建立

從鋼板的出庫整體流程分析，鋼板的倒垛屬于內(nèi)層算法，從內(nèi)往外一層一層地對(duì)鋼板進(jìn)行操作[3]，來減少鋼板的出入庫時(shí)間，提高鋼板出入庫效率。鋼板出庫算法流程如圖3所示。

圖3 鋼板出庫算法流程Fig.3 Steel plate library algorithm flow chart

其實(shí)倒垛問題可看作是約束條件下任務(wù)指派問題，可以建立數(shù)學(xué)模型[4]。定義出庫鋼板序列X=｛xi∣xi∈V，i=1，2，3…，N｝，其中 i表示鋼板 xi出庫的作業(yè)次序。τ為出庫鋼板中可行出庫序列X的集合，τ中元素的數(shù)量由出庫鋼板在堆場(chǎng)中的分布情況確定。

圖4 出庫鋼板作業(yè)次序Fig.4 Out of the library operating sequence

以Stagej中提取第j張出庫鋼板xj為例，如果xj不是位于鋼板堆垛頂端，需要先對(duì)其上方的鋼板進(jìn)行倒垛作業(yè)。因此，Stagej實(shí)際上是包含提取xj以及由此產(chǎn)生的倒垛作業(yè)的作業(yè)決策子過程。

分析可知，第一組決策變量為指定的出庫鋼板集合，用向量X的形式表示為

式中：xi為從堆場(chǎng)中選擇出的出庫鋼板，i=1，2，…，N，表示xi出庫的次序。在堆場(chǎng)狀態(tài)已知的情況下，由X可以確定倒垛鋼板的集合M：

式中：mij為提取出庫鋼板xi需要移走的等j張倒垛鋼板。為M中鋼板指定倒放堆位，可得到另外一組集合Y：

式中：yij為rij的倒垛決策，rij為指提取出庫鋼板時(shí)，需要移走第j張倒垛鋼板。

在倒垛過程中需要遵循幾個(gè)原則：①倒垛鋼板應(yīng)避免將含有待出庫鋼板的垛位作為目標(biāo)垛位；②目標(biāo)垛位的選擇要遵循堆場(chǎng)管理要求和作業(yè)規(guī)則。

基于鋼板整體目標(biāo)，需要有約束條件對(duì)其進(jìn)行約束[5]：①選定的堆垛高度不能超過允許安全高度上限；②倒垛作業(yè)必須在一定范圍內(nèi)進(jìn)行，即倒垛鋼板當(dāng)前堆位與倒垛位之間不能超過一定的距離。

4 鋼板倒垛算法實(shí)現(xiàn)

PSO算法采用隨機(jī)產(chǎn)生初始粒子，通過迭代找到最優(yōu)解。在迭代過程中跟蹤2個(gè)極值來更新自己，找到最優(yōu)解。一個(gè)是粒子本身找到的最優(yōu)解—個(gè)體極值（pbest）；另一個(gè)就整個(gè)種群找到最優(yōu)解—全局最優(yōu)解（gbest）。

粒子信息可用向量進(jìn)行表示，第t代第i個(gè)粒子位置為

第t代第i個(gè)粒子速度：

因此粒子的位置和速度的更新方程為

式中：w為慣性系數(shù)，產(chǎn)生擾動(dòng)的作用，防止算法早熟收斂；c1，c2為學(xué)習(xí)因子，分別調(diào)節(jié)向個(gè)體最好粒子和全局最好粒子方向飛行的最大步長(zhǎng)；r1，r2為介于（0，1）之間的隨機(jī)數(shù)。

開始初始化粒子群中粒子的速度和位置，初始化個(gè)體最優(yōu)值與全局最優(yōu)值，根據(jù)公式更新其速度和位置。由于在優(yōu)化過程中，需要設(shè)定一個(gè)目標(biāo)的最大函數(shù)，在迭代過程中，用其減去目標(biāo)函數(shù)值（作業(yè)時(shí)間最小值），所得到的是粒子的適應(yīng)度。

5 仿真倒垛結(jié)果及分析

為驗(yàn)證粒子群算法倒垛的可行性，使用Matlab對(duì)粒子群算法進(jìn)行仿真，根據(jù)設(shè)定的初始粒子群和倒垛堆位集合，對(duì)鋼板倒垛所用的時(shí)間進(jìn)行了仿真，同時(shí)與未采用粒子群算法的人工鋼板倒垛進(jìn)行對(duì)比，在仿真圖上迭代次數(shù)來看，迭代次數(shù)越多作業(yè)時(shí)間越少，說明選擇的倒垛方案越優(yōu)，在迭代次數(shù)達(dá)到一定次數(shù)時(shí)，作業(yè)時(shí)間趨于平緩，說明在設(shè)計(jì)時(shí)有個(gè)最優(yōu)的終止條件，將迭代停止得到最優(yōu)方案。適應(yīng)度值仿真如圖5所示。

圖5 適應(yīng)度值仿真Fig.5 Fitness simulation

此外Matlab對(duì)粒子群算法仿真和人工倒板決策進(jìn)行對(duì)比，得出結(jié)論是使用粒子群算法的倒垛方案比人工倒板方案的效率更高、作業(yè)時(shí)間更短、收斂速度和尋優(yōu)速度都更快。鋼板倒垛方案比較結(jié)果如表1所示。

表1 鋼板倒垛方案比較Tab.1 Comparison of steel plate stacking scheme

6 結(jié)語

在分析鋼板堆場(chǎng)目前狀況的情況下，基于鋼板出庫流程和優(yōu)化過程的研究，以及解決鋼板倒垛問題時(shí)存在諸多不足之處的基礎(chǔ)上，本文對(duì)鋼板出庫過程中的鋼板倒垛過程進(jìn)一步研究，提出了適用于船廠鋼板倒垛的粒子群算法，將鋼板倒垛問題轉(zhuǎn)化為求解最大值問題。通過仿真模擬與人工決策相對(duì)比，并改變仿真參數(shù)，得到鋼板倒垛適應(yīng)度值仿真模擬圖，有效地提高了鋼板倒垛的效率，減少作業(yè)時(shí)間，證明了該算法具有較好的實(shí)用性和高效性。

[1]楊乃忠.寶鋼厚板生產(chǎn)物流分析及改進(jìn)措施[D].沈陽：東北大學(xué)，2008.

[2]王龍.造船廠鋼板出庫計(jì)劃并行嵌套優(yōu)化算法研究[D].大連：大連理工大學(xué)，2011.

[3]張志英，王維澤，侯俊.船廠鋼板堆場(chǎng)多時(shí)段作業(yè)計(jì)劃優(yōu)化[J].哈爾濱工程大學(xué)學(xué)報(bào)，2015（5）：638-643.

[4]鄭武全，馮定忠，姜懿.鋼板倒垛問題的一種頂層搜索算法[J].機(jī)械設(shè)計(jì)與制造工程，2013（2）：61-64.

[5]金淳，王廣民，高鵬.造船廠鋼板出庫作業(yè)計(jì)劃的建模及優(yōu)化研究[J].工業(yè)工程與管理，2009（6）：12-17.