考虑一组需要分配
M
=
{
1
,
2
,
⋯
,
m
}
M=\{1,2,\cdots,m\}
M={1,2,⋯,m} 种类型资源的异类（不是同一类的）行为体，用
N
=
{
1
,
2
,
⋯
,
n
}
N=\{1,2,\cdots,n\}
N={1,2,⋯,n} 表示，每种资源的总量用
y
⃗
=
[
y
1
,
y
2
,
⋯
,
y
n
]
T
\vec{y}=[y_1,y_2,\cdots,y_n]^\text{T}
y=[y1,y2,⋯,yn]T 表示，其中
y
j
y_j
yj 表示资源类型
j
∈
M
j\in M
j∈M 的总量。假设对应于资源类型
j
j
j 的数量
x
i
j
x_{ij}
xij 是一个连续变量，该变量用于表示行为体
i
∈
N
i\in N
i∈N 获得的资源。定义
R
i
=
{
x
⃗
i
=
[
x
i
1
,
x
i
2
,
⋯
,
x
i
m
]
T
∣
0
≤
x
i
j
≤
x
i
j
max
,
j
∈
M
}
\mathcal{R}_i=\left\{\vec{x}_i=[x_{i1},x_{i2},\cdots,x_{im}]^\text{T} \left|0\le x_{ij}\le x_{ij}^{\text{max}},j\in M\right.\right\}
Ri={xi=[xi1,xi2,⋯,xim]T0≤xij≤xijmax,j∈M} 作为可行资源组合的集合，并设
Δ
f
=
{
X
=
[
x
⃗
1
,
x
⃗
2
,
⋯
,
x
⃗
n
]
∣
x
⃗
i
∈
R
i
,
∑
i
=
1
n
x
⃗
i
=
y
}
\Delta_f=\left\{X=[\vec{x}_1,\vec{x}_2,\cdots,\vec{x}_n]\left|\vec{x}_i\in\mathcal{R}_i,\sum_{i=1}^n\vec{x}_i=y\right.\right\}
Δf={X=[x1,x2,⋯,xn]xi∈Ri,i=1∑nxi=y} 为可行的分配曲线。在收到一系列资源集时，一个行为体获得通过收益函数
u
i
:
R
i
→
[
0
,
+
∞
)
u_i:\mathcal{R}_i\rightarrow[0,+\infty)
ui:Ri→[0,+∞) 定义的奖赏，而总和收益函数
U
:
Δ
f
→
[
0
,
+
∞
)
U:\Delta_f\rightarrow[0,+\infty)
U:Δf→[0,+∞) 定义为所有收益函数的和
∑
i
=
1
N
u
i
\displaystyle\sum_{i=1}^Nu_i
i=1∑Nui。目标是寻找分配空间
X
=
[
x
⃗
1
,
x
⃗
2
,
⋯
,
x
⃗
n
]
X=[\vec{x}_1,\vec{x}_2,\cdots,\vec{x}_n]
X=[x1,x2,⋯,xn] 使得在约束条件
X
∈
Δ
f
X\in\Delta_f
X∈Δf下最大化
U
(
X
)
U(X)
U(X)。数学上，对异类行为体的最优资源分配问题可描述为
max
x
=
[
x
1
,
x
2
,
…
,
x
n
]
U
(
x
)
=
∑
i
=
1
n
u
i
(
x
i
)
s.t.
{
0
≤
x
i
j
≤
x
i
j
max
,
i
∈
N
,
j
∈
M
(
1
)
∑
i
=
1
n
x
i
j
=
y
j
,
j
∈
M
\begin{aligned} &\max _{x=\left[x_{1}, x_{2}, \ldots, x_{n}\right]} U(x)=\sum_{i=1}^{n} u_{i}\left(x_{i}\right) \\ &\text {s.t.}\begin{cases} 0 \leq x_{ij} \leq x_{ij}^{\max}, i \in N, j \in M \qquad(1)\\ \displaystyle\sum_{i=1}^n x_{ij}=y_j, j \in M \end{cases} \end{aligned}
x=[x1,x2,…,xn]maxU(x)=i=1∑nui(xi)s.t.⎩⎨⎧0≤xij≤xijmax,i∈N,j∈M(1)i=1∑nxij=yj,j∈M
B.接触网络
为了让一组行为体合作，他们必须通过接触网络的通信了解相邻个体的状态。对于每个行为体
i
i
i，我们将邻域定义为通过通信链路连接到它的行为体集合，也就是
∀
i
∈
N
,
Ω
i
=
{
k
∈
N
∣
(
i
,
k
)
∈
E
}
\forall i\in N,\Omega_i=\{k\in N|(i,k)\in E\}
∀i∈N,Ωi={k∈N∣(i,k)∈E}，其中
E
E
E是接触网络的边。本文中的接触网络假设为支持信息和事件相互交换的无向图。特别地，如果任意两个节点间存在通路则称其为连通图，如果任意两个节点间存在边则称其为强连通图（这里对强连通的定义好像不对）。
C.收益函数
为了实现最经济的分配，根据资源生产的成本函数，假设每个行为体的收益函数
u
i
u_i
ui满足以下三个条件： 假设1: 收益函数
u
i
u_i
ui非负且在
R
i
\mathcal{R}_i
Ri上连续可微； 假设2: 收益函数
u
i
u_i
ui是在
R
i
\mathcal{R}_i
Ri上分配资源的增函数，而且是
x
i
=
[
x
i
1
,
x
i
2
,
⋯
,
x
i
m
max
]
x_i=[x_{i1},x_{i2},\cdots,x_{im}^\text{max}]
xi=[xi1,xi2,⋯,ximmax] 的最大值。这表明在生产能力范围内，接收更多的资源总能提高行为体的收益。 假设3: 收益函数
u
i
u_i
ui满足边际价格随着每个行为体类别分配的资源总量的增加而降低的条件，即
p
i
j
(
x
i
)
>
p
i
j
(
x
i
′
)
,
∀
x
i
,
x
i
′
∈
R
:
x
i
j
<
x
i
j
′
,
x
i
,
−
j
=
x
i
,
−
j
′
p_{ij}(x_i)>p_{ij}(x_i'),\forall x_i,x_i'\in\mathcal{R}:x_{ij}<x_{ij}',x_{i,-j}=x_{i,-j}'
pij(xi)>pij(xi′),∀xi,xi′∈R:xij<xij′,xi,−j=xi,−j′ 其中
−
j
-j
−j 表示除了
j
j
j 以外的资源类型，
p
i
j
(
x
i
)
=
∂
u
i
/
∂
x
i
j
p_{ij}(x_i)=\partial u_i/\partial x_{ij}
pij(xi)=∂ui/∂xij 表示
x
⃗
i
\vec{x}_i
xi 的第
j
j
j 种资源类型的边际收益。 引理1: 在前面假设1-3下，收益函数
u
i
u_i
ui 是一个定义在
R
i
\mathcal{R}_i
Ri 上的连续凹函数。 证明: 对
D.最优化条件
因为
u
i
u_i
ui在
R
i
\mathcal{R}_i
Ri上严格凹，总和收益函数也必须严格凹，且有在
Δ
f
\Delta_f
Δf 上唯一的最大值
x
∗
x^*
x∗ 。由于
U
U
U 不能在最优分配曲线上增加，所以必须存在
i
,
k
∈
N
,
j
∈
M
i,k\in N,j\in M
i,k∈N,j∈M 使得
p
i
j
(
x
i
∗
)
>
p
k
j
(
x
k
∗
)
p_{ij}(x_i^*)>p_{kj}(x_k^*)
pij(xi∗)>pkj(xk∗) 使得
x
k
j
∗
=
0
x_{kj}^*=0
xkj∗=0。 引理2: 在平衡点
x
∗
x^*
x∗ 处，对资源类型
j
∈
M
j\in M
j∈M，所有属于集合
A
j
+
=
{
i
∣
x
i
j
∗
>
0
,
i
∈
N
}
A_j^+=\{i|x_{ij}^*>0,i\in N\}
Aj+={i∣xij∗>0,i∈N} 的个体一定有相同的边际收益
m
+
≥
0
m^+\geq 0
m+≥0 且
m
0
=
max
i
∈
A
j
0
p
i
j
(
x
i
∗
)
m^0=\displaystyle\max_{i\in A_j^0}p_{ij}(x_i^*)
m0=i∈Aj0maxpij(xi∗)，
A
j
0
=
{
i
∣
x
i
j
∗
=
0
,
i
∈
N
}
A_j^0=\{i|x_{ij}^*=0,i\in N\}
Aj0={i∣xij∗=0,i∈N} 最多必须和
m
+
m^+
m+ 一样大。 证明: 对任何一个前文定义的分配问题，第
j
j
j 种资源类型的结果总处于两种情况中：(1)
A
j
0
=
∅
A_j^0=\varnothing
Aj0=∅ 和 (2)
A
j
0
≠
∅
A_j^0\neq\varnothing
Aj0=∅。
3.分布式分配算法
尽管(1)中的问题有时可以从最优化条件中通过解析法求解，但是它们假设有一个中心化的接触网络。更重要的是，这一结果是负的并且对于一些参数设置不成立。对于分布式环境的最优资源分配，我们提出了一个基于复制动态方程的合作算法，该算法一开始将个体在不同习性下的比例的演化建模为一组微分方程
{
s
˙
i
=
α
s
i
(
f
i
−
f
ˉ
)
f
ˉ
=
1
P
∑
i
=
1
N
s
i
f
i
\begin{cases} \dot{s}_i = \alpha s_i(f_i-\bar{f}) \\ \bar{f} = \displaystyle\frac{1}{P}\sum_{i=1}^Ns_if_i \end{cases}
⎩⎨⎧s˙i=αsi(fi−fˉ)fˉ=P1i=1∑Nsifi 其中住在第
i
i
i 个栖息地的种群数量
s
i
s_i
si 的增长率正比于该种群的适应度
f
i
f_i
fi 和种群平均适应度
f
ˉ
\bar{f}
fˉ 之差。从演化博弈论的视角来看，栖息地类似于纯策略，
s
i
s_i
si 是采用第
i
i
i 个策略的个体数量，
P
=
∑
i
=
1
n
P=\displaystyle\sum_{i=1}^n
P=i=1∑n 是种群总数量，
α
>
0
\alpha>0
α>0 是调整增长率的参数。（我学的演化博弈论中，
s
s
s 是单个种群占种群总数的比例，
P
=
1
P=1
P=1，见 演化博弈、复制动态方程与仿真 -CSDN博客） 这里需要说明的是，不同于中心化控制器或者全局收益给定的完全NOC情况，单个行为体只能得到所处多智能体系统中的局部信息。因此，我们将局部复制动态方程用于设计一个分布式的分配场景，其中每个个体基于局部平均值更新其资源，也就是，分配的资源
x
i
j
(
t
)
x_{ij}(t)
xij(t) 的增长率为
x
˙
i
j
(
t
)
=
x
i
j
(
t
)
(
f
i
j
(
x
⃗
i
(
t
)
)
∑
k
∈
Ω
i
x
k
j
(
t
)
y
j
−
f
~
i
j
(
t
)
)
(
12
)
f
~
i
j
=
1
y
j
∑
k
∈
Ω
i
x
k
j
f
k
j
(
x
⃗
k
)
(
13
)
\begin{aligned} &\dot{x}_{ij}(t) = x_{ij}(t)\left(f_{ij}(\vec{x}_i(t)) \frac{\displaystyle\sum_{k\in\Omega_i}x_{kj}(t)}{y_j} -\tilde{f}_{ij}(t)\right) &\qquad(12)\\ &\tilde{f}_{ij}= \frac{1}{y_j}\sum_{k\in\Omega_i}x_{kj}f_{kj}(\vec{x}_k) &\qquad(13) \end{aligned}
x˙ij(t)=xij(t)fij(xi(t))yjk∈Ωi∑xkj(t)−f~ij(t)f~ij=yj1k∈Ωi∑xkjfkj(xk)(12)(13) 其中
f
i
j
(
x
i
(
t
)
)
=
p
i
j
(
x
i
)
f_{ij}(x_i(t))=p_{ij}(x_i)
fij(xi(t))=pij(xi)，
f
~
i
j
\tilde{f}_{ij}
f~ij 为局部平均值。利用式(12)(13)，本文的分配算法通过下面几条规则定义：
从任意可能的分配曲线
x
(
0
)
x(0)
x(0) 出发，算法采用同步更新方案，每个行为体的资源总数和每种资源数都同步更新。
在每个步长
t
t
t 内，行为体
i
i
i 通过它的邻居
k
∈
Ω
i
k\in\Omega_i
k∈Ωi 收集包含
x
k
x_k
xk 和
f
k
j
(
x
k
)
f_{kj}(x_k)
fkj(xk) 的局部信息。通过这一步，每个行为体通过式(12)(13)更新它的资源量，即
x
i
j
(
t
+
1
)
=
x
i
j
(
t
)
+
x
˙
i
j
(
t
)
Δ
t
x_{ij}(t+1)=x_{ij}(t)+\dot{x}_{ij}(t)\Delta t
xij(t+1)=xij(t)+x˙ij(t)Δt
引理3: 本文算法具有求和不变性，也就是说，如果
∑
i
=
1
n
x
⃗
i
(
0
)
=
y
⃗
\displaystyle\sum_{i=1}^n\vec{x}_i(0)=\vec{y}
i=1∑nxi(0)=y，那么
∀
t
>
0
,
\forall t>0,
∀t>0,
∑
i
=
1
n
x
⃗
i
(
t
)
=
y
⃗
\displaystyle\sum_{i=1}^n\vec{x}_i(t)=\vec{y}
i=1∑nxi(t)=y。 证明: 对任意时间
t
>
0
t>0
t>0，所有行为体的增长率
x
˙
i
j
(
t
)
\dot{x}_{ij}(t)
x˙ij(t) 满足
∑
i
=
1
n
x
˙
i
j
(
t
)
=
∑
i
=
1
n
x
i
j
(
t
)
y
j
(
f
i
j
(
x
⃗
i
(
t
)
)
∑
k
∈
Ω
i
x
k
j
(
t
)
−
y
j
f
~
i
j
(
t
)
)
=
1
y
j
∑
i
=
1
n
(
x
i
j
f
i
j
(
x
⃗
i
)
∑
k
∈
Ω
i
x
k
j
−
x
i
j
∑
k
∈
Ω
i
x
k
j
f
k
j
(
x
⃗
k
)
)
\begin{aligned} \sum_{i=1}^n\dot{x}_{ij}(t) =& \sum_{i=1}^n\frac{x_{ij}(t)}{y_j} \left(f_{ij}(\vec{x}_i(t))\sum_{k\in\Omega_i}x_{kj}(t) -y_j\tilde{f}_{ij}(t)\right) \\ =& \frac{1}{y_j}\sum_{i=1}^n \left(x_{ij}f_{ij}(\vec{x}_i)\sum_{k\in\Omega_i}x_{kj} -x_{ij}\sum_{k\in\Omega_i}x_{kj}f_{kj}(\vec{x}_k)\right) \\ \end{aligned}
i=1∑nx˙ij(t)==i=1∑nyjxij(t)(fij(xi(t))k∈Ωi∑xkj(t)−yjf~ij(t))yj1i=1∑n(xijfij(xi)k∈Ωi∑xkj−xijk∈Ωi∑xkjfkj(xk)) 由于NOC是无向图，所以容易证明对于任意个体
i
i
i 和它的邻居
k
k
k
x
i
j
f
i
j
(
x
⃗
i
)
x
k
j
−
x
i
j
x
k
j
f
k
j
(
x
⃗
k
)
+
x
k
j
f
k
j
(
x
⃗
k
)
x
i
j
−
x
k
j
x
i
j
f
i
j
(
x
⃗
i
)
=
0
(
16
)
x_{ij}f_{ij}(\vec{x}_i)x_{kj} - x_{ij}x_{kj}f_{kj}(\vec{x}_k) +x_{kj}f_{kj}(\vec{x}_k)x_{ij} - x_{kj}x_{ij}f_{ij}(\vec{x}_i) =0 \qquad(16)
xijfij(xi)xkj−xijxkjfkj(xk)+xkjfkj(xk)xij−xkjxijfij(xi)=0(16) 由此得出
∑
i
=
1
n
x
˙
i
j
(
t
)
=
0
\sum_{i=1}^n\dot{x}_{ij}(t) =0
i=1∑nx˙ij(t)=0 给定初始条件
∑
i
=
1
n
x
⃗
i
(
t
)
=
y
⃗
\displaystyle\sum_{i=1}^n\vec{x}_i(t)=\vec{y}
i=1∑nxi(t)=y，即可得证。 显然，对任意
i
i
i 和
j
j
j，该算法的平衡点
X
e
X^\text{e}
Xe 满足下列条件： (C1)
X
e
=
0
X^\text{e}=0
Xe=0 或 (C2)
X
e
>
0
X^\text{e}>0
Xe>0 且
f
i
j
(
x
⃗
i
e
)
∑
k
∈
Ω
x
k
j
e
=
∑
k
∈
Ω
x
k
j
e
f
k
j
(
x
⃗
k
e
)
f_{ij}(\vec{x}_i^\text{e})\displaystyle\sum_{k\in\Omega}x_{kj}^\text{e}=\displaystyle\sum_{k\in\Omega}x_{kj}^\text{e}f_{kj}(\vec{x}_k^\text{e})
fij(xie)k∈Ω∑xkje=k∈Ω∑xkjefkj(xke) 定理1: 对一个平衡点
X
e
X^\text{e}
Xe，如果所有位于
x
i
j
e
x_{ij}^\text{e}
xije 的行为体都是非切割顶点，那么
X
e
X^\text{e}
Xe 一定是式(1)的最优解。 证明: 首先，我们考虑一种情况，
4.仿真结果
本节给出了一个示例以说明所提出的算法在全连接NOC下的有效性，其中
n
=
6
n=6
n=6，
y
⃗
=
[
545
,
467
]
T
\vec{y}=[545,467]^\text{T}
y=[545,467]T，且每个行为体与两个相邻的行为体交换信息。也就是说，
Ω
i
=
{
i
−
1
,
i
+
1
}
,
∀
i
∈
(
1
,
n
)
\Omega_i=\{i-1,i+1\},\forall i\in(1,n)
Ωi={i−1,i+1},∀i∈(1,n)，
Ω
1
=
{
6
,
2
}
\Omega_1=\{6,2\}
Ω1={6,2}，
Ω
6
=
{
5
,
1
}
\Omega_6=\{5,1\}
Ω6={5,1}，根据上面的约束条件，每个行为体的收益函数选为
u
i
(
x
i
)
=
∑
j
=
1
m
x
i
j
(
2
x
i
j
max
−
x
i
j
)
c
i
j
x
i
j
max
,
x
i
∈
R
i
u_i(x_i)=\sum_{j=1}^m\frac{x_{ij}(2x_{ij}^\text{max}-x_{ij})}{c_{ij}x_{ij}^\text{max}},x_i\in\mathcal{R}_i
ui(xi)=j=1∑mcijxijmaxxij(2xijmax−xij),xi∈Ri 其中，异质性与最大容量
x
i
j
max
x_{ij}^\text{max}
xijmax 相关，损失系数
c
i
j
c_{ij}
cij 与第
j
j
j 类资源的每个单位相关（这句话没看懂），且
x
max
=
(
x
i
j
max
)
6
×
2
=
[
172
86
47
70
66
120
106
45
100
90
80
100
]
c
=
(
c
i
j
)
6
×
2
=
[
0.2
0.85
0.3
0.4
0.4
0.5
0.1
0.2
0.5
0.4
0.85
0.8
]
x^\text{max}=(x_{ij}^\text{max})_{6\times 2}=\left[\begin{matrix} 172 & 86 \\ 47 & 70 \\ 66 & 120 \\ 106 & 45 \\ 100 & 90 \\ 80 & 100 \\ \end{matrix}\right] \\ c=(c_{ij})_{6\times 2}=\left[\begin{matrix} 0.2 & 0.85 \\ 0.3 & 0.4 \\ 0.4 & 0.5 \\ 0.1 & 0.2 \\ 0.5 & 0.4 \\ 0.85 & 0.8 \\ \end{matrix}\right] \\
xmax=(xijmax)6×2=17247661061008086701204590100c=(cij)6×2=0.20.30.40.10.50.850.850.40.50.20.40.8 仿真中时间步长
Δ
t
\Delta t
Δt 设置为常值
0.01
0.01
0.01。
图1中绘制了分配的资源
x
i
j
x_{ij}
xij、边际收益
p
i
j
p_{ij}
pij 和总收益
U
U
U 关于演化代数的函数。仿真结果表明，在协作和分布式资源分配协议中，总收益随着时间的推移单调增加，分配曲线逐渐收敛到最优解，其中所有行为体对于相同的资源类型具有相等的边际收益。需要注意的是在第800代时，损失系数
c
1
,
1
c_{1,1}
c1,1 和
c
6
,
2
c_{6,2}
c6,2 分别改变成
0.9
0.9
0.9 或
0.2
0.2
0.2。局部放大的子图显示系统有能力对变化快速反应并到达当前条件下的新平衡点。实际上，该算法还适用于涉及与
y
⃗
\vec{y}
y，
x
max
x^\text{max}
xmax 相关的其他干扰的动态环境下和通信拓扑中，只要NOC在每个步长内全连接。
总结
本文针对网络化异构行为体之间的资源分配问题，提出了一种基于局部复制动态方程的分布式协作算法。通过使用最优性条件，我们证明了算法收敛于平衡点。特别地，当所有节点都具有正资源向量或所有具有
x
i
′
j
e
=
0
x_{i'j}^e=0
xi′je=0 的行为体都是非割顶点时，平衡点对于分配问题是最优的。仿真结果表明了该方法在静态和动态环境中的有效性和可行性。
