组合优化是针对离散变量,在给定有限集的所有满足约束条件的子集中,按某种优化目标找出一个最优子集,如寻找离散事件的最优编排、分组、排序或筛选等,所研究的问题涉及系统控制、人工智能、生产调度、交通运输、网络通信、计算生物学等众多领域。作为一个应用广泛、实用性强的学科分支,组合优化理论和算法已成为许多学者和工程技术人员的研究课题。鉴于实际组合优化问题的复杂性、约束性、非线性、多极小和建模困难等特点,传统的数学规划方法(如线性规划、整数规划、非线性规划、动态规划、网络流等)在应用过程中受到了很大的限制。因此,寻求适用于大规模组合优化问题且具有智能特征的优化算法成为相关学科的主要研究方向。本文从系统的观点出发,在分析组合优化解的微观特征和解空间结构的基础上,分别从复杂系统和进化计算两个角度研究了基于极值动力学的自组织优化算法,并将其应用于微阵列基因排序和热轧带钢轧制单元调度等工程优化问题。具体的,本文在以下几个方面进行了研究:基于分散控制的思想,提出了局部适应度函数的概念来评价组成整体解的单个决策变量的优化状态,并讨论了局部适应度函数与全局适应度函数的一致性和等价性条件;在定义离散状态变量和局部适应度的基础上,文中通过统计分析的方法考察了组合优化问题状态变量间的耦合关系和优化解的微观特征;考虑到当前计算复杂性理论主要是基于最坏情形分析和平均情形分析,引入了NP-complete问题的典型情形计算复杂性的相变分析方法,并分别从计算复杂性相变和解空间相变两个方面进行了研究;最后,结合邻域定义方法,首次提出了适应度网络的概念,用于分析组合优化问题的解空间结构。鉴于组合优化与物理系统的相似性,文中首先引入了解释无序的、非线性复杂系统的自组织临界性理论,通过沙堆模型论述了系统自组织行为模式的特征,并深入研究了基于极值动力学的Bak-Sneppen模型的自组织演化过程。借鉴基于极值动力学的自组织模型和极值优化算法,提出了一种新的基于极值动力学的自组织优化算法,从搜索深度和搜索广度两个方面研究了算法参数对优化性能的影响,并从优化控制的角度分析了该算法非线性的动态优化过程。最后,通过与相关优化算法的比较分析以及针对TSP问题的仿真结果论证了该算法的有效性。针对现有的进化算法在理论基础、局部搜索能力和计算复杂性等方面的问题,引入了基因进化、协同进化和自组织进化理论,提出一种新的针对基因(对应组合优化解中分量的特征或值)层次的自组织进化算法。该算法实现了进化理论中的两个秩序源-自组织和自然选择的高度融合,和遗传算法相比体现出良好的优化性能和求解效率。随着以全面研究所有基因功能为中心的功能基因组学的发展,可同时检测成千上万个基因的微阵列技术得到广泛的应用。因此,如何处理微阵列技术在基因表达分析等应用过程中产生大量的数据、并从中提取出有价值的生物学信息成为极为重要的问题。文中针对近几年计算生物学中出现的微阵列基因排序问题,建立了合理的优化目标函数,并提出一种自组织的微阵列基因排序算法。不同数据集下的计算结果验证了该算法的有效性,可广泛应用于微阵列基因数据的分析。热轧带钢生产作为钢铁制造过程中的关键工序之一,对整个钢铁工业的技术进步和经济效益有着重要影响。因而,热轧生产调度问题也成为国际钢铁企业和学术界关注的热点问题。实现热连轧生产线的优化生产调度,可以有效地提高生产效益、降低生产成本、改善产品质量和客户服务水平。文中考虑热轧带钢生产流程和工艺约束,建立了热轧带钢轧制单元调度优化模型,同时考虑了两个方面的问题(1)定单选择:从生产定单中选定计划在当前轧制单元中生产的定单;(2)轧制单元内定单排序:根据定单(热轧板坯对应的钢卷)的宽度、厚度、硬度、温度跳变以及交货期来确定轧制序列;鉴于其为NP-hard问题,文中分别提出了基于遗传算法的轧制单元搜索算法和基于自组织优化的轧制单元优化算法,并设计了一种有效的混合进化算法;在开发的热轧调度系统上对实际生产数据的仿真结果表明了该调度方案的有效性和可行性。