没有合适的资源?快使用搜索试试~ 我知道了~
信任和效用关系约束的联盟结构生成.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 18 浏览量
2023-02-23
20:03:17
上传
评论
收藏 634KB DOCX 举报
温馨提示
试读
15页
信任和效用关系约束的联盟结构生成.docx
资源推荐
资源详情
资源评论
1. 引言
5G 网络切片、导频分配和云计算等资源分配问题是研究的热点,但是该问题通常是
NP 难的,近年来,联盟和可信联盟逐渐被应用到资源分配领域,智慧等人
[1]
用联盟分裂形
式的思想,即随机划分的方法提出了一种联合用户分组和联盟博弈的动态导频分配方案,
用户被分成若干个互不相交的子联盟。联盟形成(Coalition Formation, CF)是多智能体系统
(Multi-智能体 System, MAS)的重要研究内容之一,通过对智能体集合进行划分得到联盟结
构(Coalition Structure, CS),其中包含若干不相交的集合,即联盟(Coalition, C)。CF 的过程
通常以最大化社会福利和个体效用为目标
[2]
,称为联盟结构生成(Coalition Structure
Generation, CSG)。合作博弈论是 CF 研究的基础,例如特征函数博弈
[3]
、不可转移效用的
博弈
[4]
和享乐博弈
[5]
。联盟博弈论一般假设特征函数具有超加性,即生成的主联盟是最优
的。核
[6]
、Shapley 值
[7]
为联盟博弈提供了划分收益的解决方案。最近,研究人员考虑特征
函数不是超加性的情况,有的模型使用对称可加性可分离特征博弈
[8]
。
CSG 存在着诸多约束
[9]
,如通常情况下信任是合作的基础,信任是一方对另一方实现
承诺的主观评估。信任程度越高越容易形成长期稳定的合作关系,而信任的传递性可以促
进不熟悉的智能体之间的合作关系。信任关系对最终效用有直接的影响,因而,将信任信
息融入到效用中是合理的。王海艳等人
[10]
提出了基于可信联盟的服务推荐方法,将信任关
系融入相似度计算;Sless 等人
[11]
将社交关系引入联盟形成,负值社交关系表示合作很难成
功。童向荣等人
[12]
和 Wang 等人
[13]
对信任传递的特性进行了研究。Mao 等人
[14]
提出信任传
递取最小信任值或信任值相乘的方式,信任聚合取最大信任值或对多条路径信任值进行加
权平均。
近年来,研究人员在图上研究博弈,假设有向带权图的边表示智能体之间的关系。边
收缩方法可以枚举智能体集的所有可行分区,Karger
[15]
应用该方法解决 Min-Cut 问题,但
未应用在联盟形成中。图割将图划分为互不相交的区域,在同一区域内的特征具有较高的
相似性,而不同的区域内的特征则具有明显的差异性,其原理正是一种划分。受图割 s-t-
cut 算法的启发,研究了基于信任和效用关系约束的 CSG,在保证智能体理性和联盟稳定
(无块)的情况下,使用信任和效用关系对网络进行切割,从而形成联盟。由此,提出了两
种多项式时间的精确算法:信任约束下 CSG 和信任效用关系约束下 CSG,均能够求解设
定情况下的最优 CS。仿真实验结果验证了所提方法的有效性。
本文主要贡献:(1)将 CF 的效用关系扩展为信任和效用关系,即不仅关注效用约束,
还关注信任约束,并用信任和效用二元组表示,以此作为 CSG 的依据。(2) 在保证智能体
个体理性和联盟稳定(不存在块)的前提下,用分割信任网络的方法,生成有 k 个联盟的稳
定 CS,提出了两种多项式时间的精确算法。
2. 基本定义
传统的联盟形成只基于效用关系,没有考虑社交关系对效用的影响,近年来,学者们
注意到社交关系对合作成功有必然的影响,因此,信任关系应该与效用关系一起考虑,这
能提高联盟形成的效率和速度。
定义 1 信任和效用关系图:智能体之间的约束关系用非对称有向加权图来表示。令
G=<A,E,G=<A,E,ρ,ω>ρ,ω>是一个有向加权图,其中,A={a1,a2,⋅⋅⋅,an}A={a1,a2,···,an}表示
有限、非空的智能体集合,n=|A|表示集合 A 中的智能体数量。E 表示集合 A 中智能体之间
的关系集,边<ai,aj>∈E<ai,aj>∈E 有权重 ρρ 和 ωω,分别表示 aiai 对 ajaj 的信任关系和效
用关系,ρi,j∈[0,1]ρi,j∈[0,1]表示 aiai 对于 ajaj 的信任值,当 i=ji=j 时,ρi,i=0ρi,i=0,
ωi,jωi,j 表示 aiai 可从 ajaj 得到的效用值。如果<ai,aj>∉E<ai,aj>∉E,则 ai,ajai,aj 之间的信任
和效用可以通过第 3 部分的信任传递计算得知。
定义 2 信任和效用函数:fρ,ω(ai,aj)fρ,ω(ai,aj)表示 aiai 和 ajaj 之间信任和效用函数,
能够表征智能体之间合作的可能性,该值越大,表示合作的可能性越高,反之,则表示合
作的可能性越低。特别地,当 ω=0ω=0 时,表示 CSG 只考虑信任关系;当 ρ=0ρ=0 时,表
示 CSG 只考虑效用关系。
令 μ(ai,C)μ(ai,C)为 ai∈Cai∈C 从联盟 C 中得到的效用,即 μ(ai,C)=∑aj∈C,
j≠iω(ai,aj)μ(ai,C)=∑aj∈C,j≠iω(ai,aj),简记为 μiμi。则联盟效用可表示为
V(C)=∑ai∈Cμ(ai,C)V(C)=∑ai∈Cμ(ai,C)。集合 A 的社会福利为
SW(A)SW(A),SW(A)=∑C∈AV(C)SW(A)=∑C∈AV(C)。图 1 给出了不同联盟结构的效用示
例。
图 1 不同联盟结构的效用
下载: 全尺寸图片 幻灯片
假设需要完成的任务数为 k,0<k≤nk,0<k≤n。Sk(A)Sk(A)表示将集合 A 划分为 k 个互不
相交的非空子集,Sk(A)Sk(A)的每种可能情况称之为联盟结构,记为 CS,CS’…。
例 1:智能体集合 A={a1,a2,a3,a4}A={a1,a2,a3,a4},当 k=3 时,S3(A)S3(A)共有 6 种
情况:
{{a1},{a2},{a3,a4}}{{a1},{a2},{a3,a4}};{{a1,a2},{{a1,a2},{a3},{a4}}{a3},{a4}};{{a1},{a3},{a2,a
4}}{{a1},{a3},{a2,a4}};{{a2},{a3},{a1,{{a2},{a3},{a1,a4}}a4}};{{a1},{a4},{a2,a3}}{{a1},{a4},{
a2,a3}};{{a2},{a4},{a1,a3}}{{a2},{a4},{a1,a3}}。若
CS={{a1},{a2},{a3,a4}}={{a1},{a2},{a3,a4}},则
C1→{a1},C2→C1→{a1},C2→{a2},C3→{a3,a4}{a2},C3→{a3,a4}。
如果 CS 的智能体可以通过组建一个新联盟,在不降低新联盟内其它智能体收益的前
提下,达到提高自身收益的目的,那么这个新联盟将破坏原有的 CS,该 CS 是不稳定的。
而这个新联盟是有更大信任和效用值的联盟,称为块。
定义 3 k-联盟块:令 CS={C1,C2,⋅⋅⋅,Ck}={C1,C2,···,Ck}是一个联盟结构。如果在 CS 之
外可能存在一个联盟 B⊆A,B∉CSB⊆A,B∉CS(该联盟 B 内的智能体与 CS 中的 智能体是重复
的,但联盟是不同的),对于∀ai,aj∈B,∀ai,aj∈B,满足
∑fBρ,w(ai,aj)>∑fCSρ,w(ai,aj)∑fρ,wB(ai,aj)>∑fρ,wCS(ai,aj),∃Cm∈CS∃Cm∈CS,同时
Cm⊆BCm⊆B,那么称联盟 B 为 k-联盟块,其中 fBρ,wfρ,wB(ai,aj)(ai,aj)表示 a
i
, a
j
在块 B 中
的信任和效用值,fCSρ,wfρ,wCS(ai,aj)(ai,aj)表示 a
i
, a
j
在 CS 中的信任和效用值。
例 2:在图 2 中,已知联盟结构
CS={{a1,CS={{a1,a2,a3},{a4},{a5,a6}}a2,a3},{a4},{a5,a6}},块 B={a4,a5}B={a4,a5},存在联
盟 Cm={a4}Cm={a4},使得 Cm∈CSCm∈CS 和 Cm⊆BCm⊆B。根据定义 3,联盟 B 是一个
3-联盟块。
图 2 智能体信任网络
下载: 全尺寸图片 幻灯片
根据定义 3 易知,如果有一个联盟是块,那么 CS 中的智能体倾向于离开原联盟而形
成新的联盟,这说明块破坏了联盟结构的稳定性,因此在满足超加性的前提下,没有可能
的块就成为了联盟稳定的条件。若联盟的数量固定为常数 k,则不允许出现块,要求智能
体集合恰好生成 k 个联盟,当 k=2 时,分别记为联盟 s 和 t,s 和 t 组成新的联盟结构。
剩余14页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3836
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功