--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

08.25
Sat
遺伝的アルゴリズム的な的ななにかのようなものを使ってへんなことをしてみました。

遺伝的アルゴリズムというのは、その名の通り遺伝子を使って

問題を解決しようとするアルゴリズムです。

生き物が環境に適応していくような感じです。

おおまかな説明としては、遺伝子をもっている個体をいくらか作り

それら個体をその各々の遺伝子の通りになにかを行わせて

その行わせた結果がどれだけ解に近いか評価し、

評価がすぐれているもの同士交配したりし、次の世代の個体を作るなり

突然変異を起こさせるなり(この辺のやり方とか頻度はきっと実装によると思う)

して近似解を求めていくものです。

いろいろ間違ってるかもしれないので

詳しくは、遺伝的アルゴリズム

ここもわかりやすかったです

システムの最適化

これがどんなところに使われているかと言うと、

巡回セールスマン問題とか、

新幹線の空気抵抗を減らすような形を求めるために使われたりもしたようです。

ほかにもいろんな最適化問題に使われてると思います



で、なにをやったかというと、

適当に作った個体をある座標まで移動させるってものですww

どういうことかといいますと、まず初めに適当な遺伝子を持つ個体を直交座標の原点上に置きます

でそいつらを動かします。遺伝子がランダムに作られているので第一世代は

でたらめに動きます。でその個体の中で最も目標の座標に近づいた奴をどうたらこうたらしたり

他のやつらで交配して新しい遺伝子を作ったりとかして、次の世代を作ります。

それをずーっと繰り返してn世代目のもっとも目的地に近づいたやつの遺伝子を解とします

なんかやたら、終了までに時間かかったりしますが

突然変異とか交配の仕方とかがすんごい適当なのでそこが問題かなとか思います

この個体は自分の遺伝子にしたがって一度に8つの方向のうちどれかに進むことができます

右、左、下、上、右斜め上、右斜め下、左斜め上、左斜め下



#!/usr/bin/env python
#coding:utf-8


import random
import math

random.seed()

goal    = (6.0,4.0)
start   = (0.0,0.0)
x_speed = 1
y_speed = 1
ansgosa    = 0.1
gosa = 0.05
changeval = []
checkdis = 0
wid     = 8
individual_max = 51



sg_dis      = math.sqrt(math.pow(goal[1]-start[1],2) + math.pow(goal[0]-start[0] , 2))
maxdistance = x_speed if x_speed > y_speed else y_speed
operation   = genelength = sg_dis / maxdistance


metamorphose_p = 50
insertnew      = 100


def make_random_gene(length , width):return [random.randint(1,width) for d in xrange(int(length))]
    
def make_new_gene(gene1 , gene2):
    mask = []
    newgene_1 = []
    newgene_2 = []
    for d in range(len(gene1)):
        mask.append(random.randint(0,1))
    c = 0
    for each in mask:
        if each == 0:
            newgene_1.append(gene1[c])
            newgene_2.append(gene2[c])
        else:
            newgene_1.append(gene2[c])
            newgene_2.append(gene1[c])
        c+=1
    return newgene_1 , newgene_2
    
    
def eval(ins):
    return math.sqrt(math.pow(goal[0]-ins.pos_x,2) + math.pow(goal[1]-ins.pos_y,2))
    
def metamorphose(ins):
    ngene = []
    for each in ins.gene:
        if random.randint(0 , 1) == 1:
            ngene.append(wid-each+1)
        else:
            ngene.append(each)
    return individual(ngene)
            
def move(inses):map(lambda x: x.move() , inses)
    

def getmin(inses):
    mini = inses[0].distance
    index = 0
    counter = 0
    for e in inses:
        if e.distance < mini:
            mini = e.distance
            index = counter
        counter += 1
    return index
    
def analysis(gene):
    result = 0
    for each in gene:
        if ((each == 1)  or (each == 4)):
            result += x_speed
        elif ((each == 2) or (each == 5)):
            result += y_speed
        else:
            result += math.sqrt(x_speed*x_speed + y_speed*y_speed)
    return result
            
    
