刘 山,王 巍,马山珠
(中国民航大学计算机科学与技术学院,天津 300300)
大规模非线性0-1规划的粒子滤波算法
刘 山,王 巍,马山珠
(中国民航大学计算机科学与技术学院,天津 300300)
为解区间上随机产生均匀分布的十进制数粒子,转换为该区间长度的二进制数得到初始可行解,计算初始可行解大规模0-1非线性规划求解难题,设计并实现了粒子滤波的求解方法。粒子滤波是利用粒子集来表示概率,可以用在任何形式的状态空间模型上。其核心思想是通过从后验概率中抽取的随机状态粒子来表达其分布,是一种顺序重要性采样法。在求解大规模非线性0-1规划问题时,将解划分为M个区间,计算初始可行解中每个区间的粒子的均值和方差。然后采用正态分布迭代产生可行解粒子,使可行解粒子的分布逐步逼近或等于0-1非线性规划问题的最优解。
0-1非线性规划;粒子滤波;概率分布
在科学管理和其他领域中,大量应用问题可以采用0-1规划来解决,这种规划的决策变量仅取值0或1,一个非负整数都可以用二进制记数法用若干个0-1变量表示,0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件,因此,0-1规划非常适合描述和解决如线路设计、工厂选址、生产计划安排、旅行购物、可靠性等人们所关心的多种问题。其中大部分问题,其目标函数和(或)约束条件很难用线性函数表达。如果目标函数和(或)约束条件中包含有自变量的非线性函数,则这样的规划问题就属于非线性规划问题[1]。……