徐周波，肖 鵬，古天龍，寧黎華

（桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004）

0 引言

裝配序列規(guī)劃（Assembly Sequence Planning，ASP）是產(chǎn)品制造過程中的重要環(huán)節(jié)，裝配質(zhì)量直接影響著產(chǎn)品的性能。對(duì)于大規(guī)模產(chǎn)品的生產(chǎn)，一條較優(yōu)的裝配序列將大大縮短產(chǎn)品的生產(chǎn)周期，降低產(chǎn)品的生產(chǎn)費(fèi)用，提高產(chǎn)品的質(zhì)量性能。相關(guān)研究表明，良好的裝配序列可以減少制造費(fèi)用20%～40%、提高生產(chǎn)率100%～200%［1-2］。因此，ASP在產(chǎn)品制造過程中占有非常重要的地位。裝配序列是裝配規(guī)劃的核心組成部分，ASP 方法不僅要考慮綠色制造這一重要因素，還要考慮實(shí)際工程中的經(jīng)濟(jì)效益問題。獲取產(chǎn)品裝配序列的方法主要有幾何推理法［3-4］、知識(shí)推理法［5］和軟計(jì)算法［6-11］等，其中幾何推理法和知識(shí)推理法不可避免地面臨組合爆炸問題。為了解決組合爆炸問題，近年來研究人員主要采用軟計(jì)算方法探索ASP，典型的軟計(jì)算方法主要有遺傳算法（Genetic Algorithm，GA）［6］、蟻群優(yōu)化（Ant Colony Optimization，ACO）算法［7］、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［8-9］、免疫算法［10］、模擬退火算法［11］和螢火蟲算法［12］等，通過實(shí)驗(yàn)驗(yàn)證軟計(jì)算方法在一定程度上解決了零件數(shù)目較多的ASP問題，為進(jìn)一步優(yōu)化復(fù)雜產(chǎn)品的裝配序列奠定了基礎(chǔ)。

ACO 算法是研究人員根據(jù)螞蟻覓食行為提出的一種具有高度信息利用的啟發(fā)式優(yōu)化算法［13］。ACO 算法具有自組織、并行、正反饋和較強(qiáng)魯棒性等優(yōu)點(diǎn)。最初，ACO 算法解決了一定規(guī)模的旅行商問題（Traveling Salesman Problem，TSP）［14］，以及同步電路時(shí)序分配［15］和生產(chǎn)調(diào)度［16］等一系列NP難問題。隨著ACO 算法的不斷發(fā)展，彭濤等［17-18］將ACO 算法運(yùn)用到解決ASP 問題上，通過實(shí)驗(yàn)驗(yàn)證了該算法較傳統(tǒng)ASP 方法在搜索時(shí)間和最優(yōu)解方面都有極大提高，但是ACO 算法很容易陷入局部最優(yōu)解。針對(duì)ACO 算法過早收斂這一缺陷，于嘉鵬等［19］采用最大—最小信息素量對(duì)路徑上的信息素進(jìn)行限制；史士財(cái)［20］等通過信息素殘留系數(shù)的動(dòng)態(tài)變化和影響轉(zhuǎn)移概率的α、β參數(shù)的動(dòng)態(tài)設(shè)置來避免陷入局部最優(yōu)解。然而，單一ACO 算法的改進(jìn)還不能從根本上提高算法的全局搜索能力。

GA 是研究人員根據(jù)生物染色體交叉、變異選擇優(yōu)質(zhì)個(gè)體這一過程提出的一種軟計(jì)算法，具有全局搜索能力和信息不依賴的尋優(yōu)能力，能夠有效防止陷入局部最優(yōu)解，例如李原等［21］利用GA 解決了一定規(guī)模的飛機(jī)ASP問題。但是，GA 也有其自身的缺陷。首先，GA 比較依賴于初始種群，例如當(dāng)初始種群中的可行裝配序列比例較小或初始種群中沒有可行裝配序列時(shí)，可能找不到更優(yōu)的可行解，而且消耗的時(shí)間更長(zhǎng)；其次，GA 在搜索過程中會(huì)產(chǎn)生大量的重復(fù)解，嚴(yán)重影響搜索的效率。針對(duì)這一問題，寧黎華等［22］將ACO 算法和GA 結(jié)合起來解決ASP問題。通過實(shí)驗(yàn)驗(yàn)證，證明該混合算法具有較好的穩(wěn)定性和尋優(yōu)能力，但是GA 容易產(chǎn)生大量重復(fù)解的缺陷仍沒有被克服。如果能夠在此基礎(chǔ)上采取某種策略避免GA 產(chǎn)生重復(fù)解，將會(huì)進(jìn)一步提高混合算法的性能。

