首页 > 学术百科

差分进化算法DE和粒子算法PSO

差分进化算法DE和粒⼦算法PSO

1.差分进化算法(DE)

DE与GA的主要区别在变异步骤。

对于每个⽬标向量 X i，G (i=1，2，……，NP)，基本DE算法的变异向量如下产⽣

其中，随机选择的序号r1，r2和r3互不相同，且r1，r2和r3与⽬标向量序号i也应不同，所以须满⾜NP≥4。变异算⼦F∈[0，2]是⼀个实常数因数，控制偏差变量的放⼤作⽤。

实现如下。由于此⽬标过于简单，即便去掉交叉步，也能得到不错的结果。

# coding: utf8

import numpy as np

N=20 # 编码长度

MAX=10.0/(2**(N)) # [0,10), 区间内有两个最⼤值（17）的点

NUM=500 # 种数量

def f(x): # 函数

return 10*np.sin(5*x) + s(4*x)

def new(num=NUM,len=N): # 随机⽣成

return np.random.randint(1,2**len,num)

def n2b(nums): # 数字编码

return [bin(i)[2:].zfill(N) for i in nums]

def b2n(bits): # 解码

return [int(i,base=2) for i in bits]

def fit(nums,s_rate=0.15,r_rate=0.05): # 适应度和选择

n=len(nums)

sn=int(n*s_rate)

on=int(n*r_rate)

np.random.shuffle(nums)

outs=nums[:on]

res=[f(i*MAX) for i in nums] # 适应度选择和随机选择，可能有重复

temp=np.argsort(res)

others=[nums[i] for i in temp[-sn:]]

atenate((outs, others))

return outs,nums[temp[-1]]*MAX,res[temp[-1]]

def repo(fits,mode='DE'): # 扩增，此处5倍；增加了进化算法

n=len(fits)

pt=np.random.randint(0,n,4*n)

shape(pt,(2*n,2))

bits=n2b(fits)

new_bits=bits

for i in pt:

b1,b2=exchange([bits[j] for j in i])

new_bits.append(b1)

new_bits.append(b2)

if mode=='DE':

return dmut(new_bits)

return mut(new_bits)

def exchange(bits,change_rate=0.4,mode='cross'): #交换，提供了随机交换和节点互换

n=int(change_rate*N)

if mode=='rand':

rn=range(N)

new_bits=[list(i) for i in bits]

for i in rn[:n]:

new_bits[0][i] = bits[1][i]

new_bits[1][i] = bits[0][i]

new_bits=[''.join(i) for i in new_bits]

else:

n = int(change_rate * N)

new_bits = [list(i) for i in bits]

new_bits[0][:n] = bits[1][:n]鼻渊散

new_bits[1][:n] = bits[0][:n]

中华口腔医学网new_bits = [''.join(i) for i in new_bits]

return new_bits

def mut(bits,mut_rate=0.03): # 变异

length=len(bits)*N

n = int(mut_rate * length)

if n<1: n=1

rn = range(length)

np.random.shuffle(rn)

for i in rn[:n]:

j=int(bits[i/N][i%N])

bits[i/N]=swap(bits[i/N],i%N,str(1-j)) return bits

def swap(str,i,char): # 字符串交换

str2=list(str)

str2[i]=char

return''.join(str2)

def dmut(bits,mut_rate=1.0,F=0.5): # 差分变异 length = len(bits)

n = int(mut_rate * length)

if n < 1: n = 1

rn = np.random.randint(0,length,3*n)

rn = np.reshape(rn,(n,3))

nums=b2n(bits)

for i in rn:

nums[i[0]]+=int(F*(nums[i[1]]-nums[i[2]])) if nums[i[0]]<0:

nums[i[0]]*=-1

return n2b(nums)

def train(iter=50): # 训练⼊⼝

nums=new()

outs,x,fx=fit(nums)

for i in range(iter):

过程能力指数

new_bits = repo(outs)

nums=b2n(new_bits)

outs,x,fx=fit(nums)

print i,x,fx

if'__main__==main()':

train()

