中南大学计算机学院、生物信息学湖南省重点实验室与澳大利亚阿德莱德大学计算机系优化与逻辑学实验室展开深入合作，在进化算法设计与理论分析领域取得重要研究成果。该研究成果以“Time Complexity Analysis of Evolutionary Algorithms for 2-hop (1,2)-Minimum Spanning Tree Problem”为题，在理论计算机科学领域国际主流期刊《Theoretical Computer Science》以论文形式在线发表。
最小生成树问题是图论领域的一个经典问题，其虽是多项式时间可解，但是与其相关的若干变形却被证明为NP-难解，例如从通信网络构造领域衍生出来的k-跳最小生成树问题。该研究针对2-跳最小生成树问题（即k=2时）的一个特殊变种：限定给定图为完全图且图中边上的权值仅为1或2（该变种已被证明为NP-难解），进行了分析并设计了多个进化算法（包括单目标进化算法和多目标进化算法）。基于对图结构的深入研究，该研究分析了各个进化算法为获取近似比为3/2的近似解所需的期望时间复杂度，证明了通过有效定义个体之间的支配关系，多目标进化算法相较于经典的局部搜索技术在获取该问题近似比为3/2的近似解方面表现出更好的时间复杂度和运行效率，进一步挖掘了进化算法在求解某些组合优化问题的潜能。
王建新教授团队长期致力于计算机算法与优化、生物信息学、医学影像分析等方面研究。该研究工作得到国家自然科学基金等基金支持。