poj 2117 求割点的tarjan算法
用机器学习过滤微博

粒子群优化算法演示

scturtle posted @ 2011年11月12日 19:14 in algorithm , 2661 阅读

话说想写这个好久了,看大牛做过,直到昨天在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

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter