module Silicium::Optimization

Public Instance Methods

accept_annealing(z, min, t, d) click to toggle source

return probability to accept

# 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) click to toggle source

calculate current accuracy in Hook - Jeeves method

# 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) click to toggle source

update current min and xm if cond

# 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) click to toggle source

do one annealing step

# 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) click to toggle source

fastest(but it is not exactly) sort

# 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) click to toggle source

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

# 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) click to toggle source

Find determinant 3x3 matrix

# 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) click to toggle source

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

# 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) click to toggle source

do one half division step

# 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) click to toggle source

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

# 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) click to toggle source

do one Hook - Jeeves step

# 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) click to toggle source

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

# 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) click to toggle source

Fast multiplication of num1 and num2.

# 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) click to toggle source

find centr of interval

# File lib/optimization.rb, line 101
def middle(a, b)
  (a + b) / 2.0
end
re_lu(x) click to toggle source

reflector function

# File lib/optimization.rb, line 6
def re_lu(x)
  x.negative? ? 0 : x
end
sigmoid(x) click to toggle source

sigmoid function

# 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) click to toggle source

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

# 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) click to toggle source

return true if array is sorted

# 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) click to toggle source

switch step if current func value > previous func value

# 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

Private Instance Methods

compute_karatsuba(tp0, tp1, tp2, num) click to toggle source

Helper for karatsuba method. Computes the result of karatsuba's multiplication.

# File lib/optimization.rb, line 204
def compute_karatsuba(tp0, tp1, tp2, num)
  tp2 * 10**(2 * num) + ((tp1 - tp0 - tp2) * 10**num) + tp0
end
make_equal(num, size) click to toggle source

Helper for karatsuba method. Divides num into two halves.

# File lib/optimization.rb, line 197
def make_equal(num, size)
  mid = (size + 1) / 2
  string = num.to_s.rjust(size, '0')
  [string.slice(0...mid).to_i, string.slice(mid..-1).to_i]
end