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

01.01
Tue
あけましておもでとうございます。

2013年今年は巳年ということでPython年ですね

ということでPythonでなんか書きました

巡回セールスマン的なあれですはい



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

import math
import threading
import random
import copy

random.seed()

VARIETY = []
POSITION = "position"
NEWLINE  = "\n"
DATA = None
GENE_LEN = 0
INDIVIDUAL_NUMBER = 100     #個体の数
END_GENERATION = 4000000       #終了の世代数
TOP_GENE_INHERITANCE = 0.17 #トップの遺伝子とどれくらいの個体とが交叉させるかの確率
BASIC_PR = INDIVIDUAL_NUMBER * TOP_GENE_INHERITANCE  #具体的な個体数 
INCRATE = 0.9       #トップの遺伝子と交叉させるときの不確定な嵩増し分
NEWINDIVIDUAL = 150  #この世代毎にあたらしい個体を追加
KILL          = (INDIVIDUAL_NUMBER / 10) + 1 #上の世代のときにいくつの個体を殺して新しいのを入れるか

MIN_LOCUS = 0
MIN_GENE  = []


def cvrt(strple):
    t = strple.split(",")
    return [int(t[0].lstrip("(")) , int(t[1].rstrip(")"))]

def readposition(filename):
    data = open(filename , "r").readlines()
    if data[len(data)-1] == NEWLINE:del data[len(data)-1]
    return [cvrt(each.split(NEWLINE)[0]) for each in data]

def distance(pos1 , pos2):return math.sqrt(pow( pos1[0] - pos2[0] , 2) + pow(pos1[1] - pos2[1] , 2))

def numbering(data):
    return { index:each for index ,each in enumerate(data)}

def makenew():
    lst = range(1,GENE_LEN -1)
    random.shuffle(lst)
    lst.append(0)
    lst.insert(0 , 0)
    return lst

def crossing(gene1 , gene2):
    mask =[random.randint(0,1) for each in range(GENE_LEN-2)]
    vr = copy.deepcopy(VARIETY)
    result = []
    for index in range(GENE_LEN - 2):
        if mask[index] == 0:
            if not gene1[index+1] in vr:
                factor = random.choice(vr)
                vr.remove(factor)
                result.append(factor)
            else:
                result.append(gene1[index+1])
                vr.remove(gene1[index+1])
        else:
            if not gene2[index+1] in vr:
                factor = random.choice(vr)
                vr.remove(factor)
                result.append(factor)
            else:
                result.append(gene2[index+1])
                vr.remove(gene2[index+1])
    result.append(0)
    result.insert(0,0)
    return result



def nextgeneration(instances , generation_num):
    
    global MIN_LOCUS
    global MIN_GENE

    num = int(math.ceil(BASIC_PR + random.uniform(0.0 , INCRATE))) 
    gene = []
    min_locus = instances[0].locus
    min_gene  = instances[0].gene

    print "Top Gene: %s" %(min_gene)
    print "Distance: %s" %(min_locus)

    for each in instances:
        if min_locus > each.locus:
            min_locus = each.locus
            min_gene  = each.gene
   
    if MIN_LOCUS == 0 : 
        MIN_LOCUS = min_locus
        MIN_GENE  = min_gene
    else:
        if MIN_LOCUS > min_locus:
            MIN_LOCUS = min_locus
            MIN_GENE = min_gene

    for dummy in range(num):
        gene.append(crossing(min_gene , random.choice(instances).gene))
    
    for dummy in range(INDIVIDUAL_NUMBER - num):
        gene.append(crossing(random.choice(instances).gene , random.choice(instances).gene))
    
    if generation_num % NEWINDIVIDUAL == 0:
        for e in range(KILL):
            del gene[random.randint(0 , INDIVIDUAL_NUMBER - 1 - e)]
        for d in range(KILL):
            gene.append(makenew())
    
    return [ individual(False , gene = each) for each in gene] 


def higher_move(instances):
    for each in instances : each.move()



class individual:
    def __init__(self , is_initialize , gene = []):
        self.locus = 0
        if is_initialize:
            self.gene = makenew() 
        else:
            self.gene = gene

    def move(self):
        for each in range(GENE_LEN - 1):
            self.locus += distance(DATA[self.gene[each]] , DATA[self.gene[each+1]])

def main():
    global DATA
    global GENE_LEN
    global VARIETY

    DATA = numbering(readposition(POSITION)) 
    GENE_LEN = len(DATA)+1   
    VARIETY = range(1 , GENE_LEN - 1)
    GENERATION = 0
    l = [individual(True) for dummy in xrange(INDIVIDUAL_NUMBER)]
    higher_move(l)
    
    try:
        while True:
            print "Generation: %s" %(GENERATION)
            l = nextgeneration(l , GENERATION)
            higher_move(l)           

            if (GENERATION == END_GENERATION): break
            GENERATION += 1
    except:
        pass

    print "--END--"
    print "Most"
    print "Top Gene: %s" %(MIN_GENE)
    print "Top Locus: %s" %(MIN_LOCUS)




if __name__ == "__main__" : main()



スクリプトと同じディレクトリに以下みたいな感じで座標を書いたファイルをファイル名positionとして保存します

(0,0)
(1,2)
(1,7)
(2,4)
(2,9)
(4,2)
(4,6)
(4,8)
(5,4)
(6,1)
(7,6)
(7,8)
(8,1)
(8,3)
(9,5)
(9,9)
(10,2)
(10,8)
(11,6)


適当に実行してたら

Top Gene: [0, 1, 3, 2, 4, 7, 11, 15, 17, 18, 14, 10, 6, 8, 13, 16, 12, 9, 5, 0]
Top Locus: 47.0437205677


こんな感じになりました。これが一番近いかなたぶん。わかんない

この通りおえかきしてみました

手書きですが(汗

tspg.jpg
スポンサーサイト

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