Module: Silicium::Optimization

Defined in:
lib/optimization.rb

Instance Method Summary collapse

Instance Method Details

#accept_annealing(z, min, t, d) ⇒ Object

return probability to accept



141
142
143
144
 
# File 'lib/optimization.rb', line 141

def accept_annealing(z, min, t, d)
  p = (min - z) / (d * t * 1.0)
  Math.exp(p)
end

#accuracy(step) ⇒ Object

calculate current accuracy in Hook - Jeeves method



54
55
56
57
58
 
# File 'lib/optimization.rb', line 54

def accuracy(step)
  acc = 0
  step.each { |a| acc += a * a }
  Math.sqrt(acc)
end

#annealing_cond(z, min, t, d) ⇒ Object

update current min and xm if cond



155
156
157
 
# File 'lib/optimization.rb', line 155

def annealing_cond(z, min, t, d)
  (z < min || accept_annealing(z, min, t, d) > rand(0.0..1.0))
end

#annealing_step(x, min_board, max_board) ⇒ Object

do one annealing step



147
148
149
150
151
152
 
# File 'lib/optimization.rb', line 147

def annealing_step(x, min_board, max_board)
  x += rand(-0.5..0.5)
  x = max_board if (x > max_board)
  x = min_board if (x < min_board)
  x
end

#bogosort(a) ⇒ Object

fastest(but it is not exactly) sort

Raises:

  • (ArgumentError) 


45
46
47
48
49
50
51
 
# File 'lib/optimization.rb', line 45

def bogosort(a)
  raise ArgumentError, "Nil array in bogosort" if a.nil?

  crutch = a
  (crutch = a.shuffle) until sorted?(crutch)
  crutch
end

#bogosort!(a) ⇒ Object

fastest(but it is not exactly) sort, modify sequance

Raises:

  • (ArgumentError) 


37
38
39
40
41
42
 
# File 'lib/optimization.rb', line 37

def bogosort!(a)
  raise ArgumentError, "Nil array in bogosort" if a.nil?

  a.shuffle! until sorted?(a)
  a
end

#determinant_sarryus(matrix) ⇒ Object

Find determinant 3x3 matrix

Raises:

  • (ArgumentError) 


133
134
135
136
137
138
 
# File 'lib/optimization.rb', line 133

def determinant_sarryus(matrix)
  raise ArgumentError, "Matrix size must be 3x3" if (matrix.row_count != 3 || matrix.column_count != 3)

  matrix[0, 0] * matrix[1, 1] * matrix[2, 2] + matrix[0, 1] * matrix[1, 2] * matrix[2, 0] + matrix[0, 2] * matrix[1, 0] * matrix[2, 1] -
    matrix[0, 2] * matrix[1, 1] * matrix[2, 0] - matrix[0, 0] * matrix[1, 2] * matrix[2, 1] - matrix[0, 1] * matrix[1, 0] * matrix[2, 2]
end

#half_division(a, b, eps = 0.001, &block) ⇒ Object

find root in [a, b], if he exist, if number of iterations > iters -> error



118
119
120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/optimization.rb', line 118

def half_division(a, b, eps = 0.001, &block)
  iters = 1000000
  c = middle(a, b)
  while (block.call(c).abs) > eps
    tmp = half_division_step(a, b, c, &block)
    a = tmp[0]
    b = tmp[1]
    c = tmp[2]
    iters -= 1
    raise RuntimeError, 'Root not found! Check does he exist, or change eps or iters' if iters == 0
  end
  c
end

#half_division_step(a, b, c, &block) ⇒ Object

do one half division step



106
107
108
109
110
111
112
113
114
115
 
# File 'lib/optimization.rb', line 106

def half_division_step(a, b, c, &block)
  if (block.call(a) * block.call(c)).negative?
    b = c
    c = middle(a, c)
  else
    a = c
    c = middle(b, c)
  end
  [a, b, c]
end

#hook_jeeves(x, step, eps = 0.1, &block) ⇒ Object