混沌具有隨機(jī)性、遍歷性的特點(diǎn)，可以有效避免產(chǎn)生重復(fù)解，提高GA 的搜索效率［23］。胥小波等［24］將混沌理論用于PSO 算法，建立了一種新穎的混沌粒子群算法，遍歷了搜索空間，避免了重復(fù)解的產(chǎn)生。實(shí)驗(yàn)證明，將混沌理論用于PSO 算法，比單一PSO 算法的效率有所提高。鑒于此，本文將ACO算法、混沌算法和GA 有效結(jié)合起來，提出一種動(dòng)態(tài)的混沌混合算法。首先利用ACO 算法生成一定數(shù)目的可行裝配序列；然后以這些裝配序列為基礎(chǔ)，運(yùn)用混沌算法加強(qiáng)局部搜索，得到一些新的可行裝配序列來擴(kuò)大可行序列的數(shù)目；最后以這些可行裝配序列為基礎(chǔ)，運(yùn)用GA 進(jìn)行全局搜索。每完成一次搜索，就計(jì)算裝配序列的適應(yīng)度值，更新當(dāng)前最優(yōu)解，按最優(yōu)種群和最劣種群比例為9∶1選擇子代裝配序列，動(dòng)態(tài)增加初始種群的數(shù)目，并完成路徑信息素的更新。通過實(shí)驗(yàn)驗(yàn)證，證明混沌混合算法的性能比GA、ACO 算 法、ACO 和GA 混合算 法的性 能更好。

傳統(tǒng)的ASP的優(yōu)化指標(biāo)考慮了裝配方向、裝配工具和裝配類型等因素，但是僅從相同和不同考慮不能全面體現(xiàn)裝配的成本，并且各個(gè)指標(biāo)之間的相關(guān)性也考慮得不全面。本文將對(duì)這些評(píng)價(jià)指標(biāo)進(jìn)行進(jìn)一步細(xì)化，將裝配方向和裝配工具聯(lián)合起來評(píng)價(jià)作為裝配的連貫性，將裝配過程中輔助工具的使用次數(shù)作為新的評(píng)價(jià)標(biāo)準(zhǔn)，使裝配序列的評(píng)價(jià)標(biāo)準(zhǔn)更加全面。

1 ACO 算法原理

螞蟻在覓尋食物的路徑上會(huì)留下一定量的信息素，通過感知路徑上的啟發(fā)信息的強(qiáng)弱選擇最優(yōu)路徑，可以找到巢穴到食源的最短路徑。意大利學(xué)者Dorigo于1991年提出了ACO算法，算法的基本規(guī)則如下：

（1）信息共享原則

每只螞蟻都可以感知其他螞蟻在覓食路徑上留下的信息素，并且螞蟻每次留下的信息素量相同。

（2）路徑選擇規(guī)則

式中：k為螞蟻的編號(hào)；?k為螞蟻當(dāng)前可選擇的路徑；τij為Pi和Pj之間的信息素量；ηij為城市i和j之間的啟發(fā)信息，其值等于1／dij，dij表示城市i和城市j之間的距離；α和β分別表示路徑上原有信息素與啟發(fā)信息素的相對(duì)重要性。

為了平衡ACO 算法的局部搜索能力和全局搜索能力，運(yùn)用的路徑選擇規(guī)則如下：

式中：q為［0，1］之間的一個(gè)隨機(jī)數(shù)；Q為預(yù)先設(shè)置的參數(shù)，用以權(quán)衡選擇新路徑和選擇當(dāng)前最優(yōu)路徑的相對(duì)重要性，0＜Q＜1；S為根據(jù)式（1）中的隨機(jī)選擇的一個(gè)變量。

（3）局部信息素更新規(guī)則

式中：ρ為衰減系數(shù)，0＜ρ＜1；τij為Pi和Pj之間在搜索過程中獲取的信息素；τ（i，j）為經(jīng)過局部規(guī)則更新后Pi和Pj之間的信息素；τ0為路徑原始信息素。約定零件Pi和零件Pj路徑上的信息素τ（i，j）的最小值和最大值分別為τmin和τmax。

螞蟻完成一次搜索后，對(duì)路徑信息素進(jìn)行更新，ρ起動(dòng)態(tài)擾動(dòng)作用，即對(duì)原有信息素進(jìn)行一定量的衰減，或?qū)l(fā)信息進(jìn)行一定量的增加。

（4）全局更新規(guī)則

式中：α為全局衰減系數(shù)，0＜α＜1；Lgb為全局最優(yōu)路徑的長(zhǎng)度。

螞蟻完成一次搜索后，對(duì)當(dāng)前的m只螞蟻搜索到的路徑進(jìn)行評(píng)估，找出當(dāng)前最優(yōu)路徑。全局更新規(guī)則只對(duì)當(dāng)前最優(yōu)路徑進(jìn)行信息素更新，以達(dá)到提高搜索效率的目的，使螞蟻很快集中到最優(yōu)解上。

2 混沌混合算法原理

2.1 混沌理論

混沌是自然界中普遍存在的一種非線性現(xiàn)象，它表面上是一種隨機(jī)、無規(guī)則運(yùn)動(dòng)，實(shí)際隱藏著精密的內(nèi)部結(jié)構(gòu)，具有遍歷性。本文選擇Logistic映射作為混沌序列生成的方法，如式（6）：

