/
ga.rb
151 lines (135 loc) · 3.14 KB
/
ga.rb
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
$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