王哲

（合肥工業(yè)大學(xué)機(jī)械與汽車(chē)工程學(xué)院，合肥230009）

0 引言

拆卸是采用一定的工具和手段，解除對(duì)零件造成約束的各種聯(lián)接，將產(chǎn)品零部件逐個(gè)分離的過(guò)程。拆卸序列規(guī)劃的定義為，在滿足產(chǎn)品結(jié)構(gòu)和裝配關(guān)系等要求的前提下，生成零件拆卸序列的過(guò)程［1］。為了獲得能夠滿足裝配約束要求的拆卸序列，并對(duì)拆卸序列進(jìn)行優(yōu)化，提高拆卸效率及其使用價(jià)值，本文提出了基于拆卸混合圖的拆卸序列優(yōu)化模型［2］，并在獲得滿足要求的拆卸序列后使用遺傳算法進(jìn)行優(yōu)化求解。為了方便裝配件拆卸信息的管理及拆卸序列的優(yōu)化，編寫(xiě)了拆卸分析系統(tǒng)，通過(guò)它可以計(jì)算得到近似最優(yōu)序列。

1 拆卸序列模型

1.1 拆卸信息模型

本文考慮的產(chǎn)品拆卸信息模型主要包括三個(gè)部分：零件基本信息、拆卸過(guò)程信息及裝配信息。零件基本信息主要包括該零件的名稱(chēng)、體積、重量等具體信息；拆卸過(guò)程信息即所使用的拆卸工具、拆卸時(shí)間等信息；而裝配信息則主要是考慮零件拆卸過(guò)程中的約束關(guān)系。

根據(jù)以上拆卸信息模型采用混合圖進(jìn)行建模。拆卸混合圖是一種常用的拆卸信息建模方法，如圖1所示?；旌蠄D的頂點(diǎn)定義為產(chǎn)品的零件或部件，有向邊或無(wú)向邊分別表示了零部件之間的裝配約束關(guān)系。

拆卸混合圖可以用集合形式表示為

式中：G 為混合圖集合；V=｛v1，v2，…，vn｝表示零部件集合；UE=｛ue1，ue2，…，uen｝是無(wú)向邊集合，表示零件之間無(wú)接觸約束關(guān)系；DE=｛de1，de2，…，den｝為有向邊集合，表示零件之間存在拆卸優(yōu)先關(guān)系，即有接觸約束關(guān)系。

拆卸混合圖可以很清楚地反映出零件直接的拆卸約束關(guān)系，但是計(jì)算機(jī)是無(wú)法直接識(shí)別這類(lèi)圖模型的，因此必須對(duì)其進(jìn)行數(shù)字化處理。本文采用連接矩陣和優(yōu)先矩陣來(lái)表達(dá)。

即可將混合圖 G=｛V，UE，DE｝分解為 GC=｛V，UE｝和GP=｛V，DE｝。對(duì)于連接矩陣

其中，

特別規(guī)定當(dāng)i=j時(shí)，cij=0。

對(duì)于連接矩陣

其中，

對(duì)于如圖1所示拆卸混合圖即可表示為：

1.2 拆卸序列生成

拆卸序列的生成基于定向搜索策略，即在優(yōu)先關(guān)系矩陣的引導(dǎo)下，生成拆卸序列。具體流程如圖2所示。

圖2 拆卸序列生成圖

驗(yàn)證表明隨機(jī)選取零件作為拆卸的起始點(diǎn)比指定初始拆卸零件速度要快很多，其關(guān)鍵在于拆卸優(yōu)先關(guān)系的合理定義和全面表述。根據(jù)此流程產(chǎn)生的拆卸序列作為初始序列能夠滿足拆卸的優(yōu)先關(guān)系，因此初始序列是合理可行的。通過(guò)此方法能夠快速地生成足量的初始拆卸序列。

1.3 拆卸序列的優(yōu)化

