整數規劃問題智能求解算法綜述

摘 要:為了對大規模整數規劃問題的求解方法提供參考，對基于智能算法求解整數規劃問題的研究進行了分析和評述。鑒于現有算法的缺陷與不足，討論了應用智能算法求解整數規劃問題未來可能的研究方向。

關鍵詞:整數規劃; 遺傳算法; 分布估計算法; 粒子群算法; 蟻群算法; DNA計算; 問題求解

中圖分類號:TP301

文獻標志碼:A

文章編號:1001-3695(2010)02-0408-05

doi:10.3969/j.issn.1001-3695.2010.02.003

Survey on intelligent optimization algorithms for solvinginteger programming problems

DU Hu-kang， ZHAO Ying-kai

(School of Automation Electrical Engineering， Nanjing University of Technology， Nanjing 210009， China)

Abstract:In order to provide reference of ways for solving large-scale integer programming problems， the paper made an analy-sis and comment on research of solving integer programming problems based on intelligent algorithms. In view of the shortcomings of current algorithms， discussed some possible future research directions about intelligent optimization algorithms for solving integer programming problem.

Key words:integer programming(IP); genetic algorithms(GA); estimation of distribution algorithms; particle swarm optimization; ant colony optimization; DNA computing; problem-solving

0 引言

整數規劃(IP)和混合整數規劃(mixed integer programming， MIP)問題是運籌學領域里的一個重要分支，機械、化工、計算機、經濟、生物、軍事、社會等各個學科領域里的許多優化問題均可歸結為IP或MIP問題，且大多數的組合優化問題都可以寫成一個IP或MIP問題，如背包、旅行商、最短路、選址、分配和生產與存儲計劃問題等。因此如何求解IP或MIP問題是一個重要的研究領域。雖然整數規劃問題的解空間在結構上比連續問題好確定，但其解的計算卻十分困難。盡管持續不斷的理論研究已有幾十年時間，加之計算機速度和功能的驚人增加，整數規劃求解算法的研究還是沒能達到令人十分滿意的結果。由于整數規劃問題的可行解區域為離散點，故一般不能用連續區域的求解算法，只能用特殊方法求解，應用較多的傳統方法是分支定界法[1](branch and bound method)、割平面法[2](cutting plane algorithm)和分解算法[3～5](decomposition algorithm)，其他常規方法有圖論法[6]、交集及交集余集解法[7]、罰函數法[8]、群論法[9]等。

傳統的整數規劃問題的求解算法是一種確定性算法，即從一個搜索點到另一個搜索點的轉移有確定的轉移方法和轉移關系，其結果得到的是一個惟一最優解，對小規模整數規劃問題求解效果較佳;而當求解問題的規模較大時，其計算量相當可觀，計算時間將極大地增加，甚至無法求解問題。與之相對應的智能優化算法大多采用并行搜索技術，克服了傳統整數規劃解法的單點搜索效率低的問題，在實際優化問題應用中具有較大的靈活性，對大規模的整數規劃問題的求解較為有效。本文主要對智能優化算法在求解整數規劃問題中的應用進行分析總結，以期對大規模整數規劃問題的求解提供方法參考，并在文章最后給出了關于整數規劃問題求解的思考與展望。

1 整數規劃問題求解的群體智能優化算法

群體智能優化算法是一類從生物群體的角度對智能進行模擬的隨機搜索算法，主要包括遺傳、分布估計、粒子群和蟻群算法等。它不依賴于梯度信息的群體搜索策略及群體中個體之間信息交換的特點，可以用來解決許多傳統搜索方法解決不了的復雜問題，對求解可行解區域為離散點的大規模整數規劃問題十分有效。

1.1 基于遺傳算法的整數規劃問題求解

遺傳算法[10，11](GA)是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化的概率算法。在遺傳算法中，用種群表示優化問題的一組候選解，種群中的每個個體都有相應的適應值，然后反復進行選擇、交叉和變異等模擬自然進化的操作，對問題進行求解。GA基于模式定理產生群體中的最優個體，故其對目標函數和約束條件的要求比較低，特別是對于純整數規劃問題，由于存在有限的可行解空間，采用適當的遺傳算法可以較快地得到全局最優解或最優近似解[12，13]。此外，由于它是一種概率算法，還有可能得到一系列的最優調度策略。

