牛頓迭代法在草圖約束優(yōu)化問題中的改進

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

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

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

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

1　模型的建立

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

(1)

在采用牛頓迭代法求解方程組(1)時，為了在精確解附近選取一個合適初值來確保迭代收斂，文中使用人工蜂群算法對其進行初步探索。將方程組(1)轉(zhuǎn)化為適用于蜂群算法的單個目標方程

|f1(x)|+|fx)|+…+|fm(x)|=0

(2)

顯然，方程(2)在最小值取到0時與方程組(1)是等價的。以方程(2)為基礎(chǔ)構(gòu)造目標函數(shù)

G(x)=|f1(x)|+|f2(x)|+…+|fm(x)|

(3)

故對方程組(1)的牛頓法初值的選取問題轉(zhuǎn)化為利用人工蜂群算法求解目標函數(shù)(3)的極小值問題。當求解出方程(3)的最優(yōu)解之后，同時得到了牛頓法的合適初值，草圖約束問題求解成功。

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

2.1　牛頓法

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

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

2.2　人工蜂群算法

蜂群最小搜索模型的基本要素有食物源、引領(lǐng)蜂、跟隨蜂以及偵察蜂。食物源即為目標問題的可能解。引領(lǐng)蜂先去尋找食物源并記錄下花蜜的數(shù)量，即對應(yīng)解的“適應(yīng)度”，反映這個可能解的優(yōu)劣程度；跟隨蜂獲取到引領(lǐng)蜂傳回的標記食物源的花蜜信息后，根據(jù)花蜜信號強度選擇優(yōu)食物源，花蜜信號強度越強，則食物源越容易被選取。然后對該食物源的領(lǐng)域進行搜索，并記錄最優(yōu)的食物源。若某個食物源被遺棄，則應(yīng)由偵查蜂隨機尋找新的食物源。

設(shè)方程組(1)含有d個參數(shù)，利用蜂群算法求解迭代式(7)的初值，即式(3)的極小值[14-15]。

假設(shè)人工蜂群算法求解得到SN個初始解(即得到SN個食物源)，每個解xi(i=1,2,3,…,SN)是一個d維向量。首先，引領(lǐng)蜂對所有食物源進行循環(huán)搜索，次數(shù)為C(C=1,2,3,…,MCN)。記錄每個食物源的花蜜量(計算適應(yīng)度)

(8)

其次，引領(lǐng)蜂對所有食物源(解)進行一次領(lǐng)域搜索

vij=xij+φij(xij-xkj)

(9)

其中，j∈{1,2,…,d},k∈{1,2,…,SN}，且k≠i。φij是[-1，1]之間的一個隨機數(shù)，其決定著xij領(lǐng)域的范圍大小，且該范圍隨著搜索越靠近最優(yōu)解會逐漸減小。

對上述領(lǐng)域搜索結(jié)果再次進行適應(yīng)度計算，若尋找到的新食物源(解)具有的花蜜信息強度(適應(yīng)度)強于之前的食物源所具有的花蜜信息強度，則用新的食物源代替舊的食物源；反之，則依舊以舊食物源為最優(yōu)食物源。當所有引領(lǐng)蜂對所有食物源進行搜索后，引領(lǐng)蜂將每個食物源的花蜜信息強度傳遞給跟隨蜂，跟隨蜂根據(jù)花蜜信號強度以一定的概率Pi選擇食物源，其中

(10)

由式(10)可以看出，當食物源所具有的花蜜信號越強時，其被選中的概率越大。跟隨蜂根據(jù)花蜜信號強度選定食物源后，利用式(7)對食物源的領(lǐng)域進行搜索，并根據(jù)花蜜信號強度擇優(yōu)選中最優(yōu)食物源。

(11)

隨機獲得一個新的解來替代xi。通過反復(fù)搜索，不斷優(yōu)化解，得到最終解。其將作為牛頓迭代法的初值進行迭代得到最優(yōu)解。

2.3　混合算法的流程

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

步驟1初始化，在給定范圍內(nèi)隨機給定初始解為xi(i=1,2,…,SN)，設(shè)置最大循環(huán)次數(shù)MCN，參數(shù)MD；

步驟2根據(jù)目標函數(shù)計算獲取每個解的適應(yīng)度，同時引領(lǐng)蜂通過式(9)對該解的領(lǐng)域進行搜索，得到新的解vi，并計算得到新解的適應(yīng)度；

步驟3判斷vi的適應(yīng)度是否大于xi的適應(yīng)度，若大于，則用vi替代xi，將vi作為當前最優(yōu)解。否則，保留xi不變；

步驟4通過式(10)計算獲取解xi的概率值Pi；

步驟5跟隨蜂依據(jù)Pi大小，選擇食物源(解)，同時根據(jù)式(9)對解的鄰域進行搜索得到新的解vi，并計算其適應(yīng)度值；

步驟6進行貪婪選擇，同步驟3；

步驟7判斷是否存在被遺棄的解。若有，則根據(jù)式(3)產(chǎn)生新的解xi來代替它；

