资源约束下的联盟形成问题研究

摘要

联盟形成问题是MAS中非常活跃的研究课题，自治agents如何形成联盟提高系统效率，是联盟形成中的研究难点。目前，关于联盟形成的研究通常都假定agents资源是无限的，基于资源约束下的联盟形成问题仍然亟待研究。另外，联盟形成问题中很多问题都是计算困难的，难以利用全搜索策略，而群智能相关技术手段为联盟形成的解决提供了一种思路。　　针对上述背景，本文重点研究基于群智能技术解决资源约束下的重叠联盟生成问题和资源结盟博弈中的成功联盟问题。力图在资源约束条件下，实现一个agent灵活、高效和快速形成联盟承担任务，而能为联盟形成问题在复杂环境下的应用提供理论指导和技术支持。本文的主要内容及创新之处如下:　　(1)调研当前国内外关于重叠联盟中的群智能算法，针对其中代表性的三种算法进行深入剖析，指出三种算法的各自特点和存在的不足，为之后改进方法的提出提供理论指导。　　(2)提出一种基于剩余资源的编码修正策略，通过对重叠联盟中agents和联盟之间联系的分析，提出agent的实际资源贡献和剩余资源贡献的概念，设计出一种仅需要对编码进行行检查，不考虑agents在不同联盟中的贡献方式。真正意义上实现了不同环境下agents灵活加入多个任务的目标，提高了系统的效率。　　(3)基于一维二进制编码的离散粒子群优化搜索资源结盟博弈中的成功联盟问题，根据实际情景对agents和goals的不同偏好，提出两种不同的编码修正策略。该算法能够在多项式时间内利用粒子群优化的快速收敛特性获得最优解，通过对仿真实验结果的分析，该策略相对于全局搜索算法降低了整个系统的时间和资源成本，保证了解的质量。

目录

声明

致谢

摘要

第一章 绪论

1．1 联盟形成问题

1．1．1 联盟结构生成

1．1．2 重叠联盟生成

1．1．3 资源结盟博弈

1．2 群智能

1．2．1 群智能搜索算法概述

1．2．2 粒子群优化

1．3 论文研究目的和意义

1．4 论文研究内容

1．5 论文组织安排

第二章 基于二维编码的联盟形成算法和修正算法

2．1 二维二进制编码

2．2 Lin和Hu的算法

2．3 周鹛的算法

2．4 Zhang的算法

2．5 小结

第三章 基于剩余资源的重叠联盟形成算法

3．1 引言

3．2 相关工作分析

3．3 改进型编码修正算法

3．3．1 算法描述

3．3．2 算法性能分析

3．4 实验结果与分析

3．4．1 最优解分析

3．4．2 编码修正操作分析

3．4．3 问题的参数影响

3．5 小结

第四章 基于一维BPSO求解资源结盟博弈中的成功联盟问题

4．1 相关工作分析

4．2 Shrot等人算法

4．3 一维二进制编码

4．4 编码修正算法

4．4．1 agent偏好的调整策略(agent-oriented strategy，AOS)

4．4．2 goal偏好的调整策略(goal-oHented strategy，GOS)

4．4．3 性能分析

4．5 适应度函数

4．6 提出的算法

4．7 实验结果与分析

4．7．1 BPSO参数的影响

4．7．2 问题参数的影响

4．8 本章小结

第五章 总结与展望

5．1 本文主要内容

5．2 下一步研究工作

参考文献

攻读硕士学位期间的学术活动及成果情况