張 龍,衛(wèi)琛戈,?!?,張睿航,鐘 巖
(西北工業(yè)大學(xué) 理學(xué)院,陜西 西安 710129)
CAD技術(shù)在產(chǎn)品開(kāi)發(fā)或是科研中的作用愈來(lái)愈重要,實(shí)際應(yīng)用中人們一般將CAD草圖的幾何約束條件轉(zhuǎn)化為非線性方程組進(jìn)行求解。數(shù)值計(jì)算中求解非線性方程組的方法眾多,常用的有牛頓法、Brown等[1-4]。牛頓法因解決此類問(wèn)題具有速度快等優(yōu)良特性,而得到了廣泛的應(yīng)用。然而,此法要求給定的初值與精確解應(yīng)充分靠近,常因難以給定滿足收斂條件的初值x(0)而造成計(jì)算失敗[5-7]。因此,基于牛頓法的初值選取對(duì)于草圖約束的求解至關(guān)重要。
文獻(xiàn)[8]中結(jié)合了遺傳算法來(lái)確定采用牛頓法求解草圖約束問(wèn)題時(shí)的初值,文獻(xiàn)[9]介紹了一種用蟻群算法確定初值的方法。人工蜂群算法是一種以蜜蜂群體生活為背景實(shí)現(xiàn)在一定范圍內(nèi)尋找目標(biāo)問(wèn)題的最優(yōu)解的模型,其算法簡(jiǎn)單、具有較強(qiáng)的全局搜索能力,但收斂速度較慢[10-11]。而牛頓迭代法雖然對(duì)初值的選取要求比較高,但是其具有較高的收斂速度。因此,本文將兩種算法結(jié)合起來(lái),提出了基于蜂群算法的牛頓迭代法來(lái)求解草圖約束問(wèn)題,既保證了迭代速度,又避免了問(wèn)題求解過(guò)程中陷入局部最優(yōu)值,提高了問(wèn)題求解的成功率和求解速度,從而有效解決CAD草圖約束問(wèn)題。
對(duì)于草圖幾何約束問(wèn)題,其約束條件能夠被轉(zhuǎn)化為如下含有m個(gè)方程的n元非線性方程組的一般形式
(1)
在采用牛頓迭代法求解方程組(1)時(shí),為了在精確解附近選取一個(gè)合適初值來(lái)確保迭代收斂,文中使用人工蜂群算法對(duì)其進(jìn)行初步探索。將方程組(1)轉(zhuǎn)化為適用于蜂群算法的單個(gè)目標(biāo)方程
|f1(x)|+|fx)|+…+|fm(x)|=0
(2)
顯然,方程(2)在最小值取到0時(shí)與方程組(1)是等價(jià)的。以方程(2)為基礎(chǔ)構(gòu)造目標(biāo)函數(shù)
G(x)=|f1(x)|+|f2(x)|+…+|fm(x)|
(3)
故對(duì)方程組(1)的牛頓法初值的選取問(wèn)題轉(zhuǎn)化為利用人工蜂群算法求解目標(biāo)函數(shù)(3)的極小值問(wèn)題。當(dāng)求解出方程(3)的最優(yōu)解之后,同時(shí)得到了牛頓法的合適初值,草圖約束問(wèn)題求解成功。
牛頓迭代法[12-13]求解非線性方程組(1)本質(zhì)上是將每一個(gè)子方程fi(x)對(duì)多個(gè)變量用泰勒展開(kāi)進(jìn)行線性近似表示。設(shè)方程組(1)存在解x*,且在x*的某個(gè)開(kāi)鄰域D0內(nèi)可微,則
(4)
其中x(k)∈D0是方程組(1)第k次近似解。于是可用方程組
(5)
即
F′(xk)(x-x(k))=-F(x(k))
(6)
近似代替非線性方程組(1),并將線性方程組(6)的解作為式(1)的第k+1次近似解,從而得到牛頓迭代公式
x(k+1)=x(k)-[F′(x(k))]-1F(x(k)),k=0,1,2,…
(7)
接下來(lái)進(jìn)行人工蜂群算法在牛頓迭代法初值選取上的探索。
蜂群最小搜索模型的基本要素有食物源、引領(lǐng)蜂、跟隨蜂以及偵察蜂。食物源即為目標(biāo)問(wèn)題的可能解。引領(lǐng)蜂先去尋找食物源并記錄下花蜜的數(shù)量,即對(duì)應(yīng)解的“適應(yīng)度”,反映這個(gè)可能解的優(yōu)劣程度;跟隨蜂獲取到引領(lǐng)蜂傳回的標(biāo)記食物源的花蜜信息后,根據(jù)花蜜信號(hào)強(qiáng)度選擇優(yōu)食物源,花蜜信號(hào)強(qiáng)度越強(qiáng),則食物源越容易被選取。然后對(duì)該食物源的領(lǐng)域進(jìn)行搜索,并記錄最優(yōu)的食物源。若某個(gè)食物源被遺棄,則應(yīng)由偵查蜂隨機(jī)尋找新的食物源。
設(shè)方程組(1)含有d個(gè)參數(shù),利用蜂群算法求解迭代式(7)的初值,即式(3)的極小值[14-15]。
假設(shè)人工蜂群算法求解得到SN個(gè)初始解(即得到SN個(gè)食物源),每個(gè)解xi(i=1,2,3,…,SN)是一個(gè)d維向量。首先,引領(lǐng)蜂對(duì)所有食物源進(jìn)行循環(huán)搜索,次數(shù)為C(C=1,2,3,…,MCN)。記錄每個(gè)食物源的花蜜量(計(jì)算適應(yīng)度)
(8)
其次,引領(lǐng)蜂對(duì)所有食物源(解)進(jìn)行一次領(lǐng)域搜索
vij=xij+φij(xij-xkj)
(9)
其中,j∈{1,2,…,d},k∈{1,2,…,SN},且k≠i。φij是[-1,1]之間的一個(gè)隨機(jī)數(shù),其決定著xij領(lǐng)域的范圍大小,且該范圍隨著搜索越靠近最優(yōu)解會(huì)逐漸減小。
對(duì)上述領(lǐng)域搜索結(jié)果再次進(jìn)行適應(yīng)度計(jì)算,若尋找到的新食物源(解)具有的花蜜信息強(qiáng)度(適應(yīng)度)強(qiáng)于之前的食物源所具有的花蜜信息強(qiáng)度,則用新的食物源代替舊的食物源;反之,則依舊以舊食物源為最優(yōu)食物源。當(dāng)所有引領(lǐng)蜂對(duì)所有食物源進(jìn)行搜索后,引領(lǐng)蜂將每個(gè)食物源的花蜜信息強(qiáng)度傳遞給跟隨蜂,跟隨蜂根據(jù)花蜜信號(hào)強(qiáng)度以一定的概率Pi選擇食物源,其中
(10)
由式(10)可以看出,當(dāng)食物源所具有的花蜜信號(hào)越強(qiáng)時(shí),其被選中的概率越大。跟隨蜂根據(jù)花蜜信號(hào)強(qiáng)度選定食物源后,利用式(7)對(duì)食物源的領(lǐng)域進(jìn)行搜索,并根據(jù)花蜜信號(hào)強(qiáng)度擇優(yōu)選中最優(yōu)食物源。
(11)
隨機(jī)獲得一個(gè)新的解來(lái)替代xi。通過(guò)反復(fù)搜索,不斷優(yōu)化解,得到最終解。其將作為牛頓迭代法的初值進(jìn)行迭代得到最優(yōu)解。
采用基于蜂群算法的牛頓迭代法求解草圖約束優(yōu)化問(wèn)題的步驟如下:
步驟1初始化,在給定范圍內(nèi)隨機(jī)給定初始解為xi(i=1,2,…,SN),設(shè)置最大循環(huán)次數(shù)MCN,參數(shù)MD;
步驟2根據(jù)目標(biāo)函數(shù)計(jì)算獲取每個(gè)解的適應(yīng)度,同時(shí)引領(lǐng)蜂通過(guò)式(9)對(duì)該解的領(lǐng)域進(jìn)行搜索,得到新的解vi,并計(jì)算得到新解的適應(yīng)度;
步驟3判斷vi的適應(yīng)度是否大于xi的適應(yīng)度,若大于,則用vi替代xi,將vi作為當(dāng)前最優(yōu)解。否則,保留xi不變;
步驟4通過(guò)式(10)計(jì)算獲取解xi的概率值Pi;
步驟5跟隨蜂依據(jù)Pi大小,選擇食物源(解),同時(shí)根據(jù)式(9)對(duì)解的鄰域進(jìn)行搜索得到新的解vi,并計(jì)算其適應(yīng)度值;
步驟6進(jìn)行貪婪選擇,同步驟3;
步驟7判斷是否存在被遺棄的解。若有,則根據(jù)式(3)產(chǎn)生新的解xi來(lái)代替它;
步驟8保存目前適應(yīng)度值最優(yōu)的解;
步驟9若循環(huán)次數(shù)大于MD,執(zhí)行牛頓迭代法,否則返回步驟2,重新搜尋(若再次搜尋時(shí),不用再次隨機(jī)初始化解,而是從已搜尋到的解的鄰域再做搜尋);
步驟10對(duì)步驟8中的解進(jìn)行牛頓迭代,判斷是否滿足迭代終止條件。若滿足,輸出最優(yōu)解;反之,返回步驟2,(同步驟9,再次搜尋時(shí),不用再次隨機(jī)初始化解,而是從已搜尋到的解的鄰域再做搜尋)。
此外,在草圖約束求解的實(shí)際應(yīng)用中通常會(huì)由于約束改變而導(dǎo)致求解失敗。如:修改尺寸、大幅拖動(dòng)多邊形中心、垂直關(guān)系轉(zhuǎn)化為平行等。本文以修改正多邊形尺寸為例,來(lái)探索該算法在穩(wěn)定性上的表現(xiàn)。
首先,文中隨機(jī)取出一組仿真結(jié)果如表1所示。從表1可看出,基于人工蜂群算法的牛頓法在求解草圖約束問(wèn)題時(shí)效果更佳。其中,牛頓法求解正四邊形與正六邊形草圖約束時(shí),邊界出現(xiàn)了扭曲且未與坐標(biāo)軸平行的情況,具體邊長(zhǎng)大小不符合實(shí)際要求。而基于人工蜂群算法的牛頓法給出了更為精確的結(jié)果,具體仿真對(duì)比數(shù)據(jù)如表2所示(注:因在實(shí)際求解中通常是在求解失敗后再次求解直到成功,故計(jì)算兩種算法平均迭代時(shí)間時(shí)均統(tǒng)計(jì)所有仿真實(shí)驗(yàn)消耗時(shí)間)。
可以看出,混合算法的成功率得到顯著提高。至于平均迭代時(shí)間,在簡(jiǎn)單問(wèn)題(如正四邊形)中牛頓法要小于混合算法,對(duì)于較復(fù)雜的情況(如正六邊形),混合算法耗時(shí)更短。這是因?yàn)榛旌纤惴ㄔ谶M(jìn)行全局搜索初值時(shí)耗費(fèi)了較多時(shí)間,而對(duì)于較為簡(jiǎn)單的問(wèn)題這似乎是多余的。經(jīng)過(guò)多次仿真實(shí)驗(yàn)證明,對(duì)于復(fù)雜問(wèn)題,混合算法在迭代速度和成功率上有明顯優(yōu)勢(shì)。
為了進(jìn)一步探索算法的穩(wěn)定性,本文擴(kuò)大多邊形尺寸為原先的10倍進(jìn)行仿真,仿真結(jié)果如表3所示。
表1 不同算法仿真結(jié)果
表2 求解不同圖形參數(shù)對(duì)比
表3 擴(kuò)大10倍正六邊形仿真結(jié)果
仿真結(jié)果顯示,混合算法的成功率仍高于90%,但迭代時(shí)間表現(xiàn)一般。原因在于對(duì)單個(gè)幾何元素改變尺寸后,解在搜索域內(nèi)更為稀疏,蜂群算法全局搜索所損耗的資源增加。不過(guò)對(duì)一些多幾何元素多耦合關(guān)系的約束問(wèn)題而言,隨著解在搜索域內(nèi)稀疏程度降低,按一定程度擴(kuò)大尺寸,混合算法在時(shí)間上的優(yōu)勢(shì)仍比較明顯。
為了快速高效求解草圖約束問(wèn)題,本文將對(duì)收斂速度快而初值選取敏感的牛頓法和全局搜索能力強(qiáng)而搜索慢的人工蜂群算法有效結(jié)合起來(lái),達(dá)到了既提高收斂速度又確保成功率的目的,且優(yōu)化了算法。該算法對(duì)于較為簡(jiǎn)單的問(wèn)題雖然迭代時(shí)間有所損失,但提高了成功率。仿真實(shí)驗(yàn)顯示,該算法結(jié)果是可靠的,有較強(qiáng)的數(shù)值穩(wěn)定性,是一種不錯(cuò)的求解草圖約束問(wèn)題的方法。
[1]王愛(ài)華.遺傳算法及其在非線性方程組求解中的應(yīng)用研究[J].西華師范大學(xué)學(xué)報(bào):自然科學(xué)版,2015,36(2):204-208.
[2]譚振江,肖春英.非線性方程數(shù)值解法的研究[J]. 吉林師范大學(xué)學(xué)報(bào):自然科學(xué)版,2014(3):102-105.
[3]劉元文.帶凸約束非線性方程組解法的若干研究[D].???海南大學(xué),2015.
[4]郭妞萍.求解非線性方程的指數(shù)迭代法[J].西安文理學(xué)院學(xué)報(bào):自然科學(xué)版,2015,18(3):31-34.
[5]姚騰騰.基于一致系數(shù)求積的廣義牛頓法求解非線性方程組[J].廈門大學(xué)學(xué)報(bào):自然科學(xué)版,2016,55(2):221-226.
[6]徐林.基于改進(jìn)擬牛頓法求解非線性方程組[J].濟(jì)寧學(xué)院學(xué)報(bào),2016(6):54-57.
[7]陳飛,王海軍,曹蘇玉.求解非線性方程組的改進(jìn)不精確雅可比牛頓法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(14):45-47.
[8]于俊乾.基于偶圖和數(shù)值方法的幾何約束求解算法研究[D].長(zhǎng)春:東北大學(xué),2013.
[9]張冰冰,張宏立.求解非線性方程組的蟻群算法[J].工業(yè)控制計(jì)算機(jī),2013(1):63-64.
[10] 張姣玲,林桂友,許國(guó)良.求解非線性方程的混合人工蜂群算法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(10):48-51.
[11] 張姣玲.求解非線性方程及方程組的人工蜂群算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(22):45-47.
[12] 單吉寧,蔡靜.解非線性方程的一類改進(jìn)型牛頓法[J].湖州師范學(xué)院學(xué)報(bào),2015(2):9-13.
[13] 陳磊,霍永亮.利用改進(jìn)的遺傳算法求解非線性方程組[J].西南師范大學(xué)學(xué)報(bào)自然科學(xué)版,2015(1):23-27.
[14] 胡珂,李迅波,王振林.改進(jìn)的人工蜂群算法性能[J].計(jì)算機(jī)應(yīng)用,2011,31(4):1107-1110.
[15] 劉佳,周真真,夏少芳,等.基于人工蜂群算法的非線性方程組求解研究[J].自動(dòng)化儀表,2013,34(2):19-22.