為了提高遺傳算法在求解整數規劃問題時的尋優收斂速度和求解效率，在決策變量和約束條件很多時，大部分文獻對遺傳算法的編碼和算子進行了改進。劉樹安等人[14]提出一種新的位串編碼結構，采用一種新的加速變異算子，并為保持種群多樣性引入分散型淘汰法;文獻[15]采用二進制映射模式可變長度染色體編碼，在進化過程逐漸縮小編碼的搜索空間，可以在加快收斂速度的同時改善迭代精度;文獻[16]采用基于參考解更新的雙字符串擴展遺傳算法，在進化過程提高整數規劃松弛問題優化解的搜索效率;混合染色體編碼方式[17]也是一種有效編碼的方法。為了彌補遺傳算法的缺陷，常將遺傳算法與其他算法相結合來求解整數規劃問題，主要有遺傳算法與混沌的結合[18]，遺傳算法與罰函數的結合[19]，遺傳算法、線性規劃與序優化方法相結合[20]，遺傳算法與分支定界法相結合[21]。對于大規模整數規劃問題，采用變分組技術[22，23]從減小搜索空間維數入手，也不失為一種有效方法。當然，遺傳算法對于多目標整數規劃[24，25]、0-1規劃[26]等特殊整數規劃問題的求解已有較深入的應用。

在求解整數規劃問題的應用中，GA具有計算速度快且易與其他算法相結合的優點，其多種編碼方式和各種改進的算子克服了遺傳算法的部分缺陷。但在計算過程中遺傳算法會出現早熟問題，特別是對于全局最優解被最差解包圍的大海撈針問題，隔斷了模式的重組過程，使得GA搜索長期陷入局部極值點。

1.2 基于分布估計算法的整數規劃問題求解

分布估計算法[27～29](estimation of distribution algorithms，EDAs)是最近幾年在進化計算領域興起的一類新型的進化算法，這種算法可以顯式地表示變量之間的關系，能快速、準確、可靠地解決傳統算法束手無策的一類優化問題。與遺傳算法相比，分布估計算法提出了一種全新的進化模式，沒有交叉、變異等遺傳操作，取而代之的是概率模型的學習和采樣。分布估計算法通過一個概率模型描述候選解在空間的分布，然后采用統計學習手段從群體的角度建立一個描述解空間分布的概率模型，再對概率模型隨機采樣產生新的種群，如此反復，實現種群的進化。

分布估計算法提出較晚，目前還鮮有應用于求解一般整數規劃問題，大多數文獻只是將其應用于求解一些特殊的整數規劃問題。文獻[30]較為全面地介紹了分布估計算法在求解整數規劃問題中的應用，如0-1背包問題、旅行商問題和Job-Shop調度問題等;Paul等人[31]討論了EDAs在子集和問題、OneMax函數、n-Queen問題中的應用;此外，文獻[32]采用貝葉斯優化算法求解帕累托解集和多維0-1背包問題;文獻[33]用來求解最大團和復雜數據結構問題;文獻[34]用來求解欺騙問題。在算法的改進方面主要有文獻[35]對分布估計算法進行了改進并將其應用到多維背包問題;文獻[36]應用帶變異分布估計算法求解非線性整數規劃問題，但其對求解問題的決策變量進行了范圍限制。

較之遺傳算法，分布估計算法是在群體宏觀層面上的數學建模，在搜索能力和效率上具有很大優勢。概率模型的選擇與學習是分布估計算法的核心，但基于有限樣本的復雜模型學習本身是一個相當復雜的問題，而且概率模型的學習或多或少存在著對先驗知識的依賴，因此如何設計更為有效的模型學習方法是提高EDAs求解整數規劃問題計算效率的難點之一。

1.3 基于粒子群算法的整數規劃問題求解

