[發(fā)明專(zhuān)利]一種負(fù)反饋?zhàn)赃m應(yīng)蟻群算法的機(jī)構(gòu)運(yùn)動(dòng)鏈同構(gòu)識(shí)別方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310684570.2
• 申請(qǐng)日: 2013-12-13
• 公開(kāi)（公告）號(hào): CN103632196B
• 公開(kāi)（公告）日: 2017-02-22
• 發(fā)明（設(shè)計(jì)）人: 楊平;石順義;唐韻青;劉東靜;趙艷芳
• 申請(qǐng)（專(zhuān)利權(quán)）人: 江蘇大學(xué)
• 主分類(lèi)號(hào): G06N3/12
• 分類(lèi)號(hào): G06N3/12;G06F17/50
• 代理公司: 南京知識(shí)律師事務(wù)所32207
• 代理人: 汪旭東

技術(shù)領(lǐng)域

本發(fā)明涉及機(jī)構(gòu)運(yùn)動(dòng)鏈同構(gòu)識(shí)別的方法，特指一種用于機(jī)構(gòu)創(chuàng)新設(shè)計(jì)過(guò)程自動(dòng)化及智能CAD系統(tǒng)中機(jī)構(gòu)運(yùn)動(dòng)鏈同構(gòu)識(shí)別方法。

背景技術(shù)

由于在機(jī)構(gòu)創(chuàng)新設(shè)計(jì)過(guò)程自動(dòng)化和智能CAD系統(tǒng)中，原始型的自動(dòng)生成對(duì)機(jī)構(gòu)的綜合性能和產(chǎn)品設(shè)計(jì)過(guò)程中的經(jīng)濟(jì)性能有很大影響，原始型的生成及其選擇是機(jī)構(gòu)設(shè)計(jì)中最有創(chuàng)造性和最具活力的階段，但又包含許多復(fù)雜和困難的問(wèn)題尚需解決，問(wèn)題之一就是機(jī)構(gòu)運(yùn)動(dòng)鏈同構(gòu)判定。隨著這一問(wèn)題的提出，世界各國(guó)這方面的專(zhuān)家和學(xué)者提出了一系列的解決方法，而本發(fā)明主要針對(duì)蟻群算法用來(lái)進(jìn)行機(jī)構(gòu)運(yùn)動(dòng)鏈同構(gòu)識(shí)別中存在的問(wèn)題如：計(jì)算量大，所需時(shí)間長(zhǎng)；算法收斂慢、易陷入局部最優(yōu)；初始信息素匱乏；算法在運(yùn)行過(guò)程中多樣性變差、算法運(yùn)行中容易出現(xiàn)停滯現(xiàn)象等缺點(diǎn)而提出的方法。

發(fā)明內(nèi)容

本發(fā)明的目的是為了克服蟻群算法在進(jìn)行機(jī)構(gòu)運(yùn)動(dòng)鏈同構(gòu)識(shí)別中存在如上所述的缺陷，而提出了一種基于蟻群算法的機(jī)構(gòu)運(yùn)動(dòng)鏈同構(gòu)識(shí)別方法。

本發(fā)明技術(shù)方案是依次采用如下步驟：

1）根據(jù)機(jī)構(gòu)運(yùn)動(dòng)鏈的結(jié)構(gòu)形成其對(duì)應(yīng)的拓?fù)鋱D；

2）對(duì)運(yùn)動(dòng)鏈機(jī)構(gòu)框架進(jìn)行按結(jié)構(gòu)特征的排序主要由拓?fù)鋱D分層及層內(nèi)初步排序兩步組成；

3）得到機(jī)構(gòu)結(jié)構(gòu)特征集合，使其轉(zhuǎn)化為可降次的TSP問(wèn)題；

4）引入負(fù)反饋機(jī)制和自適應(yīng)參數(shù)調(diào)整到蟻群算法中，利用改進(jìn)的蟻群算法求解出兩機(jī)構(gòu)結(jié)構(gòu)特征集合對(duì)應(yīng)的條件最大結(jié)構(gòu)碼；