式中：Zn為混沌變量，0＜Zn＜1；μ為混沌吸引子。

假設(shè)要生成一組包含有n個(gè)變量的混沌序列，隨機(jī)賦值Z1=（0，1），根據(jù)式（6）依次生成Z2，Z3，…，Zn，混沌序列為｛Z1，Z2，…，Zn｝，其中混沌吸引子μ=4，混沌變量不能?。?，0.25，0.5，0.75，1｝，這些值會(huì)使混沌變量形成一個(gè)固定的值。

2.2 基于混沌理論生成裝配序列

GA 的個(gè)體基因均為整數(shù)，首先將個(gè)體基因轉(zhuǎn)化為（0，1）之間的混沌變量，如式（7）：

式中：n為零件編號(hào)，nPartnum為零件總數(shù)目。

利用Logistic映射生成一組混沌序列后，再將混沌變量轉(zhuǎn)化為個(gè)體基因，如式（8）：

式中［Zn×nPartnum］表示對(duì)Zn×nPartnum采用四舍五入法取整?；煦邕z傳算法完成一次搜索后，需要更新混沌變量的初始值，由于裝配序列的優(yōu)化問題不同于其他優(yōu)化模型，基礎(chǔ)件的確定對(duì)產(chǎn)品的裝配影響很大。本文用式（9）來保證每次裝配序列的基礎(chǔ)件不變。

2.3 混沌混合算法的步驟

運(yùn)用ACO 算法進(jìn)行局部搜索，使用混沌算法加強(qiáng)局部搜索，運(yùn)用GA 對(duì)裝配序列進(jìn)行全局搜索，具體操作步驟如下：

步驟1 利用ACO 算法搜索。根據(jù)式（1）和式（2）對(duì)裝配序列進(jìn)行局部搜索，得到裝配序列的部分可行解，設(shè)為解集X1。

步驟2 ACO 算法在局部搜索過程中，每完成一次零件的選擇，即用式（3）更新路徑信息素，并利用［τmin，τmax］對(duì)信息素進(jìn)行限制。

步驟3 利用混沌算法搜索。根據(jù)式（6）確定混沌變量，利用式（9）確定裝配的基準(zhǔn)件，利用式（7）和式（8）確定裝配序列可行解，設(shè)為解集X2。

步驟4 計(jì)算可行解集X1和X2的適應(yīng)度值，并記錄當(dāng)前最優(yōu)解Xopt。

步驟5 以X1和X2為初始種群，采用多點(diǎn)交叉技術(shù)，以一定的交叉概率運(yùn)用GA 對(duì)裝配序列進(jìn)行全局搜索，搜索得到的裝配序列可行解集設(shè)為X3。計(jì)算X3的適應(yīng)度值，并更新Xopt。

步驟6 對(duì)新路徑信息素進(jìn)行全局更新。對(duì)可行解集X1，X2和X3進(jìn)行降序排列，選擇前10%的可行解，用式（4）對(duì)這些路徑的信息素進(jìn)行全局更新。

步驟7 更新種群的數(shù)量。選擇X1，X2和X3占90%的種群數(shù)量，從不可行解中選擇10%作為下一輪搜索的初始種群。

步驟8 設(shè)置終止條件。當(dāng)?shù)趎代與第n+1代之間滿足式（10）時(shí)終止搜索，輸出最優(yōu)解；否則轉(zhuǎn)步驟1，繼續(xù)搜索，直至搜索次數(shù)達(dá)到最大值Ncmax。其中第n代Xn=（α1α2…αn），第n+1 代Xn+1=（γ1γ2…γn），αi，γi∈｛P1，P2，…，Pn｝。

式中：fαiαi+1，fγiγi+1（i=1，…，n-1）為 第n和n+1代裝配序列的最優(yōu)適應(yīng)度值，具體根據(jù)式（17）計(jì)算；q為實(shí)驗(yàn)誤差。

3 裝配序列優(yōu)化指標(biāo)的構(gòu)造

為進(jìn)一步優(yōu)化裝配序列的評(píng)價(jià)指標(biāo)，將裝配的方向性和裝配工具的改變次數(shù)合并為裝配的連貫性，對(duì)裝配序列的穩(wěn)定性和裝配操作類型的標(biāo)準(zhǔn)進(jìn)行更細(xì)的劃分。

3.1 可行性

在子裝配體上裝配零件Pi時(shí)，必須先考慮零件的裝配可行性。首先利用集成干涉矩陣獲取零件的裝配信息，再根據(jù)式（11）和式（12）判斷零件的裝配可行性。

式中：m的6個(gè)取值分別表示裝配的6個(gè)方向±x，±y，±z；Ci=1表示零件Pi至少可以在一個(gè)方向上裝配；Ci=0表示零件Pi不能進(jìn)行裝配。

3.2 連貫性

