【作者】 钟伟才；

【导师】 焦李成；

【作者基本信息】 西安电子科技大学 ， 模式识别与智能系统， 2004， 博士

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

【Abstract】 Multiagent systems and evolutionary computation are two valuable fields in practical applications. Although they have been widely used in many fields, a little research has been made to integrate them together. This thesis is focused on integrating multi-agent systems and evolutionary computation together to overcome their disadvantages, and form high efficient new algorithms. Systematic researches have been made along numerical optimization, combinatorial optimization, constraint satisfaction problems, constrained layout optimization, and multicast routing problems. Different behaviors are designed for agents and different methods are proposed to deal different problems, and can be summarized as follows:(1) Based on the ability of agents in sensing and acting on the environment, a new method, multiagent genetic algorithm, is proposed for the global numerical optimization. In this method, all agents live in a latticelike environment, with each agent fixed on a lattice-point. In order to increase energies, they compete or cooperate with their neighbors, and they can also use knowledge. Theoretical analyses show that it converges to the global optimum. In the experiments, 10 benchmark functions with 20~10 000 dimensions are used to validate the performance. The results show that even when the dimensions increase to as high as 10 000, it still can find high quality solutions at a low computational cost. Therefore, the method has a good scalability and is a competent algorithm for solving high dimensional optimization problems.(2) Genetic algorithms strongly depend on the lower and upper bounds for numerical optimization, which is inconvenient to practical applications. To cure this problem, we propose a search space expansion scheme. Then, this scheme is combined with multiagent genetic algorithm to form a new method to the problem of approximation of linear systems. A stable linear system and an unstable linear system are used to test its performance, with a satisfactory result obtained.(3) For decomposable functions, a macro-agent evolutionary model is proposed. Then, it is combined with multiagent genetic algorithm to form a new method, hierarchical multiagent genetic algorithm. In the experiments, for the Rosenbrock function, even when the dimension increases to 50 000, it can still find high quality solutions with a low computational cost.(4) For combinatorial optimization, a new algorithm, multiagent evolutionary algorithm for combinatorial optimization, is proposed. Theoretical analyses show that it converges to the global optimum. In the experiments, various deceptive problems, such as the ones with strong-linkage, weak-linkage and overlapping-linkage, and hierarchical problems are used to validate the performance. In order to test its performance on solving large-scale problems, it is used to solve deceptive problems and hierarchical problems with thousands of dimensions, and the computational complexity is analyzed. All results show that it has a low computational cost and obtains a good performance.(5) With the intrinsic properties of constraint satisfaction problems (CSPs) in mind, several behaviors are designed for agents. These behaviors are controlled by means of evolution, so that multiagent evolutionary algorithm for constraint satisfaction problems results. To overcome the disadvantages of the general encoding methods, the minimum conflict encoding is also proposed. Theoretical analyses show that the method has a linear space complexity and converges to the global optimum. The first part of the experiments uses 250 benchmark binary CSPs to analyze the effect of the parameters. The second part of the experiments uses w-queen problems to test the performance. The method achieves a good performance when n increases from 10~4 to 10~7.(6) For two practical cases, constrained layout optimization and multicast routing problems, the solving way by multiagent evolutionary algorithms are proposed. For constrained layout optimization, the problems with 5, 7, and 40 circles are used to test t更多还原