馬梅，李和成

青海師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西寧810008

求解TTP問(wèn)題新優(yōu)化模型的混合遺傳算法

馬梅，李和成

青海師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西寧810008

CNKI網(wǎng)絡(luò)出版：2017-04-01,http://kns.cnki.net/kcms/detail/11.2127.TP.20170401.0908.046.html

1 引言

在實(shí)踐中，很多問(wèn)題通常由兩個(gè)或兩個(gè)以上的子問(wèn)題復(fù)合而成，而這些子問(wèn)題并不是相互獨(dú)立的，一個(gè)子問(wèn)題獲得最優(yōu)解往往影響其他子問(wèn)題的解，原問(wèn)題的解需要綜合考慮所有子問(wèn)題的解，如Bonyadi等提出的流竄犯問(wèn)題（Traveling Thief Problem，TTP）[1]。TTP問(wèn)題由旅行商問(wèn)題（Traveling Sales Problem，TSP）和背包問(wèn)題（Knapsack Problem，KP）復(fù)合而成，因此同時(shí)具備了TSP問(wèn)題和KP問(wèn)題的求解難度。一個(gè)TTP問(wèn)題可以描述如下：假定有n個(gè)城市，兩兩距離已知，有m個(gè)物品分布在這n個(gè)城市中。一個(gè)小偷從某一城市出發(fā)，拜訪所有的城市僅一次，最后回到出發(fā)城市。在整個(gè)過(guò)程中，小偷從每個(gè)城市拿取一定的物品放入租賃的具有一定容量的背包中，但所拿物品的總重量不得超過(guò)背包容量。背包的租金與旅行時(shí)間相關(guān)，旅行時(shí)間既與選取的路徑有關(guān)，也與所負(fù)重量有關(guān)。重量越大，行走時(shí)間越長(zhǎng)，支付的租金越多。在該問(wèn)題中，小偷所拿的物品總價(jià)減去背包租金即為收益。問(wèn)題求解的目的是收益最大化，即小偷需要找到一條路徑和一個(gè)物品的選取方案，使得旅途結(jié)束后所得的收益最大。

TTP問(wèn)題的一個(gè)有趣應(yīng)用是具有服務(wù)利潤(rùn)的限量弧路由問(wèn)題（Capacitated Arc Routing Problem，CARP）。限量弧路由問(wèn)題由Golden等[2]提出，城市中灑水問(wèn)題、垃圾清理、信件投遞等均可建模為CARP問(wèn)題。目前基于不同的需求，限量弧路由問(wèn)題及其各種變種被廣泛提出[3-7]。但這些問(wèn)題忽視了兩個(gè)重要的現(xiàn)實(shí)因素：一是服務(wù)利潤(rùn)。每個(gè)客戶在服務(wù)過(guò)程均具有一定的需求量和服務(wù)利潤(rùn)，所有客戶在服務(wù)過(guò)程中均被服務(wù)一次且僅一次。給定車輛的負(fù)載量限制，則可能只需服務(wù)具有高利潤(rùn)客戶的一小部分就可以最大化最后利益。二是基于車輛負(fù)載量的旅行花費(fèi)。每輛車在服務(wù)過(guò)程中基于車輛的負(fù)載量還會(huì)產(chǎn)生一定的旅行花費(fèi)（例如，汽油消耗量）。每輛車對(duì)于需求的負(fù)載量均有限且小于所有客戶需求量之和。問(wèn)題求解的目標(biāo)是在滿足下列條件時(shí)，最大化服務(wù)利潤(rùn)：（1）每輛車從倉(cāng)庫(kù)出發(fā)并最終回到出發(fā)倉(cāng)庫(kù)；（2）每個(gè)客戶均被一輛且僅一輛車所服務(wù)；（3）對(duì)于每輛車，其服務(wù)的客戶所具有的總需求量不超過(guò)其容量。考慮了這些問(wèn)題后，具有服務(wù)利潤(rùn)的CARP問(wèn)題其模型即為TTP問(wèn)題。

TTP問(wèn)題是近幾年被提出的一個(gè)復(fù)合組合優(yōu)化問(wèn)題。一方面，該問(wèn)題同時(shí)具有TSP問(wèn)題和KP問(wèn)題的計(jì)算復(fù)雜度，對(duì)現(xiàn)有的組合優(yōu)化算法提出了新的挑戰(zhàn)，另一方面，在實(shí)踐領(lǐng)域的應(yīng)用越來(lái)越廣。這兩方面的需求吸引了越來(lái)越多的研究者。Mei等[8]針對(duì)大規(guī)模的TTP問(wèn)題給出了相對(duì)簡(jiǎn)單的算法，分析了不同算法的計(jì)算復(fù)雜度，并給出了減少計(jì)算復(fù)雜度的策略，提出的基于兩階段局部搜索的復(fù)合算法（MATLS）在計(jì)算結(jié)果上優(yōu)于文獻(xiàn)[9]中提出的隨機(jī)局部搜索算法（RLS）和（1+1）進(jìn)化策略。Bonyadi等[10]設(shè)計(jì)了一種協(xié)同進(jìn)化算法。該算法利用TSP問(wèn)題和KP問(wèn)題間交互式信息進(jìn)行求解，將得到的結(jié)果進(jìn)行組合作為TTP問(wèn)題的近似解。與該文提出的DH算法相比，協(xié)同進(jìn)化算法的計(jì)算更有效。文獻(xiàn)[8-10]采用的算法框架是首先確定一個(gè)子問(wèn)題的解，再求另一個(gè)問(wèn)題的解。典型的方法就是初始化最短的TSP路徑的集合，然后求解相應(yīng)的KP問(wèn)題。這種做法雖然可以得到兩個(gè)子問(wèn)題相對(duì)最優(yōu)的解，但不能保證能找到對(duì)應(yīng)TTP問(wèn)題的最優(yōu)解。

在文獻(xiàn)[11]中，Mei等提出了兩種復(fù)合算法。一個(gè)是協(xié)同進(jìn)化算法（CC），該算法分別利用進(jìn)化算法求解兩個(gè)子問(wèn)題，在每一代交換子問(wèn)題間的信息，最后獲得最優(yōu)解。另一種復(fù)合算法將TTP問(wèn)題作為一個(gè)整體進(jìn)行求解。兩種算法在同一測(cè)試集上的結(jié)果表明，第二種復(fù)合算法優(yōu)于第一種算法。Louren?o等[12]通過(guò)考慮兩個(gè)子問(wèn)題之間關(guān)系，在進(jìn)化過(guò)程中將路徑和物品選取方案作為種群個(gè)體，給出了一種進(jìn)化算法。文獻(xiàn)[11-12]中，將TTP問(wèn)題作為一個(gè)整體去求解，計(jì)算結(jié)果顯示這種處理技術(shù)是有效的。

另外，Polyakovskiy等[13]研究了一種非線性背包問(wèn)題。該問(wèn)題的主要特征是：（1）沿某條確定的路徑拿取物品；（2）考慮旅行時(shí)間。闡述了問(wèn)題的復(fù)雜度并指出即使背包容量無(wú)約束，該問(wèn)題也是NP-難問(wèn)題，并給出了求解該問(wèn)題的精確和近似混合整數(shù)規(guī)劃方法（Mixed Integer Programming，MIP）。

在以上提出的TTP問(wèn)題中，總假設(shè)小偷提前知道每個(gè)城市中物品的分布情況，故在旅行開始前利用此信息對(duì)所有物品進(jìn)行價(jià)值評(píng)估，提前決定物品選取策略。

本文從另一個(gè)角度考慮TTP問(wèn)題，即假設(shè)小偷在到達(dá)前并不知道城市中物品的具體位置。為了行走前能有效規(guī)劃路徑，選取盡可能好的方案，本文假設(shè)知道物品在每個(gè)城市分布的概率。與現(xiàn)有模型相比，考慮的新問(wèn)題具有如下特點(diǎn)：

（1）在TTP模型中考慮小偷提前不知道物品的具體位置更符合實(shí)際情況。

（2）模型中含有概率信息，具有不確定性，只能獲得概率意義上的最優(yōu)解。

與一般TTP問(wèn)題一樣，不同的出發(fā)點(diǎn)，具有不同的最優(yōu)方案，這一點(diǎn)不同于TSP問(wèn)題。不失一般性，本文選擇出發(fā)點(diǎn)為編號(hào)1的城市。另外，出發(fā)城市中的物品返回后再選擇是合理的。

2 TTP問(wèn)題

2.1 問(wèn)題描述