連貫性指裝配過程中不需要改變裝配方向和裝配工具，裝配動(dòng)作在時(shí)間和空間上具有連續(xù)性。以往的研究人員將裝配方向劃分為相同、相反和不同，但是這種劃分沒有全面反映裝配過程的連貫性。如果零件Pi和零件Pj的裝配工具不同，則對(duì)人工裝配需要完成卸下工具和安裝工具的過程，對(duì)于自動(dòng)化裝配同樣需要完成相同的操作并確認(rèn)工具安裝的穩(wěn)定性。裝配工具的不斷更換將在時(shí)間上帶來消耗，必然降低裝配的效率。本文將裝配的連貫性進(jìn)行量化，連貫性的量化準(zhǔn)則如下：

式 中：di為零件Pi的裝配方向；ti為零件Pi的裝配工具；Lij為零件Pi和Pj連貫性的相對(duì)權(quán)重值。

3.3 穩(wěn)定性

裝配序列的穩(wěn)定性指零件與子裝配體在自身重力和所需外力作用下，保持各自內(nèi)部裝配關(guān)系的能力，它體現(xiàn)了裝配操作的可靠性、夾具和工具的復(fù)雜性。在傳統(tǒng)的裝配序列穩(wěn)定性量化過程中，只考慮了重力的作用，本文進(jìn)一步考慮零件之間的內(nèi)部作用力，包括零件之間的摩擦力以及人工所使用的裝夾鉗使零件之間產(chǎn)生的力，使量化后的效果更加明顯，更接近于實(shí)際工程，具體的權(quán)重設(shè)置如下：

式中：Wij為穩(wěn)定性的權(quán)重值；若零件Pi在零件Pj之上，則wij=1，否則wij=0；若零件Pi與零件Pj有其他力支配，包括摩擦力和兩零件之間的夾力，則μij=1，否則μij=0。

3.4 零件的操作類型

ASP的操作類型在一定程度上影響裝配成本。操作類型相同意味著不需要對(duì)當(dāng)前的裝配裝置進(jìn)行調(diào)整，連續(xù)裝配的零件增多使裝配過程更具備連貫性。具體的優(yōu)化標(biāo)準(zhǔn)值設(shè)置如下：

式中：Tij為操作類型的權(quán)值；lij表示零件Pi和零件Pj的操作類型關(guān)系，lij=0表示不同，lij=1表示相同。常用的操作類型有固定操作類型和滑動(dòng)操作類型。

3.5 輔助工具的使用次數(shù)

裝配過程中運(yùn)用輔助工具來保證子裝配體的穩(wěn)定性和連續(xù)性是必不可少的。以往研究人員沒有將輔助工具的運(yùn)用次數(shù)作為裝配序列的優(yōu)化指標(biāo)，本文將對(duì)這兩種影響要素進(jìn)行權(quán)重設(shè)置，具體的設(shè)置為：

式中：Fi為權(quán)重值；fi=0表示零件Pi沒有使用輔助工具，fi=1表示零件Pi使用了輔助工具；ti=tj表示前后零件使用的輔助裝置類型相同。輔助工具為左右夾裝臺(tái)、前后夾裝臺(tái)和上下夾裝臺(tái)。

混沌混合算法對(duì)優(yōu)化指標(biāo)的運(yùn)用如下：

（1）利用集成干涉矩陣獲取零件Pi（i=1，2，…，n）的裝配信息，計(jì)算Fi的值。

（2）如果Fi＞0，則計(jì)算零件Pi在可裝配方向上的啟發(fā)式信息值；如果Fi=0，則表示零件Pi不能在當(dāng)前子裝配體上裝配。

（3）利用混沌混合算法完成一次搜索后，根據(jù)啟發(fā)式評(píng)估函數(shù)對(duì)子代裝配序列進(jìn)行評(píng)估，啟發(fā)式評(píng)估函數(shù)

式中：μ1，μ2，μ3 和μ4 為各項(xiàng)優(yōu)化指標(biāo)的權(quán)重系數(shù)。

（4）建立信息矩陣。信息矩陣將零件與零件之間的各種評(píng)優(yōu)指標(biāo)整合起來，通過設(shè)置各種指標(biāo)的權(quán)重值，將指標(biāo)刻畫成具體的數(shù)值。信息矩陣

4 混沌混合算法步驟及流程

混沌混合算法流程圖如圖1所示。本算法結(jié)合ACO 算法和混沌GA，一方面具有較強(qiáng)的局部搜索能力，另一方面有GA 的全局搜索能力和混沌的遍歷特性，能夠充分提高搜索效率，避免產(chǎn)生重復(fù)解。

（1）數(shù)據(jù)和裝配信息的初始化

1）ACO 算法的數(shù)據(jù)初始化包括：①路徑信息素的初始值τ0、路徑信息素的最大值τmax和最小值τmin。當(dāng)路徑上的信息素τij＞τmax時(shí)，將τij調(diào)為τmax；當(dāng)路徑上的信息素τij＜τmin時(shí)，將τij調(diào)為τmin。每完成一次零件的選擇，用式（3）進(jìn)行局部更新；每完成一次全局搜索，用式（4）對(duì)路徑上的信息素進(jìn)行全局更新：兩次更新信息素的策略避免了搜索過早地陷入局部最優(yōu)。②信息素的全局揮發(fā)率α、局部揮發(fā)率ρ和啟發(fā)信息素相對(duì)于原始信息素的重要性β。③各優(yōu)化指標(biāo)的相對(duì)權(quán)重值ω1～ω4。④最大迭代次數(shù)Ncmax。⑤適應(yīng)度值的誤差設(shè)置q。⑥螞蟻的數(shù)目m。