Hook - Jeeves method for find minimum point (x - array of start variables, step - step of one iteration, eps - allowable error, alfa - slowdown of step, block - function which takes array x, WAENING function doesn’t control correctness of input



84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/optimization.rb', line 84

def hook_jeeves(x, step, eps = 0.1, &block)
  prev_f = block.call(x)
  acc = accuracy(step)
  while (acc > eps)
    for i in 0..x.length - 1
      tmp = hook_jeeves_step(x, i, step, &block)
      cur_f = tmp[0]
      x[i] = tmp[1]
      step[i] = switch_step(cur_f, prev_f, step, i)
      prev_f = cur_f
    end
    acc = accuracy(step)
  end
  x
end

#hook_jeeves_step(x, i, step, &block) ⇒ Object

do one Hook - Jeeves step



61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/optimization.rb', line 61

def hook_jeeves_step(x, i, step, &block)
  x[i] += step[i]
  tmp1 = block.call(x)
  x[i] = x[i] - 2 * step[i]
  tmp2 = block.call(x)
  if (tmp1 > tmp2)
    cur_f = tmp2
  else
    x[i] = x[i] + step[i] * 2
    cur_f = tmp1
  end
  [cur_f, x[i]]
end

#integrating_Monte_Carlo_base(a, b, n = 100000, &block) ⇒ Object

integrating using method Monte Carlo (f - function, a, b - integrating limits, n - amount of random numbers)



16
17
18
19
20
21
22
23
24
 
# File 'lib/optimization.rb', line 16

def integrating_Monte_Carlo_base(a, b, n = 100000, &block)
  res = 0
  range = a..b.to_f
  (0..n).each do
    x = rand(range)
    res += (b - a) * 1.0 / n * block.call(x)
  end
  res
end

#karatsuba(num1, num2) ⇒ Object

Fast multiplication of num1 and num2.



179
180
181
182
183
184
185
186
187
188
189
190
191
192
 
# File 'lib/optimization.rb', line 179

def karatsuba(num1, num2)
  return num1 * num2 if num1 < 10 || num2 < 10

  max_size = [num1.to_s.length, num2.to_s.length].max

  first_half1, last_half1 = make_equal(num1, max_size)
  first_half2, last_half2 = make_equal(num2, max_size)

  t0 = karatsuba(last_half1, last_half2)
  t1 = karatsuba((first_half1 + last_half1), (first_half2 + last_half2))
  t2 = karatsuba(first_half1, first_half2)

  compute_karatsuba(t0, t1, t2, max_size / 2)
end

#middle(a, b) ⇒ Object

find centr of interval



101
102
103
 
# File 'lib/optimization.rb', line 101

def middle(a, b)
  (a + b) / 2.0
end

#re_lu(x) ⇒ Object

reflector function



6
7
8
 
# File 'lib/optimization.rb', line 6

def re_lu(x)
  x.negative? ? 0 : x
end

#sigmoid(x) ⇒ Object

sigmoid function



11
12
13
 
# File 'lib/optimization.rb', line 11

def sigmoid(x)
  1.0 / (1 + Math.exp(-x))
end

#simulated_annealing(min_board, max_board, t = 10000, &block) ⇒ Object

Annealing method to find min of function with one argument, between min_board max_board,



160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
# File 'lib/optimization.rb', line 160

def simulated_annealing(min_board, max_board, t = 10000, &block)
  d = Math.exp(-5) # Constant of annealing
  x = rand(min_board * 1.0..max_board * 1.0)
  xm = x
  min = block.call(x)
  while (t > 0.00001)
    x = xm
    x = annealing_step(x, min_board, max_board)
    z = block.call(x)
    if (annealing_cond(z, min, t, d))
      min = z
      xm = x
    end
    t *= 0.9999 # tempreture drops
  end
  xm
end

#sorted?(a) ⇒ Boolean

return true if array is sorted

Returns:

  • (Boolean) 


27
28
29
30
31
32
33
34
 
# File 'lib/optimization.rb', line 27

def sorted?(a)
  return false if a.nil?

  for i in 0..a.length - 2
    return false if (a[i + 1] < a[i])
  end
  true
end

#switch_step(cur_f, prev_f, step, i) ⇒ Object

switch step if current func value > previous func value



76
77
78
79
80
 
# File 'lib/optimization.rb', line 76

def switch_step(cur_f, prev_f, step, i)
  return step[i] / 2.0 if cur_f >= prev_f # you can switch 2.0 on something else

  step[i]
end