步驟8保存目前適應(yīng)度值最優(yōu)的解；

步驟9若循環(huán)次數(shù)大于MD，執(zhí)行牛頓迭代法，否則返回步驟2，重新搜尋(若再次搜尋時，不用再次隨機初始化解，而是從已搜尋到的解的鄰域再做搜尋)；

步驟10對步驟8中的解進行牛頓迭代，判斷是否滿足迭代終止條件。若滿足，輸出最優(yōu)解；反之，返回步驟2，(同步驟9，再次搜尋時，不用再次隨機初始化解，而是從已搜尋到的解的鄰域再做搜尋)。

3　仿真實例分析

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

首先，文中隨機取出一組仿真結(jié)果如表1所示。從表1可看出，基于人工蜂群算法的牛頓法在求解草圖約束問題時效果更佳。其中，牛頓法求解正四邊形與正六邊形草圖約束時，邊界出現(xiàn)了扭曲且未與坐標軸平行的情況，具體邊長大小不符合實際要求。而基于人工蜂群算法的牛頓法給出了更為精確的結(jié)果，具體仿真對比數(shù)據(jù)如表2所示(注：因在實際求解中通常是在求解失敗后再次求解直到成功，故計算兩種算法平均迭代時間時均統(tǒng)計所有仿真實驗消耗時間)。

可以看出，混合算法的成功率得到顯著提高。至于平均迭代時間，在簡單問題(如正四邊形)中牛頓法要小于混合算法，對于較復(fù)雜的情況(如正六邊形)，混合算法耗時更短。這是因為混合算法在進行全局搜索初值時耗費了較多時間，而對于較為簡單的問題這似乎是多余的。經(jīng)過多次仿真實驗證明，對于復(fù)雜問題，混合算法在迭代速度和成功率上有明顯優(yōu)勢。

為了進一步探索算法的穩(wěn)定性，本文擴大多邊形尺寸為原先的10倍進行仿真，仿真結(jié)果如表3所示。

表1　不同算法仿真結(jié)果

表2　求解不同圖形參數(shù)對比

表3　擴大10倍正六邊形仿真結(jié)果

仿真結(jié)果顯示，混合算法的成功率仍高于90%，但迭代時間表現(xiàn)一般。原因在于對單個幾何元素改變尺寸后，解在搜索域內(nèi)更為稀疏，蜂群算法全局搜索所損耗的資源增加。不過對一些多幾何元素多耦合關(guān)系的約束問題而言，隨著解在搜索域內(nèi)稀疏程度降低，按一定程度擴大尺寸，混合算法在時間上的優(yōu)勢仍比較明顯。

4　結(jié)束語

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

[1]王愛華.遺傳算法及其在非線性方程組求解中的應(yīng)用研究[J].西華師范大學(xué)學(xué)報:自然科學(xué)版,2015,36(2):204-208.

[2]譚振江,肖春英.非線性方程數(shù)值解法的研究[J]. 吉林師范大學(xué)學(xué)報:自然科學(xué)版,2014(3):102-105.

[3]劉元文.帶凸約束非線性方程組解法的若干研究[D].?？?海南大學(xué),2015.

[4]郭妞萍.求解非線性方程的指數(shù)迭代法[J].西安文理學(xué)院學(xué)報:自然科學(xué)版,2015,18(3):31-34.

[5]姚騰騰.基于一致系數(shù)求積的廣義牛頓法求解非線性方程組[J].廈門大學(xué)學(xué)報:自然科學(xué)版,2016,55(2):221-226.

[6]徐林.基于改進擬牛頓法求解非線性方程組[J].濟寧學(xué)院學(xué)報,2016(6):54-57.

[7]陳飛,王海軍,曹蘇玉.求解非線性方程組的改進不精確雅可比牛頓法[J].計算機工程與應(yīng)用,2014,50(14):45-47.

[8]于俊乾.基于偶圖和數(shù)值方法的幾何約束求解算法研究[D].長春:東北大學(xué),2013.

[9]張冰冰,張宏立.求解非線性方程組的蟻群算法[J].工業(yè)控制計算機,2013(1):63-64.

[10] 張姣玲,林桂友,許國良.求解非線性方程的混合人工蜂群算法[J].計算機工程與應(yīng)用,2014,50(10):48-51.

[11] 張姣玲.求解非線性方程及方程組的人工蜂群算法[J].計算機工程與應(yīng)用,2012,48(22):45-47.

[12] 單吉寧,蔡靜.解非線性方程的一類改進型牛頓法[J].湖州師范學(xué)院學(xué)報,2015(2):9-13.

[13] 陳磊,霍永亮.利用改進的遺傳算法求解非線性方程組[J].西南師范大學(xué)學(xué)報自然科學(xué)版,2015(1):23-27.

[14] 胡珂,李迅波,王振林.改進的人工蜂群算法性能[J].計算機應(yīng)用,2011,31(4):1107-1110.

[15] 劉佳,周真真,夏少芳,等.基于人工蜂群算法的非線性方程組求解研究[J].自動化儀表,2013,34(2):19-22.