2）混沌GA 的數(shù)據(jù)初始化包括：①初始種群規(guī)模n，將n的值設(shè)置為ACO 算法和混沌算法搜索到的可行解；②交叉概率pc；③變異概率pm；④混沌吸引子μ。

（2）裝配信息的收集

根據(jù)零件的特點(diǎn)確定基礎(chǔ)件。一方面為靜態(tài)信息的搜集，在運(yùn)用ACO 算法搜索時(shí)，需要提前確定各信息矩陣的信息，以方便用式（1）和式（2）選擇裝配零件；另一方面包括動(dòng)態(tài)信息的收集。在裝配過程中由于零件與零件之間的信息是一個(gè)動(dòng)態(tài)變化的過程，為此建立一個(gè)信息矩陣Mij來記錄零件與零件之間的適應(yīng)度值。

（3）最大—最小ACO 算法構(gòu)建路徑的過程

將m只螞蟻放置在基礎(chǔ)件上，利用集成干涉矩陣A確定零件裝配的可行性，根據(jù)路徑選擇規(guī)則式（1）和式（2），結(jié)合信息矩陣并采用輪盤賭選擇法確定下一個(gè)裝配的零件，完成一次零件的選擇后，用式（3）對(duì)路徑信息素進(jìn)行局部更新。重復(fù)上述操作，直到完成一次路徑的建立。用式（4）和式（5）對(duì)路徑信息素進(jìn)行全局更新，使信息素限制在［τmin，τmax］；用式（17）計(jì)算可行解的適應(yīng)度值，并保存最優(yōu)解。

（4）利用混沌GA 進(jìn)行全局搜索的過程

將ACO 算法搜索的可行解設(shè)置為X1，以X1為基礎(chǔ)采用混沌算法進(jìn)行初步全局搜索，將混沌算法搜索到的可行解設(shè)置為X2，將X1和X2作為GA的初始種群，利用GA 進(jìn)行全局搜索。對(duì)于GA 產(chǎn)生的子代裝配序列，用集成干涉矩陣等相關(guān)信息結(jié)合式（17）計(jì)算其適應(yīng)度值，更新當(dāng)前最優(yōu)解。完成一輪搜索后，按9∶1的比例選擇最優(yōu)解和最劣解更新初始種群。最后，用式（3）和式（4）對(duì)路徑信息素進(jìn)行全局更新。完成混沌GA 的搜索后，若不滿足終止條件則轉(zhuǎn)（3）繼續(xù)搜索。

（5）終止動(dòng)作

搜索結(jié)束有以下兩種情況：

（1）當(dāng)n和n+1兩代之間的的適應(yīng)度值之差小于設(shè)置的誤差值q時(shí)，搜索結(jié)束，輸出最優(yōu)解。

（2）將算法的迭代次數(shù)設(shè)置為Ncmax，每完成一次迭代，更新迭代次數(shù)n=n+1，當(dāng)n=Ncmax時(shí)，搜索結(jié)束，輸出最優(yōu)解。

5 實(shí)例及結(jié)果分析

5.1 應(yīng)用實(shí)例

利用Visual C++6.0開發(fā)工具，在Windows XP、Intel酷睿i5 2.26GHz、2GB內(nèi)存環(huán)境下，將本文的混沌混合算法與GA、ACO 算法，以及ACO—GA 進(jìn)行了實(shí)驗(yàn)對(duì)比。選取齒輪油泵作為分析對(duì)象，該控制器由22個(gè)零件組成，將類型完全相同的螺釘和銷簡(jiǎn)化后，只對(duì)控制器的16個(gè)零件進(jìn)行裝配序列規(guī)劃。齒輪油泵的裝配爆炸圖如圖2所示，裝配零件使用的工具和裝配工具的操作類型如表1所示。

表1 齒輪油泵的裝配信息

混沌混合算法是結(jié)合ACO算法和混沌GA 形成的一種優(yōu)勢(shì)互補(bǔ)的新算法。ACO 算法的參數(shù)設(shè)置如下：螞蟻規(guī)模m=20；搜索次數(shù)Ncmax=20；零件之間的最大信息素τmax=5.0；最小信息素τmin=1.0；全局信息素的揮發(fā)率α=0.2；局部信息素的衰減系數(shù)ρ=0.1；各優(yōu)化指標(biāo)權(quán)重系數(shù)ω1～ω4=1?；煦鏕A 的參數(shù)設(shè)置如下：染色體數(shù)目與ACO算法的數(shù)目相同；混沌吸引子μ=4；交叉概率pc=0.85；變異概率pm=0.05；迭代次數(shù)Ncmax=100；優(yōu)化指標(biāo)權(quán)重同上。

