L-systemとな

http://www14.ocn.ne.jp/~kk62526/Lsys/
なんかすごいやつっぽい。遺伝的アルゴリズムでグラフの文法エンコードが使えるとか使えないとか

def lsystem(a):
    if a==0:
        return "F"
    str = lsystem(a-1)
    result=[]
    for x in str:
        if x=="F": result.append("F-F++F-F")
        else: result.append(x)
    return ''.join(result)

inp = input("step:")
print lsystem(inp)

Traveling Salesman Problem 2

昨日の巡回セールスマン問題何かがおかしいと思ってたら、案の定Processing側のコードがおかしかったわけです。

10地点(Simulated Annealing + Genetic Algorithm)
117世代0.00313452861531　が最大適応度

50地点(Simulated Annealing + Genetic Algorithm)

まだ50地点は最短距離ではないですが、ある程度はまとまって来てると思います。50地点の最短距離っぽいのができたら、とりあえず、一つの完成としたいですね。

50地点は、もう一度計算中です

Traveling Salesman Problem 1

巡回セールスマン問題を遺伝的アルゴリズムを使って計算してみています。

ちょっとまだ、きれいな解が得られてないので、途中経過だけ残しておこうかと。

【適応度変化のグラフ】

なんかグラフ的には、厳しい感じに見えますが、絵にしてみると

【巡回の図】

なんか、全然だめなんですよね。ただ
【初期の頃】

なんか、ひょっとすると、Processingあたりでミスってる可能性とかあるんでヤバい感じある。適応度的には2倍程度は距離が縮んでるはずなんですよね

mac os mountain lionにXamarin入れるのに苦労した話

C#使うことになって、それまで「C#？ふーん」くらいしか気にしてなかったのですが、ググってみるとXamarinっていうのが使えるってことらしいんですね。
http://xamarin.com/download
こっからインストールできるわけですが、インストールすると、

こんな感じでいかにも「これ押せば入れられるんだぜ？」って感じにInstallerがおいてあるわけですが、押してみると

ん？No error？とか思いながら、ログファイルを開いてみると、以下らへんが怪しいってことになるんですね。

[2013-10-04 09:59:12.200] [Exception] Failed to detect component 'Android SDK'
[2013-10-04 09:59:12.200] [Exception] System.NullReferenceException: Object reference not set to an instance of an object
[2013-10-04 09:59:12.200] [Exception] at Xamarin.Web.Installer.Installer.AndroidSoftwareItem.Detect () [0x00000] in <filename unknown>:0
[2013-10-04 09:59:12.200] [Exception] at Xamarin.Web.Installer.Installer.AndroidSoftwareItem.NeedsUpdate () [0x00000] in <filename unknown>:0
[2013-10-04 09:59:12.200] [Exception] at Xamarin.Web.Installer.TasksManager.ComponentDetector (ISoftwareItem si) [0x00000] in <filename unknown>:0
[2013-10-04 09:59:12.201] [Error] No selected SDK, cannot enqueue downloads

ググってみると、
http://xamarin.vanillaforums.com/discussion/1496/xamarin-failing-to-install
これが出てきて、要するにAndroid SDKを「~/Library/Developer/Xamarin/android-sdk-mac_x86」に置いとけってことらしいので、そこに持っていってみたが、なんかうまく動かず、気分で

cd /volumes/Xamarin\ Installer/Install\ Xamarin.app/contents/macos

で、

sudo ./Install\ Xamarin

で、適当にぽちぽち押してたら、なんか知らないけどできるっ！

それだけです。

遺伝的アルゴリズムで遊ぶ 2

突然変異つけないと話にならないので、つけました。ようやくスタートライン一歩手前ですかね

# coding: utf-8
import random
import copy

generation = []
population_size = 10
chrom_size = 10
mutation_rate = 1 
def initialize():
    global population_size
    global generation
    for i in range(population_size):
       chrom = []
       for j in range(chrom_size):
            chrom.append(random.randint(0,1))
       generation.append(chrom)

def fitness(indiv):
    global population_size
    count = 0.0
    for x in indiv:
        if x==1: count+=1
    if count <= 5: return 0.5
    return count/population_size

# 一点交叉
def crossover(p1, p2):
    if len(p1)>len(p2): maximum = len(p2)-1
    else: maximum = len(p1) - 1
    point = random.randint(0,maximum)
    for i in range(point,maximum+1):
        x = p1[i]
        p1[i] = p2[i]
        p2[i] = x
    return p1, p2

# バブルソート
def calculate_fit():
    global generation
    k = len(generation) - 1
    for i in range(k):
        for j in xrange(k,i,-1):
            if fitness(generation[j-1])>fitness(generation[j]):
                t = generation[j-1]
                generation[j-1] = generation[j]
                generation[j] = t
            
        
def simple_crossover():
    global generation
    max = len(generation)-1
    select1 = random.randint(0,max)
    select2 = random.randint(0,max)
    while select1==select2:
        select2 = random.randint(0,max)
    p1 = generation[select1]
    p2 = generation[select2]
    p1,p2 = crossover(p1,p2)
    # fitnessの高い方を返す
    if fitness(p1)>fitness(p2): return p1
    return p2

def fitness_average():
    global generation
    global population_size
    total = 0.0
    for x in generation:
        total += fitness(x)
    return total / population_size

def dump_chrom(gene_count):
    global generation
    print "%d世代" % gene_count
    for x in generation:
        for y in x:
            print y,
        print 
    print "\n"

def mutation(p1,rate, num):
    if num > len(p1):num=len(p1)
    if (rate>1) or (rate<0): return
    if random.randint(0,100)/100.0 <= rate:
        for i in range(num):
            point = random.randint(0,len(p1)-1)
            p1[point] = random.randint(0,1)
    return p1

def simple_mutation():
    return mutation(copy.deepcopy(generation[population_size-1]), 0.91, 5)
    


def main():
    global generation
    global population_size
    global mutation_rate
    initialize()
    calculate_fit()
    for i in range(population_size):
        next_generation = []
        next_generation.append(copy.deepcopy(generation[population_size-1]))
        for j in range(population_size-1-mutation_rate):
            next_generation.append(simple_crossover())
        for k in range(j+1, population_size-1):
            next_generation.append(simple_mutation())
        generation = copy.deepcopy(next_generation)
        calculate_fit()
        for x in generation[population_size-1]:
            print x,
        print fitness_average()
        #dump_chrom(i)
        

if __name__ == '__main__':
    main()

まぁこの程度だと、あんまり違いが分かりませんが。

0 1 1 1 0 1 1 1 0 1 0.57
0 1 1 0 1 1 0 1 1 1 0.6
0 1 1 1 1 1 1 0 0 1 0.61
0 1 1 1 1 1 1 1 1 1 0.77
0 1 1 1 1 1 1 1 1 1 0.79
1 1 1 1 0 1 1 1 1 1 0.79
0 1 1 1 1 1 1 1 1 1 0.81
1 1 1 1 1 1 1 1 1 1 0.8
1 1 1 1 1 1 1 1 1 1 0.88
1 1 1 1 1 1 1 1 1 1 0.93

一番右の値は全体の個体の適応度の平均値です。

遺伝的アルゴリズムで遊ぶ 1

　学校の文化祭的なので、AI作ろうという流れになって、以前から少し興味を持ちつつ先延ばししてた遺伝的アルゴリズムに本格的に手をつけようと本を読んでいます。で、すごい簡易的ですが、交叉だけで遊んでみたので。。

# coding: utf-8
import random

generation = []
def initialize():
    global generation
    for i in range(10):
       chrom = []
       for j in range(10):
            chrom.append(random.randint(0,1))
       generation.append(chrom)

def fitness(indiv):
    count = 0
    for x in indiv:
        if x==1: count+=1
    if count <= 5: return 0.5
    return count/10.0