粒子群算法[37，38](particle swarm optimization，PSO)最早由美國科學家Kennedy和Eberhart在1995年提出，它是模擬鳥類的覓食行為受到生物群體模型啟發而設計的一種智能算法。PSO算法與其他進化算法相類似，采用群體探索問題的解空間，所不同的是群體中的每一個體按照一定的自適應速度在解空間隨機搜索，同時每一個體記憶自己所搜索解空間的最好位置，并以一定的加速度向自己所經歷的最好位置和群體中所有個體所經歷的最好位置飛行。

如何將PSO算法應用于整數規劃問題求解，文獻[39，40]較早地對這個問題進行了研究。在對基本PSO算法進行分析的基礎上，文獻[41]提出了一種保證微粒群在進化過程中始終控制在整數空間內的直接進行進化計算的PSO算法，避免了不必要的實數域搜索，提高了尋優效率。量子粒子群優化算法[42](quantum-behaved PSO)用于求解整數規劃問題的優勢是引入了量子行為來增強粒子的全局收斂能力。Kitayama等人[43]提出離散變量處理技術，將離散決策變量看做一個罰函數來求解混合整數規劃問題;文獻[44]使用兩種變異粒子群即基本要素粒子群(barebones particle swarm)和擴展基本要素粒子群(exploiting barebones particle swarm)來求解整數規劃也是有效的。此外，整數資源配置的優化問題[45]、任務分配問題[46]也都涉及到使用粒子群優化算法來求解整數規劃問題。

使用PSO來求解整數規劃問題，其優點是算法容易實現、控制參數少，因每次計算迭代結果應為整數，所以應用PSO求解整數規劃的關鍵是如何處理每次迭代后的數值，且應用PSO計算也會出現解的早熟問題。

1.4 基于蟻群算法的整數規劃問題求解

蟻群算法[47，48](ant colony optimization，ACO)是意大利學者Dorigo受自然界中真實蟻群集體行為的啟發于1991年提出的一種新型優化算法，并成功地用于求解旅行商問題。螞蟻在運動過程中，在它所經過的路徑上留下信息素，并感知信息素的存在及其強度，朝著強度高的方向移動。因此，由大量螞蟻組成的蟻群集體行為表現出一種信息正反饋現象:某一路徑上走過的螞蟻越多，后來的螞蟻選擇該路徑的概率就越大。螞蟻個體之間就是通過這種信息的交流進行路徑的最優選擇，從而達到搜索食物的目的。蟻群算法正是充分利用了這樣的優化機制，即通過個體之間的信息交流與相互協作最終找到滿意解。

鑒于蟻群算法具有很強的發現最優解的能力，很多學者紛紛將其應用于整數規劃問題的求解。文獻[49]應用蟻群算法解決了典型的無約束整數規劃問題;文獻[50]將蟻群算法中基于信息素的正反饋方法引入到求解整數規劃演化算法之中，實現了每一個體等位基因的優化，使算法穩定地收斂到全局最優解;文獻[51]正是通過螞蟻之間的信息交流進行路徑的最優選擇來解決機組組合優化問題。林錦等人[52]將蟻群算法作適當改進，用于解凸整數規劃問題;Schlüter等人[53]則將蟻群算法改進后成功用于求解非凸整數規劃問題。對于背包問題這類特殊的整數規劃問題的求解，文獻[54]給予了較詳盡的介紹;Seckiner等人[55]提出兩種改進蟻群算法較好地解決了崗位輪換調度中的整數規劃問題;文獻[56]采用改進蟻群算法來解決分批交貨的車輛路徑問題的整數規劃模型;文獻[57]使用蟻群系統(ACS)結合ASRank和MMAS蟻群算法的信息素更新策略來解決逆向物流車輛路徑問題的混合整數規劃模型。