基本GA 的參數(shù)設(shè)置如下：種群規(guī)模m=100；迭代次數(shù)Ncmax=100；交叉概率pc=0.85；變異概率pm=0.05；

基本螞蟻的參數(shù)設(shè)置如下：種群規(guī)模m=100；迭代次數(shù)Ncmax=100；全局信息素的揮發(fā)率α=0.2；局部信息素的衰減系數(shù)β=0.1。

ACO—GA 的參數(shù)設(shè)置如下：螞蟻的規(guī)模m=100；迭代次數(shù)Ncmax=50；全局信息素?fù)]發(fā)率α=0.2；局部信息素衰減系數(shù)β=0.1；GA 的規(guī)模與螞蟻數(shù)目相同，交叉概率pc=0.85；變異概率pm=0.05；

工具G2，G4和G6的質(zhì)量近似相等，作為本文的優(yōu)化指標(biāo)時(shí)，近似地令m2=m4=m6。同理，G3和G5的質(zhì)量近似相等，m3=m5。

設(shè)置算法的迭代次數(shù)：混沌混合算法的Ncmax=20；GA 的Ncmax=200；ACO 的Ncmax=20；ACO—GA 的Ncmax=50。

設(shè)置種群規(guī)模數(shù)目m：混沌混合算法m=20，其他算法m=100。

5.2 混沌混合算法與其他軟計(jì)算法的比較分析

基于以上各種參數(shù)的權(quán)重設(shè)置，混沌混合算法與其他軟計(jì)算方法搜索到的最優(yōu)裝配序列和各種序列對(duì)應(yīng)的裝配信息如表2所示。

表2 各算法找到的最優(yōu)裝配序列

（1）與ACO—GA 混合算法比較

1）迭代次數(shù) 混沌混合算法20次，螞蟻—GA混合算法50次。

2）種群規(guī)模 混沌混合算法20，螞蟻—GA 算法100。

3）最優(yōu)適應(yīng)度值 混沌混合算法38.2，螞蟻—GA 算法32.2。

4）實(shí)驗(yàn)運(yùn)行時(shí)間 混沌混合算法0.22s，螞蟻—GA 算法0.34s。

綜上所述，因?yàn)榛煦缁旌纤惴ǖ乃阉鞔螖?shù)和種群規(guī)模明顯少于螞蟻—GA 算法，所以混沌混合算法的實(shí)驗(yàn)運(yùn)行時(shí)間少于螞蟻—GA 算法，且搜索效率有一定的提高。由于混沌混合算法引進(jìn)了混沌算法，在ACO 算法的基礎(chǔ)上使用混沌算法全局搜索，能夠避免產(chǎn)生重復(fù)解，擴(kuò)大搜索空間。再以這兩種算法搜到的可行解為GA 的初始種群，能夠極大地提高GA 的性能。因此，混沌混合算法搜索到的最優(yōu)解比螞蟻—GA 好。

（2）與ACO 算法比較

1）迭代次數(shù) 混沌混合算法20次，ACO 算法100次；

2）初始種群規(guī)模 混沌混合算法20，ACO 算法100。

3）最優(yōu)適應(yīng)度值 混沌混合算法38.2，ACO算法28.4。

4）實(shí)驗(yàn)運(yùn)行時(shí)間 混沌混合算法0.22s，螞蟻算法0.21s。

綜上所述，因?yàn)榛煦缁旌纤惴ㄟ\(yùn)用了混沌算法和GA 進(jìn)行全局搜索，在很大程度上擴(kuò)大了搜索空間，所以搜索到的最優(yōu)解明顯好于單一ACO 算法。從實(shí)驗(yàn)運(yùn)行的時(shí)間上分析，混沌混合算法較ACO算法的種群規(guī)模小、搜索次數(shù)少。另外，混沌混合算法在搜索時(shí)需要完成混沌算法和GA 的搜索過程，其搜索效率略好于ACO 算法。

（3）與遺傳算法比較

1）迭代次數(shù) 混沌混合算法20次，GA 100次。

2）種群規(guī)模 混沌混合算法20，GA 100。

3）最優(yōu)適應(yīng)度值 混沌混合算法38.2，GA 25。

4）實(shí)驗(yàn)運(yùn)行時(shí)間 混沌混合算法0.22s，GA 56s。

綜上所述，因?yàn)榛煦缁旌纤惴ㄟ\(yùn)用ACO 算法和混沌算法進(jìn)行了局部和全局搜索，對(duì)GA 的初始種群是一個(gè)極大的優(yōu)化過程，所以最優(yōu)適應(yīng)度值明顯好于GA。從實(shí)驗(yàn)的運(yùn)行時(shí)間上分析，因?yàn)榛煦缁旌纤惴ㄔ诤艽蟪潭壬蟽?yōu)化了基本GA 的初始種群，所以大大提高了搜索的性能，使搜索效率的提升更加明顯。

