随着进化计算的快速发展,进化计算越来越广泛地应用于多目标函数优化、工程设计、非线性多目标寻优等大规模复杂问题的求解中。极值图论是图论的重要研究分支,主要研究满足某个给定条件下的最大图或最小图的极值问题。极图构造算法作为极图理论的一个重要研究内容,越来越受到研究者们的关注。但是利用计算机算法构造极图又是非常困难的,特别是在顶点数规模不断增大的情况下会出现组合爆炸的现象。因此,研究进化算法在极图构造中的应用具有十分重要的理论意义和实用价值。首先,根据极图问题的定义建立规划模型,以便于利用该模型构造相应的极图。在传统遗传进化算法的基础上,通过添加自适应机制和快速进化操作,提出了一种基于自适应遗传算法的给定围长图的构造算法ConstructEG_GA。还提出了一种离散映射机制使得标准粒子群进化算法能够求解离散优化问题,并在此基础上设计了一种基于离散粒子群进化算法的给定围长图的构造算法ConstructEG_PSO。然后,针对传统的量子进化算法在算法进化过程中存在旋转角步长单一的问题,提出了一种自适应的旋转角步长的调整机制,并在此基础上设计基于自适应量子进化的给定围长的图的构造算法ConstructEG_QEA。通过在进化过程中添加扰动操作和挑选对称性较好的图进入下一代进化等措施,使得算法可以快速跳出局部最优解,以加快算法的收敛速度。最后,通过构造顶点数为n(44 ≤ n ≤ 48)围长为10的图,对算法ConstructEG__GA、ConstructEG_PSO 和 ConstructEG_QEA 进行了对比实验。实验结果表明,算法ConstructEG_QEA在求解问题的次优解和最优解的准确率上要明显优于ConstructEG__GA和ConstructEG__PSO算法。还通过构造顶点数为n(21 ≤ n≤ 30)围长为11的图分析了算法ConstructEG_QEA的收敛速度,结果表明算法可以在很短的时间内达到最优解。最后,利用该算法构造出顶点数为n(31≤n≤89)围长为11的图,从而给出了相应的ex(n;11)的下界。