世界杯优化算法及其Python实现！

文章目录

算法原理Python实现

算法原理

WCO，即世界杯优化算法(World Cup Optimization)，是2016年提出的算法，这个算法的提出，充分说明了动物不够用了，人们开始通过人群来研究群体智能了。

在WCO中，最基本的抽象就是洲、国家以及参赛球队。其中，国家表示一组独立的参数，参赛球队则是单个参数。即

C

=

{

x

⃗

i

}

C=\{\vec x_i\}

C={x

i​}

x

⃗

i

\vec x_i

x

i​就是参赛国，其每个分量，都代表一个球队，许多个参赛国共同组成一个大洲。

在优化过程中，优化参数是肯定要相等的，也就是说每个国家都有相同数目的候选团队；同时每个洲又都有相同数目的参赛国家，从而每个大洲的球队可以通过矩阵表示，故将第

k

k

k个大洲的第

i

i

i个国家的第

j

j

j个球队记作

x

k

i

j

∈

C

k

x_{ki}^j\in C_k

xkij​∈Ck​

每个国家的所有球队放在一起，组成一个参数数组，带入到判定函数中，得到对应的适应度

f

k

i

=

f

(

x

k

i

)

f_{ki} = f(x_{ki})

fki​=f(xki​)

接下来开始球队之间的竞争，主要分为三个步骤

1 设总共有

N

N

N个大洲，计算各大洲适应度的平均值和标准差

−

∷

k

=

∑

i

n

f

k

i

N

σ

k

=

∑

i

=

1

n

f

k

i

−

μ

k

N

−

1

\minuscoloncolon_k=\sum^n_i\frac{f_{ki}}{N}\\ \sigma_k = \sqrt{\sum^n_{i=1}\frac{f_{ki}-\mu_k}{N-1}}

−::k​=i∑n​Nfki​​σk​=i=1∑n​N−1fki​−μk​​

​

2 计算各大洲分数

R

k

=

rand

⁡

σ

k

+

μ

k

2

R_k=\frac{\operatorname{rand}\sigma_k+\mu_k}{2}

Rk​=2randσk​+μk​​

其中，rand是用于调节步长的随机数，取值范围是

(

0

,

1

)

(0,1)

(0,1)，计算得到的

R

k

R_k

Rk​值将用于排序。

3 至此，其实就可以得到最佳球队了，冠军就是

f

f

f值最小的那个。

但接下来才是算法的关键之处，也是玄幻之处。首先，根据

R

k

R_k

Rk​的值，对所有大洲进行排序

X

1

=

[

X

11

,

⋯

,

X

1

n

]

X

2

=

[

X

21

,

⋯

,

X

2

n

]

⋮

X

m

=

[

X

m

1

,

⋯

,

X

m

n

]

\begin{aligned} X_1 &= \begin{bmatrix}X_{11},&\cdots,&X_{1n}\end{bmatrix}\\ X_2 &= \begin{bmatrix}X_{21},&\cdots,&X_{2n}\end{bmatrix}\\ &\vdots\\ X_m &= \begin{bmatrix}X_{m1},&\cdots,&X_{mn}\end{bmatrix}\\ \end{aligned}

X1​X2​Xm​​=[X11​,​⋯,​X1n​​]=[X21​,​⋯,​X2n​​]⋮=[Xm1​,​⋯,​Xmn​​]​

然后，把排名第一的大洲

X

1

X_1

X1​提取出来，作为下次参赛内定的成员。这个意图很明显，

X

1

X_1

X1​在本次世界杯比赛中表现最佳，说明

X

1

X_1

X1​的各参赛国的球队，下次参加比赛只需微调就行；其他大洲表现不佳，说明派来的球队不佳，所以需要更换球队。

所以，下一次参加世界杯的国家包括两部分，即

X

b

e

s

t

X_{best}

Xbest​和

X

r

a

n

d

X_{rand}

Xrand​，二者都有一定的随机性，区别在于，后者就按照初始化时那样随机生成就行，前者则需根据

X

1

X_1

X1​的值进行限定。

记

U

b

=

max

⁡

(

X

1

)

,

L

b

=

min

⁡

(

X

1

)

U_b=\max(X_1), L_b=\min(X_1)

Ub​=max(X1​),Lb​=min(X1​)，令

U

=

1

2

δ

(

U

b

+

L

b

)

,

L

=

1

2

δ

(

U

b

−

L

b

)

U=\frac{1}{2}\delta(U_b+L_b), L=\frac{1}{2}\delta(U_b-L_b)

U=21​δ(Ub​+Lb​),L=21​δ(Ub​−Lb​)，则

X

b

e

s

t

X_{best}

Xbest​的生成区间为

L

<

X

b

e

s

t

<

U

L

L

最后，不符合现实的魔幻设定也出现了，各参赛国可以自行选择自己的洲，相当于将

[

X

b

e

s

t

,

X

r

a

n

d

]

[X_{best},X_{rand}]

[Xbest​,Xrand​]打乱重排。

通过不断迭代上述的步骤，就完成了球队的更新和进化。

Python实现

首先，实现其迭代逻辑

import numpy as np

from itertools import chain

from random import shuffle

rand = np.random.rand

uniRand = np.random.uniform

# 表示

# cs 表示各大洲，每个大洲都是一个矩阵

# 设K个大洲，每个大洲M个国家，每个国家N个球队

def compi(cs, func):

# fs为适应度函数，为KxM维矩阵

fs = [[func(x) for x in xs] for xs in cs]

mu = np.array([np.mean(f) for f in fs]) # 各大洲平均值

sigma = np.array([np.std(f) for f in fs]) # 各大洲标准差

rs = (rand(len(mu))*sigma + mu)/2

fBest = np.min(fs)

i,j = np.where(np.array(fs)==fBest)

best = [fBest, cs[i[0]][j[0]]]

return cs[np.argmin(rs)], best

然后，实现迭代流程

# func为优化函数；

# K为大洲个数；M为每个洲的国家数；N为每个国家的球队数；

# xRange为求解范围，nIter为迭代次数

# ac用于调控最优值精度

def wco(func, K, M, N, xRange, nIter, ac=0.5):

cs = [uniRand(*xRange, N) for _ in range(K*M)]

cs = np.array(cs).reshape(K,M,N)

for _ in range(nIter):

xBest, best = compi(cs, func)

xL = np.min(xBest, axis=0)

xR = np.max(xBest, axis=0)

xL, xR = ac*(xR-xL)/2, ac*(xR+xL)/2

xBest = [uniRand(xL, xR) for _ in range(M)]

xRand = [uniRand(*xRange, N) for _ in range((K-1)*M)]

cs = xBest + xRand

len(cs)

shuffle(cs)

cs = np.array(cs).reshape(K,M,N)

msg = f"最佳值为{best[0]}, 参数为"

msg += ", ".join([f"{x:.6f}" for x in best[1]])

print(msg)

最后，做个函数测试一下

def test(xs):

_sum = 0.0

for i in range(len(xs)):

_sum = _sum + np.cos((xs[i]*i)/5)*(i+1)

return _sum

if __name__ == "__main__":

cNum = [15,20,100]

s = wco(test, 20, 32, 5, (-20,20), 200)

效果为

>python wco.py

最佳值为-12.3236101211265, 参数为-11.129479, -14.625573, -8.625970, 15.884463, -3.383388