算法 好玩的遗传算法。

rasefon · 2015年01月10日 · 最后由 love93hate 回复于 2018年08月27日 · 8098 次阅读

``````\$pm = 0.01
\$cluster_num = 20
\$result = nil

def gen_rands(n, lb, rb)
rands = []
n.times do
r = rand(lb..rb)
rands << r
end
rands
end

def gen_rands_arr(arr_num, n, lb, rb)
rands_arr = []
arr_num.times do
rands_arr << gen_rands(n, lb, rb)
end
rands_arr
end

def fit(sum, all_rands)
total_p = 0.0
curr_p_arr = []
all_rands.each do |rands|
curr_p = 0.0;
rands.each { |r| curr_p += r }
delta = sum-curr_p
if delta == 0
\$result=rands
return
end
curr_p = 1.0/(delta)
curr_p = curr_p.abs
curr_p_arr << curr_p
total_p += curr_p
end

fit_arr = []
fit_arr << curr_p_arr[0]/total_p
curr_p_arr.each_index do |i|
next if i == 0
fit_arr << fit_arr[i-1] + curr_p_arr[i]/total_p
end

fit_arr
end

def ga(sum, n, lb, rb)
rands_arr = gen_rands_arr(\$cluster_num, n, lb, rb)
fit_arr = fit(sum, rands_arr)
while \$result.nil?
fit_arr = fit(sum, rands_arr)
return unless \$result.nil?
selector_arr = []
\$cluster_num.times do
selector_arr << rand()
end

selected_rands_indexs = Array.new(\$cluster_num, 0)
selector_arr.each do |s|
# binary search
low = 0
high = fit_arr.size
while low <= high
middle = (low+high)/2
if fit_arr[middle] >= s
high = middle-1
else
low = middle+1
end
end
selected_rands_indexs[low] += 1
end

next_gen_rands_arr = []
k = 0
while k < \$cluster_num do
i = 0
while selected_rands_indexs[i] == 0
i += 1
end
selected_rands_indexs[i] -= 1

j = i+1
while selected_rands_indexs[j] == 0
j += 1
end
j = i if j == \$cluster_num
selected_rands_indexs[j] -= 1

next_gen_rands1 = []
next_gen_rands2 = []
# 随机交叉点
r1 = rand(0..n-1)
r2 = rand(0..n-1)
if r1 > r2
tmp = r1
r1 = r2
r2 = tmp
end

for ii in 0..(r1-1) do
next_gen_rands1[ii] = rands_arr[i][ii]
next_gen_rands2[ii] = rands_arr[j][ii]
end
for jj in (r2+1)..(n-1) do
next_gen_rands1[jj] = rands_arr[i][jj]
next_gen_rands2[jj] = rands_arr[j][jj]
end
# 交换基因
for kk in r1..r2 do
next_gen_rands1[kk] = rands_arr[j][kk]
next_gen_rands2[kk] = rands_arr[i][kk]
end
# 忽略修复重复基因

#新种群
next_gen_rands_arr[k] = next_gen_rands1
next_gen_rands_arr[k+1] = next_gen_rands2
k+=2
end

next_gen_rands_arr.each do |r|
#突变
pm = rand()
if pm < \$pm
#发生突变
#突变点
pi = rand(0..n-1)
new_rand = rand(lb..rb)
r[pi] = new_rand
end
end
rands_arr = next_gen_rands_arr

rands_arr.each do |rands|
curr_p=0
rands.each { |r| curr_p += r }
delta = sum-curr_p
if delta == 0
\$result=rands
return
end
end
end
end

ga 80000, 100, 4, 1300
p \$result.sort

``````