网络最小费用最大流双目标遗传优化算法

Bi-objective optimization of network min-cost and max-flow based on genetic algorithm

针对将网络最小费用最大流问题转化为单目标优化问题进行求解的缺陷,提出网络最小费用最大流的双目标优化模型,并引入多目标遗传算法.对最小支撑树对应的余树弦流量初始值进行编码,通过解码和回路矩阵计算流量网络树枝的流量.在网络最小费用、最大流量双目标函数和网络结点容量、网络分支容量约束条件基础上,按照多目标优化理论构建增广最小化双目标函数,依此对网络流量方案编码进行评价.使用进化算子对网络流量方案编码实施进化操作,最后通过迭代得到满意解.以矿井通风网络为例进行了测试.结果表明:网络最小费用最大流双目标遗传算法是完全可行和有效的.该算法减少了最优化模型中变量数目、提高了运算效率.

Aimed at the defect of transfering network min-cost and max-flow to single objective optimiza tion, the bi-objective optimization model of network min-cost and max-flow was proposed, and multi-objective genetic algorithm was adopted. The flow values of remain branches were encoded and initialized by multi-objective genetic algorithm, and the flow values of tree branches were calculated by decoding and circuit matrix. Based on network rain-cost and max-flow function, nodes capacity and branches ca- pacity restrictions, the generalized bi-objective function were set up according to multi-objective optimization theory. The flow scheme codes were evaluated by the generalized bi-objective function and evolved by evolution arithmetic operators to obtain optimization rain-cost and max-flow schemes by iterative algo- rithm. Mine ventilation network was taken as example to conduct the test. The results show that the bi objective genetic algorithm of network min-cost and max-flow is feasible and effective. The variable number is reduced in this algorithm and algorithm efficiency is improved.