大规模非线性0-1规划的粒子滤波算法

刘 山，王 巍，马山珠

（中国民航大学计算机科学与技术学院，天津 300300）

大规模非线性0-1规划的粒子滤波算法

刘 山，王 巍，马山珠

（中国民航大学计算机科学与技术学院，天津 300300）

为解区间上随机产生均匀分布的十进制数粒子，转换为该区间长度的二进制数得到初始可行解，计算初始可行解大规模0-1非线性规划求解难题，设计并实现了粒子滤波的求解方法。粒子滤波是利用粒子集来表示概率，可以用在任何形式的状态空间模型上。其核心思想是通过从后验概率中抽取的随机状态粒子来表达其分布，是一种顺序重要性采样法。在求解大规模非线性0-1规划问题时，将解划分为M个区间，计算初始可行解中每个区间的粒子的均值和方差。然后采用正态分布迭代产生可行解粒子，使可行解粒子的分布逐步逼近或等于0-1非线性规划问题的最优解。

0-1非线性规划；粒子滤波；概率分布

在科学管理和其他领域中，大量应用问题可以采用0-1规划来解决，这种规划的决策变量仅取值0或1，一个非负整数都可以用二进制记数法用若干个0-1变量表示，0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件，因此，0-1规划非常适合描述和解决如线路设计、工厂选址、生产计划安排、旅行购物、可靠性等人们所关心的多种问题。其中大部分问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划问题[1]。

目前求解0-1非线性规划问题还没有实用和有效的方法[2]，如分支限界法、隐枚举法等。本文给出的大规模0-1规划的粒子滤波求解方法，巧妙地解决了大规模问题解的表示和求解面临的组合爆炸问题，算法依据粒子滤波原理搜索可行解，能够高效准确地解决问题，为求解大规模0-1非线性规划问题开辟了一个新的研究领域，无论从实用价值和理论研究都将带来一系列新的成果和收获。

1 问题提出

考虑如下的0-1非线性规划问题

其中：x=（x1，x2，…，xn）T，f（x），gi（x），hj（x）为x的实值函数。

2 求解0-1非线性规划的粒子滤波方法

2.1 粒子滤波基本原理

粒子滤波（PF：particle filter）的思想基于蒙特卡洛方法（Monte Carlo methods）[3]，它是利用粒子集来表示概率，可以用在任何形式的状态空间模型上。粒子滤波法是指通过寻找一组在状态空间传播的随机样本对概率密度函数进行近似，以样本均值代替积分运算，从而获得状态最小方差分布的过程[4]。这里的样本即指粒子，当样本数量N→∝时可以逼近任何形式的概率密度分布。

2.2 求解方法

求解大规模0-1非线性规划粒子滤波方法的基本思路是穷尽规划问题的可行解，不是硬性搜索的简单穷举，而是按照0-1非线性规划问题可行解的基本规律搜索，最优解或可行解集中在某个区域，在此区域搜索到最优解的概率最高，即可行解粒子越集中的区域，找到0-1非线性规划问题最优解的几率就越高。

实现本方法关键要克服NP问题共有的两个难点：①当问题规模很大，解的个数很多时，如何表示问题的解；②如何避免0、1解的组合爆炸问题。设0-1非线性规划问题解的个数为N，即解的长度为N。将N分为M个等分或不等分区间，每个区间的长度表示为Mi。考虑到计算机的最大整数表示，每个区间取小于或等于16的二进制数，即216=65 536。这样无论0、1解的个数有多少，每个区间都可用小于或者等于65 535的十进制数表示。对于0、1解的组合爆炸问题，可根据粒子滤波的思想来处理。0-1非线性规划问题的解由粒子解组成，在各个划分的区间内并行执行寻找粒子解的操作，降低了时间复杂度，尤其对求解大规模0-1非线性规划问题，可有效、快速地找到问题的可行解，避免计算时间指数级增长的问题。

2.3 算法描述

算法流程图如图1所示。

第一步求初始可行解

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

输入：目标函数系数c，约束矩阵A和b，粒子数num，解的长度N，区间个数M

输出：0-1非线性规划问题的初始可行解

For i=1 to M

1）对区间I用均匀分布unifrnd函数产生num个十进制随机数；

2）将num个随机数的十进制数转换为长度为Mi的二进制串Bi；

3）把每个区间的二进制串水平拼接到一起得到0-1线性规划问题的解粒子；

4）根据约束条件提取可行解粒子；

End

第二步迭代产生可行解

输入：目标函数系数c，约束矩阵A和b，初始可行解init_Feasible，可行解的个数阈值T，当前可行解个数current-feasible-count，区间个数M，均值μi，方差σi

输出：0-1非线性规划问题的次优解或最优解

While current_feasible_count

1）根据每个区间的μi和σi，将算法第一步中的均匀分布改为正态分布normrnd函数，运用算法第一步产生当前迭代的可行解；

2）把当前产生的可行解与上一次求得的可行解垂直合并，并保证解的唯一性；

3）For i=1 to M

计算第i个区间的μi和σi；

End

4）计算当前可行解集合中的最优解。

3 实例求解与分析

为检验算法效果，在Windows环境下，编写Matlab程序实现求解0-1非线性规划的粒子滤波方法，进行大量的算例测试，并与其他算法进行比较。以下给出几个算例以及相关结果。

算例1 算例1结果如表1所示。

表1 算例1结果Tab.1 Result of Instance 1

通过算例测试结果证明，粒子滤波法比near optimization算法求解更准确，最优值精确到小数点后四位，能通过迭代逼近方式稳定地求出最优值及最优解。

算例2 算例2[5]结果如表2所示。

表2 算例2结果Tab.2 Result of Instance 2

通过算例测试结果证明，粒子滤波算法可以达到枚举法的准确度，同时又比枚举法拥有更加快速、更加稳定的算法设计。

算例3 算例3结果如表3所示。

算例测试中所撒粒子数为5 000，依据不同的可行解数量给出如表3所示的结果。

表3 算例3结果Tab.3 Result of Instance 3

4 结语

根据粒子滤波的核心思想，在求解0-1非线性规划问题过程中可通过粒子集的分布情况判断解的位置，不断的迭代逼近或等于问题的最优解。通过算法分析和算例证明，粒子滤波算法的求解速度快，健壮性好，不受变量个数的限制。

[1]李全龙，徐晓飞，赵志家.基于熵矩阵的多目标非线性0-1规划近似算法[J].哈尔滨工业大学学报，2009，41（6）：118-120.

[2]陈国华，廖小莲.0-1非线性混合整数规划的罚函数解法[J].应用数学与计算数学学报，2007，21（1）：112-115.

[3]张苗辉，辛 明，刘先省.基于粒子滤波的机动目标跟踪改进算法[J].系统工程与电子技术，2008，30（5）：949-951.

[4]张崇友，董慧颖，兰利宝.基于粒子滤波的相关跟踪算法研究[J].沈阳理工大学学报，2008，27（1）：6-9.

[5]隋永康，贾志超，杜家政.非线性0-1规划问题的连续化及其遗传算法解法[J].北京工业大学学报，2008，34（8）：786-790.

（责任编辑：杨媛媛）

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

大学生创新创业基金项目（IECAUC12061）；中国民航大学科研基金项目（09CAUC_106）

刘 山（1955—），男，天津人，教授，学士，研究方向为算法分析与设计、民航信息处理.