"""

0 1.57093048096 16.9999967425

1 1.5707015991

2 16.9999983758

2 1.57070159912 16.9999983758

3 1.57086372375 16.9999991778

4 1.57078742981 16.9999999857

5 1.57078742981 16.9999999857

6 1.57079696655 16.9999999999

7 1.57079696655 16.9999999999

8 1.57079696655 16.9999999999

9 1.57079696655 16.9999999999

10 1.57079696655 16.9999999999

11 1.57079696655 16.9999999999

12 1.57079696655 16.9999999999

13 1.57079696655 16.9999999999

14 1.57079696655 16.9999999999

15 1.57079696655 16.9999999999

16 1.57079696655 16.9999999999

17 1.57079696655 16.9999999999

18 1.57079696655 16.9999999999

19 1.57079696655 16.9999999999

20 1.57079696655 16.9999999999

21 1.57079696655 16.9999999999

22 1.57079696655 16.9999999999

23 1.57079696655 16.9999999999

24 1.57079696655 16.9999999999

25 1.57079696655 16.9999999999

26 1.57079696655 16.9999999999

27 1.57079696655 16.9999999999

28 1.57079696655 16.9999999999

29 1.57079696655 16.9999999999

30 1.57079696655 16.9999999999

31 1.57079696655 16.9999999999

32 1.57079696655 16.9999999999

33 1.57079696655 16.9999999999

34 1.57079696655 16.9999999999

35 1.57079696655 16.9999999999

36 1.57079696655 16.9999999999

37 1.57079696655 16.9999999999

38 1.57079696655 16.9999999999

39 1.57079696655 16.9999999999

40 1.57079696655 16.9999999999

41 1.57079696655 16.9999999999

42 1.57079696655 16.9999999999

43 1.57079696655 16.9999999999

44 1.57079696655 16.9999999999

45 1.57079696655 16.9999999999

46 1.57079696655 16.9999999999

47 1.57079696655 16.9999999999

48 1.57079696655 16.9999999999

49 1.57079696655 16.9999999999

"""

2.粒⼦算法

描述

⼀鸟在随机的搜索⾷物。区域⾥只有⼀块⾷物，所有的鸟都不知道⾷物在哪，但是它们知道⾃⼰当前的位置距离⾷物还有多远。那么到⾷物的最优策略是什么？

最简单有效的就是搜寻⽬前离⾷物最近的鸟的周围区域。鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒⼦I 在N维空间的位置表⽰为⽮量Xi＝(x1，x2，…，xN)，飞⾏速度表⽰为⽮量Vi＝(v1，v2，…，vN)。每个粒⼦都有⼀个由⽬标函数决定的适应值，并且知道⾃⼰到⽬前为⽌发现的最好位置(pbest)和现在的位置Xi，这个可以看作是粒⼦⾃⼰的飞⾏经验。除此之外，每个粒⼦还知道到⽬前为⽌整个体中所有粒⼦发现的最好位置(gbest)，这个可以看作是粒⼦同伴的经验。粒⼦就是通过⾃⼰的经验和同伴中最好的经验来决定下⼀步的运动。

速度向量迭代公式：

Vi=wVi+c1r1(pbesti−Xi)+c2r2(gbest−Xi)

Xi=Xi+Vi

pbest和gbest分别表⽰微粒的局部和全局最优位置。

c1和c2称为是学习因⼦，⼀般设置为2。

r1和r2为介于[0,1]之间的随机概率值。

参数w为PSO的惯性权重，介于[0,1]之间。本例中，w为0即可较快得到结果。

如果w<<1，从前的运动状态很少能影响当前的⾏为，粒⼦的速度会很快的改变；相反，w较⼤，虽然会有很⼤的搜索空间，但是粒⼦很难改变其运动⽅向，很难向较优位置收敛，由于算法速度的因素，在实际运⽤中很少这样设置。因此，较⾼的w设置促进全局搜索，较低的w设置促进快速的局部搜索。

标准PSO算法的流程：

Step1: 初始化⼀微粒(体规模为m)，包括随机位置和速度；

Step2: 评价每个微粒的适应度；

