基于遺傳算法的虛擬牙齒矯正路徑規(guī)劃

王增波[1],向海蘭，賀丹，熊湘林

(衡陽(yáng)師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖南衡陽(yáng) 421002）

摘  要:在隱形牙齒矯正仿真系統(tǒng)中，通過(guò)前期完成工作的基礎(chǔ)上采用遺傳算法對(duì)分割出來(lái)的牙齒實(shí)現(xiàn)了多顆牙齒同時(shí)移動(dòng)的路徑規(guī)劃。通過(guò)反復(fù)實(shí)驗(yàn)確定了算法中的各種遺傳參數(shù)和操作，特別是適應(yīng)度函數(shù)中加入了牙齒間的碰撞檢測(cè)，更符合真實(shí)的治療場(chǎng)景。最后，通過(guò)反復(fù)實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

關(guān)鍵詞: 遺傳算法；牙齒矯正；移動(dòng)路徑規(guī)劃；適應(yīng)度函數(shù)；碰撞檢測(cè)

中圖法分類(lèi)號(hào): TP301

Path Planning for Virtual Orthodontics Treatment Process Based on Genetic Algorithm

WANG Zeng-bo, XIANG Hai-lan, HE Dan, XIONG Xiang-lin

(College of Mathematics and Statistics， Hengyang Normal University， Hengyang Hunan 421002， China)

Abstract: In the virtual orthodontic treatment process simulation system, the genetic algorithm is used to realize the path planning of multiple teeth moving simultaneously on the basis of the preliminary work. Through repeated experiments, various genetic parameters and operations in the algorithm were determined. In particular, the collision detection was added to the fitness function, which is more in line with the real treatment scene. Finally, the effectiveness of the method is verified by repeated experiments.

Key words: genetic algorithm；orthodontics treatment；path planning；fitness function；collision detection

1  引言

現(xiàn)在很多醫(yī)院采用隱形牙齒矯正手術(shù)患者進(jìn)行牙齒矯正，為了在牙齒矯正手術(shù)前能夠讓醫(yī)生規(guī)劃牙齒的矯正路徑和讓用戶體驗(yàn)未來(lái)的矯正過(guò)程，最終可利用仿真系統(tǒng)計(jì)算出來(lái)的過(guò)程數(shù)據(jù)為患者量身定制一系列近乎無(wú)法察覺(jué)的透明牙托來(lái)完成整個(gè)矯正療程，因此開(kāi)發(fā)一套虛擬矯正仿真系統(tǒng)就具有非常重要的現(xiàn)實(shí)意義。整個(gè)虛擬仿真過(guò)程要經(jīng)歷三維牙齒模型數(shù)字化掃描、三維拓?fù)渲貥?gòu)^[1]、牙頜組織分割、牙齒交互重排、牙齒移動(dòng)路徑規(guī)劃等諸多過(guò)程。其中，牙齒移動(dòng)路徑規(guī)劃是一項(xiàng)非常重要的工作，要根據(jù)牙齒的初態(tài)和終態(tài)通過(guò)算法自動(dòng)生成中間的位置信息，初態(tài)為患者術(shù)前的牙齒位置，終態(tài)是醫(yī)生根據(jù)患者的牙頜情況確定的矯正后的理想位置。很多情況下，會(huì)存在需要對(duì)幾顆牙齒同時(shí)進(jìn)行矯正，這就是一個(gè)并行的過(guò)程，要實(shí)現(xiàn)多顆牙齒同時(shí)移動(dòng)傳統(tǒng)優(yōu)化方法在這類(lèi)問(wèn)題中缺乏優(yōu)勢(shì)，很多智能算法卻能快速求得優(yōu)化解。

這里所研究的問(wèn)題屬于虛擬移動(dòng)路徑規(guī)劃問(wèn)題，它是指在虛擬環(huán)境中，存在障礙物的工作環(huán)境中尋找一條在給定起點(diǎn)到終點(diǎn)位置前提下的最優(yōu)運(yùn)動(dòng)路徑，并使物體在運(yùn)動(dòng)過(guò)程中能避免碰撞所有的障礙物。在這里我們可以主要借鑒現(xiàn)有的移動(dòng)機(jī)器人的路徑規(guī)劃方法來(lái)實(shí)現(xiàn)牙齒移動(dòng)的路徑規(guī)劃，障礙物被認(rèn)為是其它的牙齒，為了牙齒間避免碰撞，這就需要在移動(dòng)過(guò)程中進(jìn)行碰撞檢測(cè)，碰撞檢測(cè)方法見(jiàn)文獻(xiàn)[2]。

