王袈歡 湯 卿 陸煜衡

（四川大學(xué) 制造科學(xué)與工程學(xué)院 四川成都 610065）

放射治療已有一百多年的歷史，是惡性腫瘤的三大治療手段之一。據(jù)國內(nèi)外文獻統(tǒng)計，約 50%～70%的惡性腫瘤患者需要接受放射治療。其中射波刀是全球最新型的全身立體定位放射外科治療設(shè)備[1]。放射治療過程中，射線由加速器末端發(fā)射并穿過患者體內(nèi)的腫瘤位置，從而達到殺死腫瘤細胞的效果[2]。雖然射波刀方便了人們對腫瘤細胞的治療，但是當射線穿過人體指向癌細胞時，會經(jīng)過正常細胞，損傷正常健康的細胞而影響人體正常生理機能。為了殺死癌細胞并盡可能減少對健康細胞的損傷，需要從不同的方向，即多個放射點進行放射治療[3]。此外，放射治療時，如果放射治療時間過長，病人會產(chǎn)生移動，導(dǎo)致定位不準確，同樣會降低定位精度，產(chǎn)生治療誤差，損害健康細胞并無法及時清除癌細胞。在進行多角度放射治療時，優(yōu)化放射治療點順序，減少放射治療總路徑，減少治療時間，對放射治療具有重要意義。

為了縮短放射治療過程中的放射路徑總長度，降低治療成本，提出了一種基于TSP問題的改進遺傳算法，并構(gòu)建了新的放射治療模型，對遺傳算法算子重新進行有針對性的設(shè)計。

1 放射治療點順序優(yōu)化模型建立

在對放射治療點的順序優(yōu)化問題進行分析時，發(fā)現(xiàn)其問題本質(zhì)同TSP旅行商問題有異曲同工之處。

TSP問題即旅行商問題，由數(shù)學(xué)家 Karl Menger[4]對其進行了較為完整的定義。具體描述為：有一個銷售人員要去n個城市銷售商品，每兩個城市之間的路徑是確定的，銷售人員要選擇從其中的一個城市出發(fā)，無重復(fù)的按照一定的城市順序拜訪完所有的城市，并回到始發(fā)城市，求整個過程結(jié)束后所走的最短路徑[5]。

這里采用庫卡KR16機器臂模擬射波刀，機械臂工具末端模擬加速器，放射治療點可以近似地認為是分布在以腫瘤區(qū)為中心點的球面上。放射治療時，機器人末端經(jīng)過放射治療點所行走的軌跡也是一條遍歷各個放射治療點、無重復(fù)且最終機械臂會回到初始放射治療點的路線，這一點同旅行商問題本質(zhì)一致。因此對射波刀放射治療點順序優(yōu)化進行數(shù)學(xué)建模時，參考TSP數(shù)學(xué)模型及評價指標，進行如下建模：

假設(shè)優(yōu)化方案一共有n個放射治療點τ1,τ2,τ3,…,τn,機械臂末端從其中一個放射治療點τk出發(fā)，沿著一個不重復(fù)的順序遍歷所有的放射治療點。記放射順序為r1,r2,r3,…,rn，其中1 ≤ ri≤n 。本文的優(yōu)化目標是尋找到一個最優(yōu)的放射順序，使得機械臂末端經(jīng)過的路徑最短。這一優(yōu)化問題可以公式化為：

即對于每一個個體按公式(1)均可求得其適應(yīng)度函數(shù)值fitvaluer1,r2,r3,…,rn。其中Sγi,γj為從放射治療點τγi到放射治療點τγj機械臂末端所走過的路程。此處設(shè)置機械臂的運行路徑沿著以靶區(qū)為中心，放射治療點到靶區(qū)的距離R為半徑的球上。那么Sγi,γj可以用公式(2)計算：

其中（αi,βi） ， αj,βj分別為放射治療點i, j在這個球上的經(jīng)度角與緯度角，其中經(jīng)度角即兩個經(jīng)線平面的夾角，緯度角即該放射治療點的法線與赤道平面之間的夾角。當放射治療點的位置是以歐式坐標給出時，可以通過公式(3)將歐氏坐標轉(zhuǎn)化為經(jīng)緯度坐標。

其中（xi,yi,zi） 為放射治療點i在以靶區(qū)為原點的歐氏坐標。

2 放射治療點順序優(yōu)化遺傳操作

2.1 算法整體設(shè)計

根據(jù)放射治療點的順序優(yōu)化數(shù)學(xué)模型并結(jié)合遺傳算法，對整個過程的算法流程設(shè)計如圖1所示。

圖1 放射治療點順序優(yōu)化算法流程圖

2.2 改進遺傳操作算子設(shè)計

由于遺傳算法是通過模擬生物進化的方式進行優(yōu)化選擇，其每一步與所優(yōu)化問題密切相關(guān)。針對不同的問題，通常需要對遺傳算法的算子進行不同的設(shè)計選擇，有針對性的算子可以簡化遺傳算法的復(fù)雜度，提升算法的收斂速度。本文針對編碼、種群初始化、選擇算子、交叉算子、變異算子及初始研究參數(shù)結(jié)合本文優(yōu)化問題進行了改進設(shè)計，具體改進如下：

1) 編碼及種群初始化

本文使用實數(shù)編碼。考慮個體變量的定義域以及新生成個體的值域，對個體編碼進行統(tǒng)一表述：以n 個放射治療點為例，個體數(shù)據(jù)結(jié)構(gòu)為：γ1,γ2,γ3,…,γn， γ代表一個放射治療點的位置，一個個體即一組放射治療點的順序。本文采用在限制范圍內(nèi)隨機生成初始種群。設(shè)置種群大小為k，則初始化種群為：

