| 遗传算法在消圈问题中的应用 |
| |
| 引用本文： | 刘淋.遗传算法在消圈问题中的应用[J].黄冈师范学院学报,2013(6):18-21. |
| |
| 作者姓名： | 刘淋 |
| |
| 作者单位： | 福建船政交通职业学院,福建福州350007 |
| |
| 基金项目： | 福建省交通运输建设科技项目（201330）. |
| |
| 摘 要： | 利用遗传算法实现对图论中无向图的消圈。将无向图转化为二进制的染色体个体，对于出现圈的图，算法巧妙地采用关联矩阵列向量线性相关性进行判断，对含有圈的个体进行惩罚使其进入下一代的概率微小，促使算法能较快的收敛。算法在设计过程中，进行多种遗传机制的测试，在遗传的控制参数上也都适当进行调整，使其达到较为满意的结果。将该算法应用测试后表明，算法能够有效进行消圈，并输出最优解。在交通规划的实际问题中，能很好地体现其优势。
|
| 关 键 词： | 遗传算法 无向图 消圈 |
Application of genetic algorithm in graphic de-cycling circle |
| |
| LIU Lin.Application of genetic algorithm in graphic de-cycling circle[J].Journal of Huanggang Normal University,2013(6):18-21. |
| |
| Authors: | LIU Lin |
| |
| Institution: | LIU Lin (Fujian Chuanzhen Communication Vocational College, Fuzhou 350007, Fujian, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | genetic algorithm undirected graph de-cycling circle |
| 本文献已被 维普 等数据库收录！ |
