史亞斌++李翌輝++吳安樂(lè)

摘 要：將引力搜索算法引入到復(fù)雜產(chǎn)品裝配序列規(guī)劃中，詳細(xì)討論了引力搜索算法在裝配規(guī)劃中的應(yīng)用。以裝配成本最低為目標(biāo)，采用裝配方向的重定向、裝配工具更換、裝配類(lèi)型的改變等三個(gè)裝配評(píng)價(jià)指標(biāo)，確定了序列規(guī)劃目標(biāo)函數(shù)；通過(guò)設(shè)置算法最大迭代次數(shù)、初始引力常數(shù)、衰減系數(shù)等計(jì)算參數(shù)，完成了序列規(guī)劃的迭代結(jié)束條件的設(shè)置與粒子引力合力的計(jì)算；通過(guò)對(duì)裝配序列的規(guī)劃結(jié)果進(jìn)行迭代更新，達(dá)到迭代結(jié)束條件后輸出了最優(yōu)解。以某型號(hào)攪拌機(jī)構(gòu)裝配為例，分析了引力搜索算法在復(fù)雜產(chǎn)品裝配序列規(guī)劃中的具體應(yīng)用與驗(yàn)證，結(jié)果表明：引力搜索算法能夠高效、合理地完成序列規(guī)劃優(yōu)化的計(jì)算，避免由于裝配序列枚舉引起的計(jì)算量較大的問(wèn)題。

關(guān)鍵詞：引力搜索算法 裝配成本 裝配序列規(guī)劃

中圖分類(lèi)號(hào)：TG95 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2017）10（c）-0136-04

Abstract： The gravitational search algorithm（GSA） is introduced into the planning of complex product assembly sequence， and the application of GSA in assembly planning is discussed in detail. With the minimum cost as the goal，a sequence planning objective function is determined. This function uses three assembly evaluation indexes such as redirection of assembly direction， replacement of assembly tools and change of assembly type. By setting the maximum number of iterations， the initial gravitational constants and the attenuation coefficients， the parameters of the iterative end condition of the sequence planning and the calculation of the force of the particle force are completed. The iterative updating of the planning result of the assembly sequence results in the optimal solution after the iteration end condition. Taking the assembly of a certain type of mixing mechanism as an example， the paper analyzes the application and verification of GSA in complex product assembly sequence planning. The results show that the GSA can efficiently and reasonably complete the calculation of sequence planning optimization and avoid the problem of large computation caused by the assembly sequence enumeration. The results show that the GSA can meet the requirements of assembly planning as well.

Key Words： Gravitational Search Algorithm； Assembly Cost； Assembly Sequence Planning

在現(xiàn)代設(shè)計(jì)與制造過(guò)程中，隨著產(chǎn)品結(jié)構(gòu)越來(lái)越復(fù)雜，零部件數(shù)量越來(lái)越多，零部件之間的裝配約束關(guān)系也隨之增多。研究表明，裝配序列數(shù)量與零部件數(shù)量呈指數(shù)增長(zhǎng)關(guān)系，因此，針對(duì)復(fù)雜產(chǎn)品進(jìn)行裝配規(guī)劃時(shí)，很容易導(dǎo)致序列組合爆炸問(wèn)題，工程師往往會(huì)憑借經(jīng)驗(yàn)，花費(fèi)大量的時(shí)間和精力來(lái)尋找裝配序列，而且找到的裝配序列往往不是可行裝配序列或最優(yōu)裝配序列。

2009年伊朗的克曼大學(xué)的Esmat Rashedi 等人基于牛頓的萬(wàn)有引力定律和第二運(yùn)動(dòng)定律提出了引力搜索算法[1]GSA（Gravitational Search Algorithm），該算法具有結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn)、參數(shù)設(shè)置少和全局優(yōu)化能力強(qiáng)等特點(diǎn)，且已經(jīng)在很多優(yōu)化問(wèn)題中都得到了成功應(yīng)用。本文利用引力搜索算法來(lái)解決復(fù)雜產(chǎn)品裝配序列規(guī)劃問(wèn)題，以獲取復(fù)雜產(chǎn)品的最優(yōu)裝配序列。

1 引力搜索算法在裝配序列規(guī)劃中的應(yīng)用

本文將引力搜索算法引入到裝配序列規(guī)劃當(dāng)中，通過(guò)對(duì)在裝配過(guò)程的影響因素進(jìn)行分析，構(gòu)建適應(yīng)度函數(shù)，以裝配成本作為評(píng)價(jià)裝配序列優(yōu)劣的標(biāo)準(zhǔn)，同時(shí)根據(jù)零部件的幾何約束關(guān)系構(gòu)建裝配約束數(shù)學(xué)模型，保證裝配序列的正確性與可行性?；谝λ阉魉惴ㄑb配序列規(guī)劃步驟如下。

1.1 待裝配零件群體和序列規(guī)劃目標(biāo)函數(shù)的確定

假設(shè)復(fù)雜產(chǎn)品的裝配體由個(gè)待裝配零件組成，此時(shí)搜索空間就為N維搜索空間，則在搜索空間中的第個(gè)粒子的位置標(biāo)記為：

