劉 山，王 巍，馬山珠

（中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300）

大規(guī)模非線性0-1規(guī)劃的粒子濾波算法

劉 山，王 巍，馬山珠

（中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300）

為解區(qū)間上隨機(jī)產(chǎn)生均勻分布的十進(jìn)制數(shù)粒子，轉(zhuǎn)換為該區(qū)間長(zhǎng)度的二進(jìn)制數(shù)得到初始可行解，計(jì)算初始可行解大規(guī)模0-1非線性規(guī)劃求解難題，設(shè)計(jì)并實(shí)現(xiàn)了粒子濾波的求解方法。粒子濾波是利用粒子集來(lái)表示概率，可以用在任何形式的狀態(tài)空間模型上。其核心思想是通過(guò)從后驗(yàn)概率中抽取的隨機(jī)狀態(tài)粒子來(lái)表達(dá)其分布，是一種順序重要性采樣法。在求解大規(guī)模非線性0-1規(guī)劃問(wèn)題時(shí)，將解劃分為M個(gè)區(qū)間，計(jì)算初始可行解中每個(gè)區(qū)間的粒子的均值和方差。然后采用正態(tài)分布迭代產(chǎn)生可行解粒子，使可行解粒子的分布逐步逼近或等于0-1非線性規(guī)劃問(wèn)題的最優(yōu)解。

0-1非線性規(guī)劃；粒子濾波；概率分布

在科學(xué)管理和其他領(lǐng)域中，大量應(yīng)用問(wèn)題可以采用0-1規(guī)劃來(lái)解決，這種規(guī)劃的決策變量?jī)H取值0或1，一個(gè)非負(fù)整數(shù)都可以用二進(jìn)制記數(shù)法用若干個(gè)0-1變量表示，0-1變量可以數(shù)量化地描述諸如開(kāi)與關(guān)、取與棄、有與無(wú)等現(xiàn)象所反映的離散變量間的邏輯關(guān)系、順序關(guān)系以及互斥的約束條件，因此，0-1規(guī)劃非常適合描述和解決如線路設(shè)計(jì)、工廠選址、生產(chǎn)計(jì)劃安排、旅行購(gòu)物、可靠性等人們所關(guān)心的多種問(wèn)題。其中大部分問(wèn)題，其目標(biāo)函數(shù)和（或）約束條件很難用線性函數(shù)表達(dá)。如果目標(biāo)函數(shù)和（或）約束條件中包含有自變量的非線性函數(shù)，則這樣的規(guī)劃問(wèn)題就屬于非線性規(guī)劃問(wèn)題[1]。

目前求解0-1非線性規(guī)劃問(wèn)題還沒(méi)有實(shí)用和有效的方法[2]，如分支限界法、隱枚舉法等。本文給出的大規(guī)模0-1規(guī)劃的粒子濾波求解方法，巧妙地解決了大規(guī)模問(wèn)題解的表示和求解面臨的組合爆炸問(wèn)題，算法依據(jù)粒子濾波原理搜索可行解，能夠高效準(zhǔn)確地解決問(wèn)題，為求解大規(guī)模0-1非線性規(guī)劃問(wèn)題開(kāi)辟了一個(gè)新的研究領(lǐng)域，無(wú)論從實(shí)用價(jià)值和理論研究都將帶來(lái)一系列新的成果和收獲。

1 問(wèn)題提出

考慮如下的0-1非線性規(guī)劃問(wèn)題

其中：x=（x1，x2，…，xn）T，f（x），gi（x），hj（x）為x的實(shí)值函數(shù)。

2 求解0-1非線性規(guī)劃的粒子濾波方法

2.1 粒子濾波基本原理

粒子濾波（PF：particle filter）的思想基于蒙特卡洛方法（Monte Carlo methods）[3]，它是利用粒子集來(lái)表示概率，可以用在任何形式的狀態(tài)空間模型上。粒子濾波法是指通過(guò)尋找一組在狀態(tài)空間傳播的隨機(jī)樣本對(duì)概率密度函數(shù)進(jìn)行近似，以樣本均值代替積分運(yùn)算，從而獲得狀態(tài)最小方差分布的過(guò)程[4]。這里的樣本即指粒子，當(dāng)樣本數(shù)量N→∝時(shí)可以逼近任何形式的概率密度分布。