影響拆卸效率的兩個(gè)主要因素是拆卸方向的變更次數(shù)與拆卸工具的更換次數(shù)，因此拆卸序列的優(yōu)化函數(shù)構(gòu)建應(yīng)主要考慮這兩方面。對(duì)于所得拆卸序列s，構(gòu)建的適應(yīng)度計(jì)算公式如下：

其中：ωd和ωt分別代表拆卸方向和拆卸工具的權(quán)重，n為拆卸序列中所含零件總數(shù)，常數(shù)C為保證適應(yīng)度隨著時(shí)間增大而減小。對(duì)于 di，i+1和 ti，i+1，則有：

2 拆卸序列優(yōu)化模型求解

拆卸序列規(guī)劃實(shí)際上是一個(gè)NP組合優(yōu)化的問(wèn)題，傳統(tǒng)的拆卸序列規(guī)劃方法大多是基于圖搜索的方法，但是圖搜索算法存在其弊端，即隨著被拆卸深度的增加，無(wú)法規(guī)避組合爆炸問(wèn)題。

遺傳算法無(wú)需遍歷整個(gè)搜索空間就能夠得到最優(yōu)或是次最優(yōu)解，就能夠很好地解決組合爆炸問(wèn)題。遺傳算法是由美國(guó)Michigan大學(xué)的John Holland與其同事、學(xué)生們基于生物進(jìn)化論中的自然選擇和群體遺傳學(xué)規(guī)律而提出的一種優(yōu)化搜索算法［3］?；舅枷胧牵喊颜麄€(gè)待拆卸體信息庫(kù)空間映射成遺傳空間，將具體零部件信息映射成遺傳染色體，對(duì)其中的所有個(gè)體進(jìn)行適應(yīng)度大小的計(jì)算。之后對(duì)群體進(jìn)行選擇、交叉或變異等遺傳操作，適應(yīng)度小的個(gè)體自行淘汰，適應(yīng)度大的個(gè)體保存下來(lái)。通過(guò)指定代數(shù)的反復(fù)操作或者達(dá)到適應(yīng)度閾值后，求出最優(yōu)個(gè)體。

具體算法流程圖如圖3所示。

2.1 染色體構(gòu)造

在遺傳算法中把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱(chēng)為編碼。編碼決定了交叉、變異等遺傳運(yùn)算方法，能夠極大地影響算法的運(yùn)行效率。

對(duì)于零部件的拆卸序列，直接采用零件序號(hào)進(jìn)行實(shí)數(shù)編碼明顯更加方便與合理。實(shí)數(shù)編碼省去了編碼和解碼的過(guò)程，更利于算法的實(shí)施。如染色體為“1，2，3，4，5”的一種拆卸序列為：1→4→2→3→5。

圖3 遺傳算法流程

2.2 交叉算子

交叉操作又稱(chēng)為基因重組，就是按給定的交叉概率Pc，從群體中隨機(jī)選取2個(gè)父?jìng)€(gè)體，互相替換2個(gè)父?jìng)€(gè)體的其中一部分結(jié)構(gòu)，之后進(jìn)行重組形成新個(gè)體的操作。交叉操作是生成新個(gè)體的主要方式，能夠提高算法的全局搜索能力。本模型采用的是部分映射交叉法，即在父?jìng)€(gè)體中選擇一個(gè)子序列并且在替換到另一個(gè)父?jìng)€(gè)體時(shí)次序和位置盡可能不變。方式如下：

隨機(jī)父?jìng)€(gè)體 1：1→2→|3→4|→5。

隨機(jī)父?jìng)€(gè)體 2：1→4→|2→3|→5。

交換兩父體字串：1→2→|2→3|→5；1→4→|3→4|→5。

映射關(guān)系為：2→3→4。

映射后的子代為：1→4→|2→3|→5；1→2→|3→4|→5。

2.3 變異操作

變異是以較小的概率對(duì)染色體串上的某些位值進(jìn)行改變，從而形成新的個(gè)體的過(guò)程。變異操作決定了遺傳算法的局部搜索能力，是產(chǎn)生新個(gè)體的輔助方法。