（1）

其中表示該粒子在第d維搜索空間的位置。

將適應(yīng)度函數(shù)作為裝配序列規(guī)劃中的目標(biāo)函數(shù)，采用裝配成本來(lái)構(gòu)造適應(yīng)度函數(shù)，包括裝配方向的重定向、裝配工具更換、裝配類(lèi)型的改變。endprint

依據(jù)上述3個(gè)評(píng)價(jià)標(biāo)準(zhǔn)分別添加權(quán)重系數(shù)，構(gòu)造適應(yīng)度函數(shù)為：

（2）

上式中，表示粒子的裝配花費(fèi)成本，表示第個(gè)零件到第個(gè)零件在裝配過(guò)程的成本，其中公式為：

（3）

其中，表示完成第個(gè)零件到第個(gè)零件的裝配過(guò)程所花費(fèi)的成本，，代表裝配方向的重定向次數(shù)，代表裝配工具更換次數(shù)，代表裝配類(lèi)型的改變次數(shù)，d是裝配方向的重新定向在總裝配成本中的權(quán)重系數(shù)，是裝配工具更換在總裝配成本中的權(quán)重系數(shù)，是裝配類(lèi)型的改變?cè)诳傃b配成本中的權(quán)重系數(shù)，且滿(mǎn)足。

1.2 設(shè)置序列規(guī)劃的迭代結(jié)束條件并進(jìn)行粒子引力合力的計(jì)算

設(shè)置算法最大迭代次數(shù)T為100，設(shè)置初始迭代值t為0， 指的是在t時(shí)刻粒子的適應(yīng)度函數(shù)值，即代表當(dāng)前裝配序列裝配成本。和是t時(shí)刻粒子群中最差函數(shù)值和最優(yōu)函數(shù)值，即當(dāng)前裝配可能序列中的最差適應(yīng)度函數(shù)值和最優(yōu)適應(yīng)度函數(shù)值，定義解決該裝配序列規(guī)劃問(wèn)題時(shí)使用最小排序規(guī)則，則：

（4）

（5）

根據(jù)當(dāng)前粒子的最差函數(shù)值式（4）和最優(yōu)函數(shù)值式（5），計(jì)算出當(dāng)前t時(shí)刻粒子的質(zhì)量。

（6）

（7）

萬(wàn)有引力常數(shù)公式定義為：

（8）

其中，為衰減系數(shù)，為初始引力常數(shù)，T為實(shí)際計(jì)算中定義的最大迭代次數(shù)或者時(shí)間周期，這樣就保證引力常數(shù)是隨著時(shí)間改變的變量。本文設(shè)置初始引力常數(shù)為100，衰減系數(shù)為20。

在粒子搜索的過(guò)程中由于慣性質(zhì)量小的粒子向慣性質(zhì)量大的粒子方向移動(dòng)，因此粒子間的距離是逐漸變小的，定義萬(wàn)有引力公式為：

（9）

式（9）中，是一個(gè)常數(shù)，當(dāng)兩個(gè)粒子隨著迭代的運(yùn)行，粒子之間的距離逐漸減小直至重合，此時(shí)為0，分母為0不符合定義，因此設(shè)置是保障分母不為0從而保證公式的正確性，本文中將常數(shù)設(shè)置為5。即為粒子分別受到群體中其他粒子萬(wàn)有引力的大小。在實(shí)際應(yīng)用中，粒子在特定系統(tǒng)中受到的是粒子群中其他粒子的共同作用，因此需要根據(jù)計(jì)算粒子的萬(wàn)有引力合力。定義如下：

（10）

其中Rand代表的是隨機(jī)數(shù)，該隨機(jī)數(shù)取值范圍是[0，1]，設(shè)置該隨機(jī)數(shù)的目的是為了防止算法求解陷入局部最優(yōu)，體現(xiàn)算法具有的隨機(jī)性特點(diǎn)，得出的結(jié)果更符合實(shí)際情況。

1.3 對(duì)裝配序列的規(guī)劃結(jié)果進(jìn)行迭代更新，達(dá)到迭代結(jié)束條件后輸出最優(yōu)解

利用公式（2～10）得出粒子的合力，由牛頓第二運(yùn)動(dòng)定律求得t時(shí)刻粒子的加速度：

（11）

根據(jù)t時(shí)刻已確定的粒子速度和位置，更新t+1時(shí)刻粒子的、粒子的位置：

（12）

（13）

在的定義中，Rand同樣代表的是隨機(jī)數(shù)，該隨機(jī)數(shù)取值范圍是[0，1]。通過(guò)對(duì)粒子速度和位置的不斷更新于迭代，進(jìn)而不斷優(yōu)化裝配序列規(guī)劃結(jié)果。

本文中迭代結(jié)束條件為達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)，當(dāng)達(dá)到最大迭代次數(shù)就停止循環(huán)，并輸出此時(shí)每個(gè)粒子的位置值，根據(jù)以上定義為最小排序規(guī)則，將的最終輸出值按從小到大排序，則得出的序列為使用引力搜索計(jì)算出的裝配序列。

2 裝配序列實(shí)例分析與驗(yàn)證

