遺傳帝國競爭混合算法在裝配序列規劃中的研究與應用

黃豐云，熊 雄，周 錚，蔣園健

（武漢理工大學機電工程學院，湖北 武漢 430000）

1 引言

裝配序列規劃（Assembly Sequence Planning，ASP）是裝配工藝規劃中的重要內容，裝配序列的優劣將直接影響到裝配工藝，進而影響裝配成本，因此對ASP問題的研究有重要意義。在已有的裝配序列規劃方法中，智能優化算法是一種常見的ASP求解方法。文獻[1]基于拆卸法原理，通過拆卸矩陣得到可行合理的可拆卸候選集，來指導裝配序列的構造，保證了序列的幾何可行性，并用蟻群算法優化得到最優裝配序列。文獻[2]將粒子群算法應用于復雜產品裝配序列規劃，通過采用新的學習機制來改進算法，增強了算法的搜索能力。文獻[3]也通過引入拆卸矩陣，使得裝配過程中重定向次數和裝配工具轉換次數等降到最低，并用遺傳算法求解得到最優裝配序列。文獻[4]利用有向圖法獲得了表達裝配關系的矩陣，并依據矩陣來建立評價序列優劣的標準，對帝國競爭算法進行了研究與改進來求解最優裝配序列。

近年來，除了用單一算法進行裝配序列規劃外，許多研究者將不同種算法融合來求解ASP問題。文獻[5]建立蟻群遺傳混合算法求解ASP問題，先用蟻群算法產生初始序列，再使用遺傳算法對蟻群算法的初始序列進行優化，根據優化解生成蟻群算法中螞蟻的信息素，通過加速蟻群算法最優解信息的積累來更快地得到最優裝配序列。文獻[6]在分析可行裝配序列的推理約束條件后，建立了考慮穩定性、聚合性及裝配方向改變次數三個因素的優化評價模型，以遺傳模擬退火混合算法求解最優裝配序列。文獻[7]將幾何可行性和一致性設計作為約束條件，再將可裝配性和這兩個約束結合起來建立目標函數，提出一種結合免疫算法和粒子群優化算法的裝配序列規劃方法。文獻[8]將帝國競爭算法和遺傳算法混合來求解ASP問題，首先利用帝國競爭算法產生可行的裝配序列作為遺傳算法初始種群，然后調用遺傳算法繼續迭代，達到最大迭代次數后輸出最優裝配序列。

相對于單一的算法，混合算法在求解ASP問題上表現出更大的優勢，它綜合了各自算法的優缺點，搜索能力更強。例如，遺傳算法具有良好的全局搜索能力，可擴展性強，容易與其他算法結合的優點，但是其局部搜索能力較差，導致利用單一算法求解比較費時，在算法執行后期搜索效率較低，容易產生早熟收斂的問題。模擬退火算法具有良好的局部搜索能力，但他對整個搜索空間的拓展性不夠好，因此全局搜索能力不夠強，運算效率不夠高。文獻[6]正是利用遺傳算法的全局搜索能力與模擬退火算法的局部搜索能力，提出遺傳模擬退火混合算法，快速獲得最優裝配序列。

帝國競爭算法[9]（Imperialist Competitive Algorithm，ICA）是Atashpaz-Gargari和Lucas于2007年提出了一種通過模擬殖民地同化機制和帝國競爭機制而形成的新的智能優化算法。ICA在尋優方面有著很好的全局搜索能力和信息不依賴的尋優性能，算法利用同化機制讓殖民地向其所屬帝國移動進行局部搜索，保證了算法的局部搜索能力。同時，ICA中帝國競爭操作使帝國的殖民地可以分配到其他帝國，突破了原有的搜索界限，增加了國家的多樣性，可以避免“早熟”現象的發生。利用帝國競爭算法的良好局部搜索能力，遺傳算法的較強全局搜索能力和可擴展性，提出遺傳帝國競爭混合算法。不同于文獻[8]中對ICA設定固定的迭代次數，在ICA達到設定迭代次數后將產生國家作為遺傳算法初始種群，利用遺傳算法繼續尋優，直到達到規定最大迭代次數，算法終止。以遺傳算法作為初始算法，迭代一定次數后的序列作為帝國競爭算法的初始帝國，轉至帝國競爭算法繼續尋優，在帝國競爭算法迭代過程中，達到某種條件時，認為算法陷入局部最優，更新遺傳算法種群，再調用遺傳算法繼續尋優。交替執行兩種算法，直到達到算法停止條件，輸出混合算法最優裝配序列。