本模型采用的是置換變異方法，即隨機(jī)選擇2個(gè)基因，置換它們彼此在序列中的位置，并且要注意的是這種置換并不能改變零件之間的拆卸優(yōu)先關(guān)系。舉例如下：

父?jìng)€(gè)體 1：1→2→3→4→5。

選擇3、4進(jìn)行置換后的序列為：1→2→4→3→5。

3 軟件設(shè)計(jì)

3.1 軟件設(shè)計(jì)思想

為了實(shí)現(xiàn)便捷地拆卸序列規(guī)劃操作，基于拆卸序列優(yōu)化開(kāi)發(fā)了一個(gè)計(jì)算系統(tǒng)。系統(tǒng)主要設(shè)計(jì)思想是：令使用者在輸入相對(duì)較少產(chǎn)品零件信息的基礎(chǔ)上，通過(guò)該系統(tǒng)可以對(duì)產(chǎn)品進(jìn)行拆卸分析，生成拆卸序列，并對(duì)產(chǎn)品的拆卸序列進(jìn)行回收評(píng)估，之后運(yùn)用遺傳算法進(jìn)行優(yōu)化，得出最優(yōu)或近似最優(yōu)的拆卸序列。

3.2 參數(shù)選擇

本文中采用基因組的編碼方式表達(dá)裝配體中零件的信息。一個(gè)基因組封裝了零件拆卸中所有相關(guān)的信息，同時(shí)也是在數(shù)據(jù)庫(kù)中儲(chǔ)存的基本單元?；蚪M采用三位碼編碼，包括零件編號(hào)、拆卸工具、拆卸方向信息。表示如下：

其中：PID表示零件編號(hào)，由數(shù)據(jù)庫(kù)自動(dòng)生成；P_Tool表示拆卸工具編號(hào)，對(duì)應(yīng)拆卸工具表中的工具；P_Direction表示拆卸方向，主要有｛+X，-X，+Y，-Y，+Z，-Z｝6個(gè)方向。

表1 Part數(shù)據(jù)庫(kù)字段表

遺傳算法中的參數(shù)選擇主要有群體規(guī)模S，交叉概率PC，變異概率Pm，終止條件等。這些參數(shù)的選擇對(duì)算法的運(yùn)行性能影響較大，不恰當(dāng)?shù)倪x擇會(huì)導(dǎo)致算法運(yùn)行緩慢。

群體規(guī)模S表示群體中所含個(gè)體的數(shù)量，在本模型中即為零件個(gè)數(shù)，一般的取值范圍是20～100；交叉概率PC，交叉操作是新序列生成的主要方式，所以交叉概率應(yīng)取較大值，一般的取值范圍是0.4～0.99；變異概率Pm，變異概率太小會(huì)是遺傳算法趨近隨機(jī)搜索，太大又會(huì)使產(chǎn)生新個(gè)體能力變差，一般取值范圍是0.0001～0.1；終止條件主要是終止代數(shù)或適應(yīng)度最小準(zhǔn)則。終止代數(shù)指的是遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)G之后就停止運(yùn)行，取出群體適應(yīng)度最佳的個(gè)體作為所求問(wèn)題的最優(yōu)解輸出；另一種終止條件是給定一個(gè)閾值C，當(dāng)其連續(xù)L代的平均適應(yīng)度差異小于該值時(shí)停止。

3.3 軟件結(jié)構(gòu)及系統(tǒng)流程

系統(tǒng)集成了多個(gè)模塊的功能，其中產(chǎn)品模型信息管理、拆卸序列分析、拆卸序列優(yōu)化等。系統(tǒng)具體工作流程如圖4所示。

實(shí)現(xiàn)系統(tǒng)邏輯的偽代碼表示如下∶

Initialize(s);//載入并初始化序列

Verify(x)

{驗(yàn)證序列x是否符合拆卸優(yōu)先順序}

Get_Fitness(x)