蟻群算法的生物學背景決定了它適合于求解離散空間中的組合優化問題，采用分布式并行運算機制，易于與其他算法相結合，具有很強的魯棒性和適應性。該算法的搜索時間過長，大部分計算時間被用于解的構造，在執行過程中容易出現停滯現象，當求解整數規劃問題規模較大時還可能陷入局部最優解，這也是目前大部分應用ACO求解整數規劃問題的文獻大多對基本蟻群算法進行改進的原因。

2 DNA計算求解整數規劃問題

DNA計算[58，59]是一種模擬生物分子DNA的結構并借助于分子生物技術進行計算的新方法。其基本思想是:利用DNA特殊的雙螺旋結構和堿基互補配對原則對問題進行編碼，把要運算的對象映射成DNA分子鏈，在DNA溶液的試管里，在生物酶的作用下生成各種數據池;然后按照一定的規則將原始問題的數據運算高度并行地映射成DNA分子鏈可控的生化過程;最后，利用分子生物技術獲得運算結果。

在求解整數規劃問題中很多學者將目光投向了具有特殊優勢的DNA計算。文獻[60]采用熒光標記的策略，提出了一種基于DNA計算的將決策變量的取值限定在[-1，0，1]之中的特殊整數規劃問題求解算法;文獻[61]提出了約束方程變量分解的概念，通過將約束方程進行分解和增加約束補鏈的方法將決策變量取值擴展到了[-Ti， Ti]。Yin Zhi-xiang等人[62]同樣采用基于表面的DNA計算熒光標記策略，解決了正整數線性規劃問題;WANG Shi-ying等人[63]詳細討論了DNA算法對于整數規劃的求解，但其面向的整數規劃問題要么是正整數線性規劃，要么是決策變量取值限定在[0，1]，或是對整數規劃問題的系數附加特殊要求。而采用熒光分子信標雜交后的互補DNA來求解整數線性規劃問題[64]，具有解讀、編碼簡單、計算時間短和錯誤率低等優勢;此外，DNA計算在0-1整數線性規劃[65，66]、0-1背包問題[67]等特殊的整數規劃中的應用已十分廣泛。

DNA計算的高度并行性和海量的信息存儲能力在求解整數規劃問題中，一方面有助于提高群體中個體的多樣性，從而使獲取最優解的可能性大大增加;另一方面DNA計算的顯式并行性，運算速度快，群體規模的增大并不會明顯導致計算時間的增加，對求解屬于NP問題的組合優化具有天生的優勢。但從目前文獻來看，DNA計算還沒有完全應用到一般整數規劃問題的求解。當然，現有的生化技術目前還難以應付計算中各種復雜的適應度函數，生化反應的不完備性可能會導致各種不可預測的錯誤結果。

3 整數規劃問題求解的其他智能算法

對于求解整數規劃問題，除了上面所提到的智能計算方法外，文獻[68]采用改進進化規劃求解線性約束的整數規劃和混合整數規劃問題，其高速精確的性能取得了較滿意的求解結果;文獻[69]應用差分進化的兩個變體，即自適應差分進化與使用環鄰域拓撲的差分進化來求解整數規劃問題，且其求解結果要優于標準差分進化和粒子群優化算法。李彤等人[70]針對整數規劃全局優化問題首次提出模擬植物生長算法，該算法從植物的向光性特點出發，將整數規劃的可行域作為植物的生長環境，根據各可行解目標函數的變化情況確定植物的生長信息(形態素濃度)，進而模擬出向光源(全局最優解)迅速生長的植物生長動力學模型。文獻[71]提出混合進化算法用于求解混合整數規劃問題，在進化算法中采用一種混合啟發式變異算子，將正交試驗設計作為雜交算子，并引入一種遷移算子增加種群的多樣性。文獻[72]提出了基于相似性學習的自適應演化算法，從而使得變異算子具有了很強的導向性，避免了傳統達爾文演化策略的半盲目性。其他的還有分散搜索算法[73]、禁忌搜索算法[74]和膜計算[75]等;此外，使用混合算法求解整數規劃問題也較為廣泛，如蟻群算法與粒子群算法的混合[76]、神經網絡與遺傳算法的混合[77]和混沌神經網絡[78]。

4 結束語