在動(dòng)態(tài)環(huán)境或未知環(huán)境中的移動(dòng)路徑規(guī)劃，需要解決的主要問(wèn)題是移動(dòng)對(duì)象與運(yùn)動(dòng)障礙物的避碰問(wèn)題。國(guó)內(nèi)外有許多的專(zhuān)家學(xué)者從人工勢(shì)場(chǎng)法^[3]、柵格法^[4] 、自由空間法等傳統(tǒng)方法進(jìn)行過(guò)路徑規(guī)劃的研究，也有采用各種智能算法如模糊邏輯^[5]、神經(jīng)網(wǎng)絡(luò)^[6]和遺傳算法^[7]對(duì)問(wèn)題進(jìn)行求解。其中Woong- Cie Han等^[8]采用了遺傳算法，算法中采用安全和距離作為算法的適應(yīng)度函數(shù)評(píng)估系數(shù)實(shí)現(xiàn)了實(shí)時(shí)路徑規(guī)劃。J ianping Tu等^[9]在用遺傳算法求解時(shí)，編碼方式采用變長(zhǎng)和相對(duì)位置的方法，有效減少了算法中的個(gè)體長(zhǎng)度。國(guó)內(nèi)的袁曾任等^[10]提出了一種基于改進(jìn)的柵格法和回歸預(yù)測(cè)相結(jié)合的方法，對(duì)移動(dòng)對(duì)象進(jìn)行路徑規(guī)劃并實(shí)現(xiàn)避撞和導(dǎo)航任務(wù)。

牙齒矯正的過(guò)程是多顆牙齒同時(shí)矯正的過(guò)程，虛擬牙齒矯正仿真系統(tǒng)需支持多顆牙齒同時(shí)移動(dòng)，遺傳算法存在內(nèi)在的并行性，因此本文將采用遺傳算法對(duì)牙齒移動(dòng)的路徑進(jìn)行規(guī)劃。

2 問(wèn)題的定義

本論文研究牙齒的移動(dòng)環(huán)境為三維空間，必須確定單顆牙齒矯正過(guò)程中的起止位置，初始位置是對(duì)患者治療前的牙齒進(jìn)行三維重建得來(lái)的數(shù)據(jù)，終止位置是由專(zhuān)業(yè)牙科醫(yī)生根據(jù)對(duì)患者的臨床診斷確定需要矯正的牙齒。從醫(yī)學(xué)角度來(lái)看，我們要通過(guò)牙齒的矯正得到一副整齊漂亮的牙列，必須建立一條理想牙弓形態(tài)曲線，并以該曲線為參照來(lái)調(diào)整牙齒的位置和姿態(tài)，牙弓線的繪制方法可參考文獻(xiàn)[11]。醫(yī)生可參照牙弓形態(tài)曲線并綜合考慮整個(gè)牙頜組織的情況在虛擬矯正仿真系統(tǒng)中通過(guò)交互式操作確定矯正后的位置。

由于在牙齒移動(dòng)過(guò)程中單顆牙齒之間可能會(huì)發(fā)生相互之間的碰撞，仿真系統(tǒng)中可能出現(xiàn)牙齒間的干涉問(wèn)題，因此在仿真過(guò)程中的碰撞檢測(cè)將是遺傳算法中適應(yīng)度函數(shù)的重要因素。我們的目標(biāo)是要設(shè)計(jì)一條路徑使得牙齒之間不發(fā)生干涉，并使得所有牙齒在符合患者牙頜組織可接受強(qiáng)度（由專(zhuān)業(yè)牙齒醫(yī)生根據(jù)臨床經(jīng)驗(yàn)確定矯正周期實(shí)現(xiàn)）的前提下盡快地從初始位置到達(dá)終止位置。我們建立牙齒移動(dòng)路徑規(guī)劃的數(shù)學(xué)模型，具體定義為：