一個(gè)小偷拜訪每個(gè)城市一次且僅一次，并最終回到出發(fā)城市。在整個(gè)過(guò)程中，小偷從每個(gè)城市拿取一定的物品裝進(jìn)背包，但所拿物品的總重量不得超過(guò)背包容量W。背包的租金R與旅行時(shí)間相關(guān)。小偷需要找到一條路徑和一種物品的拿取策略，使得旅途結(jié)束后所得的收益最大。

令ykj∈{0,1} 。當(dāng)物品k從城市xj拿取時(shí)，ykj=1，否則ykj=0。記小偷離開城市xj時(shí)所拿物品的總重量為wj。那么，對(duì)任意一個(gè)路徑X（xj的一個(gè)排列，不失一般性，仍記為X=(x1,x2,…,xn)）和一個(gè)拿取策略ykj，其優(yōu)化模型為：

其中：

表示小偷從城市xi到城市xj所花的時(shí)間。

2.2 問(wèn)題分析

從TTP問(wèn)題的優(yōu)化模型可知，小偷旅行時(shí)間和所拿物品的重量通過(guò)速度聯(lián)系在一起。因此求解總的旅行時(shí)間必須知道路徑和拿取方案，同時(shí)，總收益又與旅行時(shí)間有關(guān)，由此可以看出，兩個(gè)子問(wèn)題并不是相互獨(dú)立的。

圖1給出TTP問(wèn)題的一個(gè)簡(jiǎn)單例子[1]，除第一個(gè)點(diǎn)外，其他點(diǎn)均有物品分配。問(wèn)題的相關(guān)參數(shù)值如下：

（1）n=4, m=5, W=3, vmax=1, vmin=0.1 。

（2）單位時(shí)間所花的租金為R=$1。

（4）每個(gè)物品的價(jià)值及重量定義為Ik=(pk,wk),k=1,2,3,4,5。則有

（5）物品的有效性C1={0}, C2={4,5}，C3={1,2,3} ，C4={4}。

圖1 TTP問(wèn)題算例

在上述例子中，若將TTP問(wèn)題分解為兩個(gè)子問(wèn)題單獨(dú)求解，得到兩個(gè)對(duì)應(yīng)子問(wèn)題的最優(yōu)解分別為：TSP問(wèn)題的最短路徑為X={1,2,3,4}或X={1,4,3,2}。KP問(wèn)題的最佳選取方案為Y={3,0,0,0,0}，此時(shí)TTP問(wèn)題的收益G=-10。但事實(shí)上該TTP問(wèn)題的最大收益G=50，最優(yōu)路徑X={1,2,4,3}，選取方案Y={0,3,3,0,0}。

從上述例子可以看出，將兩個(gè)子問(wèn)題分別求最優(yōu)解，不能保證得到TTP問(wèn)題的最優(yōu)解，TTP問(wèn)題的兩個(gè)子問(wèn)題相互依賴。

3 基于概率分布的新模型及算法

3.1 新TTP問(wèn)題模型

在實(shí)踐中小偷往往提前不知道物品的具體位置，因此行走前無(wú)法明確地規(guī)劃行走路線和拿取方案。為了解決這個(gè)問(wèn)題，在新模型中假設(shè)已知物品分布的概率信息?；谶@些概率信息規(guī)劃合適的路徑和制定好的拿取方案。

假設(shè)物品k在城市xj中存在的情況服從概率為Pkj的0-1分布。即物品k在城市xj的概率為Pkj，不在城市xj的概率為1-Pkj。則物品k在城市xj的價(jià)值均值為相應(yīng)的，物品k在城市xj中的重量均值新的優(yōu)化模型為：

3.2 物品有效價(jià)值及選取策略

對(duì)于路徑X={x1,x2,…,xn}，評(píng)估所有物品的有效價(jià)值。令----pkj表示物品k在城市xj中的有效價(jià)值。計(jì)算公式如下：

根據(jù)每個(gè)物品的有效價(jià)值，對(duì)所有物品進(jìn)行排序，按次序選擇，有效價(jià)值大的物品優(yōu)先拿取。在物品的選取過(guò)程中應(yīng)用文獻(xiàn)[8]提出的策略消除不增加收益的物品。

3.3 局部搜索

在選擇的路徑上，物品的重量和行走距離有以下四種情況：

（1）城市中物品的重量較大，但行走距離較?。ㄈ鐖D2中的點(diǎn)a）；

