组合优化作为一类重要的优化问题,其涉及的领域甚为广泛,如信息技术领域、工业工程领域、交通运输领域以及经济管理领域。因此对组合优化问题的研究具有非常重要的实际意义。随着人工智能的发展,从上世纪80年代开始,进化算法逐渐成为求解组合优化问题的重要手段,在诸多领域得到了广泛的应用。在使用进化算法等智能优化算法求解组合优化问题的研究中,问题的表示方式在很大程度上决定了搜索空间的大小与形态,从而决定了问题的难度、影响着优化算法的性能。因此,本文以求解组合优化问题为核心目的,围绕组合优化问题的表示方式和单目标、多任务以及多目标进化优化算法两方面展开研究。主要工作可概括如下:1.针对约束满足问题设计了直接和间接混合的表示方式,进而基于混合表示方式设计了相应的多智能体进化算法。混合表示方式结合了直接表示方式操作简单、易于评价的优点和间接表示方式能解码生成质量较好的解的优点。另外针对问题特性和混合表示方式设计了邻域交叉算子、变异算子以及自学习算子等多智能体进化算法中智能体的若干行为。在250个标准二元约束满足问题测试集和79个图染色问题测试集上验证了所设计的基于混合表示方式的多智能体进化算法,实验结果表明了基于混合表示方式的多智能体进化算法相对于基于直接或者间接表示方式的多智能体进化算法具有更好的求解效率。2.针对资源受限项目调度问题设计了新的表示方式——移动模式序列。移动模式序列由模块序列和移动模式两部分组成。模块即为项目中的活动,每个活动的工期可以看作是模块的长,而对资源的需求量可以看作是模块的宽。针对模块设计了四种初始位置和对应的移动模式,解码过程即为依次将每个模块从其初始位置按照对应的移动模式移动到合适的位置。基于移动模式序列表示方式,设计了求解资源受限项目调度问题的多智能体进化算法。针对问题特性和移动模式序列表示方式设计了邻域交叉算子、变异算子、向前-向后抖动算子以及自学习算子等智能体的行为,并在资源受限项目调度问题标准测试集J30、J60、J90和J120上验证了基于移动模式序列表示方式的多智能体进化算法的性能。实验结果表明,基于移动模式序列的多智能体进化算法具有良好的求解性能,尤其是在求解大规模测试集上表现出了优秀的求解效率。3.设计了一种新的超启发式框架——面向进化多任务的图超启发式优化框架,并在考试时间表问题和图染色问题上验证了该框架的性能。超启发式作为选择或者生成启发式规则的一类算法具有良好的通用性,但目前的研究主要局限在针对单个优化任务。进化多任务优化的特点是可以同时优化多个任务,且对任务之间的关系无特殊要求。进化多任务优化通过统一表示方式将不同任务的解映射到同一个空间内,在该空间使用优化算法进行优化之后,再转换回各任务的搜索空间进行评价。进化多任务优化不仅具有跨领域的搜索能力,而且具有知识迁移的能力。面向进化多任务的图超启发式框架首次将进化多任务的概念引入超启发式算法,使得超启发式具有了知识迁移的能力,进一步提高了超启发式的通用性。同时,该框架将进化多任务优化中的统一表示方式扩展到了更高级别的启发式搜索空间,进一步拓展了进化多任务优化的通用性。在包含2、3、4、5个任务的多任务优化问题上的实验结果表明,该超启发式框架具有良好的求解效率、异步优化能力、跨领域搜索能力以及鲁棒性。4.针对“新高改”的高中“走班”排课问题设计了新的问题模型,填补了目前国内“新高改”下的高中“走班”排课问题模型的空白。该问题模型的主要特点为引入了“走班”排课,基于此设计了包含“走班”和行政班两部分课表的问题的表示方式,并使用两阶段模拟退火对该模型进行求解。首先在45个不同规模的人工生成数据集上测试了所设计的表示方式和两阶段模拟退火算法的有效性,并对算法的收敛性进行了分析。之后在10所高中的真实排课数据上进一步验证了所设计的问题模型的适用性和问题的表示方式以及两阶段模拟退火算法的有效性。5.首先验证了使用全局替换策略的基于分解的多目标进化算法在求解多目标背包问题上的性能,并分析了不同参考点的选取对算法性能的影响。之后,针对将乌托邦点作为参考点时全局替换策略将失效的问题,设计了一种改进的全局替换策略。在一组最多包含8个目标的多目标背包问题测试集上的实验结果表明,改进的全局替换策略能更好地对边界子问题对应的解进行更新,从而更好地保持种群的多样性。