今日の落書き Ruby/Tkで巡回セールスマン１

今日の落書き。Ruby/Tkで遺伝的アルゴリズムもどきを使って巡回セールスマンをやってみた。
あくまで「もどき」なので無性生殖しかしない。惜しいかな、素晴らしいイノベーションがあっても、他の長所を持つ他人と分かち合って化学反応を起こしたりしないのだ。
基本思いつきで書いてる部分が多いので、トンデモナイ間違いとかあるかも知れない。Windowsでも動く模様。

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

  #任意の２点を入れ替える
  def mutate_1
    i, j = rand(POINTS), rand(POINTS)
    @gene[i],@gene[j] = @gene[i],@gene[j]
  end

  #隣の２点を入れ替える
  def mutate_2
    i = rand(POINTS-1) # i は0〜48。49はNG注意
    @gene[i],@gene[i+1] = @gene[i+1],@gene[i]
  end

  #１点だけ他の場所へ
  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

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

#任意の２点を入れ替える

def mutate_1

i, j = rand(POINTS), rand(POINTS)

@gene[i],@gene[j] = @gene[i],@gene[j]

end

#隣の２点を入れ替える

def mutate_2

i = rand(POINTS-1) # i は0〜48。49はNG注意

@gene[i],@gene[i+1] = @gene[i+1],@gene[i]

end

#１点だけ他の場所へ

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

#オブジェクトのコピー用

#Salesmanをcloneした時に、@geneの内容もコピーして生成する。

#これ書かないと、単にコピー元の@geneの参照が渡されてしまうみたい。

def initialize_copy(obj)

@gene = obj.gene.dup

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

#最短記録が更新されたかチェック

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

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

ViewController.new

Tk.mainloop

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル