王光慧，胡赤兵，賀成柱

(1. 蘭州理工大學(xué)，甘肅 蘭州 730050； 2. 甘肅省機(jī)械科學(xué)研究院，甘肅 蘭州 730050)

?

基于改進(jìn)遺傳算法的虛擬裝配路徑規(guī)劃研究

王光慧1,2，胡赤兵1，賀成柱2

(1. 蘭州理工大學(xué)，甘肅 蘭州 730050； 2. 甘肅省機(jī)械科學(xué)研究院，甘肅 蘭州 730050)

摘要：裝配路徑規(guī)劃是虛擬裝配技術(shù)的核心，為了獲得最優(yōu)裝配路徑，在凸四邊形障礙物環(huán)境中，通過對初始種群選取方法的重新定義，保證了參加演化算法的每條染色體都是可行的，同時(shí)對傳統(tǒng)遺傳算法中的變異算子和雜交算子進(jìn)行改進(jìn)，提高了算法的有效性。最后實(shí)驗(yàn)證明將改進(jìn)的遺傳算法運(yùn)用到機(jī)械式減速箱裝配中可得到更優(yōu)的裝配路徑。

關(guān)鍵詞：路徑規(guī)劃；網(wǎng)狀圖；改進(jìn)遺傳算法；基因表；最短路徑

0引言

虛擬裝配在近幾十年發(fā)展較快，作為虛擬裝配核心的裝配路徑規(guī)劃更是得到了國內(nèi)外學(xué)者的廣泛應(yīng)用[1,2]。路徑規(guī)劃是指在虛擬環(huán)境中零部件在組裝成產(chǎn)品時(shí)所應(yīng)遵循的空間路徑，就是尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)且避免與周圍的障礙物相碰撞的避障路徑以及如何使這條避障路徑最短最優(yōu)。

虛擬裝配路徑規(guī)劃主要包括虛擬裝配環(huán)境模型的建立和路徑規(guī)劃演化算法的設(shè)計(jì)。其中環(huán)境模型的建立目前應(yīng)用較廣的有柵格表示法[3]和最小多邊形包圍盒法[4]。柵格法中柵格大小的劃分是個(gè)難題，柵格越小計(jì)算結(jié)果越精確，但需要大量的存儲空間和搜索距離。本文用凸四邊形包圍障礙物，這樣不僅可以消除由于頂點(diǎn)數(shù)目繁多而引起的算法效率低下，而且可以較精確逼真地描述障礙物空間。目前主要的路徑規(guī)劃演化算法有遺傳算法[5]、蟻群算法[6]、模擬退火算法[7]、粒子群算法[8]、郭濤算法[9]等。其中遺傳算法(GA)在多目標(biāo)虛擬裝配路徑規(guī)劃[10]和移動機(jī)器人路徑規(guī)劃[11]中得到廣泛應(yīng)用，但其初始種群都采用隨機(jī)方式選取，這樣使得計(jì)算量大，缺乏目的性，算法的收斂性也差。并且交叉算子和變異算子都是針對兩條染色體進(jìn)行，這樣雖然可以在一定程度上提高了算法的收斂速度，但是容易陷入局部最優(yōu)。為了解決此問題，本文提出了一種改進(jìn)的遺傳算法(IGA)，首先提出一種定義初始種群的全新有效方法，以基因表為條件，以網(wǎng)狀圖為方法，使得到的初始種群都是有效的，然后對選定的一條染色體進(jìn)行變異雜交運(yùn)算。本文以農(nóng)業(yè)機(jī)械的機(jī)械式減速器為模型，研究其虛擬裝配路徑規(guī)劃問題。

1空間環(huán)境的建立

1.1　裝配環(huán)境建模

用凸四邊形表示障礙物，并且將四邊形放大一個(gè)目標(biāo)物安全行走的距離，然后將三維障礙空間投射到二維平面上，形成如圖1所示的裝配環(huán)境地形圖。

圖1　環(huán)境地形圖

定義：M表示障礙物環(huán)境空間，R={Ri∣i=1,2…}表示障礙物。為了編碼方便，令障礙物的所有頂點(diǎn)以及起始點(diǎn)、目標(biāo)點(diǎn)統(tǒng)稱為頂點(diǎn)，按順時(shí)針方向編碼，以頂點(diǎn)集合V為編碼空間，頂點(diǎn)集合為V={vi∣i=0,1,2,…,n}，其中v0表示起始點(diǎn)S，vn表示目標(biāo)點(diǎn)T，(xi,yi)為頂點(diǎn)vi的坐標(biāo)，vi-vj表示兩頂點(diǎn)相連，四邊形各邊集合為E={ei∣i=1,2,…}。

1.2　編碼方式

采用實(shí)數(shù)編碼，因?yàn)閷?shí)數(shù)編碼是直接以解空間的形式進(jìn)行編碼，這樣大大縮短了串長，擴(kuò)大搜索域，對一些多維，高精度連續(xù)函數(shù)的優(yōu)化問題同樣適用。采用順序表達(dá)方法，如：路徑Pi={S,v2,v5,v6,T}表示從起始點(diǎn)S依次到頂點(diǎn)v2-v5-v6再到目標(biāo)點(diǎn)T的一條路徑，其中起始點(diǎn)S和目標(biāo)點(diǎn)T的位置始終不變。

1.3　成本矩陣

兩頂點(diǎn)連線與多邊形的邊相交時(shí)，d=∞，兩頂點(diǎn)相同時(shí)d=0。數(shù)學(xué)表達(dá)式為：

(1)

成本矩陣的計(jì)算式：

C[i][j]=d(vi,vj)

(2)

由式(1)和式(2)可得圖1的成本矩陣為：

(3)

2算法設(shè)計(jì)

2.1　初始種群的選取

為了保證初始種群的有效性，避免引入非法路徑，路徑的選取必須滿足一定的條件，將這些條件匯總成表格，在此命為條件基因表。如以成本矩陣(3)為基礎(chǔ)提取信息，得圖1中與各個(gè)頂點(diǎn)可相連的基因表，如表1所示。

表1　基因表

根據(jù)基因表從起點(diǎn)S到目標(biāo)點(diǎn)T的初始路徑應(yīng)該滿足條件：1)路徑合法，不與障礙物相交；2)為了避免形成環(huán)路，與頂點(diǎn)vi相連的下一個(gè)頂點(diǎn)vj的位置應(yīng)比vi到目標(biāo)點(diǎn)T近。可用網(wǎng)狀圖2來表示初始種群的選擇過程。

圖2　網(wǎng)狀圖

圖2中每一條由S到T的合理路徑構(gòu)成了初始種群P={Pi|i=1,2,…,N}，如Pi={v0,v2,v5,v8,v7,v9}。用此方法得到的初始種群，避免了以往用隨機(jī)方法產(chǎn)生的無用染色體，讓隨后的算法在合理可行的染色體上進(jìn)行，大大提高了算法的有效性，節(jié)省運(yùn)算時(shí)間。當(dāng)障礙物較少時(shí)初始路徑的選取不是很龐大，可以直接用此方法搜索出最短路徑，無需進(jìn)行后續(xù)工作。

2.2　目標(biāo)函數(shù)

本研究的目的是尋求最短裝配路徑，其目標(biāo)函數(shù)是計(jì)算每條路徑的長度，將一條路徑的長度作為該路徑的適應(yīng)度函數(shù)，路徑越短其適應(yīng)度越好。適應(yīng)度函數(shù)：

(4)

2.3　選擇算子

用樹形圖法得到初始種群數(shù)量較多，為了提高算法的效率，從初始種群P中選擇M條染色體構(gòu)成解空間Q參加演化計(jì)算。具體方法是：根據(jù)式(4)求出P中每條染色體的適應(yīng)度值f(Pi)，并從大到小排序，選取前M個(gè)適應(yīng)度值較大的染色體構(gòu)成Q={Qi|i=1,2,…,M}，P中剩余的染色體構(gòu)成P’={Pi’|i=1,2,…,N-M}。本文選擇適應(yīng)性較差的個(gè)體進(jìn)行演化算法，目的是為了防止P中適應(yīng)性好的個(gè)體在演化過程中失去它的優(yōu)越性。

2.4　變異算子

變異算子是對某些染色體的某一處基因進(jìn)行替換，主要是針對適應(yīng)性較差的個(gè)體進(jìn)行。傳統(tǒng)的變異操作是互換兩條染色體中的某一個(gè)基因位，此處是針對一條染色體進(jìn)行變異操作。具體為選擇染色體Qi中的一個(gè)基因點(diǎn)ai，根據(jù)表1選出ai對應(yīng)的下一個(gè)基因點(diǎn)為bi、ci…,并分別用bi、ci…替換掉Qi中ai的下一個(gè)基因點(diǎn)，計(jì)算各自的適應(yīng)度值，求得適應(yīng)度值最小的Qj，將Qj賦給Qi。依次進(jìn)行，直到Qi中的每一個(gè)基因點(diǎn)都被取過。如染色體Qi={v0,v2,v3,v8,v7,v9}，若先選定基因點(diǎn)v2，由表1得v2點(diǎn)的下一個(gè)基因點(diǎn)分別為v3、v5、v6，替換得Q1j={v0,v2,v5,v8,v7,v9}，Q2j={v0,v2,v6,v8,v7,v9}，計(jì)算f(Q1j)

變異概率Pm的選取關(guān)系到該條染色體是否進(jìn)行變異操作，本文定義Qi的變異概率為：

(5)

2.5　交叉算子

交叉概率Pc越大，可以越快收斂到希望的最優(yōu)解區(qū)域，因此一般選取較大的交叉概率，但太大的交叉概率也可能導(dǎo)致早熟現(xiàn)象，一般取0.4~0.9。當(dāng)Pc<λ(0<λ<1)時(shí)進(jìn)行交叉運(yùn)算。運(yùn)算剛開始主要是交叉算子在起作用，所以選取的交叉概率較大，隨著計(jì)算的進(jìn)行，為了保持算法的穩(wěn)定性交叉，概率的取值會相應(yīng)的減少。

2.6　停機(jī)條件

傳統(tǒng)的停機(jī)條件有，達(dá)到了最大進(jìn)化代數(shù)、收斂標(biāo)準(zhǔn)、時(shí)間標(biāo)準(zhǔn)和精度標(biāo)準(zhǔn)等。本文采用收斂準(zhǔn)則，即：

(6)

當(dāng)適應(yīng)度函數(shù)的值趨于穩(wěn)定時(shí)，運(yùn)算結(jié)束。

3算法流程圖

在設(shè)計(jì)完該算法后，需要按照一定的流程對算法進(jìn)行實(shí)施，以實(shí)現(xiàn)對裝配路徑的規(guī)劃。首先是裝配環(huán)境模型的建立，將障礙物用凸四邊形表示并放大一個(gè)安全距離，按順時(shí)針對各頂點(diǎn)采用實(shí)數(shù)編碼構(gòu)成圖1所示的裝配環(huán)境，然后計(jì)算各點(diǎn)的成本矩陣C。重要的是通過成本舉證提取基因表，以基因表為條件，按照網(wǎng)狀圖法隨機(jī)選出N個(gè)染色體，再從N個(gè)染色體中選出M個(gè)形成種群P，參加IGA演化計(jì)算。根據(jù)算法設(shè)計(jì)得到的具體操作流程如圖3所示。

圖3　改進(jìn)遺傳算法流程圖

4實(shí)驗(yàn)分析

如何讓指定的零部件繞開障礙物快速地安裝到指定的位置是虛擬裝配路徑規(guī)劃的難點(diǎn)，也是最終目的。例如DELMIA軟件采用可拆即可裝的原理完成對零部件的裝配，主要依靠人的經(jīng)驗(yàn)，無法保證所規(guī)劃的裝配路徑是最優(yōu)最短的。

為了驗(yàn)證改進(jìn)遺傳算法的優(yōu)越性，以農(nóng)業(yè)機(jī)械的機(jī)械式減速器為模型，將改進(jìn)的遺傳算法和傳統(tǒng)的遺傳算法在計(jì)算機(jī)上運(yùn)行40次得到圖4所示的結(jié)果，其中定義P=100，M=80，pc=0.7。從圖4中可以明顯得到改進(jìn)的遺傳算法在運(yùn)行了17次之后就基本趨于收斂穩(wěn)定，而傳統(tǒng)遺傳算法在運(yùn)行40次之后才開始收斂到最優(yōu)解，說明改進(jìn)的遺傳算法大大提高了傳統(tǒng)遺傳算法的收斂性。

圖4　IGA與GA收斂性對比

IGA與GA的收斂性對比可知IGA在運(yùn)行20次之后可趨于穩(wěn)定。為了進(jìn)一步說明改進(jìn)遺傳算法在虛擬裝配路徑規(guī)劃中的優(yōu)越性，將其與傳統(tǒng)遺傳算法運(yùn)行20次得到圖5所示的路徑規(guī)劃圖。定義P=100，M=80，pc=0.7。其中用IGA所的路徑長為15.246m，途經(jīng)4個(gè)障礙物；用GA所得路徑長28.562m，途經(jīng)9個(gè)障礙物。改進(jìn)的遺傳算法在運(yùn)行相同次數(shù)下所得的路徑短，經(jīng)過的障礙物少，所以更容易得到裝配件的最佳裝配路徑。

圖5　IGA與GA路徑規(guī)劃對比

5結(jié)論

本研究為了更好更快地得到最佳的裝配路徑，以凸四邊形障礙物為裝配環(huán)境，對初始種群選取方法重新定義，通過成本矩陣提取基因表并依此為條件建立初始種群，保

證了參加演化算法的每條染色體都是可行的。同時(shí)改進(jìn)了傳統(tǒng)GA中的變異算子和雜交算子。最后實(shí)驗(yàn)證明改進(jìn)后的IGA的收斂速度、動態(tài)收斂性和計(jì)算效率比遺傳算法好。以頂點(diǎn)作為基因點(diǎn)所得到的路徑都是直線段不夠平滑，應(yīng)該對所得到的路徑進(jìn)行平滑處理，本文中沒有涉及，以后會繼續(xù)完善。IGA不僅可以用于虛擬裝配路徑規(guī)劃，在對機(jī)器人避障路徑規(guī)劃中同樣適用，可以應(yīng)用于未來智能裝配及路徑規(guī)劃。

參考文獻(xiàn):

[1] R. G. Dewar, I. D. Carpenter, J.M. Ritchie, J. E. L. Simmons, “Assembly planning in a virtual environment,” International Conference on Management and Technology, July 1997, pp. 664-667.

[2] A. Seth,J. M. Vance, J. H. Oliver, “Virtual reality for assembly methods prototyping: a review,” Virtual Reality, 2011, pp. 5-20.

[3] A. Elfes, “Using occupancy grids for mobile robot perception and navigation,” Computer, vol. 22, Issue 6, June 1989, pp. 46-57.

[4] T. Simeon, S. Leroy, J. P. Lauumond, “Path coordination for multiple mobile robots: a resolution-complete algorithm,” Robotics and Automation, IEEE Transaction, vol. 18, Issue 1, 2002, pp. 42-49.

[5] A. Elashmli, H. A. Abdullah,S. Areibi, “Genetic algorithm for dynamic path planning,” Electrical and Computer Engineering, 2004. Canadian, vol. 2, May 2004, pp. 677-680.

[6] Tan Guan-zheng, He Huan, Sloman Aaron. Ant Colony System Algorithm for Real-Time Globally Optimal Path Planning of Mobile Robots. Acta Automation Sinica, 2007,33(3)：007-0279.

[7] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by Simulated Annealing,” Science, New Series, vol. 220,May 1983, pp. 671-680.

[8] M. Saska, M. Macas, L. Preucil, L. Lhotska, “Robot path planning using particle swarm optimization of Fergusion splines,” Emerging Technologies and Factory Automation, 2006. ETFA’06. IEEE Conference, Sept. 2006, pp. 833-839.

[9] 戴光明. 避障路徑規(guī)劃[D]. 武漢：華中科技大學(xué)博士生學(xué)位論文，2004,4.

[10] F. Tao, K. Qiao, L. Zhang, Z. Li, “GA-BHTR: an improved genetic algorithm for partner selection in virtual manufacuring,” International Journal of Production Research, vol. 50, Issue 8, 2012, pp. 2079-2100.

[11] F. Ahmed, K. Deb, “Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms,” Soft Computing, July 2013, vol.17, Issue 7, pp. 1283-1299.

[12] 張超群，鄭建國，錢潔.遺傳算法編碼方案比較[J]. 計(jì)算機(jī)應(yīng)用研究，2011,28(3).

Study of Virtual Assembly Path Planning Based on Improved Genetic Algorithm

WANG Guang-hui1,2, HU Chi-bing1, HE Cheng-zhu2

(1. Lanzhou University of Technology, Lanzhou 730050, China;

2. Mechanical Engineering Research Institute of Gansu Province, Lanzhou 730050, China)

Abstract:Assembly path planning is the core of virtual assembly. In order to obtain the optimal path, an improved algorithm based on genetic algorithm is proposed in the convex quadrilateral obstacle environment. The selection of the sample population is redefined to make sure that all the chromosomes involved in the evolutionary algorithms are useful. And the traditional mutation operator and crossover operator of genetic algorithm are improved to enhance the efficiency of the algorithm. Experiment shows that the mechanical reducer can be used to optimize the assembly path.

Keywords:path planning; nelwork chart; improved algorithml; genetic list; shortest path

收稿日期：2013-09-11

中圖分類號：TP301

文獻(xiàn)標(biāo)志碼：A

文章編號：1671-5276(2015)01-0205-04

作者簡介：王光慧(1987-)，女，甘肅蘭州人，碩士研究生，研究方向?yàn)閿?shù)字化制造。

基金項(xiàng)目：“十二五”國家科技支撐計(jì)劃資助項(xiàng)目(2011BAD20B01)