粒子群优化算法演示
scturtle
posted @ 2011年11月12日 19:14
in algorithm
, 3647 阅读
话说想写这个好久了,看大牛做过,直到昨天在twitter上看到有人在iPad上用Codify(Codea)实现了,确实好玩,这才随便找了点资料开工。
算法意想之外的简单,模拟鸟群的行动,每个鸟根据离目标最近的那个鸟的位置调整自己的方向。实现的效果是点追随鼠标汇聚。效果没有意想中的那么好,不知是不是有bug,参数设置的不好的时候不能汇聚或者其他诡异行为,╮(╯_╰)╭。
update at 2011.11.13:设置了最小最大速率参数后,果然效果好多了
代码很简单:
# coding: utf-8 import pygame from pygame.locals import * from myvector import Vector, distance # 向量类 from random import random pygame.init() SIZE=(640, 480) screen = pygame.display.set_mode(SIZE) pygame.display.set_caption('pso test') clock = pygame.time.Clock() FPS = 60 # 帧率 speed = 0.1 # 调整速度 w = 0.7 # 惯性权重 c1 = c2 = 2 # 学习因子 minv = 10 # 最小速度 maxv = 50 # 最大速度 def sig(x): return x/abs(x) #======================================================# class Bird: def __init__(self): self.v=Vector(random()-0.5,random()-0.5) self.pos=Vector(SIZE[0]*random(),SIZE[1]*random()) self.bestpos=self.pos def update(self, dt, mpos, gbestpos): global speed,w,c1,c2,minv,maxv # 更新速度和位置的公式 self.v = self.v*w + ((self.bestpos-self.pos)*random()*c1 +\ (gbestpos-self.pos)*random()*c2) # 限制最小最大速度 self.v = Vector(sig(self.v[0]) * max(abs(self.v[0]), minv),\ sig(self.v[1]) * max(abs(self.v[1]), minv)) self.v = Vector(sig(self.v[0]) * min(abs(self.v[0]), maxv),\ sig(self.v[1]) * min(abs(self.v[1]), maxv)) # 更新位置 self.pos += self.v * speed * dt /(1000.0/FPS) # 更新个体最优位置 if distance(self.pos, mpos) < distance(self.bestpos, mpos): self.bestpos = self.pos def paint(self,screen): pygame.draw.circle(screen,(255,0,0), map(int,self.pos), 2) #======================================================# birds=[ Bird() for i in xrange(200)] pygame.event.set_allowed([QUIT]) while True: for event in pygame.event.get(): if event.type == QUIT: exit() dt = clock.tick(FPS) # 目标位置 mpos = pygame.mouse.get_pos() mpos = Vector(*mpos) # 更新种群最优位置 gbestpos = min(birds,key=lambda b: distance(b.pos,mpos)).pos screen.fill((255, 255, 255)) # 更新每个个体 for b in birds: b.update(dt ,mpos, gbestpos) b.paint(screen) pygame.display.update()
为了实现方便的写的向量类:
class Vector: def __init__(self,x=0,y=0): self.val=[float(x),float(y)] def __getitem__(self,key): return self.val[key] def __setitem__(self,key,value): self.val[key]=value def __str__(self): return '('+str(self[0])+', '+str(self[1])+')' def __add__(self,v): return Vector(self[0]+v[0],self[1]+v[1]) def __sub__(self,v): return Vector(self[0]-v[0],self[1]-v[1]) def __div__(self,n): return Vector(self[0]/n,self[1]/n) def __mul__(self,n): return Vector(self[0]*n,self[1]*n) def __iadd__(self,v): self[0]+=v[0] self[1]+=v[1] return self def __isub__(self,v): self[0]-=v[0] self[1]-=v[1] return self def __idiv__(self,n): self[0]/=n self[1]/=n return self def __imul__(self,n): self[0]*=n self[1]*=n return self def distance(v1,v2): return ((v1[0]-v2[0])*(v1[0]-v2[0]) +\ (v1[1]-v2[1])*(v1[1]-v2[1])) if __name__ == '__main__': v1=Vector(1,2) v2=Vector(2,1) print v1+v2