張 鴿 張 弘李宗亮

（1.西安郵電大學自動化學院 西安 710121）（2.北京建工集團有限責任公司 北京 100055）

1 引言

塔吊以其工作效率高，使用范圍廣等特點，成為使用最為廣泛的建筑工程機械。塔吊資源的調度與運輸是建筑項目中不可缺少的環(huán)節(jié)。目前工地上對塔吊裝載物料的分配還處于簡單的人工決策階段，浪費大量時間的同時還經常造成分配不均，從而導致建設項目進度滯后，不得已采取加班保證工期的手段。合理的裝載方案不僅可以降低運輸成本，而且能夠大大提高塔吊的作業(yè)效率，有效地提高施工企業(yè)的經濟效益和競爭力。因此，找到一種合理的塔吊裝載方案十分必要。

塔吊的裝載問題是一個復雜的工程應用問題，建筑材料的大小、形狀、材料是否可以同時裝載等都決定了在裝載時可以采取的不同策略，也就形成了不同子類別的裝載問題。求解裝載問題的方法有貪心算法［1］、遺傳算法［2］、動態(tài)規(guī)劃算法［3］等，這些算法均能找到問題的最優(yōu)解，但也均有各自的局限性和缺陷［4］。因此，本文采用一種新的算法—混合遺傳算法［5］，來求解塔吊裝載問題，尋求一種裝載總價值最大的解決方法。通過實例驗證表明，該混合遺傳算法裝載總價值大且求解速度、收斂速度快，能夠很好地實現物料裝載的合理分配。

2 裝載問題的數學模型

裝載問題的定義：假設某施工現場有n種建筑材料需要用同一塔吊進行裝載起吊，其中物料i的重量為wi，該類物料的價值為vi?，F在需要求解一種裝載方案，尋求對承載總量為W的塔吊，如何運載物料才能使裝載的物料總價值最大。

此類裝載問題類似于0-1背包問題，即向一個背包中裝入該類物品，求解能裝入最大價值物品的解決方案。此類問題的求解過程可以看作一系列決策的過程，即決策所給定的物料中哪些應載入塔吊，哪些不能載入塔吊。借助背包問題的基本思想，將本文涉及的問題抽象化，并形式化描述為如下問題：

W＞0,wi＞0,vi＞0(1 ≤i≤n )，要找出另一 n元向量，1表示選用該材料，0表示不選該材料。

由此，塔吊裝載問題可以表示為0-1整數規(guī)劃問題：

且滿足以下兩個約束條件：

3 求解裝載問題的兩種基本算法

3.1 遺傳算法求解裝載問題

由于裝載問題是一個典型的組合最優(yōu)化問題，遺傳算法是解決搜索問題的一種通用算法，它通過模擬自然進化過程搜索到最優(yōu)解。因此，我們可以將此算法應用于裝載問題。遺傳算法應用于裝載問題時，涉及到約束條件滿足下的遺傳編碼方法，以及選擇、交叉、變異操作算子的設計等方面［6］。遺傳算法求解塔吊裝載問題的基本原理為通過隨機方式為物料進行編碼，形成初始群體，若載入塔吊，編碼為1；不載入塔吊，編碼為0。通過適應度函數對每個個體進行數值評價，選出高適應度的個體進行遺傳操作，從而形成下一代新的種群。

3.2 貪心算法求解裝載問題

常用的貪心準則是價值密度（價值重量比viwi）貪心算法，這種選擇準則為從剩余物料中選擇可載入塔吊的viwi值最大的物品，這也是最常用的貪心策略［8］。

4 混合遺傳算法求解裝載問題

4.1 問題描述

簡單遺傳算法在求解塔吊裝載問題的搜索過程中，由于該個體的適應值大大優(yōu)于當前種群的平均適應值，使進化初期的超常個體可能限制了其他個體進化，根據遺傳算法適者生存的原理，使得該個體迅速充滿整個種群，種群的多樣性大大降低，導致種群的進化停滯，從而出現算法收斂于局部最優(yōu)解的早熟現象，基于以上問題，本文提出一種將貪心算法與遺傳算法相結合的混合遺傳算法，應用到塔吊裝載問題中，充分利用貪心算法的修正以及遺傳算法的擇優(yōu)，不斷重復執(zhí)行選擇、雜交和變異，從而得到最優(yōu)個體，這個個體可能就是裝載問題的最優(yōu)解。

4.2 算法流程圖

該混合遺傳算法流程圖如圖1所示。

圖1 混合遺傳算法流程圖

根據塔吊在承載量約束限制之內求解所載物料的最優(yōu)解和最大總價值。具體步驟如下：

1）基因編碼及物料初始化

本文使用等長度的二進制編碼對由n個物料xi的值順序排列構成的裝載問題進行遺傳編碼，編碼串中1表示將對應的物料載入塔吊中，0表示不載入。