2 系統整體架構

在進行裝配序列規劃時，首先根據CAD產品的裝配模型，獲得裝配的裝配有向圖和裝配連接圖，并根據圖推理獲得裝配干涉矩陣、連接矩陣等，根據各矩陣構建表達綜合成本的適應度函數，適應度函數值越低，說明綜合成本越低，裝配序列越優?；旌纤惴ㄒ匝b配綜合成本最低為目標，進行混合迭代，當達到算法終止條件時，輸出結果?；诨旌纤惴ǖ难b配序列規劃系統整體架構，如圖1所示。

圖1 基于混合算法的裝配序列規劃方法整體架構Fig.1 An Overall Architecture of Assembly Sequence Planning Method Based on Hybrid Algorithms

3 適應度函數構造

在ASP問題中，首先要保證的是裝配序列可行，然后，綜合考慮裝配序列可行性、裝配序列穩定性、裝配重定向性和裝配聚合性。量化各項指標的計算方法，通過加權處理得到綜合適應度函數，為最優裝配序列生成提供計算依據。

3.1 裝配序列的可行性

在空間直角坐標系中，零件的基本裝配方向有d(k)={+x，-x，+y，-y，+z，-z}={d k}六個方向，建立零件在空間直角坐標系中的干涉矩陣，其中，k為裝配方向，a ij為零件P j沿k方向裝配到位時與零件P i的干涉情況，其取值為：

定義I k(P i)(k=1,2,3,4,5,6)為零件P i沿k方向運動到裝配位置時與已裝配好的各零件之間的干涉值之和，若I k(P i)=0，則零件P i可沿方向k進行裝

定義V g為所有零件裝配到位后的干涉值之和，則有：

判斷一個裝配序列是否可行的依據是：如果V g=0，裝配序列可行，如果V g≠0，則裝配序列不可行。

3.2 裝配序列的穩定性

裝配序列的穩定性是指零件或子裝配體參與裝配中，零件與零件之間，零件與子裝配之間在自身重力和夾具等產生的裝配力作用下，保持裝配零件穩定性的能力[10]。裝配序列的穩定性體現了裝配的安全性和可靠性。

為量化表示裝配序列的穩定性，建立裝配體的連接矩陣C=其中c i j表示零件P i與零件P j的連接關系，其取值為：

穩定連接表示零件之間通過緊固件或者是過盈配合連接，接觸連接表示零件之間相互接觸但必須有外力才能保持穩定的連接。裝配序列穩定性的表示為：

式中：n—零件的個數；S ji—零件P i的穩定性，這里的裝配序列穩定性不僅考慮了序列中零件與相鄰零件之間的穩定性，還考慮了零件與已經裝配好的零件間的穩定性，更符合實際。S ji的取值與c ij的取值相同。顯然，V s越大，裝配序列越穩定。

3.3 裝配的重定向性

裝配的重定向性表示了裝配方向的改變次數，裝配方向的改變次數越多，操作越復雜，裝配效率越低。建立零件的裝配方向矩陣其取值為：

裝配方向的改變次數V d的求解算法如下：

（1）令i=0,m=1,V d=0；

（3）令i=i+m+1，如果i

（4）結束。

V d越小，裝配的方向改變次數越少，裝配序列越好。

3.4 裝配的聚合性

裝配的聚合性表示裝配過程中裝配工具的改變次數，根據實際情況，建立裝配工具集矩陣，則裝配工具改變次數V t的求解算法為：