# 一点交叉
def crossover(p1, p2):
    max = len(p1) - 1
    point = random.randint(0,max)
    x = p1[point]
    p1[point] = p2[point]
    p2[point] = x
    return p1, p2

# バブルソート
def calculate_fit():
    global generation
    k = len(generation) - 1
    for i in range(k):
        for j in xrange(k,i,-1):
            if fitness(generation[j-1])>fitness(generation[j]):
                t = generation[j-1]
                generation[j-1] = generation[j]
                generation[j] = t
            
        
def simple_crossover():
    max = len(generation)-1
    select1 = random.randint(0,max)
    select2 = random.randint(0,max)
    while select1==select2:
        select2 = random.randint(0,max)
    p1 = generation[select1]
    p2 = generation[select2]
    p1,p2 = crossover(p1,p2)
    # fitnessの高い方を返す
    if fitness(p1)>fitness(p2): return p1
    return p2


def main():
    global generation
    initialize()
    calculate_fit()
    for i in range(10):
        next_generation = []
        next_generation.append(generation[9])
        next_generation.append(generation[8])
        for j in range(8):
            next_generation.append(simple_crossover())
        generation = next_generation
        calculate_fit()
        for x in generation[9]:
            print x,
        print "\n"

if __name__ == '__main__':
    main()

ゴミみたいなプログラムですが。。。。

出力は

% python ga_test1.py
1 1 0 1 1 0 1 1 0 1 

1 1 1 1 1 0 1 0 0 1 

0 1 1 0 1 1 1 1 1 1 

1 1 1 0 0 1 1 1 1 1 

1 1 1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 1 1 1 

うまく行くとこんな感じになりますが、うまくいかないとゴミですし、そもそもやってることが（ry

現実逃避

期末が近いという理由だけで現実逃避に変な計算してました。題して「某ソシャゲに使った体力に関するアレ」てきな。

某ソシャゲでは、体力は3分で1回回復します。僕は無課金ですから、まあ基本的にこの時間回復だけが頼りなはずなわけなのです。で、ちょっと適当にPCあさってたら今年の7/26のデータがあってそのときのレベルが140だったっぽいのです。現在（9/1の17時）では、レベルが148で経験値が5574たまっています。このソシャゲでは、レベルアップのための経験値がレベルが上がるごとに高くなっていくので（ある意味当たり前ですが）、単純計算で、当時レベル140の経験値0だったと仮定して、現在まで使った体力を計算してみると（この数値は経験値テーブルがネットに落ちてるのでそっからとってきました）

4650+4755+4860+5065+5270+5475+5680+5885+5574 = 47214 
(lv140→141に必要な経験値+lv141→142に必要な経験値+...+lv146→147に必要な経験値+現在の経験値)

となります。つまり、体力は47214消費されているということになります。イベントなどでは大抵6ずつ減って、そうじゃないときは7〜9奪われる某ソシャゲですが、まぁ、少なくとも5300回くらい生産性なく画面をタッチしたということになります。

で、ですね。7/26から、9/1までの時間回復を計算してみると

38*24*60/3 = 18240 (単純回復）
47214 - 18240 = 28974 (ファッ！？）

と、明らかに時間回復だけでは、間に合わないことになるんです。まぁ、この某ソシャゲでは、無料で大量に『体力半分回復アイテム』が配られます。僕の体力はずいぶん前から300だったので、とりあえずたぶん7/26でも体力が300だったと仮定すると（多分そうです）、体力半分回復アイテムで150回復できるため、

28974-300*7 = 26874(レベルアップ回復を抜いた）
26874/150 = 179.16(体力半分回復を使った回数）

つまり、180個くらいの体力半分アイテムを使ったことになります（記憶によると多分8月中は5回くらい、体力全回復まで触らなかったことがあってそこのロスを考えると、もう少し使ってるかもしれません）。

結論として

生産性のないソシャゲはやらないにこしたことはないでしょう。そして、生産性のないこのような計算もやらないにこしたことはないでしょう