基于改进的遗传算法的多目标优化问题研究

研究多目标优化算法问题,针对传统的多目标优化算法由于计算复杂度非常高,难以获得令人满意的解等问题,在图论和遗传算法基础上,提出了一种改进的遗传算法求解多目标优化方法。首先采用二进制编码表示最小树问题,然后采用深度优先搜索算法进行图的连通性判断,给出了一种新的适应度函数,以提高算法执行速度和进化效率。最后仿真结果表明,与经典的Prim算法和Kruskal算法相比,新算法复杂度较低,并能在第一次遗传进化过程中获得一批最小生成树,适合于解决不同类型的多目标最小树问题。

Multi- objective Minimum Spanning Tree Algorithms Based on Genetic Algorithms

Solve the problem of minimum spanning tree.The traditional algorithm for solving multi-objective minimum spanning tree problem is of high computational complexity,and difficult to obtain satisfactory solutions.Based on graph theory and genetic algorithm,a improved genetic algorithm was proposed based on multi-objective minimum spanning tree methods.The algorithm used binary code to express minimum trees,and then used depth-first search algorithm to determine the connectivity of the graph.A new fitness function was given to improve the algorithm execution speed and evolutionary efficiency.The simulation results show that compared with the classical Prim algorithm and Kruskal algorithm,the new algorithm is of low complexity,can obtain the minimum spanning tree in the first genetic evolution process,and is suitable for solving different types of problems of multi-objective minimum trees.