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

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

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

1 引言

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

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

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

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

2 系統(tǒng)整體架構(gòu)

在進(jìn)行裝配序列規(guī)劃時，首先根據(jù)CAD產(chǎn)品的裝配模型，獲得裝配的裝配有向圖和裝配連接圖，并根據(jù)圖推理獲得裝配干涉矩陣、連接矩陣等，根據(jù)各矩陣構(gòu)建表達(dá)綜合成本的適應(yīng)度函數(shù)，適應(yīng)度函數(shù)值越低，說明綜合成本越低，裝配序列越優(yōu)?；旌纤惴ㄒ匝b配綜合成本最低為目標(biāo)，進(jìn)行混合迭代，當(dāng)達(dá)到算法終止條件時，輸出結(jié)果?；诨旌纤惴ǖ难b配序列規(guī)劃系統(tǒng)整體架構(gòu)，如圖1所示。

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

3 適應(yīng)度函數(shù)構(gòu)造

在ASP問題中，首先要保證的是裝配序列可行，然后，綜合考慮裝配序列可行性、裝配序列穩(wěn)定性、裝配重定向性和裝配聚合性。量化各項指標(biāo)的計算方法，通過加權(quán)處理得到綜合適應(yīng)度函數(shù)，為最優(yōu)裝配序列生成提供計算依據(jù)。

3.1 裝配序列的可行性

在空間直角坐標(biāo)系中，零件的基本裝配方向有d(k)={+x，-x，+y，-y，+z，-z}={d k}六個方向，建立零件在空間直角坐標(biāo)系中的干涉矩陣，其中，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進(jìn)行裝

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

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

3.2 裝配序列的穩(wěn)定性

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

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

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

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

3.3 裝配的重定向性

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

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

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

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

（4）結(jié)束。

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

3.4 裝配的聚合性

裝配的聚合性表示裝配過程中裝配工具的改變次數(shù)，根據(jù)實際情況，建立裝配工具集矩陣，則裝配工具改變次數(shù)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，轉(zhuǎn)至步驟（3），否則，令m=m+1，如果i+m+1

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

（4）結(jié)束。

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

3.5 建立適應(yīng)度函數(shù)

綜合考慮裝配序列的可行性、裝配序列的穩(wěn)定性、裝配序列的重定向性、裝配序列的聚合性，可建立對這些評價指標(biāo)加權(quán)的適應(yīng)度函數(shù)，如下：

式中：ω1，ω2，ω3，ω4—各 項指標(biāo)的權(quán)重系數(shù)。

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

4 基于遺傳帝國競爭混合算法的ASP尋優(yōu)

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

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

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

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

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

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

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

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

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

（2）隨機生成Q個父代個體，并將父代按適應(yīng)度值從小到大順序排列（適應(yīng)度值越小，序列越優(yōu)），記錄父代對應(yīng)的標(biāo)簽。

（3）對父代進(jìn)行選擇操作。

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

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

（6）當(dāng)?shù)螖?shù)未達(dá)到T時，轉(zhuǎn)至（3），當(dāng)?shù)螖?shù)達(dá)到T時，選擇最優(yōu)（適應(yīng)度值最低）的前λ個個體，作為帝國競爭算法的初始帝國，調(diào)用帝國競爭算法。

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

4.2.1 建立初始帝國

在混合算法中，帝國競爭算法選擇遺傳算法中前λ個最優(yōu)個體作為帝國競爭算法初始帝國，并隨機生成N pop-λ個初始國家，計算每個國家的權(quán)利，在ASP問題中，權(quán)利的大小與適應(yīng)度函數(shù)有關(guān)，適應(yīng)度函數(shù)值越小，權(quán)利值越大。

式中：c i—第i個國家的權(quán)利；fitness(i)為第i個國家的適應(yīng)度值。

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

對初始帝國權(quán)利歸一化處理

式中：p n和c n—第n個帝國的歸一化權(quán)利和標(biāo)準(zhǔn)權(quán)利，根據(jù)帝國的歸一化權(quán)利，分配殖民地，第n個帝國的殖民地數(shù)量為：

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

4.2.2 殖民地同化

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

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

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

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

4.2.3 殖民地革命

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

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

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

4.2.4 帝國競爭

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

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

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

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

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

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

帝國競爭算法在經(jīng)過反復(fù)殖民地同化、革命，帝國競爭后，不斷收斂到最優(yōu)解，當(dāng)只有一個帝國后，算法達(dá)到終止條件，也可以用迭代次數(shù)作為終止條件，此處以迭代次數(shù)作為終止條件。混合算法中帝國競爭算法的計算流程圖，如圖3所示。

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