本文以某攪拌機(jī)構(gòu)的裝配序列規(guī)劃為例，對(duì)基于引力搜索算法的裝配序列規(guī)劃方法進(jìn)行分析與驗(yàn)證。

在不影響裝配規(guī)劃結(jié)果的前提下，為了減少計(jì)算量，提高計(jì)算速度，本文對(duì)攪拌機(jī)構(gòu)的實(shí)際裝配情況做如下簡(jiǎn)化。

（1）將攪拌機(jī)構(gòu)的所有零部件都看作是剛體，同時(shí)，忽略零部件在裝配過(guò)程中產(chǎn)生的變形、公差累積等影響因素。

（2）只考慮每個(gè)零部件沿±X、±Y、±Z六個(gè)坐標(biāo)軸方向的平移與旋轉(zhuǎn)的裝配，而不考慮零件沿其他方向的旋轉(zhuǎn)裝配。

（3）本文研究的產(chǎn)品模型不涉及電氣、非機(jī)械零部件以及螺釘?shù)嚷?lián)接件。

（4）在裝配過(guò)程中，一個(gè)零件一次只能在一個(gè)方向裝配。

簡(jiǎn)化后該機(jī)構(gòu)主要包含14個(gè)零件，如圖1所示。

攪拌機(jī)構(gòu)零部件爆炸圖如圖2所示，其中，、…表示每個(gè)零件的編號(hào)。

零件序號(hào)、零部件名稱(chēng)以及零件編號(hào)的對(duì)照表如表1所示。

由于攪拌機(jī)構(gòu)簡(jiǎn)化后有14個(gè)零部件，則搜索空間為14維，該群體中第粒子的位置標(biāo)記為：

其中，所構(gòu)造的適應(yīng)度函數(shù)為：

基于引力搜索算法的裝配序列規(guī)劃中執(zhí)行步驟進(jìn)行編碼，并按照參數(shù)討論中得出的相關(guān)結(jié)論設(shè)置參數(shù)值，將的最終輸出值按從小到大規(guī)則排序后輸出最優(yōu)裝配序列，如表1所示。由于篇幅限制只列出最后20次的運(yùn)行結(jié)果，第一行代表的是裝配前各零件的編號(hào)，總共有14個(gè)零件則編號(hào)為1～14，最后一行代表的是經(jīng)過(guò)引力搜索算法計(jì)算后最終輸出的裝配序列。

從程序運(yùn)算輸出的裝配序列分析可知，該序列裝配穩(wěn)定性較佳，裝配方向改變次數(shù)較少，滿(mǎn)足實(shí)際裝配過(guò)程的要求，零件裝配序列中未出現(xiàn)裝配干涉的情況，滿(mǎn)足幾何可行性的要求。搜索代理相互之間由于萬(wàn)有引力作用會(huì)聚集在一起，因此用引力搜索算法來(lái)解決序列規(guī)劃這種非線性?xún)?yōu)化問(wèn)題具有自身優(yōu)越性，符合裝配規(guī)劃的需求，可使裝配序列更加合理、更能夠貼近實(shí)際的裝配過(guò)程，大大提高了運(yùn)算效率，可有效解決由于零件數(shù)量較多對(duì)所有裝配序列一一枚舉時(shí)引起計(jì)算量較大的問(wèn)題，從而避免對(duì)所有裝配序列進(jìn)行全排列。

3 結(jié)語(yǔ)

產(chǎn)品的設(shè)計(jì)制造中，合理高效的裝配序列規(guī)劃起到了非常重要的作用，決定了產(chǎn)品設(shè)計(jì)制造方案是否合理與可行。本文將最低裝配成本作為優(yōu)化目標(biāo)，提出了基于引力搜索算法的裝配序列規(guī)劃方法，通過(guò)建立產(chǎn)品裝配序列優(yōu)化模型，利用粒子位置和速度更新規(guī)則，實(shí)現(xiàn)了復(fù)雜產(chǎn)品裝配規(guī)劃序列的尋優(yōu)，并通過(guò)攪拌機(jī)構(gòu)裝配序列規(guī)劃的實(shí)例，對(duì)算法進(jìn)行了分析和驗(yàn)證，結(jié)果表明，基于引力搜索算法的裝配序列規(guī)劃方法具有穩(wěn)定性好、收斂速度快等優(yōu)點(diǎn)，可有效提高復(fù)雜產(chǎn)品最優(yōu)裝配序列規(guī)劃的效率。

參考文獻(xiàn)

[1] Esmat Rashedi，Hossein Nezamabadi-pour，Saeid Saryazdi.A Gravitational Search Algorithm[J].Information Sciences，2009，179（13）：2232-2248.

[2] 張愛(ài)竹，孫根云，王振杰，等.一種基于數(shù)據(jù)場(chǎng)的多目標(biāo)引力搜索算法[J].控制與決策，2017，32（1）：47-54.

[3] 陶俐言，楊海斌.基于改進(jìn)引力搜索算法的公差多目標(biāo)優(yōu)化設(shè)計(jì)[J].機(jī)械設(shè)計(jì)與研究，2017，33（2）：133-137.endprint