(1)牙齒的移動(dòng)是一個(gè)連續(xù)的過(guò)程，仿真過(guò)程中我們利用基于slerp運(yùn)算的四元數(shù)插值方法^[31]實(shí)現(xiàn)移動(dòng)過(guò)程的離散化，這樣能夠減少計(jì)算量并得到一個(gè)平滑移動(dòng)的路徑。

(2)按照前面的方法，我們就可以把每顆牙齒的移動(dòng)路徑簡(jiǎn)化成起止位置狀態(tài)間的一系列的散離點(diǎn)狀態(tài)，散離點(diǎn)間的距離和角度根據(jù)路徑長(zhǎng)度和牙列的整體情況進(jìn)行確定，這些散離點(diǎn)我們把它稱(chēng)為路徑點(diǎn)。

(3)每顆牙齒都有從起始位置到終止位置的若干個(gè)路徑點(diǎn)，我們可以利用前面講到的碰撞檢測(cè)算法，計(jì)算出相鄰牙齒路徑點(diǎn)間的干涉情況，得到一個(gè)碰撞檢測(cè)表作用適應(yīng)度函數(shù)的其中的一個(gè)參數(shù)，這樣才能避免在仿真過(guò)程中出現(xiàn)牙齒間的干涉問(wèn)題。

3 遺傳算法實(shí)現(xiàn)牙齒移動(dòng)的路徑規(guī)劃

3.1 編碼

染色體的表示和編碼是運(yùn)用遺傳算法的關(guān)鍵步驟。對(duì)于牙齒移動(dòng)路徑規(guī)劃這個(gè)具體問(wèn)題來(lái)說(shuō)，很自然地考慮到可由路徑中的點(diǎn)的序列來(lái)構(gòu)成。我們用二進(jìn)制的0和1表示牙齒是否移動(dòng)到下一個(gè)路徑點(diǎn)，如：0110表示在整個(gè)移動(dòng)時(shí)間序列中，時(shí)間序列1的0表示走了0步停止在原處，時(shí)間序列2的1走了1步進(jìn)入了第一個(gè)路徑點(diǎn)，時(shí)間序列3的1表示走到了第二個(gè)路徑點(diǎn)，時(shí)間序列4的0表示停止在第二個(gè)路徑點(diǎn)了。因此，把染色體用一個(gè)只存儲(chǔ)0和1的數(shù)組來(lái)表示，圖1表示了染色體的基因存儲(chǔ)結(jié)構(gòu)，一個(gè)染色體把所有需移動(dòng)牙齒的路徑移動(dòng)信息都整合在了一起，不需要移動(dòng)的牙齒自然就不被編入到基因組中。在這里每顆牙齒的基因個(gè)數(shù)(二進(jìn)制位數(shù))要根據(jù)的實(shí)際情況計(jì)算得到，并不固定在一個(gè)確定的長(zhǎng)度。

圖1 牙齒移動(dòng)的染色體表示

3.2 路徑評(píng)估的適應(yīng)度函數(shù)計(jì)算

遺傳算法根據(jù)適者生存原則，從當(dāng)前群體中選擇出比較適應(yīng)環(huán)境的下一代個(gè)體，這些被選中的個(gè)體用于繁殖下一代。在選擇時(shí)，以適應(yīng)度函數(shù)為選擇原則。

對(duì)路徑優(yōu)劣程度的評(píng)估就可以作為遺傳算法中染色體的適應(yīng)度。因此要將我們規(guī)劃路徑時(shí)所作的要求包含進(jìn)去，并用數(shù)值的形式體現(xiàn)出來(lái)，以便進(jìn)行比較和衡量。對(duì)于可行路徑的適應(yīng)度我們要綜合考慮碰撞強(qiáng)度、路徑長(zhǎng)度、距離長(zhǎng)度這幾個(gè)因素。這樣看來(lái)該問(wèn)題是一個(gè)典型的多目標(biāo)優(yōu)化問(wèn)題，多目標(biāo)進(jìn)化算法已用于求解該類(lèi)問(wèn)題，但通常的算法過(guò)程復(fù)雜或者需要人工干預(yù)。為了減少運(yùn)算量，我們?cè)谶@里采用“加權(quán)和”形式求得綜合反映各子目標(biāo)要求的單一適應(yīng)度函數(shù)，將多目標(biāo)問(wèn)題轉(zhuǎn)化為可利用單目標(biāo)遺傳算法求解的等效問(wèn)題：

