最大独立集问题是图论中的经典组合优化问题。已被证明是NP完备的，具有较高的计算复杂性。本文从最大独立集问题的应用背景、界的估计、求解的难点以及现代优化算法的设计等方面综述了国内外专家学者对此问题的研究成果。 在此基础上，本文首先给出并证明了独立数的一个上界，然后通过分析最大独立集元素的构成特点，综合现代启发式算法，提出了一种新的具有多项式时间的算法——非邻域贪婪算法，并依此算法过程证明了独立数的一个下界。然后详细介绍了解决最大团问题的性能最好的遗传算法——EA/G算法，接着对此算法进行分析，指出它存在的不足，从而在此基础上提出自学习进化算法。此外，还利用DIMACS提供的benchmark基准图，对非邻域贪婪算法和自学习进化算法的性能进行了测试，实验结果表明，非邻域贪婪算法产生的极大独立集的性能较好，而自学习进化算法产生的最大独立集的性能较好。在适当地选取参数后，自学习进化算法能够求解得到绝大多数基准图的最优解，充分表明了该算法的有效性。