（2）城市中物品的重量較小，且行走距離也較?。ㄈ鐖D2中的點(diǎn)b）；

（3）城市中物品的重量較小，但行走距離較大（如圖2中的點(diǎn)c）；

（4）城市中物品的重量較大，且行走距離也較大（如圖2中的點(diǎn)d）。

以上四種情形，（4）是不利于獲得最優(yōu)解的情況，因此對(duì)該路徑進(jìn)行局部調(diào)整，將重量大的物品放在后面拿取，即將相應(yīng)城市的次序向后調(diào)整，使之變成（1）的情況，有利于改進(jìn)解的質(zhì)量。

圖2 城市中物品重量及行走距離

對(duì)于給定的路徑X={x1,x2,…,xn}，通過(guò)有效價(jià)值計(jì)算，獲得物品的拿取方案。定義集合Rj?Cj，表示城市xj中所拿物品的集合。則每個(gè)城市中所拿物品的重量定義為：

城市xj到城市x1的行走距離記為d(xj,x1)，則

特別的，d(x1,x1)=0。

給出局部搜索算法的步驟：

（1）對(duì)wj和距離d(xj,x1)進(jìn)行標(biāo)準(zhǔn)化，其標(biāo)準(zhǔn)化形式如下：

其中wmax、wmin表示每個(gè)城市中拿取物品重量的最大值和最小值。

（2）對(duì)每個(gè)城市計(jì)算w′j和d′j的乘積，記作wdj=w′j×d′j,j=1,2,…,n，作為城市xj對(duì)最后收益是否有利的指標(biāo)。

（3）令wdmax=max{wdj,j=1,2,…,n}，并記對(duì)應(yīng)城市為xmax。

（4）對(duì)給定的路徑，在城市xmax所在位置后隨機(jī)產(chǎn)生兩個(gè)插入位置，將城市xmax分別移位至產(chǎn)生的兩個(gè)隨機(jī)位，得到兩個(gè)新的路徑，記為X1和X2。對(duì)產(chǎn)生的路徑X1和X2，利用物品選取策略求得相應(yīng)的物品拿取方案。

（5）求解新方案(X1,Y1)、(X2,Y2)的目標(biāo)函數(shù)值，兩者中較好者與原方案比較，若優(yōu)于原方案，則替換原方案，否則保留原方案。

3.4 提出的復(fù)合算法

基于物品選擇策略和局部搜索方法，給出求解TTP問(wèn)題新模型的一個(gè)復(fù)合遺傳算法（HGA算法）。考慮到遺傳算法的全局收斂性，在該算法框架中，利用遺傳算法搜索路徑。

HGA算法：

（1）初始化種群。采用文獻(xiàn)[14]中路徑的編碼方式產(chǎn)生初始種群P(0)。種群規(guī)模為N。個(gè)體雜交概率為pc，變異概率為pm。令代數(shù)t=0。

（2）適應(yīng)度評(píng)估。利用物品拿取策略給出拿取方案，并計(jì)算目標(biāo)函數(shù)值作為適應(yīng)度。

（3）雜交、變異。采用文獻(xiàn)[14]中的雜交、變異算子產(chǎn)生后代集合，并基于相應(yīng)的物品拿取方案評(píng)估個(gè)體。

（4）局部搜索。對(duì)后代中較差的v個(gè)個(gè)體進(jìn)行局部搜索，并評(píng)估新產(chǎn)生的個(gè)體。

（5）終止條件。當(dāng)?shù)螖?shù)達(dá)到最大代數(shù)時(shí)，算法停止，輸出最大收益Gmax，否則，令t=t+1，轉(zhuǎn)（3）。

由于TTP問(wèn)題的目標(biāo)函數(shù)不僅與距離有關(guān)，而且與物品的拿取方案有關(guān)。遺傳算法能有效通過(guò)選擇算子搜索較好的個(gè)體。另外，局部搜索方法是在現(xiàn)有路徑上考慮了物品的重量和距離，這個(gè)方法有效彌補(bǔ)了單純路徑搜索的不足。

盡管遺傳算法具有全局收斂性，但考慮到問(wèn)題中物品的分布具有不確定性，因此本文算法獲得的是概率意義下的最優(yōu)解。

4 仿真實(shí)驗(yàn)