（1）令i=0,m=1,V t=0；

（2）若T(i+m)=t i+m=k（k為裝配方向），但T(i+m+1)=t i+m+1≠k，則在裝配零件P i+m+1時需要改變裝配工具，V t=V t+1，轉至步驟（3），否則，令m=m+1，如果i+m+1

（3）令i=i+m+1，如果i

（4）結束。

V t越小，裝配的工具改變次數越少，裝配序列越好。

3.5 建立適應度函數

綜合考慮裝配序列的可行性、裝配序列的穩定性、裝配序列的重定向性、裝配序列的聚合性，可建立對這些評價指標加權的適應度函數，如下：

式中：ω1，ω2，ω3，ω4—各 項指標的權重系數。

適應度值越小，表示綜合裝配成本越低，裝配序列越好。

4 基于遺傳帝國競爭混合算法的ASP尋優

針對ASP問題的特點，在進行混合算法求解ASP問題時，對遺傳算法和帝國競爭算法做以下改進：

（1）對零件序列的編碼采用十進制實數編碼，遺傳算法中的種群個體、帝國競爭算法中的國家和殖民地位置為零件組成的序列。

（2）在遺傳算法中引入最佳個體保留策略，最佳個體保留策略的操作過程如下：

找出當前代中最好的（最優的裝配序列）和最差的個體；若當前代所有種群中最好個體比迄今為止的最好個體還要優，則以這個個體作為新的迄今為止的最好個體；用迄今為止的最好個體替換掉當前群體中的最差個體。

（3）在帝國競爭中，改變標準帝國競爭算法中將權利最弱的帝國的殖民地分配給權利最高的帝國，采用賭輪選擇法，隨機選擇帝國分配殖民地，可防止算法早熟。

4.1 基于遺傳算法的ASP求解過程

遺傳算法作為混合的初始迭代算法，其作用是：產生初始較優的序列作為帝國競爭算法的初始帝國；在帝國競爭算法陷入局部最優時，調用遺傳算法，增加局部搜索能力。

遺傳算法的求解過程如下：

（1）設置初始參數，包括種群數量Q，交叉概率P c和變異概率P m，迭代次數T。

（2）隨機生成Q個父代個體，并將父代按適應度值從小到大順序排列（適應度值越小，序列越優），記錄父代對應的標簽。

（3）對父代進行選擇操作。

（4）對選擇的父代進行交叉、變異操作，獲得子代裝配序列，并計算適應度值。

（5）把所有的父代子代個體放在一起，按最佳個體保留策略操作，并計算所有個體適應度值，迭代次數加1。

（6）當迭代次數未達到T時，轉至（3），當迭代次數達到T時，選擇最優（適應度值最低）的前λ個個體，作為帝國競爭算法的初始帝國，調用帝國競爭算法。

4.2 基于帝國競爭算法的ASP求解過程

4.2.1 建立初始帝國

在混合算法中，帝國競爭算法選擇遺傳算法中前λ個最優個體作為帝國競爭算法初始帝國，并隨機生成N pop-λ個初始國家，計算每個國家的權利，在ASP問題中，權利的大小與適應度函數有關，適應度函數值越小，權利值越大。

式中：c i—第i個國家的權利；fitness(i)為第i個國家的適應度值。

對計算的權利值進行排序，選擇權利值最大的前N imp個國家作為初始帝國，其余的N col個國家作為初始殖民地。

對初始帝國權利歸一化處理

式中：p n和c n—第n個帝國的歸一化權利和標準權利，根據帝國的歸一化權利，分配殖民地，第n個帝國的殖民地數量為：

其中，round為四舍五入取整。

4.2.2 殖民地同化

殖民地同化過程采用部分匹配交叉（Partially Matching Cross‐over，PMX）算法交叉M次，其中，部分匹配交叉（Partially Matching Crossover，PMX）算法的處理過程如下：