式中為個(gè)體X關(guān)于子目標(biāo)的歸一化適應(yīng)度。在此基礎(chǔ)上，借鑒人工神經(jīng)網(wǎng)絡(luò)中的后向傳播(Back-propagation)學(xué)習(xí)算法，令權(quán)值系數(shù)跟隨的優(yōu)化程度動(dòng)態(tài)地更新：

.

式中0≤≤1，可統(tǒng)一選取為0.8；為第t代種群關(guān)于的平均適應(yīng)度。這樣優(yōu)化程序較高的子目標(biāo)的優(yōu)化壓力將逐漸減小，優(yōu)化程序較低的子目標(biāo)則相反，從而使遺傳搜索能夠兼顧各個(gè)子目標(biāo)；但仍可利用的初始值來(lái)表達(dá)對(duì)子目標(biāo)的重視程序。

這里的碰撞強(qiáng)度就是參照前面提到的碰撞檢測(cè)表，在這個(gè)表里保存任兩個(gè)相鄰牙齒的路徑點(diǎn)間的碰撞檢測(cè)情況，通過(guò)它計(jì)算出路徑點(diǎn)間發(fā)生碰撞的次數(shù)。所謂路徑長(zhǎng)度即牙齒從初始位置到終止位置間的路徑點(diǎn)的數(shù)目，路徑的長(zhǎng)度是決定到達(dá)終點(diǎn)快慢程度的首要因素，在適應(yīng)度函數(shù)里所占的權(quán)重也最大，在這里設(shè)置所有的路徑長(zhǎng)度一樣，即取所有牙齒所需路徑點(diǎn)的最大值。所謂距離長(zhǎng)度即指牙齒當(dāng)前位置距離終點(diǎn)位置的步長(zhǎng)。

我們令(t)= d(t),(t)= c(t)，＝，＝，則一條可行路徑P(有n顆牙齒，路徑長(zhǎng)度為m)，其適應(yīng)度函數(shù)定義如下：

這里和分別表示距離長(zhǎng)度、碰撞強(qiáng)度在適應(yīng)度函數(shù)中的權(quán)重。其它參數(shù)分別定義如下：

d(t)表示歸一化的距離長(zhǎng)度，計(jì)算如下：

其中表示牙齒i的距離長(zhǎng)度。

c(t)表示歸一化的碰撞強(qiáng)度，計(jì)算如下：

其中表示牙齒k_i當(dāng)前所處路徑點(diǎn)與鄰接牙齒k_i+1當(dāng)前所處路徑點(diǎn)的碰撞函數(shù)，當(dāng)牙齒k_i與k_i+1發(fā)生碰撞時(shí)函數(shù)值為1，否則為0。

3.3 路徑規(guī)劃的遺傳操作

根據(jù)牙齒移動(dòng)路徑規(guī)劃問(wèn)題的特點(diǎn)，本文使用選擇、交叉和變異三種遺傳操作算子。

(1)選擇操作

選擇(Selection)，就是從群體中挑選出一些個(gè)體，將其作為創(chuàng)建下一代個(gè)體的基因庫(kù)(gene base)。

我們?cè)谝?guī)劃過(guò)程中采用賭輪選擇方法，該方法使個(gè)體被選中的幾率和它們的適應(yīng)度函數(shù)值成比例，適應(yīng)度函數(shù)值越大的染色體，被選中的概率也越大。這并不能保證適應(yīng)度函數(shù)值最高的個(gè)體一定能選入下一代，僅僅說(shuō)明它有最大的概率被選中。

(2)交叉操作

在生物的自然進(jìn)化過(guò)程中，兩個(gè)同源染色體通過(guò)交配而重組，形成新的染色體，從而產(chǎn)生出新的個(gè)體或物種。