混沌混合算法與混合算法、ACO 算法和GA 的性能對(duì)比結(jié)果如表3所示。

表3 算法的性能比較

1）裝配方向改變次數(shù) 混沌混合算法3次，螞蟻—GA 8次，ACO 算法10次，GA 12次。

2）裝配工具改變次數(shù) 混沌混合算法5次，螞蟻—GA 5次，ACO 算法9次，GA 10次。混沌混合算法的優(yōu)化序列較其他算法搜索到的序列有本質(zhì)上的提升。

3）操作類型的改變次數(shù) 混沌混合算法5次，螞蟻—GA 8次，ACO 算法9次，GA 13次。

4）輔助工具的使用次數(shù) 每種算法各使用1次。

5）穩(wěn)定性的裝配操作次數(shù) 每種算法的穩(wěn)定性的裝配操作次數(shù)均為15次。

產(chǎn)生裝配序列優(yōu)劣的根本原因是混沌混合算法在利用混沌算法時(shí)增強(qiáng)了全局搜索范圍，利用這些可行解作為GA 的初始種群，較大地提高GA 的性能，使搜索的范圍進(jìn)一步擴(kuò)大。最終，混沌混合算法在一個(gè)較大的搜索空間找到了更優(yōu)的可行解。

6 結(jié)束語

本文將ACO算法與混沌GA 相結(jié)合，建立了一種優(yōu)勢(shì)互補(bǔ)的混沌混合算法，充分利用ACO 算法的啟發(fā)式信息特點(diǎn)、混沌算法的全局搜索能力和混沌的遍歷性特點(diǎn)，在一定程度上克服了GA 對(duì)初始種群的依賴以及在搜索過程中產(chǎn)生重復(fù)解的缺陷。實(shí)驗(yàn)證明，混沌混合算法較其他單一算法有更好的性能。如果將此智能算法用于子裝配體之間的裝配，則裝配的效率將得到進(jìn)一步提高。本文的裝配方向僅限于三維坐標(biāo)，在實(shí)際裝配中，很多產(chǎn)品都是從球面坐標(biāo)進(jìn)行裝配，將此智能算法用于球面方向裝配是裝配序列規(guī)劃研究的一個(gè)大的突破，將是未來研究的方向。

［1］MOLLOY E，YANG H，BROWNE J.Feature-based modeling in design for assembly［J］.International Journal of Computer Integrated Manufacturing，1993，6（1）：119-125.

［2］WANG Junfeng，LI Shiqi，LIU Jihong，et al.Computer aided assembly planning：a survey［J］.Journal of Engineering Graphics，2005，25（2）：1-6（in Chinese）.［王峻峰，李世其，劉繼紅，等.計(jì)算機(jī)輔助裝配規(guī)劃研究綜述［J］.工程圖學(xué)學(xué)報(bào)，2005，25（2）：1-6.］

［3］GOTTIPOL U R B，GHOSH K.A simplified and efficient representation for evaluation and selection of assembly sequences［J］.Computers in Industry，2003，50（3）：251-264.

［4］WANG Y，LIU J H，LI L S.Assembly sequence merging based on assembly unit partitioning［J］.International Journal of Advanced Manufacturing Technology，2009，45（7／8）：808-820.

［5］LI Rong，F(xiàn)U Yili，F(xiàn)ENG Haibo.Assembly sequence planning based on connecter-structure knowledge［J］.Computer Integrated Manufacturing Systems，2008，14（6）：1130-1135（in Chinese）.［李 榮，付宜利，封海波.基于連接結(jié)構(gòu)知識(shí)的裝配序列規(guī)劃［J］.計(jì)算機(jī)集成制造系統(tǒng)，2008，14（6）：1130-1135.］

［6］LAZZERINI B，MARCELLONI F.A genetic algorithm for generation optimal assembly plans［J］.Artificial Intelligence in Engineering，2000，14（4）：319-329.

［7］TANG Qiuhua，LEI Zhe，DENG Mingxing.Study on assembly sequence planning based on improved ant colony algorithm［J］.Machinery Design &Manufacture，2012（5）：42-44（in Chinese）.［唐秋華，雷 喆，鄧明星.基于改進(jìn)蟻群算法的裝配序列規(guī)劃研究［J］.機(jī)械設(shè)計(jì)與制造，2012（5）：42-44.］

［8］WANG Y，LIU J H.Chaotic particle swarm optimization for assembly for assembly sequence planning［J］.Robotics and Computer-Integrated Manufacturing，2010，26（2）：212-222.

［9］XING Yanfeng，WANG Yansong.Assembly sequence planning based on a hybrid particle swarm optimization and genetic algorithm［J］.International Journal of Production Research，2012，50（24）：7303-7312.

［10］NING Lihua，GU Tianlong.Immune algorithm for assembly sequence planning problem［J］.Computer Integrated Manufacturing Systems，2007，13（1）：81-87（in Chinese）.［寧黎華，古天龍.基于免疫算法的裝配序列規(guī)劃問題求解［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007，13（1）：81-87.］

