基于协同机制和智能算法的多代理系统研究及应用

论文摘要

在经济计划、工程设计、生产制造、数据存储、信息安全等领域存在着大量的分配调度问题,即在众多可行的决策方案中寻求最佳的分配调度方案。有效解决这些问题不仅具有重要的社会意义,而且也能产生巨大的经济效益。任务分配、资源分配、生产调度是计算机研究领域的一些经典问题,其中有许多问题尚未彻底解决,对它们进行研究具有重要的理论意义和实际应用价值。而随着先进制造技术的发展,实际的分配调度问题变得越来越复杂,这使得传统的分配调度方法越发显得无能为力,因此,亟待寻求面向复杂问题的新的分配调度方法。Agent和多Agent系统（multi-agent systems,MAS）已经成为人工智能研究实用化和分布式计算环境下软件智能化的重要技术。不同于传统算法在设计时需要对问题有全面的分析,Agent能够模拟人类的行为,只需指定Agent的目标,它们就可以彼此互动,进而实现用户的最终意图,因此Agent具有普适化、网络化、智能化、代理化、人性化等计算技术的特性。对于大型分布式问题,通过建立MAS可以使计算机系统变得更加智能化,代替更多人类的工作,促进计算机技术的不断繁荣。MAS区别于其他计算模式的关键所在,就是它具有协同机制这一优秀特性。近年来,由于对市场经济以及社会系统某些现象的深入观察,人们提出了一些新的、模拟这些现象的协同机制。这些协同机制对于各类复杂的分配调度问题具有很强的适应性、鲁棒性和并行性,因此得到了广大学者的普遍关注。另一方面,以智能计算为代表的仿生智能算法通常对解决各类复杂优化问题具有很强的针对性和实效性,并被广泛地应用于科学研究和工业生产等众多领域。本文基于协同机制和智能算法的MAS,对任务分配、资源分配和生产调度等问题进行了较为深入的研究,提出了一些分配调度算法和模型,并通过大量的实验对算法和模型的性能进行了验证。实验结果表明,本文提出的算法和模型不仅能够有效地提高分配调度效率,降低资源损耗,而且对克服算法过早收敛,也具有十分明显的效果。主要研究内容如下:1、以入侵检测任务分配问题为研究对象,建立了一种基于合同网协议（contract net protocol,CNP）与免疫机理（immune mechanism,IM）的多Agent入侵检测模型。提出了一种改进的资源可用度的任务分配策略,用于一般入侵检测任务的有效分配;在被动免疫抗体PAb（passive immune antibody）、记忆自动免疫抗体MANAb（memory automatic immune antibody）及模糊自动免疫抗体FANAb（fuzzy automatic immune antibody）的基础上,将CNP（contract net protocol）协同机制应用到抗体检测中,提出了联合免疫抗体UAb（unite immune antibody）的概念,利用UAb具有共享Agent间分析经验的特性,解决了超复杂入侵检测任务的分配问题。实验结果表明,该模型具有较高的检测性能和环境适应性。2、提出了一种基于遗传—模拟退火算法（genetic algorithms-simulated annealing algorithm,GASA）的网络存储资源分配方法,并将其用于实现异构系统间的数据存储备份以及存储过程中作为资源的移动Agent派遣次序的优化分配。该方法综合考虑了各移动Agent的产生时序、优先级和存储可用度等指标,在确保各移动Agent有效执行的前提下,使资源分配次序更合理。同时,在GA（genetic algorithms）中通过引入SA（simulated annealing algorithm）来进行局部精细搜索,维护群体的多样性,避免早熟收敛。仿真实验表明,基于GASA算法的移动Agent存储资源分配方法可以有效提高存储效率,改善网络实时性和存储性能。3、车间调度问题是比较典型的生产调度问题,要求多个作业在不同的机器上进行加工,并且每台机器上的所有作业的加工顺序都不尽相同。针对该问题,提出了一种结合通用部分全局规划机制（generalized partial global planning,GPGP）与遗传—禁忌搜索算法（genetic algorithms-tabu search,GATS）的多Agent车间调度模型,设计了从“初始宏观调度”到“微观再调度”的大规模复杂问题的调度步骤,实现了调度的多目标优化。同时,在初始宏观调度中采用GATS搜索算法,通过对个体进行重组与禁忌变异操作,确保种群的多样性以及算法的快速收敛。最后使用仿真Agent软件模拟了车间调度的协同机制,并与其他机制进行了比较。结果表明,所提出的模型不仅提高了调度的效率,而且降低了资源的损耗。4、针对半导体可重入生产动态调度的实际问题,提出了一种基于改进的GPGP（generalized partial global planning）协同机制与免疫进化策略算法（immune evolutionary strategies algorithms,IESA）的多Agent半导体可重入生产动态调度模型,设计了从“宏观调度—微观调度—重调度”的三层调度步骤,构建了一个柔性强且Agent可自我动态调度的仿真系统,并克服了GPGP协同机制在应用领域和构造设计上的缺陷。同时,为了避免宏观调度算法过早地陷入局部极值,通过采用IESA算法来强化个体的局部搜索能力,提高了算法的收敛速度。最后对调度模型进行了仿真验证,结果表明,所提出模型不仅提高了调度的效率,而且还具有较好的生产率。近年来,基于协同机制和智能算法的MAS及其应用的研究已经得到了国内外众多学者的关注,并且涌现了大量的改进算法和新的应用。本文对使用协同机制和智能算法的MAS求解任务分配问题、资源分配问题和生产调度问题进行了研究,并提出了一些更有效的模型和算法。本文的研究工作对MAS的协同机制和智能算法的改进、融合等以及在相关领域的应用,具有一定的理论意义和应用价值。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 任务分配问题
• 1.2.1 问题概述
• 1.2.2 研究现状
• 1.3 资源分配问题
• 1.3.1 问题概述
• 1.3.2 研究现状
• 1.4 生产调度问题
• 1.4.1 问题概述
• 1.4.2 研究现状
• 1.5 本文工作及组织结构
• 第2章 多Agent系统及其协同机制
• 2.1 引言
• 2.2 Agent与多Agent系统基本理论
• 2.2.1 Agent技术
• 2.2.2 多Agent系统
• 2.2.3 多Agent系统的协同机制
• 2.3 合同网协议
• 2.4 通用部分全局规划
• 2.4.1 GPGP协同机制的提出
• 2.4.2 TAEMS概述
• 2.4.3 GPGP的基本协同机制
• 2.5 本章小结
• 第3章 基于CNP与IM的多Agent任务分配模型
• 3.1 引言
• 3.2 问题应用与描述
• 3.2.1 入侵检测系统
• 3.2.2 免疫机理
• 3.2.3 问题描述
• 3.3 模型框架
• 3.4 分配算法
• 3.4.1 基于资源可用度的任务分配策略
• 3.4.2 联合免疫抗体（UAb）
• 3.4.3 免疫检测算法
• 3.5 实验结果与分析
• 3.5.1 仿真实验系统
• 3.5.2 实验一
• 3.5.3 实验二
• 3.6 本章小结
• 第4章 基于GASA算法的网络存储资源分配模型
• 4.1 引言
• 4.2 问题应用与描述
• 4.2.1 网络存储技术
• 4.2.2 问题描述
• 4.3 模型框架
• 4.4 分配算法
• 4.4.1 遗传算法
• 4.4.2 模拟退火算法
• 4.4.3 资源分配算法
• 4.5 实验结果与分析
• 4.5.1 仿真实验系统
• 4.5.2 实验一
• 4.5.3 实验二
• 4.6 本章小结
• 第5章 基于GPGP与GATS算法的多Agent生产调度模型
• 5.1 引言
• 5.2 问题应用与描述
• 5.2.1 车间调度问题
• 5.2.2 问题描述
• 5.3 模型框架
• 5.4 调度算法
• 5.4.1 禁忌搜索算法
• 5.4.2 初始宏观调度算法
• 5.4.3 车间调度的总体步骤
• 5.5 实验结果与分析
• 5.5.1 仿真实验系统
• 5.5.2 GPGP协同机制的DECAF仿真
• 5.5.3 结果分析
• 5.6 本章小结
• 第6章 基于改进的GPGP和IESA算法的多Agent可重入生产调度模型
• 6.1 引言
• 6.2 问题应用与描述
• 6.2.1 半导体生产调度问题
• 6.2.2 问题描述
• 6.3 GPGP的局限和改进
• 6.3.1 基于GPGP应用局限的改进
• 6.3.2 基于GPGP构造局限的改进
• 6.4 模型框架
• 6.5 调度算法
• 6.5.1 进化策略算法
• 6.5.2 宏观调度算法
• 6.5.3 半导体生产线总体调度步骤
• 6.6 实验结果与分析
• 6.6.1 仿真实验系统
• 6.6.2 协同机制仿真
• 6.6.3 结果比较
• 6.7 本章小结
• 第7章 结论与展望
• 参考文献
• 作者简介及科研成果
• 致谢