今日の落書き。Ruby/Tkで遺伝的アルゴリズムもどきを使って巡回セールスマンをやってみた。
あくまで「もどき」なので無性生殖しかしない。惜しいかな、素晴らしいイノベーションがあっても、他の長所を持つ他人と分かち合って化学反応を起こしたりしないのだ。
基本思いつきで書いてる部分が多いので、トンデモナイ間違いとかあるかも知れない。Windowsでも動く模様。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 |
require 'tk' #セールスマンの人数 SALESMEN = 300 #ポイントの数 POINTS = 30 #世代数 LASTG = 1000 #キャンバスの横幅 WIDTH = 300 #キャンバスの縦幅 HEIGHT = 300 class Salesman attr_accessor :gene def initialize(points) #遺伝子は座標の配列を、巡回する順にならべたもの #[[x1,y1],[x2,y2],[x3,y3],……[xmax],[ymax]] @gene = points.shuffle end #任意の2点を入れ替える def mutate_1 i, j = rand(POINTS), rand(POINTS) @gene[i],@gene[j] = @gene[i],@gene[j] end #隣の2点を入れ替える def mutate_2 i = rand(POINTS-1) # i は0〜48。49はNG注意 @gene[i],@gene[i+1] = @gene[i+1],@gene[i] end #1点だけ他の場所へ def mutate_3 i, j = rand(POINTS), rand(POINTS) temp = @gene.slice!(i) @gene.insert(j, temp) end #一部分を逆回転する def mutate_4 i = (Array.new(2){rand(POINTS)}).sort @gene[i[0]..i[1]] = @gene[i[0]..i[1]].reverse end #距離の合計を求める def score @gene.each_cons(2).inject(0) do |sum, (p1,p2)| x1, y1 = *p1; x2, y2 = *p2 sum + Math::sqrt(((x1-x2)**2) + ((y1-y2)**2)) end end #オブジェクトのコピー用 #Salesmanをcloneした時に、@geneの内容もコピーして生成する。 #これ書かないと、単にコピー元の@geneの参照が渡されてしまうみたい。 def initialize_copy(obj) @gene = obj.gene.dup end end class Company def initialize #巡回ポイントの座標 @points = Array.new(POINTS){[rand(WIDTH),rand(HEIGHT)]} #セールスマン詰め合わせ @pool = Array.new(SALESMEN){Salesman.new(@points)} #世代数 @generation = 1 #その時点での最高の遺伝子を保存用 @record = [] end attr_reader :generation, :record def checkResult #成績順に並べ替え @pool.sort_by!{|salesman| salesman.score} #最優秀遺伝子を記録 @record << @pool[0].gene.clone #下位1/20はトップと入れ替え @pool[-(@pool.size/20)..-1] = Array.new(@pool.size/20){@pool[0].clone} end def mutate #突然変異を行う @pool.each do |salesman| case rand(100)/100.0 when 0..0.05 salesman.mutate_1 when 0.05..0.25 salesman.mutate_2 when 0.25..0.30 salesman.mutate_3 when 0.30..0.35 salesman.mutate_4 end end end #最短記録が更新されたかチェック def new_champion? @record.last != @record[-2] end def best_gene @record.last end def tick @generation += 1 end def best_score @pool[0].score end end class ViewController def initialize @root = TkRoot.new(title:"Ruby/Tk 巡回セールスマン") @generation_label = TkLabel.new(@root).pack @canvas = TkCanvas.new(@root, width:WIDTH, height:HEIGHT).pack @button = TkButton.new(text:"スタート").pack @button.command proc{start} @company = Company.new end def start LASTG.times{round} end def round @company.checkResult if @company.new_champion? @generation_label.text = "#{@company.generation}:#{@company.best_score.round}" show(@company.best_gene) end @company.mutate @company.tick end def show(gene) @canvas.delete :all #線を引く TkcLine.new(@canvas, gene, fill: :red) #ポイントを□で描出 gene.each { |x,y| TkcRectangle.new(@canvas, x-3,y-3,x+3,y+3, fill: :white, outline: :red) } #↓これ入れておかないと表示されない Tk.update end end ViewController.new Tk.mainloop |