5）判斷條件最大結(jié)構(gòu)碼是否相等，若相等，則兩機(jī)構(gòu)同構(gòu)，否則，不同構(gòu)。

本發(fā)明的有益效果如下所示：1、本發(fā)明將負(fù)反饋機(jī)制引入蟻群算法中，保證算法在運(yùn)行過(guò)程中的多樣性。克服了蟻群算法容易收斂到局部最優(yōu)的缺點(diǎn)；2、本發(fā)明將自適應(yīng)的改變蟻群算法的揮發(fā)度系數(shù)，保證算法在運(yùn)行過(guò)程中的全局搜索能力和收斂速度。克服了蟻群算法收斂速度底和運(yùn)算過(guò)程中出現(xiàn)的停滯的缺點(diǎn)。

附圖說(shuō)明

圖1為螞蟻算法求解最大結(jié)構(gòu)碼的流程示意圖。

圖2為一種10桿同構(gòu)運(yùn)動(dòng)鏈。

圖3為圖2中對(duì)應(yīng)的拓?fù)鋱DG1,其中d=10。

圖4為另一種10桿同構(gòu)運(yùn)動(dòng)鏈。

圖5為圖4中對(duì)應(yīng)的拓?fù)鋱DG2,其中d=10。

具體實(shí)施方式

如圖1所示，為螞蟻算法求解最大結(jié)構(gòu)碼的過(guò)程為:

1)參數(shù)初始化。令時(shí)間t=0和循環(huán)次數(shù)為0，設(shè)置最大循環(huán)次數(shù)N_max，將m只螞蟻置于n個(gè)元素上，令圖上每條邊（i，j）的初始化信息量τ_ij(t)=const，其中const表示常數(shù)，且初始時(shí)刻Δτ_ij(0)=0;

2)螞蟻的禁忌表索引號(hào)k=1;

3)螞蟻數(shù)目k=k+1;

4)螞蟻個(gè)體根據(jù)狀態(tài)轉(zhuǎn)移概率公式計(jì)算的概率選擇元素j并前進(jìn)，j∈{C-tabu_k}；其中，k=（1,2，。。。。，m）;tabu_k(k=1,2,...,m)是用來(lái)記錄螞蟻k當(dāng)前所走過(guò)的路經(jīng)，C表示所有路徑的集合，C-tabu_k表示螞蟻k可以選擇的路徑集合；

5)修改禁忌表指針，即選擇好之后將螞蟻移動(dòng)到新的元素，并把該元素移動(dòng)到該螞蟻個(gè)體的禁忌表中；

6)若集合C中元素未遍歷完，即k<m，則跳轉(zhuǎn)到第3)步，否則執(zhí)行第9）步；

7)等全部群體狀態(tài)轉(zhuǎn)移結(jié)束之后，按結(jié)構(gòu)碼公式計(jì)算解的質(zhì)量；

8)對(duì)解的質(zhì)量由好到差進(jìn)行排序，同時(shí)把當(dāng)前最好的解用一個(gè)專(zhuān)用變量保存下來(lái)；

9)按照帶負(fù)反饋機(jī)制和自適應(yīng)參數(shù)調(diào)整更新信息素；

10)判斷是否有滿足結(jié)束條件，若滿足即循環(huán)次數(shù)N>N_max，則循環(huán)結(jié)束并輸出程序計(jì)算結(jié)果，若不滿足則循環(huán)次數(shù)增1，清空禁忌表并跳轉(zhuǎn)到第2）步。

其中步驟4）中的狀態(tài)轉(zhuǎn)移概率的計(jì)算公式如下所示

式中，allowed_k∈{C-tabu_k}表示螞蟻k下一步允許選擇的城市；α、β分別為信息啟發(fā)式因子和期望啟發(fā)式因子；τ_ij(t)為t時(shí)刻路徑（i，j）上的信息量，η_ij(t)為啟發(fā)函數(shù)其表達(dá)式如下：式中d_ij表示相鄰兩個(gè)城市之間的距離。

如圖2所示，本發(fā)明的實(shí)施方式如下：

（1）運(yùn)動(dòng)鏈的無(wú)向拓?fù)鋱D表示