量子遺傳算法在口腔種植定位中的研究與應用

黃俊華，唐 平，陳松齡，江小平，梁英蓬

(1.廣東工業大學自動化學院，廣州 510006；2.中山大學附屬第一醫院口腔科，廣州 510080；3.廣東工業大學醫院，廣州 510006)

1 概述

口腔種植體通過外科手術植入人體缺牙牙骨中完成缺牙修復。傳統的口腔種植外科手術術前設計都是基于X線平片(根尖片和全景片)，臨床操作中常因設計估計不足而發生牙槽骨意外穿孔等嚴重并發癥，而且往往給上部結構修復帶來困難，導致種植修復的最終失敗[1]。隨著醫學圖像三維可視化等計算機輔助技術的發展，根據CT影像數據制作的手術導板增加了手術定位的準確性和操作的可控性。國內外分別推出VISIT導航系統和 SIM/plant等口腔種植軟件[2-3]。文獻[1]通過重建CT影像以人工交互的方式測量牙槽骨相關數據，但該方法工作步驟繁瑣，容易造成因主觀因素而導致的定位參數不準確。

結合量子計算和遺傳算法的量子遺傳算法有較好的全局搜索能力，已廣泛地應用于解決組合優化和多屬性決策規劃問題。文獻[4]提出用于解決背包問題的遺傳量子算法(Genetic Quantum Algorithm, GQA)，種群個體的多樣性是基于量子比特和量子態疊加特性表示的。文獻[5]提出一種利用量子染色體相位比較來更新旋轉角的量子遺傳算法。文獻[6]提出一種基于量子位 Bloch球面的量子遺傳算法(Bloch Quantum Genetic Algorithm, BQGA)，該算法中種群的染色體有并行的3條基因鏈，優化性能優于普通量子進化算法。

現有的口腔種植系統智能程度不高，而且鮮有運用人工智能解決種植手術的學術報道。基于上述分析，為了提高種植手術的精度以及種植系統的智能處理能力，針對口腔醫學螺旋CT數據量較大的特點，本文提出一種改進的 Bloch量子遺傳算法(Improved Bloch Quantum Genetic Algorithm, IBQGA)，用于完成口腔種植體的智能設計。

2 量子遺傳算法

2.1 基本量子遺傳算法

基本量子遺傳算法可以從以下方面進行說明：

(1)量子比特的表示

量子比特是量子計算的基本單位。基于Bloch球面的量子比特可以用φ和θ一對相位角度表示，其對應的向量表達式如下：

其中，|·>為量子表示符號。

本文采用基于Bloch球面的量子比特作為BQGA種群個體的基因位。設pi為基于Bloch球面的染色體，則其染色體編碼為：

其中，i是進化種群中第i個染色體；φij、θij為第i個染色體第j號基因的一組相位角度；i=1,2,…,m，j=1,2,…,n，m是種群規模，n是量子位數。

(2)量子旋轉門

在量子遺傳算法中，對量子比特狀態實施遺傳操作是由量子旋轉門來實現的，由酉矩陣與種群個體的量子比特編碼運算實現。對于基于Bloch球面的量子比特，相應的量子旋轉門是3×3的酉矩陣U：

其中，Δφ和Δθ都是量子旋轉門的旋轉角度，可以控制變換后的量子比特所處的狀態；旋轉角Δφ、Δθ的正負和大小控制著進化算法的收斂速度，如果幅值過大，會導致種群早熟；若幅值過小，會使收斂速度減慢。

文獻[6]中的 BQGA算法充分利用量子算法的多態性，但實際進化的是染色體中的某一基因鏈，造成最終優化群體中只有小部分優化個體。文獻[7]提出一種引入進化穩定策略的量子競爭決策算法，用以解決旅行商問題。該算法利用競爭力函數評價競爭者的競爭力，從而提高算法的全局優化能力。

2.2 改進算法

針對上述 BQGA存在的問題，結合本文應用，現提出下列3種改進方法：

(1)把種群分為不同的進化群體，即特征群體，使各特征群體獨自進化。