計算流程如下：

（1）設(shè)置帝國競爭算法的初始參數(shù)，包括算法的初始國家數(shù)量N pop-λ，初始帝國的數(shù)量N imp，從遺傳算法中選擇前λ個最優(yōu)個體作為帝國競爭算法初始帝國，調(diào)節(jié)系數(shù)為ξ，權(quán)利系數(shù)為δ，最小和最大迭代次數(shù)Gmin和Gmax，殖民地同化操作次數(shù)M，革命操作次數(shù)R，當(dāng)前迭代代數(shù)K=K+T。

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

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

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

（5）當(dāng)?shù)蹏偁幩惴ǖ鷶?shù)K未達(dá)到Gmin時，繼續(xù)進(jìn)行（3）操作；在K達(dá)到Gmin時，且滿足調(diào)用條件（見4.3.1節(jié)）時，調(diào)用遺傳算法，更新迭代代數(shù)K=K+T；當(dāng)K達(dá)到Gmax時，終止帝國競爭算法操作。

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

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

在算法開始時，采用遺傳算法迭代T次，計算所有序列的適應(yīng)度值，并根據(jù)適應(yīng)度從小到大順序取出前λ個個體，作為帝國競爭算法初始帝國，并隨機生成N pop-λ個初始國家，開始執(zhí)行帝國競爭算法。當(dāng)?shù)蹏偁幩惴ㄔ趫?zhí)行過程中陷入局部最優(yōu)時，調(diào)用遺傳算法提高局部搜索能力?；旌纤惴ǖ娜诤喜呗匀缦拢?/p>

（1）設(shè)定遺傳算法迭代次數(shù)T，當(dāng)達(dá)到T時，將產(chǎn)生的序列作為帝國競爭算法的初始帝國，并隨機生成N po p-λ個初始國家，開始執(zhí)行帝國競爭算法。

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

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

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

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

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

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

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

4.3.3 混合算法的計算流程

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

（2）執(zhí)行遺傳算法，計算每一個種群個體的適應(yīng)度，記錄對應(yīng)的序列。

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

（4）判斷帝國競爭算法迭代數(shù)K是否達(dá)到Gmin，若否，繼續(xù)執(zhí)行帝國競爭算法；若是，啟動遺傳帝國競爭算法融合策略，連續(xù)判斷從當(dāng)前代之后的n代帝國競爭算法迭代的Δf變化情況，以確定是否調(diào)用遺傳算法。若滿足調(diào)用條件，則調(diào)用遺傳算法，計算遺傳算法的全局最優(yōu)解，并轉(zhuǎn)至（2），更新帝國競爭算法迭代代數(shù)K；否則，繼續(xù)執(zhí)行帝國競爭算法，并更新代數(shù)K。

（5）判斷帝國競爭算法迭代代數(shù)K是否達(dá)到Gmax，若否，繼續(xù)執(zhí)行帝國競爭算法，若是，計算帝國競爭算法的全局最優(yōu)帝國，記錄前α個帝國或殖民地的序列，并更新遺傳算法的序列，轉(zhuǎn)至（2），更新帝國競爭算法迭代代數(shù)K。

（6）判斷K是否達(dá)到混合算法最大迭代代數(shù)MaxDecad es，若是，則輸出最優(yōu)裝配序列；若否，則繼續(xù)執(zhí)行前面步驟，直至達(dá)到最大迭代代數(shù)MaxDecad es。

5 實例驗證與分析

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

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

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

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

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

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

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

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

從執(zhí)行效果看，混合算法在50次迭代中均收斂到最優(yōu)解，收斂率達(dá)到100%，而單一算法在50次迭代中均有無法收斂到最優(yōu)解的情況。從某次迭代中的收斂曲線可以看出，混合算法的求解效率明顯優(yōu)于單一的優(yōu)化算法，混合算法最佳個體在144代收斂到全局最優(yōu)解，而單一的GA、ICA、PSO分別在258代、301代、188代收斂到最優(yōu)解，混合算法需要最少的迭代次數(shù)即可完成收斂。而且，混合算法在233代時所有種群均收斂到最優(yōu)解，而單一算法迭代500代只有部分個體收斂到最優(yōu)解?；旌纤惴色@得一條裝配綜合成本較?。ㄟm應(yīng)度值最低）的可行裝配序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 結(jié)論

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