常見(jiàn)的交叉算子有單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉、均勻交叉、均勻兩點(diǎn)交叉^[37,38]等。上面的例子就是使用了單點(diǎn)交叉算子進(jìn)行交叉操作。

交叉算子通過(guò)對(duì)所選擇的兩個(gè)父代染色體的基因片斷互換形成子代個(gè)體，交叉操作的方式很多，但對(duì)于由路徑點(diǎn)序列構(gòu)成的染色體來(lái)說(shuō)，只有單點(diǎn)交叉和多點(diǎn)交叉具有實(shí)際意義，而多點(diǎn)交叉與單點(diǎn)交叉相比并無(wú)本質(zhì)差別，因此本文中采用單點(diǎn)交叉的方法。

(3)變異操作

交叉算子最后不可避免的使群體失去多樣性，從而造成程序陷入局部，達(dá)不到全局最優(yōu)解的現(xiàn)象。變異算子在遺傳算法中起著相當(dāng)重要的作用，它不僅被視為找回因交叉操作而遺失的優(yōu)良基因的手段，而且還是優(yōu)化性能的有力工具。

我們實(shí)現(xiàn)變異操作的方法是沿著一個(gè)染色體的長(zhǎng)度，一位一位地進(jìn)行考察，并按一定的幾率下將其中某些位進(jìn)行翻轉(zhuǎn)。

3.4 路徑規(guī)劃終止條件

作為一種算法不能無(wú)限地執(zhí)行下去，要在合理的時(shí)間內(nèi)終止。

在這里我們對(duì)遺傳算法的終止采用最大遺傳代數(shù)和設(shè)定收斂條件的復(fù)合準(zhǔn)則。當(dāng)遺傳算法滿足設(shè)定的收斂判斷條件時(shí)，遺傳算法終止；若進(jìn)化了指定的代數(shù)仍然沒(méi)有滿足設(shè)定的收斂判斷條件，也令遺傳算法終止。

本文將判斷算法收斂的條件設(shè)為：若連續(xù)進(jìn)化5代，最優(yōu)解均未發(fā)生變化，且種群的平均適應(yīng)值提高不足1%，或算法進(jìn)化代數(shù)已達(dá)到了設(shè)定的最大值。

4 實(shí)驗(yàn)結(jié)果與分析

從前面對(duì)遺傳算法的分析我們可以看到，組成算法的每個(gè)部分都有許多參數(shù)，如變異概率、交叉概率、群體大小等，不同的參數(shù)取值使遺傳算法體現(xiàn)不同的行為。

我們通過(guò)反復(fù)實(shí)驗(yàn)，群體規(guī)模選擇140，交叉概率選擇0.7，變異概率選擇0.001，能夠得到良好的規(guī)劃效果。

另一個(gè)系統(tǒng)參數(shù)是個(gè)體的長(zhǎng)度，它對(duì)算法的性能也有影響。由于GA是一個(gè)概率過(guò)程，所以每次迭代的情況是不一樣的，系統(tǒng)參數(shù)不同，迭代情況也不同，也直接影響了牙齒的矯正過(guò)程。

我們通過(guò)實(shí)驗(yàn)分析遺傳算法中各參數(shù)對(duì)算法性能的影響，以便為的實(shí)際應(yīng)用選擇參數(shù)提供依據(jù)。同其它啟發(fā)式搜索技術(shù)一樣，遺傳算法也是一種隨機(jī)性的技術(shù)，因此我們不能根據(jù)一次運(yùn)行的結(jié)果來(lái)判斷參數(shù)的好壞。在下面的試驗(yàn)過(guò)程中，我們對(duì)于每一種環(huán)境都運(yùn)行10次，并記錄下每次實(shí)驗(yàn)的基因長(zhǎng)度、染色體長(zhǎng)度和遺傳代數(shù)，表1和表1中列出了在不同的基因長(zhǎng)度和染色體長(zhǎng)度情況下得到可行解的時(shí)間效率，在這里每遺傳100代耗時(shí)5.729秒。