考慮到不同的植入點對種植方案的差異，故以植入點為分類標準，把種群細分為不同的特征群體。每個個體在自己所屬的特征群體中進化：即與同一特征群體中的其他個體比較，執行遺傳操作和交叉操作。

(2)針對不同的特征群體及特征群體的進化程度，實施自適應調整進化步長的遺傳操作。

對于量子遺傳算法的遺傳操作，文獻[4-5]通過遍歷查詢表生成量子旋轉門角度，此方法適合二進制編碼的量子進化算法。雖能推廣到一般的量子算法中，但涉及的多路判斷影響算法的效率。在不同特征群體的基礎上，相應進化特征群體中各個體的植入角度。本文采用如下自適應調整旋轉角度的生成方法：

其中，φb和 θb為最優解中量子位概率幅所對應的相位；φc和θc是當前解中量子位概率幅所對應的相位；若A=0時，sgn(A)取正負號均可；若B=0時，sgn(B)取正負號均可。Δφ0和Δθ0同為種群進化的步長。fij是第j代種群某特征群體中個體i的適應值。fjmax和fjmin分別為當代此群體的最大優適應值和最小適應值。

(3)引入隨機錯位的交叉操作

在許多遺傳算法的應用中容易發現，當種群進化到一定程度時，種群中各染色體相似或相同[8]，種群的多樣性減弱，難以突破局部最優所帶來的影響。而適當的交叉操作能保證遺傳算法良好的搜索性能，有利于保持種群的多樣性。考慮到經典遺傳算法中，二進制編碼的染色體執行交叉操作的特點是，分別隨機地選擇兩父代的某一個基因位作為交叉基因位，父代之間的交叉基因位相互交換，生成2個新的子代染色體，從而子代染色體隱含父代染色體的特征信息。針對醫學影像數據數據量大的特點，本文算法引入隨機的錯位交叉操作。隨機的錯位交叉操作的算法如下：

(1)隨機生成一個0～1之間的數rand。

(2)由父代 V1、V2 分別按下式生成子代 V1’、V2’：

3 種植體定位參數優化算法設計

3.1 口腔種植定位問題的描述

設口腔種植定位問題有一個解集 SP={S1, S2,…,Sn}，n為解的總數，而每一個解Si都有一個評價種植方案 Si優劣的綜合評價 criticism(Si)。每一個解Si={Positioni, Anglei, Li, Ri}，i=1, 2,…, n；每個種植方案有如下特征屬性：植入點位置 Position，植入方向Angle，種植體長度L以及種植體半徑R。解中的植入點位置是主特征屬性，可根據各個解的植入點屬性的差異，把解集細分不同的小集合SPj，SPj即為特征群體。口腔種植體定位設計就是要在解集SP中尋找一個這樣的Si，Si的各項特征屬性使其對應的綜合評價criticism(Si)最好。

口腔種植手術中種植體定位，由種植體的半徑、長度、植入點與方位角度決定。上述4個種植體信息構成具體的種植方案，是口腔種植體定位模型的參數。假設已知植入點的坐標(x0, y0, z0)，植入方向角度ρ和 ω，種植體的半徑和長度分別為 r和 L；則可建立以植入點(x0, y0, z0)為原點的球面坐標系，分別以植入方向角ρ和ω為此球面坐標系的2個角度坐標，以種植體長度L為此球面坐標系的長度坐標，口腔種植體定位模型如圖1所示。建立的球面坐標系是以種植植入點(x0, y0, z0)為原點的種植方案搜索空間。

圖1 口腔種植體定位模型示意圖

下列數學語言可以描述口腔種植體定位模型：

口腔的影像數據量龐大且包含噪聲信息，因而不能直接作為搜索空間，還需要考慮定位模型和原數據空間的坐標轉換。故需要提取缺牙區域的影像數據作為原數據空間。通過數字圖像處理的方法去噪，簡化區域數據；對提取的數據進行坐標變換，映射到搜索空間。因為口腔內牙列和牙槽骨的分布及形態具有一定的特征，把口腔牙列分為左上/下和右上/下 4個部分(分別記為I、IV、II和III區)。只需按照下式進行適當的坐標變換，口腔中缺牙區域的數據就能映射到相應的搜索空間，解決口腔種植體的定位問題：

