摘要
利用遗传算法实现对图论中无向图的消圈。将无向图转化为二进制的染色体个体,对于出现圈的图,算法巧妙地采用关联矩阵列向量线性相关性进行判断,对含有圈的个体进行惩罚使其进入下一代的概率微小,促使算法能较快的收敛。算法在设计过程中,进行多种遗传机制的测试,在遗传的控制参数上也都适当进行调整,使其达到较为满意的结果。将该算法应用测试后表明,算法能够有效进行消圈,并输出最优解。在交通规划的实际问题中,能很好地体现其优势。
We introduce a new method de-cycling circles in an undirected graph through genetic algorithm. The method transforms an undirected graph into chromosomes of binary code. The algorithm not only uses linearly dependent column vector in incident matrix to make judgment on whether or not a graph has any circles, but also punishes the graph with circle by minimizing its chance entering into the next generation, which promotes the algorithm＇s convergence process as quickly as possible. The algorithm can reach satisfied results through the test of different kinds of genetic mechanisms and the proper adjustment on genetic control parameter. The test in different kinds of graphs shows that the discussed algo- rithm can de-cycle circles effectively, produce the optimized solution, and play an efficient roll in traffic-planning.
出处
《黄冈师范学院学报》
2013年第6期18-21,共4页
Journal of Huanggang Normal University
基金
福建省交通运输建设科技项目(201330)
关键词
遗传算法
无向图
消圈
genetic algorithm
undirected graph
de-cycling circle
