probabilistic algos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Probabilistic Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bayesian Optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":onemax"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def onemax(vector)\n",
    "  return vector.inject(0){|sum, value| sum + value}\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":random_bitstring"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def random_bitstring(size)\n",
    "  return Array.new(size){ ((rand()<0.5) ? 1 : 0) }\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":path_exists?"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def path_exists?(i, j, graph)\n",
    "  visited, stack = [], [i]\n",
    "  while !stack.empty?\n",
    "    return true if stack.include?(j)\n",
    "    k = stack.shift\n",
    "    next if visited.include?(k)\n",
    "    visited << k\n",
    "    graph[k][:out].each {|m| stack.unshift(m) if !visited.include?(m)}    \n",
    "  end\n",
    "  return false\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":can_add_edge?"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def can_add_edge?(i, j, graph)\n",
    "  return !graph[i][:out].include?(j) && !path_exists?(j, i, graph)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":get_viable_parents"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_viable_parents(node, graph)\n",
    "  viable = []\n",
    "  graph.size.times do |i|\n",
    "    if node!=i and can_add_edge?(node, i, graph)\n",
    "      viable << i\n",
    "    end\n",
    "  end\n",
    "  return viable\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":compute_count_for_edges"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def compute_count_for_edges(pop, indexes)\n",
    "  counts = Array.new(2**(indexes.size)){0}\n",
    "  pop.each do |p|\n",
    "    index = 0\n",
    "    indexes.reverse.each_with_index do |v,i|\n",
    "      index += ((p[:bitstring][v] == 1) ? 1 : 0) * (2**i)\n",
    "    end\n",
    "    counts[index] += 1\n",
    "  end\n",
    " return counts\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":fact"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fact(v)\n",
    "  return v <= 1 ? 1 : v*fact(v-1)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":k2equation"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def k2equation(node, candidates, pop)\n",
    "  counts = compute_count_for_edges(pop, [node]+candidates)\n",
    "  total = nil\n",
    "  (counts.size/2).times do |i|\n",
    "    a1, a2 = counts[i*2], counts[(i*2)+1]\n",
    "    rs = (1.0/fact((a1+a2)+1).to_f) * fact(a1).to_f * fact(a2).to_f\n",
    "    total = (total.nil? ? rs : total*rs)\n",
    "  end\n",
    "  return total\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":compute_gains"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def compute_gains(node, graph, pop, max=2)\n",
    "  viable = get_viable_parents(node[:num], graph)\n",
    "  gains = Array.new(graph.size) {-1.0}\n",
    "  gains.each_index do |i|\n",
    "    if graph[i][:in].size < max and viable.include?(i)\n",
    "      gains[i] = k2equation(node[:num], node[:in]+[i], pop)\n",
    "    end\n",
    "  end\n",
    "  return gains\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":construct_network"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def construct_network(pop, prob_size, max_edges=3*pop.size)\n",
    "  graph = Array.new(prob_size) {|i| {:out=>[], :in=>[], :num=>i} }\n",
    "  gains = Array.new(prob_size)  \n",
    "  max_edges.times do\n",
    "    max, from, to = -1, nil, nil\n",
    "    graph.each_with_index do |node, i|\n",
    "      gains[i] = compute_gains(node, graph, pop)\n",
    "      gains[i].each_with_index {|v,j| from,to,max = i,j,v if v>max}\n",
    "    end\n",
    "    break if max <= 0.0\n",
    "    graph[from][:out] << to\n",
    "    graph[to][:in] << from\n",
    "  end\n",
    "  return graph\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":topological_ordering"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def topological_ordering(graph)\n",
    "  graph.each {|n| n[:count] = n[:in].size}\n",
    "  ordered,stack = [], graph.select {|n| n[:count]==0}  \n",
    "  while ordered.size < graph.size\n",
    "    current = stack.shift\n",
    "    current[:out].each do |edge|\n",
    "      node = graph.find {|n| n[:num]==edge}\n",
    "      node[:count] -= 1\n",
    "      stack << node if node[:count] <= 0\n",
    "    end\n",
    "    ordered << current\n",
    "  end\n",
    "  return ordered\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":marginal_probability"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def marginal_probability(i, pop)\n",
    "  return pop.inject(0.0){|s,x| s + x[:bitstring][i]} / pop.size.to_f\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":calculate_probability"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def calculate_probability(node, bitstring, graph, pop)\n",
    "  return marginal_probability(node[:num], pop) if node[:in].empty?\n",
    "  counts = compute_count_for_edges(pop, [node[:num]]+node[:in])\n",
    "  index = 0\n",
    "  node[:in].reverse.each_with_index do |v,i|\n",
    "    index += ((bitstring[v] == 1) ? 1 : 0) * (2**i)\n",
    "  end  \n",
    "  i1 = index + (1*2**(node[:in].size))\n",
    "  i2 = index + (0*2**(node[:in].size)) \n",
    "  a1, a2 = counts[i1].to_f, counts[i2].to_f\n",
    "  return a1/(a1+a2)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":probabilistic_logic_sample"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def probabilistic_logic_sample(graph, pop)\n",
    "  bitstring = Array.new(graph.size)\n",
    "  graph.each do |node|\n",
    "    prob = calculate_probability(node, bitstring, graph, pop)\n",
    "    bitstring[node[:num]] = ((rand() < prob) ? 1 : 0)\n",
    "  end\n",
    "  return {:bitstring=>bitstring}\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":sample_from_network"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sample_from_network(pop, graph, num_samples)\n",
    "  ordered = topological_ordering(graph)  \n",
    "  samples = Array.new(num_samples) do\n",
    "    probabilistic_logic_sample(ordered, pop)\n",
    "  end\n",
    "  return samples\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":search"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def search(num_bits, max_iter, pop_size, select_size, num_children)\n",
    "  pop = Array.new(pop_size) { {:bitstring=>random_bitstring(num_bits)} }\n",
    "  pop.each{|c| c[:cost] = onemax(c[:bitstring])}\n",
    "  best = pop.sort!{|x,y| y[:cost] <=> x[:cost]}.first\n",
    "  max_iter.times do |it|    \n",
    "    selected = pop.first(select_size)\n",
    "    network = construct_network(selected, num_bits)\n",
    "    arcs = network.inject(0){|s,x| s+x[:out].size}\n",
    "    children = sample_from_network(selected, network, num_children)\n",
    "    children.each{|c| c[:cost] = onemax(c[:bitstring])}\n",
    "    #children.each {|c| puts \" >>sample, f=#{c[:cost]} #{c[:bitstring]}\"}\n",
    "    pop = pop[0...(pop_size-select_size)] + children\n",
    "    pop.sort! {|x,y| y[:cost] <=> x[:cost]}\n",
    "    best = pop.first if pop.first[:cost] >= best[:cost]\n",
    "    #puts \" >it=#{it}, arcs=#{arcs}, f=#{best[:cost]}, [#{best[:bitstring]}]\"\n",
    "    converged = pop.select {|x| x[:bitstring]!=pop.first[:bitstring]}.empty?\n",
    "    break if converged or best[:cost]==num_bits\n",
    "  end\n",
    "  return best\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done! Solution:\n",
      "f=19/20\n",
      " s=[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "# problem configuration\n",
    "num_bits = 20\n",
    "\n",
    "# algorithm configuration\n",
    "max_iter = 100\n",
    "pop_size = 50\n",
    "select_size = 15\n",
    "num_children = 25\n",
    "\n",
    "# execute the algorithm\n",
    "best = search(num_bits, max_iter, pop_size, select_size, num_children)\n",
    "puts \"done! Solution:\",\"f=#{best[:cost]}/#{num_bits}\",\" s=#{best[:bitstring]}\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Compact Genetic Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":onemax"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def onemax(vector)\n",
    "  return vector.inject(0){|sum, value| sum + value}\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":generate_candidate"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def generate_candidate(vector)\n",
    "  candidate = {}\n",
    "  candidate[:bitstring] = Array.new(vector.size)\n",
    "  vector.each_with_index do |p, i|\n",
    "    candidate[:bitstring][i] = (rand()<p) ? 1 : 0\n",
    "  end\n",
    "  candidate[:cost] = onemax(candidate[:bitstring])\n",
    "  return candidate\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":update_vector"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def update_vector(vector, winner, loser, pop_size)\n",
    "  vector.size.times do |i|  \n",
    "    if winner[:bitstring][i] != loser[:bitstring][i]\n",
    "      if winner[:bitstring][i] == 1\n",
    "        vector[i] += 1.0/pop_size.to_f\n",
    "      else \n",
    "        vector[i] -= 1.0/pop_size.to_f\n",
    "      end\n",
    "    end\n",
    "  end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":search"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def search(num_bits, max_iterations, pop_size)\n",
    "  vector = Array.new(num_bits){0.5}\n",
    "  best = nil\n",
    "  max_iterations.times do |iter|\n",
    "    c1 = generate_candidate(vector)\n",
    "    c2 = generate_candidate(vector)\n",
    "    winner, loser = (c1[:cost] > c2[:cost] ? [c1,c2] : [c2,c1])\n",
    "    best = winner if best.nil? or winner[:cost]>best[:cost]\n",
    "    update_vector(vector, winner, loser, pop_size)\n",
    "    #puts \" >iteration=#{iter}, f=#{best[:cost]}, s=#{best[:bitstring]}\"\n",
    "    break if best[:cost] == num_bits\n",
    "  end\n",
    "  return best\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done! Solution:\n",
      "f=32/32\n",
      "s=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "# problem configuration\n",
    "num_bits = 32\n",
    "\n",
    "# algorithm configuration\n",
    "max_iterations = 200\n",
    "pop_size = 20\n",
    "\n",
    "# execute the algorithm\n",
    "best = search(num_bits, max_iterations, pop_size)\n",
    "puts \"done! Solution:\",\"f=#{best[:cost]}/#{num_bits}\",\"s=#{best[:bitstring]}\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cross-Entropy Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":objective_function"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def objective_function(vector)\n",
    "  return vector.inject(0.0) {|sum, x| sum +  (x ** 2.0)}\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":random_variable"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def random_variable(minmax)\n",
    "  min, max = minmax\n",
    "  return min + ((max - min) * rand())\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":random_gaussian"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def random_gaussian(mean=0.0, stdev=1.0)\n",
    "  u1 = u2 = w = 0\n",
    "  begin\n",
    "    u1 = 2 * rand() - 1\n",
    "    u2 = 2 * rand() - 1\n",
    "    w = u1 * u1 + u2 * u2\n",
    "  end while w >= 1\n",
    "  w = Math.sqrt((-2.0 * Math.log(w)) / w)\n",
    "  return mean + (u2 * w) * stdev\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":generate_sample"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def generate_sample(search_space, means, stdevs)\n",
    "  vector = Array.new(search_space.size)\n",
    "  search_space.size.times do |i|\n",
    "    vector[i] = random_gaussian(means[i], stdevs[i])\n",
    "    vector[i] = search_space[i][0] if vector[i] < search_space[i][0]\n",
    "    vector[i] = search_space[i][1] if vector[i] > search_space[i][1]\n",
    "  end\n",
    "  return {:vector=>vector}\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":mean_attr"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def mean_attr(samples, i)\n",
    "  sum = samples.inject(0.0) do |s,sample| \n",
    "    s + sample[:vector][i]\n",
    "  end \n",
    "  return (sum / samples.size.to_f)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":stdev_attr"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def stdev_attr(samples, mean, i)\n",
    "  sum = samples.inject(0.0) do |s,sample| \n",
    "    s + (sample[:vector][i] - mean)**2.0\n",
    "  end \n",
    "  return Math.sqrt(sum / samples.size.to_f)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":update_distribution!"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def update_distribution!(samples, alpha, means, stdevs)\n",
    "  means.size.times do |i|\n",
    "    means[i] = alpha*means[i] + ((1.0-alpha)*mean_attr(samples, i))\n",
    "    stdevs[i] = alpha*stdevs[i]+((1.0-alpha)*stdev_attr(samples,means[i],i))\n",
    "  end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":search"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def search(bounds, max_iter, num_samples, num_update, learning_rate)\n",
    "  means = Array.new(bounds.size){|i| random_variable(bounds[i])}\n",
    "  stdevs = Array.new(bounds.size){|i| bounds[i][1]-bounds[i][0]}\n",
    "  best = nil\n",
    "  max_iter.times do |iter|\n",
    "    samples = Array.new(num_samples){generate_sample(bounds, means, stdevs)}\n",
    "    samples.each {|samp| samp[:cost] = objective_function(samp[:vector])}\n",
    "    samples.sort!{|x,y| x[:cost]<=>y[:cost]}\n",
    "    best = samples.first if best.nil? or samples.first[:cost] < best[:cost]\n",
    "    selected = samples.first(num_update)\n",
    "    update_distribution!(selected, learning_rate, means, stdevs)\n",
    "    #puts \" > iteration=#{iter}, fitness=#{best[:cost]}\"\n",
    "  end\n",
    "  return best\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done! Solution: \n",
      "f=2.0511013646169462e-18\n",
      "s=[1.2934784391249768e-09, -4.819400717021263e-10, 3.81770427644035e-10]\n"
     ]
    }
   ],
   "source": [
    "# problem configuration\n",
    "problem_size = 3\n",
    "search_space = Array.new(problem_size) {|i| [-5, 5]}\n",
    "\n",
    "# algorithm configuration\n",
    "max_iter = 100\n",
    "num_samples = 50\n",
    "num_update = 5\n",
    "l_rate = 0.7\n",
    "\n",
    "# execute the algorithm\n",
    "best = search(search_space, max_iter, num_samples, num_update, l_rate)\n",
    "puts \"done! Solution: \",\"f=#{best[:cost]}\",\"s=#{best[:vector].inspect}\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Population-Based Incremental Learning (PBIL)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":onemax"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def onemax(vector)\n",
    "  return vector.inject(0){|sum, value| sum + value}\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":generate_candidate"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def generate_candidate(vector)\n",
    "  candidate = {}\n",
    "  candidate[:bitstring] = Array.new(vector.size)\n",
    "  vector.each_with_index do |p, i|\n",
    "    candidate[:bitstring][i] = (rand()<p) ? 1 : 0\n",
    "  end\n",
    "  return candidate\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":update_vector"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def update_vector(vector, current, lrate)\n",
    "  vector.each_with_index do |p, i|\n",
    "    vector[i] = p*(1.0-lrate) + current[:bitstring][i]*lrate\n",
    "  end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":mutate_vector"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def mutate_vector(vector, current, coefficient, rate)\n",
    "  vector.each_with_index do |p, i|\n",
    "    if rand() < rate\n",
    "      vector[i] = p*(1.0-coefficient) + rand()*coefficient\n",
    "    end\n",
    "  end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":search"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def search(num_bits, max_iter, num_samples, p_mutate, mut_factor, l_rate)\n",
    "  vector = Array.new(num_bits){0.5}\n",
    "  best = nil\n",
    "  max_iter.times do |iter|\n",
    "    current = nil\n",
    "    num_samples.times do \n",
    "      candidate = generate_candidate(vector)\n",
    "      candidate[:cost] = onemax(candidate[:bitstring])\n",
    "      current = candidate if current.nil? or candidate[:cost]>current[:cost]\n",
    "      best = candidate if best.nil? or candidate[:cost]>best[:cost]\n",
    "    end\n",
    "    update_vector(vector, current, l_rate)\n",
    "    mutate_vector(vector, current, mut_factor, p_mutate)\n",
    "    #puts \" >iteration=#{iter}, f=#{best[:cost]}, s=#{best[:bitstring]}\"\n",
    "    break if best[:cost] == num_bits\n",
    "  end\n",
    "  return best\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done! Solution:\n",
      "f=64/64\n",
      "s=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "# problem configuration\n",
    "num_bits = 64\n",
    "\n",
    "# algorithm configuration\n",
    "max_iter = 100\n",
    "num_samples = 100\n",
    "p_mutate = 1.0/num_bits\n",
    "mut_factor = 0.05\n",
    "l_rate = 0.1\n",
    "\n",
    "# execute the algorithm\n",
    "best=search(num_bits, max_iter, num_samples, p_mutate, mut_factor, l_rate)\n",
    "puts \"done! Solution:\",\"f=#{best[:cost]}/#{num_bits}\",\"s=#{best[:bitstring]}\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Univariate Marginal Distribution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":onemax"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def onemax(vector)\n",
    "  return vector.inject(0){|sum, value| sum + value}\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":random_bitstring"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def random_bitstring(size)\n",
    "  return Array.new(size){ ((rand()<0.5) ? 1 : 0) }\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":binary_tournament"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def binary_tournament(pop)\n",
    "  i, j = rand(pop.size), rand(pop.size)\n",
    "  j = rand(pop.size) while j==i\n",
    "  return (pop[i][:fitness] > pop[j][:fitness]) ? pop[i] : pop[j]\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":calculate_bit_probabilities"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def calculate_bit_probabilities(pop)\n",
    "  vector = Array.new(pop.first[:bitstring].length, 0.0)\n",
    "  pop.each do |member|\n",
    "    member[:bitstring].each_with_index {|v, i| vector[i] += v}\n",
    "  end\n",
    "  vector.each_with_index {|f, i| vector[i] = (f.to_f/pop.size.to_f)}\n",
    "  return vector\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":generate_candidate"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def generate_candidate(vector)\n",
    "  candidate = {}\n",
    "  candidate[:bitstring] = Array.new(vector.size)\n",
    "  vector.each_with_index do |p, i|\n",
    "    candidate[:bitstring][i] = (rand()<p) ? 1 : 0\n",
    "  end\n",
    "  return candidate\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":search"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def search(num_bits, max_iter, pop_size, select_size)\n",
    "  pop = Array.new(pop_size) do\n",
    "    {:bitstring=>random_bitstring(num_bits)}\n",
    "  end\n",
    "  pop.each{|c| c[:fitness] = onemax(c[:bitstring])}\n",
    "  best = pop.sort{|x,y| y[:fitness] <=> x[:fitness]}.first\n",
    "  max_iter.times do |iter|\n",
    "    selected = Array.new(select_size) { binary_tournament(pop) }\n",
    "    vector = calculate_bit_probabilities(selected)\n",
    "    samples = Array.new(pop_size) { generate_candidate(vector) }\n",
    "    samples.each{|c| c[:fitness] = onemax(c[:bitstring])}\n",
    "    samples.sort!{|x,y| y[:fitness] <=> x[:fitness]}\n",
    "    best = samples.first if samples.first[:fitness] > best[:fitness]\n",
    "    pop = samples\n",
    "    #puts \" >iteration=#{iter}, f=#{best[:fitness]}, s=#{best[:bitstring]}\"\n",
    "  end\n",
    "  return best\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "done! Solution:\n",
      "f=60\n",
      "s=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "# problem configuration\n",
    "num_bits = 64\n",
    "\n",
    "# algorithm configuration\n",
    "max_iter = 100\n",
    "pop_size = 50\n",
    "select_size = 30\n",
    "\n",
    "# execute the algorithm\n",
    "best = search(num_bits, max_iter, pop_size, select_size)\n",
    "puts \"done! Solution:\",\"f=#{best[:fitness]}\",\"s=#{best[:bitstring]}\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Ruby 2.2.5",
   "language": "ruby",
   "name": "ruby"
  },
  "language_info": {
   "file_extension": ".rb",
   "mimetype": "application/x-ruby",
   "name": "ruby",
   "version": "2.2.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}