混合整数规划问题遗传算法的研究及仿真实现

A Mixed Integer Genetic Algorithms for Solving the Mixed Integer Programming Problems and Simulation Implementing

提出了一种可以处理混合整数规划问题(MIP)的混合遗传算法MIGA。该算法采用二进制映射模式可变长度染色体编码,在进化过程逐渐缩小编码的搜索空间,从而在加快收敛速度的同时改善了迭代的精度,能很好处理离散变量和连续变量的混合整数规划问题。以一纯整数规划问题为例,利用分枝定界算法只能得到唯一的一个最优调度策略,而MIGA算法则可以得到一系列的最优调度策略,对这些最优调度策略进一步的分析,还可以得到调度问题一些灵敏度参数,在实际应用中具有更大的灵活性。

In this paper, a Mixed Integer Genetic Algorithm (MIGA) is presented for solving the mixed integer programming (MIP) problems. Encoding the discrete and continue variables as a changeable genome based on binary map mode, the MIGA can reduce the search space by shorten the chromosome length in the process of population evolving, so it can get rapid convergence speed and more highly precision. Specially, to an integer programming formulation, the MIGA can get a series of optimal scheduling solutions, whereas the branch-and-bound algorithm can only get an optimal solution. By analyzing the optimal scheduling solutions gotten from the MIGA algorithm, we can also get some inspiring results about the sensitivity of formulation parameters.