2.2 求解方法

求解大規(guī)模0-1非線性規(guī)劃粒子濾波方法的基本思路是窮盡規(guī)劃問(wèn)題的可行解，不是硬性搜索的簡(jiǎn)單窮舉，而是按照0-1非線性規(guī)劃問(wèn)題可行解的基本規(guī)律搜索，最優(yōu)解或可行解集中在某個(gè)區(qū)域，在此區(qū)域搜索到最優(yōu)解的概率最高，即可行解粒子越集中的區(qū)域，找到0-1非線性規(guī)劃問(wèn)題最優(yōu)解的幾率就越高。

實(shí)現(xiàn)本方法關(guān)鍵要克服NP問(wèn)題共有的兩個(gè)難點(diǎn)：①當(dāng)問(wèn)題規(guī)模很大，解的個(gè)數(shù)很多時(shí)，如何表示問(wèn)題的解；②如何避免0、1解的組合爆炸問(wèn)題。設(shè)0-1非線性規(guī)劃問(wèn)題解的個(gè)數(shù)為N，即解的長(zhǎng)度為N。將N分為M個(gè)等分或不等分區(qū)間，每個(gè)區(qū)間的長(zhǎng)度表示為Mi?？紤]到計(jì)算機(jī)的最大整數(shù)表示，每個(gè)區(qū)間取小于或等于16的二進(jìn)制數(shù)，即216=65 536。這樣無(wú)論0、1解的個(gè)數(shù)有多少，每個(gè)區(qū)間都可用小于或者等于65 535的十進(jìn)制數(shù)表示。對(duì)于0、1解的組合爆炸問(wèn)題，可根據(jù)粒子濾波的思想來(lái)處理。0-1非線性規(guī)劃問(wèn)題的解由粒子解組成，在各個(gè)劃分的區(qū)間內(nèi)并行執(zhí)行尋找粒子解的操作，降低了時(shí)間復(fù)雜度，尤其對(duì)求解大規(guī)模0-1非線性規(guī)劃問(wèn)題，可有效、快速地找到問(wèn)題的可行解，避免計(jì)算時(shí)間指數(shù)級(jí)增長(zhǎng)的問(wèn)題。

2.3 算法描述

算法流程圖如圖1所示。

第一步求初始可行解

圖1 粒子濾波方法流程圖Fig.1 Flow chart of particle filter algorithm

輸入：目標(biāo)函數(shù)系數(shù)c，約束矩陣A和b，粒子數(shù)num，解的長(zhǎng)度N，區(qū)間個(gè)數(shù)M

輸出：0-1非線性規(guī)劃問(wèn)題的初始可行解

For i=1 to M

1）對(duì)區(qū)間I用均勻分布unifrnd函數(shù)產(chǎn)生num個(gè)十進(jìn)制隨機(jī)數(shù)；

2）將num個(gè)隨機(jī)數(shù)的十進(jìn)制數(shù)轉(zhuǎn)換為長(zhǎng)度為Mi的二進(jìn)制串Bi；

3）把每個(gè)區(qū)間的二進(jìn)制串水平拼接到一起得到0-1線性規(guī)劃問(wèn)題的解粒子；

4）根據(jù)約束條件提取可行解粒子；

End

第二步迭代產(chǎn)生可行解

輸入：目標(biāo)函數(shù)系數(shù)c，約束矩陣A和b，初始可行解init_Feasible，可行解的個(gè)數(shù)閾值T，當(dāng)前可行解個(gè)數(shù)current-feasible-count，區(qū)間個(gè)數(shù)M，均值μi，方差σi

輸出：0-1非線性規(guī)劃問(wèn)題的次優(yōu)解或最優(yōu)解

While current_feasible_count

1）根據(jù)每個(gè)區(qū)間的μi和σi，將算法第一步中的均勻分布改為正態(tài)分布normrnd函數(shù)，運(yùn)用算法第一步產(chǎn)生當(dāng)前迭代的可行解；

2）把當(dāng)前產(chǎn)生的可行解與上一次求得的可行解垂直合并，并保證解的唯一性；

3）For i=1 to M

計(jì)算第i個(gè)區(qū)間的μi和σi；

End

4）計(jì)算當(dāng)前可行解集合中的最優(yōu)解。

3 實(shí)例求解與分析