分別調整紡絲組件壓力和改變PE、PA6兩組分比例，當紡絲熔體從復合紡絲組件噴絲孔中擠出，達到穩(wěn)定狀態(tài)后，剪取噴絲板下約1 m位置的初生絲，用纖維切片器制得纖維截面樣品，在雙目纖維鏡下觀察纖維截面形狀。繼續(xù)PE/PA6皮芯型復合纖維FDY紡絲試驗，觀察紡絲狀況變化。

例如“101010”就代表一個解，它表示將第1，3，5號物料載入塔吊中，其他的物料則不載入。

2）編碼修復

解決塔吊裝載問題的關鍵是處理好約束條件。我們利用貪心算法的思想對那些不滿足約束條件的基因編碼串進行修復。其基本思想是優(yōu)先載入（viwi）較大且 xi=1的物料，直到滿足塔吊的承載量約束為止。對于基因編碼串中指示應該裝入而已經裝不下的物料，修改其基因編碼串對應的xi為0［9］。這樣就可以產生一些新的并且滿足塔吊裝載問題約束條件的基因編碼串。

3）適應度函數

適應度函數是遺傳算法進化過程的驅動力，也是進化自然選擇的唯一標準［10］。由于對每種物料使用貪心算法修正已保證了不會產生無效的數據，所以在進行物料適應度評價時直接用目標函數值作為適應度函數值，即

4）選擇

選擇操作的任務就是從父代群體中選取一些個體，遺傳到下一代群體［11］。本文采用輪盤賭的方式進行選擇［12］。其基本思想是每件物料被選中的概率與其適應度函數值大小成正比［13］。設共有N件物料，物料xi的適應度為 f()xi，則物料 xi的選擇概率為

5）交叉

交叉是指把兩個父個體的部分結構加以替換重組而產生新的個體［14］。論文采用單點交叉方式，具體操作方法為在基因串中以概率Pc選擇一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并產生新個體［15］。

為了使求得的解最優(yōu)且收斂速度快，根據經驗本文選用的交叉概率Pc=0.4。

6）變異

變異是指子代基因按小概率（即選擇相對較少的個體產生變異，這樣即能保證種群的多樣性，又不至于過多地丟失父代中有價值的信息）擾動產生的變化［6］。為了求得最優(yōu)解并且保證種群的多樣性，本文中使用一個較小的值如Pm=0.02。

5 實例分析

某施工現場用承載量為2000kg的塔吊裝載20件物料，載入的物料不可分割，求使得在塔吊承載量約束限制之內所載物料的最優(yōu)解和最大總價值。每種物料的重量和價值如表1所示。

表1 物料參數信息表

本文分別用貪心算法、基本遺傳算法和基于貪心算法的混合遺傳算法來求解塔吊裝載問題，3種算法解決裝載問題的運行結果如表2所示。算法運行參數設定：交叉概率Pc=0.4，變異概率Pm=0.02，終止進化代數為1000。

表2 3種方法解決裝載問題的運行結果比較

從表2看出，采用上述3種方法，在運行參數一定情況下，改進的遺傳算法較簡單的遺傳算法將塔吊的總價值增加了46。進而驗證了混合遺傳算法在求解塔吊裝載問題的可行性。通過程序運行時間的對比，改進后的算法較2種基本算法求解速度更快，驗證了混合遺傳算法在求解塔吊裝載問題的高效性。

基于Matlab軟件環(huán)境對該裝載問題進行了仿真［16］，結果如圖2所示。（a）和（b）分別為遺傳算法和混合遺傳算法的仿真圖，從圖中可以看出，將貪心算法的思想融入到混合遺傳算法中，在求解塔吊裝載問題時，塔吊的總價值較單一的遺傳算法更優(yōu)，并且求解速度更快。與單一的遺傳算法相比，運行速度提高了1/2，相對于貪心算法，運行速度提高了1/5。因此，混合遺傳算法相對于貪心算法和基本遺傳算法在求解塔吊裝載問題上效果更好。

圖2 2種算法仿真圖

6 結語

塔吊的裝載問題一直是建筑行業(yè)工程施工的一大難題，是嚴重影響施工企業(yè)的經濟效益的一個重要因素。本文應用遺傳算法進行優(yōu)化處理并將貪心算法引入到遺傳算法中，避免了在尋優(yōu)過程中出現局部最優(yōu)。實例分析表明，在塔吊承載范圍內，混合遺傳算法實現了對塔吊裝載問題的合理分配，且該算法求解速度快，所以，該算法是求解塔吊裝載問題的一種有效算法，能有效緩解人工制訂塔吊裝載物料計劃所造成的物料分配不均、浪費時間等現象，提升了塔吊作業(yè)效益。