基于遗传算法的多约束网格检查对策问题研究

Genetic Algorithm Based Research on the Problem of Inspection Games on a Lattice under the Constraints of Multiple Factors

综合考虑物品数量以及列容量约束,将隐藏成本与检查概率引入支付函数.建立一种新的多约束的网格检查对策模型.根据矩阵对策性质及Holder不等式,将对策论问题转化为非线性整数规划问题.提出一个基于遗传算法的模型求解方法,将归一化处理得到的变量进行二进制编码,通过数据变换将问题转化为无约束问题,采用轮盘赌选择、多点交叉及单点变异操作求解模型.仿真结果表明了模型及所提算法的有效性.

Considering the constraints such as the quantities of objects and the capacity of each column,and introducing hidden costs and the inspection probability into the payoff function,the inspection game model on a lattice under the constraints of multiple factors was established.According to properties of the matrix game and Holder inequality,the game theory problem was transformed into a nonlinear integer programming problem.A genetic algorithm based method of solving the model was proposed,in which a binary encoding method for variables after normalization processing was designed and the problem was transferred to an unconstrained one through data transformation,and thus the roulette wheel selection method,multi-point crossover and single point mutation can be used to solve the model.The simulation results showed the effectiveness of the model and the proposed algorithm.