基于熵矩阵的多目标非线性0-1规划近似算法

为了简化多目标二元匹配问题的求解,将该问题建模为多目标非线性0-1规划模型,该模型将变量约束转移到目标函数中,从而降低了问题求解难度.针对该模型,设计了基于熵矩阵计算的贪心近似算法,该算法通过熵矩阵的熵值计算确定多目标二元匹配度,并根据熵值的大小预先优化匹配顺序,从而使近似解更快速地接近最优解.仿真实验结果证明,对于单目标非线性0-1规划问题,本算法优于已有的近似算法,对于多目标非线性0-1规划问题,本算法在计算时间以问题规模的指数级减少的情况下,近似解能够很好地逼近最优解.因此,本算法与其它近似算法相比,在不增加时间复杂度的前提下,结果更优,近似度更高.

Approximation algorithm for multi-criterion nonlinear 0-1 programming based on entropy matrix

In order to simplify the solving of two-class matching problem under multiple criterions,a model of multi-criterion nonlinear 0-1 programming is established,in which constraints on variables are transferred to objective function to reduce the difficulty in solving the problem. A greedy approximate algorithm based on entropy matrix computing is designed to solve this nonlinear 0-1 programming model more efficiently. By calculating the value of entropy which indicates the matching degree of two types of objects,the algorithm can optimize the scheduling matching sequence,then the solution calculated by the algorithm can approximate the optimal solution more quickly. Simulation results show that the algorithm proposed in this paper is superior to other approximate algorithms for solving single-criterion nonlinear 0-1 programming problem. For multi-criterion nonlinear 0-1 programming problem,the approximate solution given by this algorithm is more close to the optimal solution while the computing time is decreased exponentially.