其中，x、y、z為原數據空間中某點的3個直角坐標，sx、sy、sz為搜索空間下的坐標。Tn為屬于n區的原數據空間映射到搜索空間的變換矩陣。

運用坐標變換和利用上面的定位模型，把種植方案的植入方向優化限制為2個植入角度的組合優化，且 2個角度的優化范圍限制為 0°～90°，而不是 360°乃至空間中的搜索優化，能有效地減少進化算法搜索最優解的難度，有利于提高問題的優化效率。數據的提取與映射流程如圖2所示。

圖2 數據的提取與映射流程

3.2 量子染色體編碼

一個染色體代表一個種植方案，分別由植入點、種植方向和種植體半徑長度等參數決定。為了簡化染色體結構，現考慮給定種植體半徑和長度的情況，即每條染色體由植入點編碼 1、植入點編碼 2、角度編碼1以及角度編碼2這4個部分組成。每條染色體的量子比特均采用如式(1)表示的基于 Bloch球面的實數相位角度編碼。

3.3 適應值函數

合理的種植體定位需要種植體外圍有足夠密度的牙骨支撐，以及植入方向符合生物力學、吻合度，此外，還需要考慮牙槽骨的骨密度、形態、寬度、高度和骨缺損等情況[9-10]。因此，本文算法的適應值函數 Fitness分為支撐部分 Fsup和方向部分 Fdir，Fsup評價此種植方案的種植體外圍牙骨密度的大小；Fdir作為種植體對應的植入方向是否滿足生物力學的評價。最優的種植方案有如下特點：適應值函數的支撐部分和方向部分的適應值總和最大，即max{Fsup+Fdir}。

Fsup作為評價種植體周圍的牙骨灰度，假設植入坐標(x0, y0, z0)，角度ρ、ω，半徑r和長度L已知，其數學表述如下：

其中，value(x, y, z)表示的是點(x, y, z)對應的骨灰度值；X、Y、Z為原數據空間的各維度的最大值。

種植方向的適應度Fdir，由2個定位方向角度來評價。牙長軸與種植體植入方向的夾角應在一定角度范圍以內，為合理的種植方向，符合牙合力傳導的規律[10]。定位方向的適應度可通過引入與植入方向和牙長軸的夾角相關的懲罰函數決定。如果植入方向和牙長軸的夾角較大，則使適應度值為0；若夾角在口腔醫學允許范圍之內，可增大對應的適應度值。

本文算法步驟如下：

Step1 隨機初始化種群，并建立一個用以記錄種植點、植入方向和最優適應值的空表 list。初始化迭代截止代數。

Step2 計算種群中各個體的適應值。然后根據植入點的不同劃分特征群體，記入 list。其中，各特征群體需記錄最優及最小適應值。

Step3 根據list表中當前特征群體的最優適應值以及最小適應值，分別按式(2)～式(4)更新群體中個體，直至當前特征群體更新完畢。

Step4 重復Step3，直至全部群體被更新為止。

Step5 更新當前代數，并返回 Step2，直到滿足收斂條件為止。

4 實驗結果與分析

為了證明本文算法在解決種植體定位問題具有優于經典優化算法的特性，下面將本文算法與 GA、BQGA進行比較。生成一個模擬CT醫學影像數據的三維數組，作為測試種植體定位算法的實驗數據。實驗數據是一個隨機生成的服從正態分布的大小為10×10×10的三維數組，僅設置 3個對角相鄰，且數組標號遞增的數組元素值為10，已知最優的坐標及對應的最優角度(π/4)和理論最優值(37)。下面利用GA、BQGA與本文算法測試上述測試數據，得出各優化算法的綜合比較結果如表1所示，其中，qq表示平均角度；pp表示角度平均相對誤差；kk表示平均優化值。

表1 各優化算法的綜合比較結果

