求解固定费用运输问题的遗传算法

摘要：

为克服基于边集编码的遗传算法求解固定费用运输问题的不足,对采用先根遍历边构成有序边集编码的生成树,提出了森林补充式多点交叉操作的遗传算法.经证明,对于有m个源节点和n个目的节点的固定费用运输问题,该算法的空间复杂度为O((m+n-1)2),时间复杂度为Oβ(m+n-1)3),β为最大迭代次数.实验数据表明,随着问题规模和求解难度的增加,该算法与边集编码的遗传算法解的质量都呈下降趋势,但所得解的质量优于边集编码的遗传算法.

关键词：固定费用运输问题、遗传算法、有序边集编码、先根遍历、多点交叉、生成树

所属期刊栏目：29

分类号：TP301.6(计算技术、计算机技术)

资助基金：甘肃省自然科学基金3ZS051-A25-037;辽宁工程技术大学青年科研基金07A205

在线出版日期：2008-05-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1777-1779,1846