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

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

(衡陽師范學院 數學與統計學院，湖南衡陽 421002）

摘  要:在隱形牙齒矯正仿真系統中，通過前期完成工作的基礎上采用遺傳算法對分割出來的牙齒實現了多顆牙齒同時移動的路徑規劃。通過反復實驗確定了算法中的各種遺傳參數和操作，特別是適應度函數中加入了牙齒間的碰撞檢測，更符合真實的治療場景。最后，通過反復實驗驗證了該方法的有效性。

關鍵詞: 遺傳算法；牙齒矯正；移動路徑規劃；適應度函數；碰撞檢測

中圖法分類號: 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  引言

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

這里所研究的問題屬于虛擬移動路徑規劃問題，它是指在虛擬環境中，存在障礙物的工作環境中尋找一條在給定起點到終點位置前提下的最優運動路徑，并使物體在運動過程中能避免碰撞所有的障礙物。在這里我們可以主要借鑒現有的移動機器人的路徑規劃方法來實現牙齒移動的路徑規劃，障礙物被認為是其它的牙齒，為了牙齒間避免碰撞，這就需要在移動過程中進行碰撞檢測，碰撞檢測方法見文獻[2]。

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

牙齒矯正的過程是多顆牙齒同時矯正的過程，虛擬牙齒矯正仿真系統需支持多顆牙齒同時移動，遺傳算法存在內在的并行性，因此本文將采用遺傳算法對牙齒移動的路徑進行規劃。

2 問題的定義

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

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

(1)牙齒的移動是一個連續的過程，仿真過程中我們利用基于slerp運算的四元數插值方法^[31]實現移動過程的離散化，這樣能夠減少計算量并得到一個平滑移動的路徑。

(2)按照前面的方法，我們就可以把每顆牙齒的移動路徑簡化成起止位置狀態間的一系列的散離點狀態，散離點間的距離和角度根據路徑長度和牙列的整體情況進行確定，這些散離點我們把它稱為路徑點。

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

3 遺傳算法實現牙齒移動的路徑規劃

3.1 編碼

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

圖1 牙齒移動的染色體表示

3.2 路徑評估的適應度函數計算

遺傳算法根據適者生存原則，從當前群體中選擇出比較適應環境的下一代個體，這些被選中的個體用于繁殖下一代。在選擇時，以適應度函數為選擇原則。

對路徑優劣程度的評估就可以作為遺傳算法中染色體的適應度。因此要將我們規劃路徑時所作的要求包含進去，并用數值的形式體現出來，以便進行比較和衡量。對于可行路徑的適應度我們要綜合考慮碰撞強度、路徑長度、距離長度這幾個因素。這樣看來該問題是一個典型的多目標優化問題，多目標進化算法已用于求解該類問題，但通常的算法過程復雜或者需要人工干預。為了減少運算量，我們在這里采用“加權和”形式求得綜合反映各子目標要求的單一適應度函數，將多目標問題轉化為可利用單目標遺傳算法求解的等效問題：

式中為個體X關于子目標的歸一化適應度。在此基礎上，借鑒人工神經網絡中的后向傳播(Back-propagation)學習算法，令權值系數跟隨的優化程度動態地更新：

.

式中0≤≤1，可統一選取為0.8；為第t代種群關于的平均適應度。這樣優化程序較高的子目標的優化壓力將逐漸減小，優化程序較低的子目標則相反，從而使遺傳搜索能夠兼顧各個子目標；但仍可利用的初始值來表達對子目標的重視程序。

這里的碰撞強度就是參照前面提到的碰撞檢測表，在這個表里保存任兩個相鄰牙齒的路徑點間的碰撞檢測情況，通過它計算出路徑點間發生碰撞的次數。所謂路徑長度即牙齒從初始位置到終止位置間的路徑點的數目，路徑的長度是決定到達終點快慢程度的首要因素，在適應度函數里所占的權重也最大，在這里設置所有的路徑長度一樣，即取所有牙齒所需路徑點的最大值。所謂距離長度即指牙齒當前位置距離終點位置的步長。

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

這里和分別表示距離長度、碰撞強度在適應度函數中的權重。其它參數分別定義如下：

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

其中表示牙齒i的距離長度。

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

其中表示牙齒k_i當前所處路徑點與鄰接牙齒k_i+1當前所處路徑點的碰撞函數，當牙齒k_i與k_i+1發生碰撞時函數值為1，否則為0。

3.3 路徑規劃的遺傳操作

根據牙齒移動路徑規劃問題的特點，本文使用選擇、交叉和變異三種遺傳操作算子。

(1)選擇操作

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

我們在規劃過程中采用賭輪選擇方法，該方法使個體被選中的幾率和它們的適應度函數值成比例，適應度函數值越大的染色體，被選中的概率也越大。這并不能保證適應度函數值最高的個體一定能選入下一代，僅僅說明它有最大的概率被選中。

(2)交叉操作

在生物的自然進化過程中，兩個同源染色體通過交配而重組，形成新的染色體，從而產生出新的個體或物種。

常見的交叉算子有單點交叉、兩點交叉、多點交叉、均勻交叉、均勻兩點交叉^[37,38]等。上面的例子就是使用了單點交叉算子進行交叉操作。

交叉算子通過對所選擇的兩個父代染色體的基因片斷互換形成子代個體，交叉操作的方式很多，但對于由路徑點序列構成的染色體來說，只有單點交叉和多點交叉具有實際意義，而多點交叉與單點交叉相比并無本質差別，因此本文中采用單點交叉的方法。

(3)變異操作

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

我們實現變異操作的方法是沿著一個染色體的長度，一位一位地進行考察，并按一定的幾率下將其中某些位進行翻轉。

3.4 路徑規劃終止條件

作為一種算法不能無限地執行下去，要在合理的時間內終止。

在這里我們對遺傳算法的終止采用最大遺傳代數和設定收斂條件的復合準則。當遺傳算法滿足設定的收斂判斷條件時，遺傳算法終止；若進化了指定的代數仍然沒有滿足設定的收斂判斷條件，也令遺傳算法終止。

本文將判斷算法收斂的條件設為：若連續進化5代，最優解均未發生變化，且種群的平均適應值提高不足1%，或算法進化代數已達到了設定的最大值。

4 實驗結果與分析

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

我們通過反復實驗，群體規模選擇140，交叉概率選擇0.7，變異概率選擇0.001，能夠得到良好的規劃效果。

另一個系統參數是個體的長度，它對算法的性能也有影響。由于GA是一個概率過程，所以每次迭代的情況是不一樣的，系統參數不同，迭代情況也不同，也直接影響了牙齒的矯正過程。

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

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

矯正16顆牙齒時，基因長度取6時染色體長度取144,基因長度取7時染色體長度取160,基因長度取8時染色體長度取176，規劃效果良好，效果參見圖2-圖5。

表1 規劃16顆牙齒的情況

圖2 調整單顆牙齒	圖3矯正過程圖一
圖4 矯正過程圖二	圖5 矯正后的效果圖

5 結論

本文研究了利用基于遺傳算法實現虛擬牙齒矯正仿真的路徑規劃方法，在完成的三維牙齒數字模型拓撲重構、牙頜組織分割等基礎工作完成的前提下，實現了多顆牙齒的同時移動路徑的規劃工作，仿真系統的運行效果較理想。當然這個系統還必須通過一段時間的臨床實驗才能真正投入使用，后期可以根據實際臨床情況對一些參數進行調整就能適應牙科醫生的要求，未來還要考慮增加牙齒移動過程中牙齦組織的變形仿真，這樣該系統將是更加的完善。

參考文獻:

[1] 王增波.STL格式文件的快速拓撲重建算法[J].計算機應用,2014,34(09):2720-2724.

[2] 劉濤,王增波,李占利.碰撞檢測過程中的包圍盒技術及應用研究[J].西安科技大學學報,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].無線通信技術,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] 王功亮,王好臣,李振雨,李家鵬.基于優化遺傳算法的移動機器人路徑規劃[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] 哀曾任,高明.在動態環境中移動機器人導航和避碰的一種新方法[J].機器人.2000, 22 (2): 81-88.

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

 

• 上一篇：沒有了
• 下一篇：基于連續潮流計算的VSC-MTDC異步互聯電網換流站參數優化方法