sa.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Simulated Annealing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "VERSION = v\"1.5.3\"\n"
     ]
    }
   ],
   "source": [
    "@show VERSION\n",
    "using BenchmarkTools, Random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "qinit = [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0]\n",
      "Einit = 5.0\n",
      "\n",
      "Tfinal = 0.01989046877970967\n",
      "q = [-1.0, 1.0, 1.0, 1.0, 1.0, -1.0, 1.0, -1.0]\n",
      "E = -27.0\n"
     ]
    }
   ],
   "source": [
    "#適当なコスト関数を設定。今回は8変数使いました。\n",
    "\n",
    "function energy(a)\n",
    "  return a[1]*a[2]-2*a[2]*a[3]+3*a[1]-4*a[4]-5*a[5]+6*a[6]*a[5]+5*a[6]-a[7]+a[8]+a[7]*a[2]\n",
    "end\n",
    "\n",
    "#変数の数\n",
    "N = 8\n",
    "\n",
    "#初期温度\n",
    "T = 100.0\n",
    "#減衰\n",
    "r = 0.99\n",
    "#終了温度\n",
    "Tf = 0.02\n",
    "#温度あたりのイテレーションの数\n",
    "ite = 10\n",
    "\n",
    "#全て1で初期化\n",
    "q = ones(N)\n",
    "println(\"qinit = \",q)\n",
    "\n",
    "#エネルギーを表示\n",
    "println(\"Einit = \",energy(q))\n",
    "\n",
    "function run(T, r, Tf, q, ite)\n",
    "    N = length(q)\n",
    "    #温度が終了温度以上の場合、\n",
    "    while T > Tf\n",
    "        for i=1:ite\n",
    "            x = rand(1:N)\n",
    "            qq = copy(q)\n",
    "            qq[x] *= -1\n",
    "\n",
    "            #エネルギー差を計算\n",
    "            dx = energy(qq) - energy(q)\n",
    "\n",
    "            #評価\n",
    "            if exp(dx/T) < rand()\n",
    "              q = copy(qq)\n",
    "            end\n",
    "        end\n",
    "        #温度を下げる\n",
    "        T *= r\n",
    "    end\n",
    "    return T, q\n",
    "end\n",
    "\n",
    "Tf_, qf = run(T, r, Tf, q, N)\n",
    "#最終温度、もとまった変数の値、エネルギーの値を表示\n",
    "println()\n",
    "println(\"Tfinal = \",Tf_)\n",
    "println(\"q = \",qf)\n",
    "println(\"E = \",energy(qf))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "BenchmarkTools.Trial: \n",
       "  memory estimate:  1.16 MiB\n",
       "  allocs estimate:  8484\n",
       "  --------------\n",
       "  minimum time:     629.208 μs (0.00% GC)\n",
       "  median time:      654.708 μs (0.00% GC)\n",
       "  mean time:        674.542 μs (2.10% GC)\n",
       "  maximum time:     1.463 ms (53.41% GC)\n",
       "  --------------\n",
       "  samples:          7399\n",
       "  evals/sample:     1"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@benchmark run(T, r, Tf, q, ite)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Tfinal = 0.01989046877970967\n",
      "q = [-1.0, 1.0, 1.0, 1.0, 1.0, -1.0, 1.0, -1.0]\n",
      "E = -27.0\n"
     ]
    }
   ],
   "source": [
    "function run_opt!(q, T::Float64, r::Float64, Tf::Float64, ite, rng)\n",
    "    N = length(q)\n",
    "    #温度が終了温度以上の場合、\n",
    "    ene = energy(q)\n",
    "    while T > Tf\n",
    "        for i=1:ite\n",
    "            x = rand(rng, 1:N)\n",
    "            q[x] *= -1\n",
    "            \n",
    "            #エネルギー差を計算 (注: エネルギー差を直接計算すればさらにコストは下がる)\n",
    "            ene_prop = energy(q)\n",
    "            dx = ene_prop - ene\n",
    "\n",
    "            #評価\n",
    "            if exp(dx/T) < rand(rng)\n",
    "                ene = ene_prop\n",
    "            else\n",
    "                q[x] *= -1\n",
    "            end\n",
    "        end\n",
    "        #温度を下げる\n",
    "        T *= r\n",
    "    end\n",
    "    return T\n",
    "end\n",
    "\n",
    "q = ones(N)\n",
    "rng = MersenneTwister(4649)\n",
    "Tf_ = run_opt!(q, T, r, Tf, ite, rng)\n",
    "#最終温度、もとまった変数の値、エネルギーの値を表示\n",
    "println()\n",
    "println(\"Tfinal = \",Tf_)\n",
    "println(\"q = \",q)\n",
    "println(\"E = \",energy(qf))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "BenchmarkTools.Trial: \n",
       "  memory estimate:  16 bytes\n",
       "  allocs estimate:  1\n",
       "  --------------\n",
       "  minimum time:     286.458 μs (0.00% GC)\n",
       "  median time:      294.125 μs (0.00% GC)\n",
       "  mean time:        297.584 μs (0.00% GC)\n",
       "  maximum time:     521.875 μs (0.00% GC)\n",
       "  --------------\n",
       "  samples:          10000\n",
       "  evals/sample:     1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rng = MersenneTwister(4649)\n",
    "q = ones(N)\n",
    "@benchmark run_opt!(q, T, r, Tf, ite, rng)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.5.2",
   "language": "julia",
   "name": "julia-1.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}