假設帝國的位置為( 1，2，3，4，5，6，7，8)，殖民地的位置為(2，3，5，1，6，7，8，4)，首先隨機選擇兩個交叉的點，假如第一個隨機選擇的交叉點位置為4，第二個交叉點位置為6，將這兩個點之間的位置將進行交叉，其它的位置進行復制或者用相匹配的數進行替換。在此實例中，第一個父代個體中456被選中，第二個父代個體中167被選中。那么4與1，5與6，6與7相匹配。匹配過程，如圖2所示。

圖2 PMX交叉操作Fig.2 PMX Crossover Operation

首先將456與167分別加入到子代2和子代1中相應的位置，然后將其他位置上的數字直接復制到相應的后代中，如果該數字已經在該子代中已經存在，則用相應的匹配法則進行替換，最終得到兩個新的子代，選擇兩個子代中權利較大的個體，替換原來的殖民地成為同化殖民地。

4.2.3 殖民地革命

殖民地革命過程采用交換變異（Exchange Mutation，EM）算法變異R次，即從殖民地個體中選擇兩個基因位置，然后互換這兩個位置的基因，得到新的殖民地。為了更好的保持殖民地的多樣性，綜合考慮到迭代次數和帝國權利大小，設計殖民地革命概率動態調節公式：

式中：p r—革命概率；ξ—調節系數；d—當前迭代次數；Gmax—最大迭代次數—帝國i的殖民地歸一化權利—帝國i的最大歸一化權利。在式（12）中，權利越小的殖民地，革命的概率越大，這樣可以促進解的不斷優化，在算法迭代后期，革命概率會變大，可增加搜索范圍，避免算法陷入局部最優，增強全局搜索能力。

在完成殖民地同化和革命操作后，對所有帝國及其所屬殖民地，檢查帝國和殖民地的權利大小，如果存在殖民地權利大于其帝國權利，交換殖民地與帝國位置來更新帝國。

4.2.4 帝國競爭

帝國競爭算法中帝國之間的競爭是算法收斂的關鍵步驟，帝國競爭實際上是帝國所屬殖民地的再分配過程，通過競爭，權利較大的帝國獲得更多的殖民地，相應的，權利最小的帝國不斷失去殖民地，當其殖民地全部消失時，該帝國消失。帝國競爭過程如下：

（1）計算帝國總權利。帝國的權利由該帝國的權利和帝國所屬殖民地的平均權利的加權和組成，公式為：

式中：TR n—第n個帝國的總權利；δ—權利系數；p n—帝國的權利；p n j—帝國的殖民地j的權利；N R n—帝國殖民地的個數。

（2）帝國權利的歸一化。第n個帝國的歸一化權利TP n計算公式如下：

（3）根據歸一化的帝國權利，賭輪選擇分配權利最弱殖民地的帝國i。帝國競爭算法通過不斷的殖民地同化、革命，帝國競爭，最終只剩下一個帝國，即得到算法最優解。

4.2.5 混合算法中帝國競爭算法計算流程

帝國競爭算法在經過反復殖民地同化、革命，帝國競爭后，不斷收斂到最優解，當只有一個帝國后，算法達到終止條件，也可以用迭代次數作為終止條件，此處以迭代次數作為終止條件?；旌纤惴ㄖ械蹏偁幩惴ǖ挠嬎懔鞒虉D，如圖3所示。

圖3 改進帝國競爭算法流程圖Fig.3 Improved Imperial Competition Algorithms Flow Chart

計算流程如下：

（1）設置帝國競爭算法的初始參數，包括算法的初始國家數量N pop-λ，初始帝國的數量N imp，從遺傳算法中選擇前λ個最優個體作為帝國競爭算法初始帝國，調節系數為ξ，權利系數為δ，最小和最大迭代次數Gmin和Gmax，殖民地同化操作次數M，革命操作次數R，當前迭代代數K=K+T。

