基于引力搜索算法的復雜產(chǎn)品裝配規(guī)劃研究

史亞斌++李翌輝++吳安樂

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

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

中圖分類號：TG95 文獻標識碼：A 文章編號：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)代設計與制造過程中，隨著產(chǎn)品結(jié)構(gòu)越來越復雜，零部件數(shù)量越來越多，零部件之間的裝配約束關系也隨之增多。研究表明，裝配序列數(shù)量與零部件數(shù)量呈指數(shù)增長關系，因此，針對復雜產(chǎn)品進行裝配規(guī)劃時，很容易導致序列組合爆炸問題，工程師往往會憑借經(jīng)驗，花費大量的時間和精力來尋找裝配序列，而且找到的裝配序列往往不是可行裝配序列或最優(yōu)裝配序列。

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

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

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

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

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

（1）

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

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

依據(jù)上述3個評價標準分別添加權(quán)重系數(shù)，構(gòu)造適應度函數(shù)為：

（2）

上式中，表示粒子的裝配花費成本，表示第個零件到第個零件在裝配過程的成本，其中公式為：

（3）

其中，表示完成第個零件到第個零件的裝配過程所花費的成本，，代表裝配方向的重定向次數(shù)，代表裝配工具更換次數(shù)，代表裝配類型的改變次數(shù)，d是裝配方向的重新定向在總裝配成本中的權(quán)重系數(shù)，是裝配工具更換在總裝配成本中的權(quán)重系數(shù)，是裝配類型的改變在總裝配成本中的權(quán)重系數(shù)，且滿足。

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

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

（4）

（5）

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

（6）

（7）

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

（8）

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

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

（9）

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

（10）

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

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

利用公式（2～10）得出粒子的合力，由牛頓第二運動定律求得t時刻粒子的加速度：

（11）

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

（12）

（13）

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

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

2 裝配序列實例分析與驗證

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

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

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

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

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

（4）在裝配過程中，一個零件一次只能在一個方向裝配。

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

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

零件序號、零部件名稱以及零件編號的對照表如表1所示。

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

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

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

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

3 結(jié)語

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

參考文獻

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

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

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