2) 選擇算子設(shè)計

將規(guī)模為k的種群按照適應(yīng)度函數(shù)值從小到大排序，并按照數(shù)量等分為三份。用第一部分的個體替換掉第三部分的個體，從而產(chǎn)生新的種群。此種選擇算子既保留了鐘群部分的多樣性，也有效地保留了優(yōu)秀個體的基因，使其遺傳下去。

3) 交叉算子設(shè)計

對于TSP問題有以下幾種常用的交叉方式：單點交叉、雙點交叉、多點交叉。綜合考慮上述幾種交叉算子，并結(jié)合優(yōu)化問題，交叉算子設(shè)計如下所示：

對于兩個父代個體：

隨機選擇兩個交叉點l和m ，（1＜l＜m＜n），截取染色體中間片段：

交叉置于對方父代染色體后：

從染色體前方開始刪除重復(fù)基因，最終可得到新的子代個體：

進行交叉運算后的種群附加到原來未進行交叉操作的父代種群后，計算合并后種群每個個體的適應(yīng)度函數(shù)值，并按從小到大的順序重新排列，取前個個體作為新的種群。如果進行交叉運算后種群的最優(yōu)個體沒有交叉運算前優(yōu)，則這種運算操作保留了最優(yōu)個體不被交叉運算破壞。

4)變異算子設(shè)計

常見的變異算法有以下幾種：基本位變異、均勻變異、非均勻變異、逆序變異等。分析以上幾種變異算子并結(jié)合本文要優(yōu)化的問題，設(shè)計變異算子如下：

（1）對于個體γ1,γ2,…,γn，隨機產(chǎn)生兩個數(shù)i、j，其中0 ＜ i＜ j＜ n 。

（2）從原個體上截取出γi和γj之間的基因片段γi…γj。

將剩余的基因整合γ1,… ,γi?1,γj+1,… ,γn，并在整合的基因片段上重新隨機選擇一個新位置，將截取的片段插入此位置，組合成一個新的個體。

5） 初始運行參數(shù)設(shè)定

在使用遺傳算法進行尋優(yōu)過程中，除了遺傳算子會對遺傳運算的解產(chǎn)生重要影響外，遺傳運算的各種運行參數(shù)如種群規(guī)模、交叉、變異概率、迭代次數(shù)等都會影響遺傳運算最終的收斂結(jié)果[6]，因此應(yīng)該認真選取。經(jīng)過多次試驗運算，設(shè)計種群規(guī)模500，交叉概率0.8，變異概率0.1，逆轉(zhuǎn)概率0.1，迭代次數(shù)500次。

3 放射治療點順序優(yōu)化仿真

為了驗證算法的有效性，在matlab平臺上進行優(yōu)化仿真。在放射治療空間中隨機產(chǎn)生30個放射點，并隨機產(chǎn)生一組放射順序：16 10 4 27 22 8 23 18 15 11 20 13 6 17 19 29 24 2 3 7 9 30 1 28 14 25 12 26 5 21。其放射點的順序規(guī)劃如圖2中（a）所示，路徑交叉，且其路徑總長度為2 754.6 mm。通過本算法對路徑進行優(yōu)化后其路徑順序為：12 11 14 5 27 16 21 29 26 10 4 28 8 2 23 25 1 24 15 18 3 19 6 7 20 9 17 13 30 22，如圖2中（b）所示，路徑總長度為685.1 mm。與初始路徑比較優(yōu)化了75.1% 。

圖2 30個放射治療點順序優(yōu)化對比圖

在圖2中，中心“*”點表示患者身體內(nèi)部腫瘤位置；紅色實心球表示放射治療點；放射治療點之間的黑色曲線代表放射治療加速器末端在放射點之間的運動軌跡。

為了驗證算法的穩(wěn)定性，隨機產(chǎn)生10組放射點，每組30個點進行優(yōu)化實驗，對于每一次隨機產(chǎn)生的一組放射點位置，計算未優(yōu)化前放射路徑總長度及優(yōu)化后放射路徑總長度，并計算路徑優(yōu)化率，如表1所示。

表1 隨機10組30個放射點適應(yīng)度值優(yōu)化表

從表1可見，該算法的優(yōu)化效果穩(wěn)定，平均優(yōu)化率達到 76.5%?；谝陨蠈嶒灒梢缘贸觯涸诜派渲委熯^程中，隨機產(chǎn)生30個放射治療點，通過本文設(shè)計的算法可以對其進行有效的順序優(yōu)化，優(yōu)化后放射點空間軌跡線無交叉，軌跡流暢，優(yōu)化率高，從而在射波刀運行速度恒定時，可有效減少運行時間，提高治療精度及效率。

4 結(jié)語

本文為減少放射治療時間，對放射治療點順序優(yōu)化進行了總體遺傳算法設(shè)計，并且針對各個算子進行了選型及設(shè)計。主要有：從放射治療點順序優(yōu)化引出TSP問題；對TSP問題的基本定義、理論及建模進行介紹；在此基礎(chǔ)上進行放射治療點順序優(yōu)化模型的建立；對于放射治療點順序優(yōu)化進行總體算法設(shè)計；進行隨機測試實驗；對構(gòu)建的算法模型建立程序，在matlab平臺上進行數(shù)據(jù)的優(yōu)化計算，得到空間放射點順序優(yōu)化圖。