［11］MILNER J M，GRAVES S C，WHITNEY D E.Using simulated annealing to select least-cost assembly sequences［C］／／Proceedings of IEEE International Conference on Robotics and Automation.Washington，D.C.，USA：IEEE，1994：2058-2063.

［12］ZENG Bing，LI Mingfu，ZHANG Yi，et al.Research on assembly sequence planning on firefly algorithm［J］.Journal of Mechanical Engineering，2013，49（11）：177-184（in Chinese）.［曾 冰，李明富，張 翼，等.基于螢火蟲算法的裝配序列規(guī)劃研究［J］.機(jī)械工程學(xué)報(bào)，2013，49（11）：177-184.］

［13］DORIGO M，GAMBARDELLA L M.Ant colony systems：a cooperative learning approach to the traveling salesman problem［J］.IEEE Transcation on Evolutionary Computation，1997，1（1）：53-66.

［14］YOU Daoming，CHEN Jian.Application of ant system in multi-object traveling salesman problem［J］.Mimi-Micro Systems，2003，24（10）：1808-1811（in Chinese）.［游道明，陳堅(jiān).用螞蟻算法解決多目標(biāo)TSP問題［J］.小型微型計(jì)算機(jī)系統(tǒng)，2003，24（10）：1808-1811.］

［15］LI Zhi，XU Chuanpei，MO Wei.Initialization for synch renous sequential circuits based on ant algorithm &genetic algorithm［J］.Acta Electronica Sinica，2003，31（8）：1276-1280（in Chinese）.［李 智，許川佩，莫 瑋.基于螞蟻算法和遺傳算法的同步時(shí)序電路初始化［J］.電子學(xué)報(bào)，2003，31（8）：1276-1280.］

［16］LIAO C J，LIAO C C.An ant colony optimization algorithm for scheduling in agile manufacturing［J］.International Journal of Production Research，2008，46（7）：1813-1824.

［17］PENG Tao，LI Shiqi，WANG Junfeng，et al.Integrated interference matrix based ant colony algorithm for assembly sequence planning［J］.Computer Science，2010，37（4）：179-182（in Chinese）.［彭 濤，李世其，王峻峰，等.基于集成干涉矩陣的蟻群裝配序列規(guī)劃［J］.計(jì)算機(jī)科學(xué)，2010，37（4）：179-182.］

［18］WANG J F，LIU J H，ZHONG Y F.A novel ant colony algorithm for assembly sequence planning［J］.International Journal of Advanced Manufacturing Technology，2005，25（11／12）：1137-1143.

［19］YU Jiapeng，WANG Cheng'en，WANG Jianxi.Assembly sequence planning based on max-min ant colony system［J］.Journal of Mechanical Engineering，2012，48（23）：151-166（in Chinese）.［于嘉鵬，王成恩，王健熙.基于最大—最小蟻群系統(tǒng)的裝配序列規(guī)劃［J］.機(jī)械工程學(xué)報(bào)，2012，48（23）：151-166.］

［20］SHI Shicai，LI Rong，F(xiàn)U Yili，et al.Assembly sequence planning based on improved ant colony algorithm［J］.Computer Integrated Manufacturing Systems，2010，16（6）：1189-1194（in Chinese）.［史士財(cái)，李 榮，付宜利，等.基于改進(jìn)螞蟻算法的裝配序列規(guī)劃［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（6）：1189-1194.］

［21］LI Yuan，ZHANG Kaifu，WANG Ting，et al.Assembly sequence planning optimization for aircraft assembly based on GA［J］.Computer Integrated Manufacturing Systems，2006，12（2）：188-191（in Chinese）.［李 原，張開富，王 挺，等.基于遺傳算法的飛機(jī)裝配序列規(guī)劃優(yōu)化方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006，12（2）：188-191.］

［22］NING Lihua，GU Tianlong.Hybrid algorithm for assembly sequence planning［J］.Computer Integrated Manufacturing Systems，2007，13（4）：762-769，776（in Chinese）.［寧黎華，古天龍.裝配序列規(guī)劃問題求解的一種混合算法［J］.計(jì)算機(jī)集成制造，2007，13（4）：762-769，776.］

［23］YAO Junfeng，MEI Zhi，PENG Xiaoqi.The application research of the chaos genetic algorithm（CGA）and its evaluation of optimization efficiency［J］.Act Automatic Sinica，2002，28（6）：935-942（in Chinese）.［姚俊峰，梅 熾，彭小奇.混沌遺傳算法（CGA）的應(yīng)用研究及其優(yōu)化效率評(píng)價(jià)［J］.自動(dòng)化學(xué)報(bào)，2002，28（6）：935-942.］

［24］XU Xiaobo，ZHENG Kangfeng，LI Dan，et al.New chaosparticle swarm optimization algorithm［J］.Journal on Communication，2012，33（1）：24-30（in Chinese）.［胥小波，鄭康鋒，李丹，等.新的混沌粒子群優(yōu)化算法［J］.通信學(xué)報(bào)，2012，33（1）：24-30.］