3種算法種群規模均為 200，截止進化代數均為200。GA中的交叉概率為 0.8，變異概率為 0.3，而BQGA與本文算法的交叉概率均為 0.6，變異概率均為 0.1。進化算法的優化值相對誤差比較如圖 3所示。

圖3 進化算法的優化值相對誤差比較

從表1的實驗數據中，可以得出：GA的優化效率不如 BQGA和本文算法高。在 10次實驗中，GA只有2次優化接近最優方案，即植入坐標優化為最優的植入坐標，總體優化值的平均相對誤差是0.416 6；而 BQGA和本文算法均能收斂且優化值的平均相對誤差均優于GA。在本文實驗的GA中，種群中的坐標以及角度的優化信息都依賴于交叉以及變異算子。即使增大種群數量或進化代數，也難以保證GA能搜索到理論的最優坐標。而角度優化僅在坐標得以優化下討論才有意義，因此，植入點坐標的優化程度決定了最終優化解的優劣。在種群進化過程中，如果種群中坐標及植入角度得到充分的優化，最終得到的優化解就越接近問題的最優解。與 BQGA相比，由于本文算法考慮到種群個體間的差異性，本文算法在角度平均相對誤差及優化值的平均相對誤差上均優于BQGA算法。

針對中山大學第一附屬醫院提供的 CT影像資料，結合本文研究的種植定體位模型，將本文算法應用于種植體方案設計優化上，完成種植體的智能生成，最終優化結果的矢狀切面圖如圖4所示，其中，牙骨中的直線部分為種植體。

圖4 本文算法優化種植體方案的矢狀切面圖

由圖4可見，本文算法能正確生成缺牙區域的種植體種植方案。但就其植入方向等指標的合理性，仍有待提高與改進。造成這樣的原因可能是圖像處理的方法及其參數的選取設置不當造成的，也可能是量子遺傳算法適應值函數的設置問題。

5 結束語

本文提出一種改進的量子遺傳算法。利用基于Bloch球面的量子基因編碼種群多樣性，引入交叉操作，使該算法的全局搜索能力和種群的多樣性得以保證。實驗結果表明，該算法比GA和BQGA有較好的搜索能力和收斂性能，能解決種植體的定位問題。今后的研究內容主要有：如何合理設置進化算法的參數與約束，如種植體長度半徑以及適應函數的定型等。

[1]康 璐, 黃遠亮, 顧立栩, 等.計算機輔助設計軟件在口腔種植外科的應用研究[J].口腔頜面外科雜志, 2008,18(4): 265-268.

[2]吳 婷, 廖文和, 戴 寧, 等.口腔種植導板計算機輔助技術研究[J].生物醫學工程學雜志, 2011, 28(1): 1-6.

[3]王培志, 夏 露, 陳 寧, 等.種植導航模板的計算機輔助設計和制造[J].中國口腔種植學雜志, 2010, 15(3):128-130, 133.

[4]Han Kuk-Hyun, Kim Jong-Hwan.Genetic Quantum Algorithm and Its Application to Combinatorial Optimization Problems[C]//Proc.of IEEE Conference on Evolutionary Computation.[S.l.]: IEEE Press, 2000.

[5]李士勇.一種基于相位比較的量子遺傳算法[J].系統工程與電子技術, 2010, 32(10): 2219-2222.

[6]李士勇, 李盼池.量子計算與量子優化算法[M].哈爾濱:哈爾濱工業大學出版社, 2009.

[7]劉 勇, 馬 良, 寧愛兵.量子競爭決策算法及其在旅行商問題中的應用[J].計算機應用研究, 2010, 27(2):586-589.

[8]陳國龍, 陳火旺, 郭文忠, 等.基于隨機錯位算術交叉的遺傳算法及其應用[J].模式識別與人工智能, 2004,17(2): 250-255.

[9]周 苗, 陳松齡, 陳建靈, 等.螺旋CT在牙種植術前評估和設計中的應用[J].實用醫技雜志, 2005, 12(6):1562-1563.

[10]孫婷婷, 潘 瑾, 崔明軍, 等.基于CT影像的牙種植模板相關的頜骨解剖學研究[J].口腔頜面外科雜志, 2007,17(3): 252-255.