以上對整數規劃問題的智能求解算法進行了較為全面的分析與總結。雖然進化計算(GA、EDAs、PSO、ACO)和DNA計算是從生物群體、生物分子不同的層次對智能的模擬進行問題求解，但它們都是對問題的整個參數空間給出編碼方案，都采用并行搜索技術，在搜索中用到的都是隨機變換規則。此外，由于混合整數規劃問題計算復雜度是隨整數變量增加而增加的，對于求解整數規劃問題的智能算法只要稍作修改，對混合整數規劃問題求解同樣適用。

整數規劃問題的智能求解算法研究至今方興未艾，還有許多有價值的問題有待進一步的深入研究:

a)對求解整數規劃問題智能算法的結構、參數及操作算子進行改進研究。雖然很多學者對此已展開了研究，但這方面仍舊有很大的研究空間。

b)目前很多智能算法只是用來求解一些特殊的整數規劃問題，還應對其完全求解一般整數規劃問題進行擴展研究。

c)智能算法不是傳統的確定性的計算工具，對整數規劃問題的求解不是確定性的，應展開問題解的評價標準研究。

d)發展各種可能的求解整數規劃問題的高效并行或分布式混合優化算法，如DNA計算與進化計算的集成研究。構造更有效的混合智能優化算法還有很多工作可以做，其發展空間很大，期待更好算法的出現。

參考文獻:

[1]SHERALI H D， DRISCOLL P J. Evolution and state-of-the-art in integer programming[J]. Journal of Computational and Applied Mathematics， 2000， 124(1-2): 319-340.

[2]GOMORY R E. Outline of an algorithm for integer solutions to linear problem[J]. Bulletin of the American Mathematical Society， 1958， 64(5): 275-278.

[3]BELL D E， SHAPIRO J F. A convergent duality theory for integer programming[J]. Operations Research， 1977， 25(3): 419-443.

[4]FISHER M L. The Lagrangian relaxation method for solving integer programming problems[J]. Management Science， 2004， 50(12):1861-1874.

[5]GUIGNARD M. On solving structured integer programming problems with Lagrangian relaxation and/or decomposition[C]//Proc of IEEE Conference on Decision and Control. Piscataway:IEEE Press， 1989:1136-1141.

[6]譚尚旺，張德龍.一類整數規劃的圖論解法[J].石油大學學報:自然科學版，2003，27(2):124-129.

[7]馮振笑，柯越華.整數規劃的交集及交集余集解法[J].石油大學學報:自然科學版，2001，25(2):122-125.

[8]孟志青，胡奇英，楊曉琪.一種求解整數規劃與混合整數規劃非線性罰函數方法[J].控制與決策，2002，17(3):310-314.

[9]黎青松，周雙貴，杜文.用群論方法求解整數規劃問題的初步探討[J].西南交通大學學報，2000，35(4):417-420.

[10]HOLLAND J H. Adaptation in natural and artificial systems[M]. Cambridge:MIT Press， 1992: 1-20.

[11]GOLDBERG D E. Genetic algorithms in search， optimization， and machine learning[M]. Boston:Addison-Wesley， 1989: 1-217.

[12]RENDERS J M， FLASSE S P. Hybrid methods using genetic algorithms for global optimization[J]. IEEE Trans on System， Man， and Cybernetics， Part B:Cybernetics， 1996， 26(2): 243-258.

[13]MALASRI S， MARTIN J R， MEDINA R A， et al. Solving mathema-tical programming problems using genetic algorithms[C]//Proc of the 3rd Conference on Computing in Civil Engineering. 1996:233-239.

[14]劉樹安，鄭秉霖，王夢光. 基于GAs求解整數規劃問題的算法設計[J]. 東北大學學報:自然科學版，1998，19(2):198-200.

[15]豐建榮，劉志河，劉正和.混合整數規劃問題遺傳算法的研究及仿真實現[J].系統仿真學報，2004，16(4):845-848.

[16]SAKAWA M， KATO K. Integer programming through genetic algorithms with double strings based on reference solution updating[C]//Proc of the 26th Annual Conference on Industrial Electronics Society. 2000:2744-2749.

[17]LIN Y C， HWANG K S， WANG Feng-sheng. A mixed-coding scheme of evolutionary algorithms to solve mixed-integer nonlinear programming problems[J]. Computers and Mathematics with Applications， 2004， 47(8-9):1295-1307.

[18]寧偉華，陳紹順，王鳳山.求解整數規劃的混合遺傳算法[J].空軍工程大學學報:自然科學版，2004，5(6):80-83.

[19]LI Yin-xiu， GEN M. Nonlinear mixed integer programming problems using genetic algorithm and penalty function[C]//Proc of IEEE International Conference on Systems， Man and Cybernetics. Piscataway: IEEE Press， 1996: 2677-2682.

[20]LUO Y C， CHEN C H， GUIGNARD M. An efficient approach integrating genetic algorithm， linear programming， and ordinal optimization for linear mixed-integer programming problems[J]. International Journal of Smart Engineering System Design， 2001， 3(4): 279-287.

[21]FRENCH A P， ROBINSON A C， WILSON J M. Using a hybrid genetic-algorithm/branch and bound approach to solve feasibility and optimization integer programming problems[J]. Journal of Heuristics， 2001， 7(6): 551-564.

[22]HUA Zhong-sheng， HUANG Fei-hua. A variable-grouping based genetic algorithm for large-scale integer programming[J]. Information Sciences， 2006， 176(19): 2869-2885.

[23]HUA Zhong-sheng， HUANG Fei-hua. An effective genetic algorithm approach to large scale mixed integer programming problems[J]. Applied Mathematics and Computation， 2006， 174(2): 897-909.

[24]HADJ-ALOUANE A B， BEAN J C. Genetic algorithm for the multiple-choice integer program[J]. Operations Research， 1997， 45(1):92-101.

[25]黃樟燦.多目標整數規劃中的遺傳算法[J].武漢大學學報:自然科學版， 1999，45(5B):755-757.

[26]YANO H， SAKAWA M， SHIBANO T. Fuzzy multiobjective 0-1 programming through revised genetic algorithms[C]//Proc of the 2nd International Conference on Knowledge-based Intelligent Electronic Systems. 1998:101-108.

[27]周樹德，孫增圻.分布估計算法綜述[J]. 自動化學報，2007，33(2):113-124.

[28]ZHANG Qing-fu， SUN Jian-yong， TSANG E， et al. Hybrid estimation of distribution algorithm for global optimization[J]. Engineering Computations， 2004， 21(1):91-107.

[29]PELIKAN M， GOLDBERG D E， et al. A survey of optimization by building and using probabilistic models[J]. Computational Optimization and Applications， 2002， 21(1): 5-20.

[30]LARRAAGA P， LOZANO J A. Estimation of distribution algorith-ms: a new tool for evolutionary computation[M]. San Francisco:Kluwer Academic Publishers， 2002:1-30.

[31]PAUL T K， IBA H. Linear and combinatorial optimizations by estimation of distribution algorithms[C]//Proc of the 9th MPS Symposium on Evolutionary Computation. 2002:1-8.

[32]SCHWARZ J， OCENEK J. Multiobjective Bayesian optimization algorithm for combinatorial problems:theory and practice [J]. Neural Network World， 2001， 11(5):423-441.

[33]ZHANG Qing-fu， SUN Jian-yong， TSANG E. Combinations of estimation of distribution algorithms and other techniques[J]. International Journal of Automation and Computing， 2007， 4(3):273-280.

[34]丁才昌，殷曉東，盧露，等.基于概率模型的分布估計算法求解欺騙問題[J].長江大學學報:自然科學版，2008，5(4):350-352.

[35]楊廣益，歐陽智敏，全惠云.松馳互補的分布估計算法求解多維背包問題[J].計算機工程與應用，2007，43(12):77-80.

[36]劉明芳.基于分布估計算法的整數規劃研究[D].武漢:武漢理工大學，2008.

