基于TSP改進(jìn)遺傳算法的放射治療點(diǎn)順序*優(yōu)化研究

王袈歡 湯 卿 陸煜衡

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

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

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

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

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

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

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

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

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

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

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

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

2.1 算法整體設(shè)計(jì)

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

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

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

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

1) 編碼及種群初始化

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

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

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

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

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

對(duì)于兩個(gè)父代個(gè)體：

隨機(jī)選擇兩個(gè)交叉點(diǎn)l和m ，（1＜l＜m＜n），截取染色體中間片段：

交叉置于對(duì)方父代染色體后：

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

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

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

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

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

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

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

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

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

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

為了驗(yàn)證算法的有效性，在matlab平臺(tái)上進(jìn)行優(yōu)化仿真。在放射治療空間中隨機(jī)產(chǎn)生30個(gè)放射點(diǎn)，并隨機(jī)產(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。其放射點(diǎn)的順序規(guī)劃如圖2中（a）所示，路徑交叉，且其路徑總長(zhǎng)度為2 754.6 mm。通過本算法對(duì)路徑進(jìn)行優(yōu)化后其路徑順序?yàn)椋?2 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）所示，路徑總長(zhǎng)度為685.1 mm。與初始路徑比較優(yōu)化了75.1% 。

圖2 30個(gè)放射治療點(diǎn)順序優(yōu)化對(duì)比圖

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

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

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

從表1可見，該算法的優(yōu)化效果穩(wěn)定，平均優(yōu)化率達(dá)到 76.5%?；谝陨蠈?shí)驗(yàn)，可以得出：在放射治療過程中，隨機(jī)產(chǎn)生30個(gè)放射治療點(diǎn)，通過本文設(shè)計(jì)的算法可以對(duì)其進(jìn)行有效的順序優(yōu)化，優(yōu)化后放射點(diǎn)空間軌跡線無交叉，軌跡流暢，優(yōu)化率高，從而在射波刀運(yùn)行速度恒定時(shí)，可有效減少運(yùn)行時(shí)間，提高治療精度及效率。

4 結(jié)語

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