{按公式計(jì)算個(gè)體適應(yīng)度值

returen Fs;}

Verify(Random(s));//隨機(jī)打亂并驗(yàn)證序列s是否符合拆卸優(yōu)先順序

for(i=0;Fs＜=C||i＜=G;i++)//C代表給定的終止閾值,G代表給定的進(jìn)化代數(shù)

{

While(Verify(s))

{Intersect(s);//交叉操作

圖4 軟件邏輯流程

Mutate(s);//變異操作

Get_Fitness(s);//計(jì)算個(gè)體適應(yīng)度}

}

輸出結(jié)果;

3.4 操作實(shí)例

圖5為某裝配體的裝配體信息管理界面，該裝配體由12個(gè)零件組成，界面支持裝配體信息及零件信息的添加刪除修改。

圖6為拆卸序列規(guī)劃界面，在參數(shù)設(shè)定框體中輸入預(yù)先設(shè)定的遺傳算法參數(shù)，這里取交叉概率PC=0.5，變異概率Pm=0.05，終止代數(shù)G=50，適應(yīng)度閾值=180。生成初始序列為 8→9→2→10→3→4→11→1→12→7→5→6，之后點(diǎn)擊計(jì)算即可在滿足終止條件時(shí)生成最優(yōu)或近似最優(yōu)解，即 3→5→8→9→2→10→11→1→12→7→4→6。經(jīng)驗(yàn)證，所得拆卸序列符合約束條件且為適應(yīng)度最大解，證明軟件從算法的執(zhí)行上是可行的。

圖6 拆卸序列規(guī)劃界面

4 結(jié)語(yǔ)

本文提出了基于拆卸混合圖的拆卸序列優(yōu)化模型，并對(duì)序列優(yōu)化的適應(yīng)度進(jìn)行了闡述。之后給出了使用遺傳算法的拆卸序列模型求解辦法。為方便裝配件拆卸信息的管理及拆卸序列計(jì)算，編寫(xiě)了拆卸分析系統(tǒng)，計(jì)算了實(shí)例并獲得了最優(yōu)或近似最優(yōu)拆卸序列，證明了軟件的可用性。能夠?yàn)檠b配件信息管理及拆卸序列的智能生成提供一定的支持。

［1］ 劉志峰，胡迪，高洋，等.基于貪婪算法的產(chǎn)品拆卸序列規(guī)劃［J］.中國(guó)機(jī)械工程，2011（18）：2162-2166.

［2］ Zhang H C，Kuo T C.A Graph-Based Approach to Disassembly Model for End-of-Life Product Recycling［C］//IEEE/CPMT International Electronics Manufacturing Technology Symposium，1996：247-254.

［3］ 韓建升.基于遺傳算法的拆卸序列規(guī)劃研究［D］.武漢：華中科技大學(xué)，2007.

［4］ Silveira L R，Tanscheit R，Vellasco M.Quantum-Inspired Genetic Algorithms applied to Ordering ombinatorialptimization Problems［C］//WCCI2012IEEEWorld Congresson Computational Intelligence June，10-15，2012，Brisbane，Australia.

［5］ 張秀芬，張樹(shù)有.基于粒子群算法的產(chǎn)品拆卸序列規(guī)劃方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2009（3）：508-514.

［6］ 江吉彬，劉志峰，劉光復(fù).基于工程語(yǔ)義信息的拆卸序列規(guī)劃算法研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006（4）∶625-629.

［7］ 趙樹(shù)恩，李玉玲.模糊推理Petri網(wǎng)及其在產(chǎn)品拆卸序列決策中的應(yīng)用［J］.控制與決策，2005（10）∶1181-1184，1188.

［8］ 章小紅，李世其，王峻峰，等.基于蟻群算法的單目標(biāo)選擇性拆卸序列規(guī)劃研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007，13（6）∶1109-1114.

［9］ 謝歆，趙國(guó)華.Visual C++高級(jí)編程實(shí)例精解［M］.北京∶國(guó)防工業(yè)出版社，2001.