利用多群体DNA遗传算法求解线性规划问题  

Using DNA Genetic Algorithm With Multi-Population to Solve Linear Programming

作　　者：崔志华[1] 曾建潮[1] 

机构地区：[1]太原重型机械学院系统仿真与计算机应用研究所,山西太原030024

出　　处：《系统工程与电子技术》2002年第3期104-107,共4页Systems Engineering and Electronics

摘　　要：针对经典遗传算法存在的问题 ,提出了多群体DNA遗传算法。该方法在经典遗传算法的基础上 ,通过借鉴生物学及社会学 ,引入了多群体及DNA片断等概念 ,并提出迁移与自适应变异算法 ,可以提高遗传算法的有效性与收敛性。为了验证算法的有效性 ,将该算法应用于线性规划问题的求解。在求解过程中 ,首先利用熵障碍对偶方法对原问题进行转换 ,然后使用多群体DNA遗传算法对转换后的目标函数进行求解。仿真结果表明 ,该方法具有良好的全局搜索能力和较快的收敛速度。以上工作为解决大规模线性规划问题的求解提供了全新的思路和方法 。DNA genetic algorithm with multi-population is presented for overcoming the slow and premature convergence of the classic genetic algorithm. In order to enhance the validity and convergence of the genetic algorithm, the concepts such as multi-population and DNA fraction are introduced by learning from biology and sociology, and the migration and mutation operators are also proposed. To prove its validity, the algorithm is used to solve the linear programming. At first, the problem is translated by using entropic perturbation,then DNA genetic algorithm with multi-population is used to solve the above problem, thus the result is obtained. The optimization computing of some examples is made to show that the new genetic algorithm has a better global search capability and rapid convergence rate. The above work provides a new idea and method for solving large-scope linear programming and contributes much to further application of genetic algorithm.

关 键 词：遗传算法 多群体DNA 线性规划 熵障碍对偶法 

分 类 号：O221.1[理学—运筹学与控制论]