蚁群优化算法是一种基于自然启发的metaheuristic算法,从其提出到现在历经10多年的发展到目前已经成为一种解决组合优化问题的有效工具。最大团问题是一个经典的NP难的组合优化问题,很多实际问题都可以抽象为对无向图上最大团问题的求解,所以,对最大团问题的研究无论在理论上还是实际上都有重要意义。鉴于此,本文对蚁群优化算法解决最大团问题的能力进行了研究,提出一个解决最大团问题的intensification和diversification平衡协作的蚁群优化算法。并且应用这个算法改进解决多序列比对问题的progressvie算法。本文首先简要介绍了解决最大团问题常用的metaheuristic方法,并对最大团问题进行描述。然后详细介绍了解决最大团问题的两个机制类似的metaheuristic方法:迄今为止性能最好的遗传算法—EA/G算法和现存的简单的蚁群优化算法。接着,对解决最大团问题现存的简单的蚁群优化算法进行分析,指出它存在的不足,从而在此基础上提出一个改进的蚁群优化算法,并对该算法的intensification和diversification机制进行了分析。此外还利用DIMACS提供的最大团问题的基准实例,对改进的蚁群优化算法的性能进行了测试,实验结果表明,该算法的性能不仅超过了简单的蚁群优化算法,还超过了与其机制类似的迄今为止性能最好的遗传算法—EA/G算法。最后,本文对改进的蚁群优化算法在多序列比对问题上的应用进行了研究,采取分治思想改进现有的progressive算法,提出利用最长公共子序列进行多序列分割的策略,并给出怎样利用解决最大团问题的蚁群优化算法求解多序列的最长公共子序列的方法。此外,通过实验说明了这种改进思想的有效性。