class individual:
    def __init__(self , gene = None):
        if not gene is None:
            self.gene = gene
        else:
            self.gene = make_random_gene(genelength , wid)
        self.pos_x = start[0]
        self.pos_y = start[1]
        self.distance = 0
        
    def move(self):
        for each in self.gene:
            if each == 1:
                self.pos_x += x_speed
            elif each == 2:
                self.pos_y += y_speed
            elif each == 3:
                self.pos_x += x_speed
                self.pos_y += y_speed
            elif each == 4:
                self.pos_x -= x_speed
            elif each == 5:
                self.pos_y -= y_speed
            elif each == 6:
                self.pos_x -= x_speed
                self.pos_y -= y_speed
            elif each == 7:
                self.pos_x += x_speed 
                self.pos_y -= y_speed
            else:
                self.pos_x -= x_speed
                self.pos_y += y_speed
        self.distance = eval(self)


firstgene_ins = [individual() for e in xrange(individual_max)]
move(firstgene_ins)
counter = 0

while True:
	top = firstgene_ins[getmin(firstgene_ins)]
	if abs(top.distance - checkdis) > gosa:changeval.append(counter)
	checkdis = top.distance
	print "%d Generation Top Gene" %(counter)
	print top.gene
	print "The distance = " , top.distance
	print "Percent of 1 = " , top.gene.count(1) * 100.0/genelength ,"%"
	print "Percent of 2 = " , top.gene.count(2) * 100.0/genelength ,"%"
	print "Percent of 3 = " , top.gene.count(3) * 100.0/genelength ,"%"
	print "Percent of 4 = " , top.gene.count(4) * 100.0/genelength ,"%"
	print "Percent of 5 = " , top.gene.count(5) * 100.0/genelength ,"%"
	print "Percent of 6 = " , top.gene.count(6) * 100.0/genelength ,"%"
	print "Percent of 7 = " , top.gene.count(7) * 100.0/genelength ,"%"
	print "Percent of 8 = " , top.gene.count(8) * 100.0/genelength ,"%"
	print 
	
	if top.distance <= ansgosa:break
	nextgeneration = []
	if random.randint(0 , metamorphose_p) == 1:top = metamorphose(top)
	nextgeneration.append(top)
	nextgeneration[0].pos_x = start[0]
	nextgeneration[0].pos_y = start[1]
	for d in range(individual_max/2):
		one , two = make_new_gene(firstgene_ins[random.randint(0,individual_max-1)].gene , firstgene_ins[random.randint(0,individual_max-1)].gene)
		nextgeneration.append(individual(one))
		nextgeneration.append(individual(two))
	if random.randint(0 , insertnew) == 1:
		del nextgeneration[random.randint(0,individual_max-1)]
		nextgeneration.append(individual())
	move(nextgeneration)
	firstgene_ins = nextgeneration
	counter += 1

print "----Calculation End----"
print "Generation:                " , counter
print "Top Gene:                  " , top.gene
print "Gene length:               " , len(top.gene)
print "End Position:               (%f , %f)" %(top.pos_x , top.pos_y)
print "Start Position:            " , start
print "Goal Position:             " , goal
print "Linear distance:           " , sg_dis
print "Locus:                     " , analysis(top.gene)
print "Metamorphose Probability:   %f" %(100.0/metamorphose_p) , "%"
print "Make new Probability:       %f" %(100.0/insertnew) , "%"
print "Gene Changed Generation:   " , changeval


間違い等あったら、コメント頂けると嬉しいです

(いつにも増してもうめっちゃコードが汚いしいろいろ適当すぎw)
スポンサーサイト

comment 0 trackback 0
トラックバックURL
http://telracsmoratori.blog.fc2.com/tb.php/129-e6d0818f
トラックバック
コメント
管理者にだけ表示を許可する
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。