[37]KENNEDY J， EBERHART R. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. Pisca-taway:IEEE Press， 1995:1942-1948.

[38]SHI Yu-hui， EBERHART R. Parameter selection in particle swarm optimization[C]//Proc of the 7th International Conference on Evolutionary Programming.[S.l.]:Springer-Verlag， 1998:591-600.

[39]PARSOPOULOS K， VRAHATIS M. Recent approaches to global optimization problems through particle swarm optimization[J]. Natural Computing， 2002， 1(2-3): 235-306.

[40]LASKARI E， PARSOPOULOS K， VRAHATIS M. Particle swarm optimization for integer programming[C]//Proc of Congress on Evolutionary Computation. Washington DC:IEEE Computer Society， 2002: 1582-1587.

[41]譚瑛，高慧敏，曾建潮.求解整數規劃問題的微粒群算法[J].系統工程理論與實踐，2004，24(5):126-129.

[42]劉靜，須文波，孫俊.基于量子粒子群算法求解整數規劃[J].計算機應用研究，2007， 24(3):79-81.

[43]KITAYAMA S， YASUDA K. A method for mixed integer programming problems by particle swarm optimization[J]. Electrical Engineering in Japan， 2006， 157(2): 40-49.

[44]OMRAN M G H， ENGELBRECHT A， SALMAN A. Barebones particle swarm for integer programming problems[C]//Proc of IEEE Swarm Intelligence Symposium. 2007:170-175.

[45]QIU Qi-rong， ZHANG Yong-fang. Particle swarm optimization for integer resource allocation problem[C]//Proc of International Confe-rence on Risk Management and Engineering Management. 2008:141-144.

[46]SALMAN A， AHMAD I， AL-MADANI S. Particle swarm optimization for task assignment problem[J]. Microprocessors and Microsystems， 2002， 26(8):363-371.

[47]段海濱，王道波，朱家強，等. 蟻群算法理論及應用研究的進展[J].控制與決策，2004，19(12):1321-1326.

[48]DORIGO M， BIRATTARI M， STTZLE T. Ant colony optimization artificial ants as a computational intelligence technique[J]. IEEE Computational Intelligence Magazine， 2006， 1(4): 28-39.

[49]高尚，楊靜宇.非線性整數規劃的蟻群算法[J].南京理工大學學報，2005，29(增刊):120-123.

[50]黃樟燦，吳方才，胡曉林.基于信息素的整數規劃的演化求解[J].計算機應用研究，2001，18(7):27-29.

[51]SIMON S P， PADHY N P， ANAND R S. An ant colony system approach for unit commitment problem[J]. International Journal of Electrical Power and Energy Systems， 2006， 28(5):315-323.

[52]林錦，朱文興.凸整數規劃問題的混合蟻群算法[J].福州大學學報:自然科學版，1999，27(6):5-9.

[53]SCHLTER M， EGEA J A， BANGA J. Extended ant colony optimization for non-convex mixed integer nonlinear programming[J]. Computers and Operations Research， 2009， 36(7):2217-2229.

[54]SHI Han-xiao. Solution to 0/1 knapsack problem based on improved ant colony algorithm[C]//Proc of IEEE International Conference on Information Acquisition. 2006:1062-1066.

[55]SECKINER S U， KURT M. Ant colony optimization for the job rotation scheduling problem[J]. Applied Mathematics and Computation， 2008， 201(1-2):149-160.

[56]SUI Lu-si， TANG Jia-fu， PAN Zhen-dong， et al. Ant colony optimization algorithm to solve split delivery vehicle routing problem[C]//Proc of Chinese Control and Decision Conference. 2008:997-1001.

[57]ZHANG Tao， TIAN Wen-xin， ZHANG Yue-jie， et al. RLC_ACS: an improved ant colony algorithm for VRPSDP[C]//Proc of the 6th International Conference on Machine Learning and Cybernetics. 2007:978-983.

[58]ADLEMAN L. Molecular computation of solution to combinatorial problems[J]. Science， 1994， 266(11): 1021-1024.

