Eugene Kalenkovich
10/8/2007 4:31:00 AM
One more variation of GA theme. For mutationsd I use reversals only, with
variable lengths up to 1/2 of trip (+2). Apparently random shift also helps
a lot.
Additional twist to the algorithm, that works only for a limited problem
space (but works well) - population and productivity increase in time
exponentially. I've tried different rates of increase, **1 gives a realy
good speed in lucky cases, but miserable on bad ones. **2 is good, but
decreases speed of lucky ones too much. **1.5 seems to be a good compromise
(I am starting to think that "good enough", being a pragmatic one, should be
a Ruby slogan). I have no mathematical explanation/proof, but can expect
that magic number is either 1.5 or 1.(3) :)
I believe that result has a good balance between code simplicity and
performance (any volunteers to test performance of different solutions on
cases >7 ?)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
require 'enumerator'
require 'grid'
def distance(p1,p2,sqrt=true)
dist=((p1[0]-p2[0])**2 +(p1[1]-p2[1])**2)
sqrt ? Math::sqrt(dist) : dist
end
def length(path, sqrt=true)
len=distance(path[0],path[-1],sqrt)
path.each_cons(2) {|p1,p2| len+=distance(p1,p2,sqrt)}
len
end
def mutation(path,i)
len=path.length
rev=i%(len/2)+2
shift=rand(len-1)
pos=rand(len-rev)
newpts=path[shift..-1]+path[0...shift]
newpts[pos,rev]=newpts[pos,rev].reverse
newpts
end
num,pct=ARGV
num||=5
pct||=0
num=num.to_i
pct=pct.to_i
grid=Grid.new(num)
pass=grid.min+grid.min*pct/100.0+0.1
pathset=[grid.pts]
count=0
while (length(pathset[0])>pass) do
count+=1
newpaths=[]
sample=(count**1.5).round
pathset.each { |path| sample.times {|i| newpaths << mutation(path,i)} }
pathset=(pathset+newpaths).sort_by { |path|
length(path,false) }.first(sample)
puts "#{count}. #{length(pathset[0])}"
end
p pathset[0]