（2）計算N pop-λ個國家的適應度值，并按適應度值升序排列。當λ≤N imp時，從N po p-λ個國家中再挑選出適應度值最低的前N imp-λ個作為初始帝國，使初始帝國數量達到N imp，初始殖民地數量為N pop-N im p；當λ>N imp時，按適應度值升序從λ個中選取N imp個作為初始帝國，將剩下的λ-N imp個并入到初始國家中。

（3）所有帝國和殖民地進行同化、革命和競爭操作。

（4）計算所有帝國和殖民地的位置和適應度值，迭代代數K=K+1。

（5）當帝國競爭算法迭代代數K未達到Gmin時，繼續進行（3）操作；在K達到Gmin時，且滿足調用條件（見4.3.1節）時，調用遺傳算法，更新迭代代數K=K+T；當K達到Gmax時，終止帝國競爭算法操作。

4.3 基于遺傳帝國競爭混合算法的裝配序列規劃

4.3.1 遺傳帝國競爭算法融合策略

在算法開始時，采用遺傳算法迭代T次，計算所有序列的適應度值，并根據適應度從小到大順序取出前λ個個體，作為帝國競爭算法初始帝國，并隨機生成N pop-λ個初始國家，開始執行帝國競爭算法。當帝國競爭算法在執行過程中陷入局部最優時，調用遺傳算法提高局部搜索能力。混合算法的融合策略如下：

（1）設定遺傳算法迭代次數T，當達到T時，將產生的序列作為帝國競爭算法的初始帝國，并隨機生成N po p-λ個初始國家，開始執行帝國競爭算法。

（2）設定帝國競爭算法的最小和最大迭代次數Gmin和Gmax。

（3）在帝國競爭算法執行過程中，對于?G i，G min≤G i≤G max時，對于最佳帝國，若其后的連續n代( )Gmin≤G i+n≤Gmax，n=1，2...，都存在Δf i+n-1-Δf i+n<τ，則可認為帝國競爭算法中帝國競爭已停滯，算法陷入局部最優，此時需要調用遺傳算法提高局部搜索能力。其中為第i代帝國的平均適應度值，為第i代帝國的最小適應度值）。

4.3.2 混合算法的裝配序列更新策略

在混合算法執行的過程中，存在遺傳算迭代T次后，執行帝國競爭算法，以及帝國競爭算法在陷入局部最優時調用遺傳算法的過程。但是，在帝國競爭算法執行階段，遺傳算法并未進行全局搜索，其裝配序列也未改變，在調用遺傳算法時，需要及時更新遺傳算法的裝配序列，同理，在遺傳算法執行過程中，帝國競爭算法也未執行，其裝配序列也未更新。因此，需要對混合算法相互調用時裝配序列更新做研究。針對ASP問題的特點，同時兼顧考慮算法局部搜索時，保持種群的多樣性，提高局部搜索能力，定義如下的裝配序列更新策略。

（1）帝國競爭算法執行后調用遺傳算法時，選擇權利值最高的前α個國家和殖民地加入遺傳算法種群中，按賭輪選擇法從遺傳算法種群隨機刪除α個個體，執行遺傳算法；

（2）遺傳算法迭代T次后，執行帝國競爭算法時，選擇最優的前β(β≤Nimp)個個體替換最弱的β個帝國，執行帝國競爭算法。

基于如上策略，保證了混合算法迭代過程中序列的及時更新，同時增加了群體的多樣性，提高了局部搜索能力。

4.3.3 混合算法的計算流程

（1）設置算法初始參數，包括P c，P m，λ，n，N pop，N im p，τ，α，β，K等。

（2）執行遺傳算法，計算每一個種群個體的適應度，記錄對應的序列。

（3）判斷遺傳算法迭代次數是否達到T，若是，從遺傳算法所有父代與子代個體中取出前λ個作為帝國競爭算法初始帝國，并隨機生成N pop-λ個初始國家，開始執行帝國競爭算法，按4.2.5節方法更新帝國競爭算法迭代代數K；若否，繼續執行遺傳算法。