[59]LIPTON R J. DNA solution of hard computation problems[J]. Scie-nce， 1995， 268(4): 542-545.

[60]王雷，林亞平. DNA計算在整數規劃問題中的應用[J]. 電子與信息學報，2005， 27(5):814-818.

[61]胡宇舟，王雷，顧學道. 有界整數規劃問題的DNA計算[J]. 計算機應用， 2008， 28(Z1):18-23.

[62]YIN Zhi-xiang， CUI Jian-zhong， YANG Jin. A surface-based DNA computing for the positive integer linear programming problem[C]//Proc of the 3rd International Conference on Intelligent Computing. Heidelberg: Springer-Verlag， 2007:1-9.

[63]WANG Shi-ying， YANG Ai-ming. DNA solution of integer linear programming[J]. Applied Mathematics and Computation， 2005， 170(1): 626-632.

[64]YIN Zhi-xiang， CUI Jian-zhong， YANG Jin， et al. DNA computing model of the integer linear programming problem based on molecular beacon[C]//Proc of International Conference on Intelligent Computing. Berlin:Springer:238-247.

[65]YEH C W， CHU C P， WU K R. Molecular solutions to the binary integer programming problem based on DNA computation[J]. Biosystems， 2006， 83(1): 56-66.

[66]LI Wang-gen， DING Yong-sheng. A microfluidic systems-based DNA algorithm for solving special 0-1 integer programming problem[J]. Applied Mathematics and Computation， 2007， 185(2):1160-1170.

[67]DAREHMIRAKI M， NEHI M H. Molecular solution to the 0-1 knapsack problem based on DNA computing[J]. Applied Mathematics and Computation， 2007， 187(2): 1033-1037.

[68]REN Qing-sheng， ZENG Jin， QI Fei-hu. Evolutionary programming for IP/MIP problems with linear constraints[J]. Journal of Systems Engineering and Electronics， 2000， 11(3): 59-64.

[69]OMRAN M G H， ENGELBRECHT A P. Differential evolution for integer programming problem[C]//Proc of IEEE Congress on Evolutionary Computation. 2007:2237-2242.

[70]李彤，王春峰，王文波，等.求解整數規劃的一種仿生類全局優化算法——模擬植物生長算法[J].系統工程理論與實踐，2005，25(1):76-85.

[71]李宏，焦永昌，張莉.一種求解混合整數規劃的混合進化算法[J].控制與決策，2008，23(10):1098-1102.

[72]王衛華，余林琛，成浩，等.基于相似性學習的整數規劃問題演化求解[J].武漢理工大學學報:信息與管理工程版，2004，26(2):64-67.

[73]DELL’AMICO M， IORI M， MARTELLO S. Heuristic algorithms and scatter search for the cardinality constrained PCmax problem[J]. Journal of Heuristics，2004，10(2):169-204.

[74]GLOVER F. Parametric tabu-search for mixed integer programs[J]. Computers and Operations Research， 2006， 33(9): 2449-2494.

[75]PAN Lin-qiang， MARTN-VIDE C. Solving multidimensional 0-1 kna-psack problem by P systems with input and active membranes[J]. Journal of Parallel and Distributed Computing， 2005， 65(12):1578-1584.

[76]XIAO Gang， LI Shou-zhi， WANG Xuan-hong， et al. A solution to unit commitment problem by ACO and PSO hybrid algorithm[C]//Proc of the 6th World Congress on Intelligent Control and Automation. 2006: 7475-7479.

[77]GEN M， IDA K， KOUBUCHI R， et al. Hybridized neural network and genetic algorithms for solving nonlinear integer programming[C]//Proc of International Conference on Knowledge-based Intelligent Electronic Systems. Berlin:Springer， 1998: 272-277.

[78]WANG Xiu-hong， QIAO Qing-li， WANG Zhen-gou. A quickly searching algorithm for “0-1” optimization problems based on chaotic neural network[C]//Proc of the 7th International Conference on Signal Processing. Piscataway:IEEE Press， 2004:1517-1520.