目前文獻(xiàn)中對(duì)不知道物品具體位置的情況研究不多，為了檢驗(yàn)本文模型的可行性和算法的有效性，本文在文獻(xiàn)[9]中選擇了7個(gè)TTP算例（eil51、u159、ts225、u574、u724、dsj1000、fl1577），城市數(shù)分別為51、159、225、574、724、1 000、1 577。按照文獻(xiàn)[8]中物品的重量與價(jià)值的3種關(guān)系（Uncorrelated Type with Similar Weights（UT/SW）、Bounded Strongly correlated Type（BST）、Uncorrelated Type（UT）），每個(gè)算例產(chǎn)生3個(gè)不同的算例，共計(jì)算21個(gè)算例。參照算例中物品的位置信息，給出了相應(yīng)物品的分布概率。為了和現(xiàn)有結(jié)果作參考，按如下規(guī)則取概率分布：原例中若物品k在城市xj中出現(xiàn)，則在[0.9，1]中隨機(jī)產(chǎn)生一個(gè)數(shù)作為Pkj；若不出現(xiàn)，則在[0，0.1]中隨機(jī)產(chǎn)生一個(gè)數(shù)作為Pkj。

算法參數(shù)如下：種群規(guī)模N=500，雜交概率pc=0.8，變異概率pm=0.05，對(duì)算例eil51、u159、ts225，最大迭代次數(shù)為500，其他算例最大代數(shù)為1 000。對(duì)每個(gè)算例，算法重復(fù)執(zhí)行20次。

計(jì)算結(jié)果分別見表1。其中mean表示20次計(jì)算的平均目標(biāo)值，std表示20次計(jì)算所得目標(biāo)值的均方差，CPU表示本文提出的HGA算法運(yùn)行的平均CPU時(shí)間。

從實(shí)驗(yàn)結(jié)果可以看出，HGA算法對(duì)算例計(jì)算的平均目標(biāo)值和文獻(xiàn)中確定模型的最優(yōu)目標(biāo)值相差不大，同時(shí)看到，HGA算法計(jì)算的均方差較小，在算例eil51、u159、ts225-BST、ts225-UT/SW等14個(gè)算例上，HGA算法的均方差好于文獻(xiàn)方法，在其他算例上，不如文獻(xiàn)中得到的均方差，但結(jié)果相差不大。另外，從計(jì)算時(shí)間上可以看出，HGA算法獲得最好解的時(shí)間均在70 s內(nèi)。這意味著本文算法能有效求解這種含不確定信息的TTP問(wèn)題。

表1 實(shí)驗(yàn)結(jié)果

5 結(jié)論

本文在已有的TTP問(wèn)題的框架上，考慮了提前不知道物品分布的情況下，如何使收益“最大”的新模型。針對(duì)該問(wèn)題，設(shè)計(jì)了一個(gè)混合遺傳算法。該算法利用遺傳算法搜索路徑，基于有效價(jià)值計(jì)算選定拿取方案，根據(jù)城市中物品的重量和行走距離對(duì)路徑進(jìn)行局部?jī)?yōu)化。這個(gè)算法的特點(diǎn)是將兩個(gè)問(wèn)題的優(yōu)化有效地整合到一個(gè)算法框架內(nèi)，這有別于一些文獻(xiàn)中分開優(yōu)化，然后“對(duì)接”的思路。實(shí)驗(yàn)結(jié)果表明，提出的算法是有效可行的。下一步將在算法中進(jìn)一步綜合考慮路徑、價(jià)值和重量的關(guān)系，利用啟發(fā)式信息改進(jìn)算法的搜索效率。

[1] Bonyadi M R，Michalewicz Z，Batone L.The traveling thief problem：The first step in the transition from theoretical problems to realistic problems[C]//IEEE Congress on Evolutionary Computation（CEC），2013：1037-1044.

[2] Golden B L，Wong R T.Capacitated arc routing problems[J].Networks，1981，11（3）：305-316.

[3] Dror M.Arc routing：Theory，solutions and application[M].[S.l.]：Springer Science&Business Media，2000.

[4] Mei Y，Tang K，Yao X.Improved memetic algorithm for capacitated arc routing problem[C]//2009 IEEE Congress on Evolutionary Computation，2009：1699-1706.

[5] Mei Y，Tang K，Yao X.Decomposition-based memetic algorithm for multi-objective capacitated arc routing problem[J].IEEE Transactions on Evolutionary Computation，2011，15（2）：151-165.

