張　龍，衛(wèi)琛戈，?！?，張睿航，鐘　巖

(西北工業(yè)大學(xué) 理學(xué)院，陜西 西安 710129)

CAD技術(shù)在產(chǎn)品開發(fā)或是科研中的作用愈來愈重要，實(shí)際應(yīng)用中人們一般將CAD草圖的幾何約束條件轉(zhuǎn)化為非線性方程組進(jìn)行求解。數(shù)值計(jì)算中求解非線性方程組的方法眾多，常用的有牛頓法、Brown等[1-4]。牛頓法因解決此類問題具有速度快等優(yōu)良特性，而得到了廣泛的應(yīng)用。然而，此法要求給定的初值與精確解應(yīng)充分靠近，常因難以給定滿足收斂條件的初值x(0)而造成計(jì)算失敗[5-7]。因此，基于牛頓法的初值選取對(duì)于草圖約束的求解至關(guān)重要。

文獻(xiàn)[8]中結(jié)合了遺傳算法來確定采用牛頓法求解草圖約束問題時(shí)的初值，文獻(xiàn)[9]介紹了一種用蟻群算法確定初值的方法。人工蜂群算法是一種以蜜蜂群體生活為背景實(shí)現(xiàn)在一定范圍內(nèi)尋找目標(biāo)問題的最優(yōu)解的模型，其算法簡(jiǎn)單、具有較強(qiáng)的全局搜索能力，但收斂速度較慢[10-11]。而牛頓迭代法雖然對(duì)初值的選取要求比較高，但是其具有較高的收斂速度。因此，本文將兩種算法結(jié)合起來，提出了基于蜂群算法的牛頓迭代法來求解草圖約束問題，既保證了迭代速度，又避免了問題求解過程中陷入局部最優(yōu)值，提高了問題求解的成功率和求解速度，從而有效解決CAD草圖約束問題。

1　模型的建立

對(duì)于草圖幾何約束問題，其約束條件能夠被轉(zhuǎn)化為如下含有m個(gè)方程的n元非線性方程組的一般形式

(1)

在采用牛頓迭代法求解方程組(1)時(shí)，為了在精確解附近選取一個(gè)合適初值來確保迭代收斂，文中使用人工蜂群算法對(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)的牛頓法初值的選取問題轉(zhuǎn)化為利用人工蜂群算法求解目標(biāo)函數(shù)(3)的極小值問題。當(dāng)求解出方程(3)的最優(yōu)解之后，同時(shí)得到了牛頓法的合適初值，草圖約束問題求解成功。

2　基于人工蜂群的牛頓迭代算法

2.1　牛頓法

牛頓迭代法[12-13]求解非線性方程組(1)本質(zhì)上是將每一個(gè)子方程fi(x)對(duì)多個(gè)變量用泰勒展開進(jìn)行線性近似表示。設(shè)方程組(1)存在解x*，且在x*的某個(gè)開鄰域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)

接下來進(jìn)行人工蜂群算法在牛頓迭代法初值選取上的探索。

2.2　人工蜂群算法

蜂群最小搜索模型的基本要素有食物源、引領(lǐng)蜂、跟隨蜂以及偵察蜂。食物源即為目標(biāo)問題的可能解。引領(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è)新的解來替代xi。通過反復(fù)搜索，不斷優(yōu)化解，得到最終解。其將作為牛頓迭代法的初值進(jìn)行迭代得到最優(yōu)解。

2.3　混合算法的流程

采用基于蜂群算法的牛頓迭代法求解草圖約束優(yōu)化問題的步驟如下：

步驟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)蜂通過式(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通過式(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來代替它；

步驟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ī)初始化解，而是從已搜尋到的解的鄰域再做搜尋)。

3　仿真實(shí)例分析

此外，在草圖約束求解的實(shí)際應(yīng)用中通常會(huì)由于約束改變而導(dǎo)致求解失敗。如：修改尺寸、大幅拖動(dòng)多邊形中心、垂直關(guān)系轉(zhuǎn)化為平行等。本文以修改正多邊形尺寸為例，來探索該算法在穩(wěn)定性上的表現(xiàn)。

首先，文中隨機(jī)取出一組仿真結(jié)果如表1所示。從表1可看出，基于人工蜂群算法的牛頓法在求解草圖約束問題時(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)單問題(如正四邊形)中牛頓法要小于混合算法，對(duì)于較復(fù)雜的情況(如正六邊形)，混合算法耗時(shí)更短。這是因?yàn)榛旌纤惴ㄔ谶M(jìn)行全局搜索初值時(shí)耗費(fèi)了較多時(shí)間，而對(duì)于較為簡(jiǎn)單的問題這似乎是多余的。經(jīng)過多次仿真實(shí)驗(yàn)證明，對(duì)于復(fù)雜問題，混合算法在迭代速度和成功率上有明顯優(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)更為稀疏，蜂群算法全局搜索所損耗的資源增加。不過對(duì)一些多幾何元素多耦合關(guān)系的約束問題而言，隨著解在搜索域內(nèi)稀疏程度降低，按一定程度擴(kuò)大尺寸，混合算法在時(shí)間上的優(yōu)勢(shì)仍比較明顯。

4　結(jié)束語

為了快速高效求解草圖約束問題，本文將對(duì)收斂速度快而初值選取敏感的牛頓法和全局搜索能力強(qiáng)而搜索慢的人工蜂群算法有效結(jié)合起來，達(dá)到了既提高收斂速度又確保成功率的目的，且優(yōu)化了算法。該算法對(duì)于較為簡(jiǎn)單的問題雖然迭代時(shí)間有所損失，但提高了成功率。仿真實(shí)驗(yàn)顯示，該算法結(jié)果是可靠的，有較強(qiáng)的數(shù)值穩(wěn)定性，是一種不錯(cuò)的求解草圖約束問題的方法。

[1]王愛華.遺傳算法及其在非線性方程組求解中的應(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.