多智能体系统和进化计算都是多学科相融合、具有很高实用价值的研究领域，它们也已在多个领域得到了广泛的应用，但其结合是一个具有挑战性的研究课题。本文从多智能体系统和进化计算相结合的角度出发，结合数值优化、组合优化、约束满足问题、约束布局问题、组播路由问题等多个具有挑战性的实际问题进行了系统深入地研究。针对不同问题为智能体设计了不同的行为，提出了多种新的算法和实现策略，主要工作概括如下： (1) 针对数值优化问题，基于智能体对环境的感知与反作用的能力，提出了一种新的数值优化方法——多智能体遗传算法。该方法将智能体固定在网格上，而每个智能体为了增加自身能量将与其邻域展丌竞争或合作，同样智能体也可利用自身的知识进行自学习来增加能量。从理论上证明了其具有全局收敛性。实验中用10个20～10 000维的标准测试函数对算法性能进行了测试。对上万维的函数，算法都能快速找到高智能量的解，充分显示了算法具有收敛速度快，不易陷入局部极值的优越性能。 (2) 针对连续域优化问题，提出了一种在进化算法中自适应伸缩搜索空间的方法，可有效求解实际问题中无法得知全局最优解所在区间上下界有关信息的问题。并将此方法与多智能体遗传算法相结合，提出了用于线性系统逼近的多智能体遗传算法，用稳定线性系统逼近问题和不稳定线性系统逼近问题对算法性能进行了测试验证。 (3) 针对可分解的函数优化问题，提出了一种宏智能体进化模型。并将其与多智能体遗传算法相结合，提出了层次多智能体遗传算法，证明了其全局收敛性。求解了高达50 000维的Rosenbrock函数，表现出了优越的性能。 (4) 针对组合优化问题，提出了组合优化多智能体进化算法，证明了其全局收敛性。实验中用强联接、弱联接、重叠联接等各种类型的欺骗问题和具有树状等级结构的问题对算法性能进行了全面测试，并用上千维的函数研究了算法求解大规模问题的计算复杂度。 (5) 针对约束满足问题，提出了约束满足智能体进化算法。该方法根据约束满足问题的特点，设计了智能体的竞争行为与自学习行为。为了克服已有编码方式的缺点，为智能体设计了最小冲突编码。对算法的空间复杂度和收敛性进行了理论分析。实验中首先用250个不同难度的标准二元约束满足问题对算法的两个参摘要数进行了系统分析。确定了其取值范围，便于读者应用。然后用104一107个皇后的问题对算法的时间复杂度进行了研究。 (6)针对两个实际问题—约束布局优化问题和组播路由问题，提出了用多智能体进化方式求解的方法。在争束布局优化问题中，分别用5个、7个和40个待布圆问题验证了算法性能。在组播路由问题中，针对进化算法求解时延受限组播路由问题出现的搜索空间过大的问题，提出了离散域中搜索空间动态扩展的方法。借鉴自组织临界现象，为智能体设计了自组织临界行为。实验中分析了算法随目的节点数和网络节点数增长的性能变化。结果表明该算法具有搜索能力强、收敛速度快的优点，同时具有良好的扩展性。关键词:进化算法 近问题多智能体系统数值优化搜索空间动态扩展可分解函数优化问题欺骗问题等级问题 线性系统逼约束满足问题n一皇后问题最小冲突编码约束布局优化问题组播路由问题自组织临界现象西安电子科技大学博士学位论文