[6] Mei Y，Tang K，Yao X.A memetic algorithm for periodic capacitated arc routing problem[J].IEEE Transactions on Systems，Man，and Cybernetics：Part B Cybernetics，2011，41（6）：1654-1667.

[7] Mei Y，Tang K，Yao X.Cooperative co-evolution with route distance grouping for large-scale capacitated arc routing problem[J].IEEE Transactions on Evolutionary Computation，2014，18（3）：435-449.

[8] Mei Y，Li X，Yao X.Improving efficiency of heuristics for the large scale traveling thief problem[C]//Simulated Evolution and Learning，2014，8886：631-643.

[9] Polyakovskiy S，Bonyadi M R，Michalewicz Z，et al.A comprehensive benchmark set and heuristics for the traveling thief problem[C]//Genetic and Evolutionary Computation Conference（GECCO），2014：477-484.

[10] Bonyadi M R，Michalewicz Z，Przybylek M R，et al.Socially inspired algorithms for the traveling thief problem[C]//Genetic and Evolutionary Computation Conference（GECCO），2014：421-428.

[11] Mei Y，Li X，Yao X.On investigation of interdependence between sub-problems of the traveling thief problem[J].Soft Computing，2014：1-16.

[12] Louren?o N，F(xiàn)rancisco B，Costa E.An evolutionary approach to the full optimization of the traveling thief problem[C]//16th European Conference on Evolutionary Computation，2016，9595：34-45.

[13] Polyakovskiy S，Neumann F.Packing while traveling：Mixed integer programming for a class of nonlinear knapsack problems[C]//International Conference on AI and OR Techniques in Constraint Programming for CombinatorialOptimizationProblems，2015，9075：332-346.

[14] Wang Y P，Han L X，Li Y H，et al.A new encoding based genetic algorithm for the traveling salesman problem[J].Engineering Optimization，2006，38（1）：1-13.

MA Mei,LI Hecheng.Hybrid genetic algorithm for solving new optimization model of TTP.Computer Engineering andApplications,2018,54（6）：156-160.

MAMei,LI Hecheng

School of Mathematics and Statistics,Qinghai Normal University,Xining 810008,China

The Traveling Thief Problem（TTP）is a composite optimization problem which combines the Traveling Salesman Problem（TSP）with the Knapsack Problem（KP）,and has an accumulated computational complexity caused by these two problems.In this paper,based on the original version of TTP,a new optimization model with probability distribution information is firstly proposed by considering that the thief doesn’t explicitly know the item location in advance in all cities.Then,by calculating the effective value of each item,a selection scheme of items is provided.Finally,taking advantage of a present genetic algorithm for solving TSP and a designed local search scheme,a new hybrid genetic algorithm is developed for dealing with the new TTP model.The simulation results show the proposed algorithm is feasible and efficient.

traveling thief problem;genetic algorithm;effective value;maximum profit

流竄犯問(wèn)題（Traveling Thief Problem，TTP）是旅行商問(wèn)題和背包問(wèn)題的一個(gè)組合問(wèn)題，同時(shí)具有兩個(gè)問(wèn)題的計(jì)算復(fù)雜度。在現(xiàn)有TTP問(wèn)題中考慮了小偷提前不知道物品具體位置的情況，給出了新的具有概率分布信息的優(yōu)化模型；利用有效價(jià)值指標(biāo)，給出了物品的選取方法；基于一個(gè)TSP的遺傳算法框架和新設(shè)計(jì)的局部搜索策略，提出了求解該模型的混合遺傳算法。數(shù)值仿真結(jié)果表明，提出的算法是可行有效的。

流竄犯問(wèn)題；遺傳算法；有效價(jià)值；最大收益

2016-09-27

2017-01-11

1002-8331（2018）06-0156-05

A

TP39

10.3778/j.issn.1002-8331.1609-0392

國(guó)家自然科學(xué)基金（No.61463045，No.11301291）；青海省自然科學(xué)基金（No.2013-Z-937Q）。

馬梅（1991—），女，碩士研究生，主要研究方向?yàn)樽顑?yōu)化理論及應(yīng)用，E-mail：1450670013@qq.com；李和成，男，博士，教授，博士研究生導(dǎo)師，主要研究方向?yàn)樽顑?yōu)化理論與方法，進(jìn)化算法及其應(yīng)用。

◎圖形圖像處理◎