Step3: 对每个微粒，将其适应值与其经过的最好位置 pbest作⽐较，如果较好，则将其作为当前的最好位置pbest;

Step4: 对每个微粒，将其适应值与其经过的最好位置 gbest作⽐较，如果较好，则将其作为当前的最好位置gbest;

Step5: 根据(2)、(3)式调整微粒速度和位置；

Step6: 未达到结束条件则转Step2。

迭代终⽌条件根据具体问题⼀般选为最⼤迭代次数Gk或(和)微粒迄今为⽌搜索到的最优位置满⾜预定最⼩适应阈值。

以下为所选Schaffer F6测试函数的图像，[0,1]间有多个极值点，最⼤值为1。魅族e3c

# coding: utf8mm理论

import numpy as np

MAX = 10000

NUM = 100

D = 2

c1 = 2

c2 = 2

ERR = 1e-6

W = 0.0 # 此处为0效果合适

class Particle:

pass

def f6(x): # F6测试函数

a = (np.sin(np.sqrt(x[0]**2 + x[1]**2)))**2 - 0.5

b = (1.0 + 0.001 * (x[0]**2 + x[1]**2))**2

f6 = 0.5 - (a/b)

err = 1 - f6

return f6, err

all = []

for i in range(NUM):

p = Particle()

#p.x= np.random.random(D) # 效果差很多

p.x = np.array([np.random.random() for i in range(D)])

p.fit = 0.0

p.v = 0.0

all.append(p)

gbest = all[0]

err = 1e6

for i in range(MAX) :

for p in all:

fit,err = f6(p.x)

if fit > p.fit:

p.fit = fit

p.best = p.x

在可可西里回头if fit > gbest.fit:

gbest = p

r1,r2=np.random.random(2)

p.v = W *p.v + c1 *r1 * (p.best - p.x) + c2 * r2 * (gbest.x - p.x)

p.x = p.x + p.v

if err < ERR:

break

print'best fit= {0}, best x= {1}, iter= {2}'.format(gbest.fit,gbest.x, i+1)

3.⽐较

转⾃博⽂。

遗传算法、粒⼦算法、差分进化算法的⼀些指标分别进⾏分析现归纳如下：

（1）编码标准 GA 采⽤⼆进制编码，PSO、DE 都采⽤实数编码，近年来许多学者通过整数编码将GA 算法、PSO 算法应⽤与求解离散型问题，特别是 0-1 ⾮线性优化为题，整数规划问题、混合整数规划问题，⽽离散的 DE 算法则研究的⽐较少，⽽采⽤混合编码技术的 DE 算法则研究更少.

（2）参数设置问题 DE 算法主要有两个参数要调整，⽽且参数设置对结果影响不太明显，因此更容易使⽤.相对于 GA 和 PSO 算法的参数过多，不同的参数设置对最终结果影响也⽐较⼤，因此在实际使⽤中，要不断调整，加⼤了算法的使⽤难度．⾼维问题在实际问题中，由于转化为个体的向量维数⾮常⾼，因此算法对⾼维问题的处理，将是很重要的.只有很好的处理⾼维问题，算法才能很好的应⽤于实际问题.

（3）⾼维问题 GA 对⾼维问题收敛速度很慢甚⾄很难收敛，但是 PSO 和 DE 则能很好解决.尤其是DE 算法，收敛速度很快⽽且结果很精确.

（4）收敛性能对于优化问题，相对 GA，DE 和 PSO 算法收敛速度⽐较快，但是 PSO 容易陷⼊局部最优解，⽽且算法不稳定.

（5）应⽤⼴泛性由于 GA 算法发明⽐较早，因此应⽤领域⽐较⼴泛，PSO 算法⾃从发明以来，已成为研究热点问题，这⽅⾯应⽤也⽐较多，⽽ DE 算法近⼏年才引起⼈们的关注⽽且算法性能好，因此应⽤领域将会增多.

本文发布于:2024-09-22 15:32:16，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/358859.html

上一篇：显式中心差分法

下一篇：计算一阶导数的四阶中心差分格式