為了分析算法，在這里我們針對(duì)矯正16顆牙的情況下進(jìn)行統(tǒng)計(jì)。如下表1所示，基因長(zhǎng)度與染色體長(zhǎng)度要相互配合才能得到良好的規(guī)劃效果，表格里的數(shù)據(jù)都可以應(yīng)用到矯正過(guò)程中作為參考。

矯正16顆牙齒時(shí)，基因長(zhǎng)度取6時(shí)染色體長(zhǎng)度取144,基因長(zhǎng)度取7時(shí)染色體長(zhǎng)度取160,基因長(zhǎng)度取8時(shí)染色體長(zhǎng)度取176，規(guī)劃效果良好，效果參見(jiàn)圖2-圖5。

表1 規(guī)劃16顆牙齒的情況

5 結(jié)論

本文研究了利用基于遺傳算法實(shí)現(xiàn)虛擬牙齒矯正仿真的路徑規(guī)劃方法，在完成的三維牙齒數(shù)字模型拓?fù)渲貥?gòu)、牙頜組織分割等基礎(chǔ)工作完成的前提下，實(shí)現(xiàn)了多顆牙齒的同時(shí)移動(dòng)路徑的規(guī)劃工作，仿真系統(tǒng)的運(yùn)行效果較理想。當(dāng)然這個(gè)系統(tǒng)還必須通過(guò)一段時(shí)間的臨床實(shí)驗(yàn)才能真正投入使用，后期可以根據(jù)實(shí)際臨床情況對(duì)一些參數(shù)進(jìn)行調(diào)整就能適應(yīng)牙科醫(yī)生的要求，未來(lái)還要考慮增加牙齒移動(dòng)過(guò)程中牙齦組織的變形仿真，這樣該系統(tǒng)將是更加的完善。

參考文獻(xiàn):

[1] 王增波.STL格式文件的快速拓?fù)渲亟ㄋ惴?/span>[J].計(jì)算機(jī)應(yīng)用,2014,34(09):2720-2724.

[2] 劉濤,王增波,李占利.碰撞檢測(cè)過(guò)程中的包圍盒技術(shù)及應(yīng)用研究[J].西安科技大學(xué)學(xué)報(bào),2006(03):395-399.

[3] KHATB O. Real-time obstacle avoidance for manipulators and mobile robots[A]. IEEE International Conference on Robotics and Automation[C], St Louis,  1985.500-505

[4] 馬浩浩,鄭紫微.基于柵格模型下機(jī)器人路徑規(guī)劃的改進(jìn)遺傳算法[J].無(wú)線通信技術(shù),2019,28(02):55-57+61.

[5] MARTIVEZA,'IUNSTEL E, JARNSH D IM. Fuzzy logic based collision avoidance for a mobile robot[A]. Third International Conference on Industrial Fuzzy Control and Intelligent Systems[C]. Houston, 1993, 66-69.

[6] AHMED F, CHIN CLP  An efficient obstacle avoidance scheme in mobile robot path planning using polynomial neural networks[A].Aerospace and Electronics Conference[C].1993,2, 848-850.

[7] 王功亮,王好臣,李振雨,李家鵬.基于優(yōu)化遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].機(jī)床與液壓,2019,47(03):37-40+100.

[8] HAN W-G, BAEK S-M, KUC T-Y Genetic algorithm based path planning and dynamic  obstacle avoidance of mobile robots[A]. 1997 IEEE International Conference on SMC[C]. Fbrida, 1997,3, 2747-2751.

[9] TU JP, YANG 3M. Genetic algorithm based path planning for a mobile robot[A]. ICRA'03[C]. Taipei, 2003, 3. 1221-1226.

[10] 哀曾任,高明.在動(dòng)態(tài)環(huán)境中移動(dòng)機(jī)器人導(dǎo)航和避碰的一種新方法[J].機(jī)器人.2000, 22 (2): 81-88.

[11] 王增波.虛擬牙齒矯正過(guò)程中的牙弓繪制方法研究[J].貴州大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,28(06):62-65.

• 上一篇：沒(méi)有了
• 下一篇：基于連續(xù)潮流計(jì)算的VSC-MTDC異步互聯(lián)電網(wǎng)換流站參數(shù)優(yōu)化方法