（4）判斷帝國競爭算法迭代數K是否達到Gmin，若否，繼續執行帝國競爭算法；若是，啟動遺傳帝國競爭算法融合策略，連續判斷從當前代之后的n代帝國競爭算法迭代的Δf變化情況，以確定是否調用遺傳算法。若滿足調用條件，則調用遺傳算法，計算遺傳算法的全局最優解，并轉至（2），更新帝國競爭算法迭代代數K；否則，繼續執行帝國競爭算法，并更新代數K。

（5）判斷帝國競爭算法迭代代數K是否達到Gmax，若否，繼續執行帝國競爭算法，若是，計算帝國競爭算法的全局最優帝國，記錄前α個帝國或殖民地的序列，并更新遺傳算法的序列，轉至（2），更新帝國競爭算法迭代代數K。

（6）判斷K是否達到混合算法最大迭代代數MaxDecad es，若是，則輸出最優裝配序列；若否，則繼續執行前面步驟，直至達到最大迭代代數MaxDecad es。

5 實例驗證與分析

以某乘用車后橋減速器零部件裝配為例，對所提混合算法在MATLAB程序中進行驗證，所涉零部件共計25個，如圖4所示。零件的編號和零件名稱，如表1所示。需要指出的是，混合算法不需要指定裝配基礎件，裝配基礎件的獲得由程序運行中自動得到。

圖4 減速器爆炸圖Fig.4 Reducer Explosion Chart

表1 減速器零件編號和名稱Tab.1 Reducer Part Number and Name

對混合算法設置參數：遺傳算法中，最大迭代次數T=20，初始種群數量Q=200，交叉概率P c=0.9，變異概率P m=0.1，λ=15；帝國競爭算法中，初始種群規模N imp=10，初始國家數目為N pop=500；調節系數ξ=0.3，權利系數δ=0.1，最小迭代次數Gmin=50，最大迭代次數Gmax=100，α=β=10，n=2，τ=0.2，混合算法中K=1，最大迭代次數Max Dec ades=500。

各個算法執行50次中算法收斂到最優解的情況，如表2所示。某次迭代中混合算法，遺傳算法和帝國競爭算法求解裝配序列的迭代收斂曲線，如圖5所示。某次迭代中混合算法同文獻[11]對比的迭代曲線，如圖6所示。

表2 50次迭代收斂情況Tab.2 Convergence of 50 Iterations

圖5 各類算法仿真結果Fig.5 Simulation Results of Various Algorithms

圖6 GA-ICA與PSO仿真結果Fig.6 Simulation Results of GA-ICA and PSO

從執行效果看，混合算法在50次迭代中均收斂到最優解，收斂率達到100%，而單一算法在50次迭代中均有無法收斂到最優解的情況。從某次迭代中的收斂曲線可以看出，混合算法的求解效率明顯優于單一的優化算法，混合算法最佳個體在144代收斂到全局最優解，而單一的GA、ICA、PSO分別在258代、301代、188代收斂到最優解，混合算法需要最少的迭代次數即可完成收斂。而且，混合算法在233代時所有種群均收斂到最優解，而單一算法迭代500代只有部分個體收斂到最優解。混合算法可獲得一條裝配綜合成本較?。ㄟm應度值最低）的可行裝配序P25-P6-P9-P10-P4-P11-P8-P7-P5-P3-P2-P1-P18-P13-P23-P12-P24-P14-P22-P17-P19-P15-P16-P20-P21。

6 結論

針對ASP問題的特點，提出了用遺傳帝國競爭混合算法求解ASP問題的方法。建立了綜合考慮裝配序列可行性、裝配序列穩定性、裝配重定向性以及裝配聚合性四個評價指標的適應度函數，利用兩種算法各自的優點，提出了遺傳帝國競爭混合算法的融合策略，以適應度值最低為目標，利用混合算法快速得到最優解。以減速器為實例對混合算法進行了試驗，驗證了混合算法的可行性，通過實驗對比分析，結果表明，混合算法收斂速度明顯優于單一的優化算法，為ASP問題求解提供了一種有效的方法。