為檢驗(yàn)算法效果，在Windows環(huán)境下，編寫(xiě)Matlab程序?qū)崿F(xiàn)求解0-1非線性規(guī)劃的粒子濾波方法，進(jìn)行大量的算例測(cè)試，并與其他算法進(jìn)行比較。以下給出幾個(gè)算例以及相關(guān)結(jié)果。

算例1 算例1結(jié)果如表1所示。

表1 算例1結(jié)果Tab.1 Result of Instance 1

通過(guò)算例測(cè)試結(jié)果證明，粒子濾波法比near optimization算法求解更準(zhǔn)確，最優(yōu)值精確到小數(shù)點(diǎn)后四位，能通過(guò)迭代逼近方式穩(wěn)定地求出最優(yōu)值及最優(yōu)解。

算例2 算例2[5]結(jié)果如表2所示。

表2 算例2結(jié)果Tab.2 Result of Instance 2

通過(guò)算例測(cè)試結(jié)果證明，粒子濾波算法可以達(dá)到枚舉法的準(zhǔn)確度，同時(shí)又比枚舉法擁有更加快速、更加穩(wěn)定的算法設(shè)計(jì)。

算例3 算例3結(jié)果如表3所示。

算例測(cè)試中所撒粒子數(shù)為5 000，依據(jù)不同的可行解數(shù)量給出如表3所示的結(jié)果。

表3 算例3結(jié)果Tab.3 Result of Instance 3

4 結(jié)語(yǔ)

根據(jù)粒子濾波的核心思想，在求解0-1非線性規(guī)劃問(wèn)題過(guò)程中可通過(guò)粒子集的分布情況判斷解的位置，不斷的迭代逼近或等于問(wèn)題的最優(yōu)解。通過(guò)算法分析和算例證明，粒子濾波算法的求解速度快，健壯性好，不受變量個(gè)數(shù)的限制。

[1]李全龍，徐曉飛，趙志家.基于熵矩陣的多目標(biāo)非線性0-1規(guī)劃近似算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2009，41（6）：118-120.

[2]陳國(guó)華，廖小蓮.0-1非線性混合整數(shù)規(guī)劃的罰函數(shù)解法[J].應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)報(bào)，2007，21（1）：112-115.

[3]張苗輝，辛 明，劉先省.基于粒子濾波的機(jī)動(dòng)目標(biāo)跟蹤改進(jìn)算法[J].系統(tǒng)工程與電子技術(shù)，2008，30（5）：949-951.

[4]張崇友，董慧穎，蘭利寶.基于粒子濾波的相關(guān)跟蹤算法研究[J].沈陽(yáng)理工大學(xué)學(xué)報(bào)，2008，27（1）：6-9.

[5]隋永康，賈志超，杜家政.非線性0-1規(guī)劃問(wèn)題的連續(xù)化及其遺傳算法解法[J].北京工業(yè)大學(xué)學(xué)報(bào)，2008，34（8）：786-790.

（責(zé)任編輯：楊媛媛）

Particle filter algorithm of solving large-scale 0-1 none linear programming

LIU Shan，WANG Wei，MA Shan-zhu
（College of Computer Science&Technology，CAUC，Tianjin 300300，China）

In order to solve large-scale 0-1 nonlinear problem，particle filter is designed and implemented.Particle filter using particle set to indicate the probability can be used in any form of state space model.The core idea is to express the random state particles extracted from the posterior probability distribution，which is a sequential importance sampling method.In solving large-scale nonlinear 0-1 programming problem，the solution is divided into M intervals，uniformly distributed random decimal number particles in each interval，the conversion of the interval length binary number is used to get the initial feasible solution，calculating the mean and variance of the initial particles feasible solution in each interval.Then normal distribution iterations are used to produce feasible solution particles，so that the particle distribution of the feasible solutions gradually approaches or is equal to 0-1 nonlinear programming and get the optimal solution.

0-1 nonelinear programming；particle filter；probability distribution

O221

：A

：1674-5590（2014）01-0057-03

2012-11-02；

：2012-11-25

大學(xué)生創(chuàng)新創(chuàng)業(yè)基金項(xiàng)目（IECAUC12061）；中國(guó)民航大學(xué)科研基金項(xiàng)目（09CAUC_106）

劉 山（1955—），男，天津人，教授，學(xué)士，研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)、民航信息處理.