(************** Content-type: application/mathematica **************
                     CreatedBy='Mathematica 4.2'

                    Mathematica-Compatible Notebook

This notebook can be used with any Mathematica-compatible
application, such as Mathematica, MathReader or Publicon. The data
for the notebook starts with the line containing stars above.

To get the notebook into a Mathematica-compatible application, do
one of the following:

* Save the data starting with the line of stars above into a file
  with a name ending in .nb, then open the file inside the
  application;

* Copy the data starting with the line of stars above to the
  clipboard, then use the Paste menu command inside the application.

Data for notebooks contains only printable 7-bit ASCII and can be
sent directly in email or through ftp in text mode.  Newlines can be
CR, LF or CRLF (Unix, Macintosh or MS-DOS style).

NOTE: If you modify the data for this notebook not in a Mathematica-
compatible application, you must delete the line below containing
the word CacheID, otherwise Mathematica-compatible applications may
try to use invalid cache data.

For more information on notebooks and Mathematica-compatible 
applications, contact Wolfram Research:
  web: http://www.wolfram.com
  email: info@wolfram.com
  phone: +1-217-398-0700 (U.S.)

Notebook reader applications are available free of charge from 
Wolfram Research.
*******************************************************************)

(*CacheID: 232*)


(*NotebookFileLineBreakTest
NotebookFileLineBreakTest*)
(*NotebookOptionsPosition[     16893,        393]*)
(*NotebookOutlinePosition[     17595,        417]*)
(*  CellTagsIndexPosition[     17551,        413]*)
(*WindowFrame->Normal*)



Notebook[{
Cell["\<\
Metropolis Monte Carlo simulation of points uniformly in the unit square.  \
(To test our simulation, we estimate the area of the unit circle by counting \
the number of points landing in the circle)\
\>", "Text",
  FontSize->18],

Cell[BoxData[{
    \(x = 0.0; y = 0.0; nincircle = 0; 
    ptlist = Table[{0, 0}, {10000}];\), "\[IndentingNewLine]", 
    \(\(Do[\[IndentingNewLine]th = Random[]*2*Pi; \[IndentingNewLine]xtemp = 
          x + 0.8*Cos[th]; \[IndentingNewLine]ytemp = 
          y + 0.8*Sin[th]; \[IndentingNewLine]If[
          xtemp > 1.0\  || \ xtemp\  < \ \(-1.0\)\  || \ 
            ytemp\  > \ 1.0\  || \ 
            ytemp\  < \ \(-1.0\), \[IndentingNewLine]x = x; y = y; 
          ptlist[\([i]\)] = {x + Random[]*0.02, y + Random[]*0.02}, 
          x = xtemp; y = ytemp; 
          ptlist[\([i]\)] = {x, y}\[IndentingNewLine]]; \[IndentingNewLine]If[
          x^2 + y^2 < 1, nincircle = nincircle + 1], \[IndentingNewLine]{i, 
          1, 10000}\[IndentingNewLine]];\)\), "\[IndentingNewLine]", 
    \(\(Print["\<Estimate of circle area is \>", 
        nincircle/10000. *4];\)\), "\[IndentingNewLine]", 
    \(\(plot1 = 
        ListPlot[ptlist, AspectRatio \[Rule] Automatic, 
          DisplayFunction \[Rule] Identity];\)\), "\[IndentingNewLine]", 
    \(\(plot2 = 
        ParametricPlot[{Cos[t], Sin[t]}, {t, 0, 2*Pi}, 
          PlotStyle \[Rule] RGBColor[1, 0, 0], 
          DisplayFunction \[Rule] Identity];\)\), "\[IndentingNewLine]", 
    \(Show[plot1, plot2, 
      DisplayFunction \[Rule] $DisplayFunction]\)}], "Input",
  FontSize->10],

Cell["\<\
Here's what would have happened if we hadn't kept an extra copy of points \
when they were rejected.  (Note the incorrect estimation of area of circle, \
bias away from edges of square)\
\>", "Text",
  FontSize->18],

Cell[BoxData[{
    \(x = 0.0; y = 0.0; ptlist = Table[{0, 0}, {10000}]; nincircle = 0; 
    ntot = 0;\), "\[IndentingNewLine]", 
    \(\(While[
        ntot < 10000, \[IndentingNewLine]th = 
          Random[]*2*Pi; \[IndentingNewLine]xtemp = 
          x + 0.8*Cos[th]; \[IndentingNewLine]ytemp = 
          y + 0.8*Sin[th]; \[IndentingNewLine]If[
          xtemp <= 1.0\  && \ xtemp\  >= \ \(-1.0\)\  && \ 
            ytemp\  <= \ 1.0\  && \ 
            ytemp\  >= \ \(-1.0\), \[IndentingNewLine]x = xtemp; y = ytemp; 
          If[x^2 + y^2 < 1, 
            nincircle = nincircle + 1]; \[IndentingNewLine]ntot = ntot + 1; 
          ptlist[\([ntot]\)] = {x, 
              y}\[IndentingNewLine]]\[IndentingNewLine]];\)\), "\
\[IndentingNewLine]", 
    \(\(Print["\<Estimate of circle area is \>", 
        nincircle/ntot*4. ];\)\), "\[IndentingNewLine]", 
    \(\(plot1 = 
        ListPlot[ptlist, AspectRatio \[Rule] Automatic, 
          DisplayFunction \[Rule] Identity];\)\), "\[IndentingNewLine]", 
    \(\(plot2 = 
        ParametricPlot[{Cos[t], Sin[t]}, {t, 0, 2*Pi}, 
          PlotStyle \[Rule] RGBColor[1, 0, 0], 
          DisplayFunction \[Rule] Identity];\)\), "\[IndentingNewLine]", 
    \(Show[plot1, plot2, 
      DisplayFunction \[Rule] $DisplayFunction]\)}], "Input",
  FontSize->10],

Cell["Now consider a double-well energy function E", "Text",
  FontSize->18],

Cell[BoxData[
    \(Clear[x]; en[x_] = x^4 - x^2 + 0.1*x; 
    Plot[en[x], {x, \(-2\), 2}, PlotRange \[Rule] {\(-0.5\), 1}]\)], "Input"],

Cell[TextData[{
  "Use Metropolis Monte Carlo to simulate the probability density ",
  Cell[BoxData[
      \(TraditionalForm\`\[ExponentialE]\^\(\(-\(E(x)\)\)/T\)\)]],
  ".  (Moves are random change in x between -1 and 1)."
}], "Text",
  FontSize->18],

Cell[BoxData[{
    \(Clear[x]; en[x_] = x^4 - x^2 + 0.1*x; x = 0.0; T =  .05; npts = 5000; 
    xlist = Table[0, {npts}];\), "\[IndentingNewLine]", 
    \(\(Do[\[IndentingNewLine]dx = Random[]*2 - 1; \[IndentingNewLine]xtemp = 
          x + dx; \[IndentingNewLine]If[
          en[xtemp] < en[x], \[IndentingNewLine]\ \ x = 
            xtemp, \[IndentingNewLine]\ \ p = Random[]; 
          If[p < \[ExponentialE]\^\(\(-\((en[xtemp] - en[x])\)\)/T\), 
            x = xtemp, 
            x = x];\[IndentingNewLine]]; \[IndentingNewLine]xlist[\([i]\)] = 
          x, \[IndentingNewLine]{i, 1, 
          npts}\[IndentingNewLine]];\)\)}], "Input",
  FontSize->12],

Cell["\<\
First we plot the position of the Metropolis \"walk\" versus time.\
\>", "Text",
  FontSize->18],

Cell[BoxData[
    \(ListPlot[xlist, PlotJoined \[Rule] True, 
      PlotRange \[Rule] {\(-2\), 2}]\)], "Input",
  FontSize->14],

Cell["\<\
Now make a histogram of the position of the Metropolis \"walk\" versus step \
in the algorithm.\
\>", "Text",
  FontSize->18],

Cell[BoxData[{
    \(<< Graphics`Graphics`\), "\[IndentingNewLine]", 
    \(Histogram[xlist]\)}], "Input",
  FontSize->14],

Cell[TextData[StyleBox["What do you think would happen if we change T?",
  FontColor->RGBColor[1, 1, 0]]], "Text",
  FontSize->24],

Cell["Now consider an energy function with larger barrier.", "Text",
  FontSize->18],

Cell[BoxData[
    \(Clear[x]; en[x_] = 3*\((x^4 - x^2 + 0.03*x + 0.3)\) - 0.45; 
    Plot[en[x], {x, \(-2\), 2}, PlotRange \[Rule] {\(-0.5\), 1}]\)], "Input",
  FontSize->14],

Cell[BoxData[{
    \(Clear[x]; en[x_] = 3*\((x^4 - x^2 + 0.03*x + 0.3)\) - 0.45; x = 0.0; 
    T =  .1; npts = 20000; 
    xlist = Table[0, {npts}];\), "\[IndentingNewLine]", 
    \(\(Do[\[IndentingNewLine]dx = Random[]*2 - 1; \[IndentingNewLine]xtemp = 
          x + dx; \[IndentingNewLine]If[
          en[xtemp] < en[x], \[IndentingNewLine]\ \ x = 
            xtemp, \[IndentingNewLine]\ \ p = Random[]; 
          If[p < \[ExponentialE]\^\(\(-\((en[xtemp] - en[x])\)\)/T\), 
            x = xtemp, \ 
            x = x];\[IndentingNewLine]]; \[IndentingNewLine]xlist[\([i]\)] = 
          x, \[IndentingNewLine]{i, 1, 
          npts}\[IndentingNewLine]];\)\), "\[IndentingNewLine]", 
    \(\(Print["\<Plot of position versus step in Metropolis algorithm:\>"];\)\
\), "\[IndentingNewLine]", 
    \(ListPlot[xlist, PlotJoined \[Rule] True, 
      PlotRange \[Rule] {\(-2\), 2}]\)}], "Input",
  FontSize->12],

Cell[BoxData[
    \(Histogram[xlist]\)], "Input"],

Cell["\<\
Simulated annealing on the first of our double-well energy functions\
\>", "Text",
  FontSize->18],

Cell[BoxData[{
    \(Clear[x]; en[x_] = x^4 - x^2 + 0.1*x; x = 0.0; i = 0; 
    xlist = Table[0, {npts}];\), "\[IndentingNewLine]", 
    \(Tinit = 1; Tfinal\  = \ 0.01; npts = 500;\), "\[IndentingNewLine]", 
    \(\(Do[\[IndentingNewLine]logT = 
          Log[Tinit] + 
            i/npts*\((Log[Tfinal] - Log[Tinit])\); \[IndentingNewLine]T = 
          Exp[logT]; \[IndentingNewLine]dx = Random[]*2 - 1; 
        xtemp = x + dx; \[IndentingNewLine]If[
          en[xtemp] < en[x], \[IndentingNewLine]\ \ x = 
            xtemp, \[IndentingNewLine]\ \ p = Random[]; 
          If[p < \[ExponentialE]\^\(\(-\((en[xtemp] - en[x])\)\)/T\), 
            x = xtemp, 
            x = x];\[IndentingNewLine]]; \[IndentingNewLine]xlist[\([i]\)] = 
          x, \[IndentingNewLine]{i, 1, 
          npts}\[IndentingNewLine]];\)\), "\[IndentingNewLine]", 
    \(\(Print["\<Plot of position versus step in Metropolis algorithm:\>"];\)\
\), "\[IndentingNewLine]", 
    \(\(ListPlot[xlist, PlotJoined \[Rule] True, 
        PlotRange \[Rule] {\(-2\), 2}];\)\), "\[IndentingNewLine]", 
    \(\(Print["\<Final value of energy is \>", en[x], "\< at x = \>", 
        x];\)\)}], "Input",
  FontSize->10],

Cell[TextData[StyleBox["What if we change the initial value of T?\nWhat if we \
change the final value of T?\nWhat if we change the number of steps?",
  FontColor->RGBColor[1, 1, 0]]], "Text",
  FontSize->24],

Cell["\<\
Simulated annealing on the hanging 3-link chain problem.  \"Moves\" are \
swivels.\
\>", "Text",
  FontSize->18],

Cell[BoxData[{
    \(Clear[x1, y1, z1, x2, y2, z2, en]; 
    en[z1_, z2_] = 10*z1 + 20*z2;\), "\[IndentingNewLine]", 
    \(x1 = 3.0; y1 = 0.0; z1 = 0.0; x2 = 5.5; y2 = 0; 
    z2 = \(-Sqrt[16.0 - \((2.5)\)^2]\); i = 1; Tinit = 1; Tfinal\  = \ 0.002; 
    npts = 10000;\), "\[IndentingNewLine]", 
    \(<< LinearAlgebra`Orthogonalization`\), "\[IndentingNewLine]", 
    \(<< Calculus`VectorAnalysis`\), "\[IndentingNewLine]", 
    \(\(enlist = Table[0, {npts}];\)\), "\[IndentingNewLine]", 
    \(\(Do[\[IndentingNewLine]logT = 
          Log[Tinit] + \((i - 1)\)/\((npts - 1)\)*\((Log[Tfinal] - 
                  Log[Tinit])\); \[IndentingNewLine]T = 
          Exp[logT]; \[IndentingNewLine]p = Random[]; \[IndentingNewLine]th = 
          Pi/2*Random[] - Pi/4; \[IndentingNewLine]If[
          p < 0.5, \[IndentingNewLine]proj\  = \ 
            Projection[{x1, y1, z1}, {x2, y2, 
                z2}]; \[IndentingNewLine]perpproj\  = \ {x1, y1, z1} - 
              proj; \[IndentingNewLine]lenperpproj\  = \ 
            Sqrt[perpproj[\([1]\)]^2 + perpproj[\([2]\)]^2 + 
                perpproj[\([3]\)]^2]; \[IndentingNewLine]perpproj\  = \ 
            Normalize[perpproj]; \[IndentingNewLine]other = 
            CrossProduct[
              perpproj, {x2/Sqrt[x2^2 + y2^2 + z2^2], 
                y2/Sqrt[x2^2 + y2^2 + z2^2], 
                z2/Sqrt[x2^2 + y2^2 + z2^2]}]; \[IndentingNewLine]{x1temp, 
              y1temp, z1temp} = 
            proj + lenperpproj*\((Cos[th]*perpproj + 
                    Sin[th]*other)\); \[IndentingNewLine]If[
            en[z1temp, z2] < 
              en[z1, z2], \[IndentingNewLine]\ \ {x1, y1, z1} = {x1temp, 
                y1temp, z1temp}, \[IndentingNewLine]\ \ q = Random[]; 
            If[q < \[ExponentialE]\^\(\(-\((en[z1temp, z2] - en[z1, \
z2])\)\)/T\), \[IndentingNewLine]\ \ {x1, y1, z1} = {x1temp, y1temp, 
                  z1temp}, \[IndentingNewLine]\ \ {x1, y1, z1} = {x1, y1, 
                  z1}];\[IndentingNewLine]], \[IndentingNewLine]proj\  = \ 
            Projection[{x2 - 8, y2, z2}, {x1 - 8, y1, 
                z1}]; \[IndentingNewLine]perpproj\  = \ {x2 - 8, y2, z2} - 
              proj; \[IndentingNewLine]\(lenperpproj\  = \ 
                Sqrt[perpproj[\([1]\)]^2 + perpproj[\([2]\)]^2 + 
                    perpproj[\([3]\)]^2];\)\[IndentingNewLine]\(perpproj\  = \
\ Normalize[perpproj];\)\[IndentingNewLine]\(other = 
              CrossProduct[
                perpproj, {\((x1 - 8)\)/Sqrt[\((x1 - 8)\)^2 + y1^2 + z1^2], 
                  y1/Sqrt[\((x1 - 8)\)^2 + y1^2 + z1^2], 
                  z1/Sqrt[\((x1 - 8)\)^2 + y1^2 + 
                        z1^2]}]\); \[IndentingNewLine]{x2temp, y2temp, 
              z2temp} = {8, 0, 0} + proj + 
              lenperpproj*\((Cos[th]*perpproj + 
                    Sin[th]*other)\); \[IndentingNewLine]If[
            en[z1, z2temp] < 
              en[z1, z2], \[IndentingNewLine]\ \ {x2, y2, z2} = {x2temp, 
                y2temp, z2temp}, \[IndentingNewLine]\ \ q = Random[]; 
            If[q < \[ExponentialE]\^\(\(-\((en[z1, z2temp] - en[z1, \
z2])\)\)/T\), \[IndentingNewLine]\ \ {x2, y2, z2} = {x2temp, y2temp, 
                  z2temp}, \[IndentingNewLine]\ \ {x2, y2, z2} = {x2, y2, 
                  z2}];\[IndentingNewLine]]\[IndentingNewLine]]; \
\[IndentingNewLine]enlist[\([i]\)] = en[z1, z2], \[IndentingNewLine]{i, 1, 
          npts}];\)\)}], "Input",
  FontSize->10],

Cell[BoxData[{
    \(\(Print["\<Plot of energy versus step in simulated annealing algorithm:\
\>"];\)\), "\[IndentingNewLine]", 
    \(ListPlot[enlist]\), "\[IndentingNewLine]", 
    \(\(Print["\<Values of unknowns at final step:\>", {x1, y1, z1, x2, y2, 
          z2}];\)\), "\[IndentingNewLine]", 
    \(\(Print["\<Energy at final step:\>", enlist[\([npts]\)]];\)\)}], "Input",\

  FontSize->12],

Cell["The traveling salesman problem.", "Text",
  FontSize->18],

Cell["\<\
First initialize the cities and plot them, and set up the \"energy\" function \
(total distance traveled for a given choice of itinerary)\
\>", "Text",
  FontSize->18],

Cell[BoxData[{
    \(ncities = 6; Clear[x, y];\), "\[IndentingNewLine]", 
    \(\(en[ord_] := 
        Sum[\((x[\([ord[\([i + 1]\)]]\)] - 
                    x[\([ord[\([i]\)]]\)])\)^2 + \((y[\([ord[\([i + 
                              1]\)]]\)] - y[\([ord[\([i]\)]]\)])\)^2, {i, 1, 
              ncities - 1}] + \((x[\([ord[\([1]\)]]\)] - 
                x[\([ord[\([ncities]\)]]\)])\)^2 + \((y[\([ord[\([1]\)]]\)] - 
                y[\([ord[\([ncities]\)]]\)])\)^2;\)\), "\[IndentingNewLine]", \

    \(x = Table[0, {ncities}]; 
    y = Table[0, {ncities}];\), "\[IndentingNewLine]", 
    \(\(Do[x[\([i]\)] = Random[]; 
        y[\([i]\)] = Random[], {i, 1, ncities}];\)\), "\[IndentingNewLine]", 
    \(\(ListPlot[Transpose[{x, y}], PlotRange \[Rule] {{0, 1}, {0, 1}}, 
        PlotStyle \[Rule] PointSize[0.02]];\)\)}], "Input",
  FontSize->12],

Cell["\<\
Now simulated annealing to find the itinerary with minimum distance traveled. \
 A \"move\" is a swap of two cities in the itinerary.\
\>", "Text",
  FontSize->18],

Cell[BoxData[{
    \(ord = Table[i, {i, 1, ncities}]; i = 0; Tinit = 1; Tfinal\  = \ 0.01; 
    npts = 500; enlist = Table[0, {npts}];\), "\[IndentingNewLine]", 
    \(\(Do[\[IndentingNewLine]logT = 
          Log[Tinit] + 
            i/npts*\((Log[Tfinal] - Log[Tinit])\); \[IndentingNewLine]T = 
          Exp[logT]; \[IndentingNewLine]p = 
          Random[Integer, {1, ncities}]; \[IndentingNewLine]q = 
          Random[Integer, {1, ncities}]; \[IndentingNewLine]While[
          q \[Equal] p, 
          q = Random[Integer, {1, ncities}]]; \[IndentingNewLine]ordtemp = 
          ord; \[IndentingNewLine]Do[\[IndentingNewLine]If[
            ord[\([j]\)] \[Equal] p\  || \ ord[\([j]\)] \[Equal] q, 
            ordtemp[\([j]\)] = q + p - ord[\([j]\)]], {j, 1, 
            ncities}]; \[IndentingNewLine]If[
          en[ordtemp] < en[ord], \[IndentingNewLine]\ \ ord = 
            ordtemp, \[IndentingNewLine]\ \ p = Random[]; 
          If[p < \[ExponentialE]\^\(\(-\((en[ordtemp] - en[ord])\)\)/T\), \
\[IndentingNewLine]\ \ ord = ordtemp, \[IndentingNewLine]\ \ ord = 
              ord];\[IndentingNewLine]]; \[IndentingNewLine]enlist[\([i]\)] = 
          en[ord], \[IndentingNewLine]{i, 1, 
          npts}];\)\), "\[IndentingNewLine]", 
    \(\(Print["\<Here's the graph of total distance traveled versus step in \
the simulated annealing:\>"];\)\), "\[IndentingNewLine]", 
    \(ListPlot[enlist, PlotJoined \[Rule] True]\), "\[IndentingNewLine]", 
    \(\(Print["\<Total distance for final step is \>", 
        enlist[\([npts]\)]];\)\)}], "Input",
  FontSize->10],

Cell[BoxData[
    \(ord\)], "Input"],

Cell[BoxData[{
    \(\(choices = 
        Permutations[Table[i, {i, 1, ncities}]];\)\), "\[IndentingNewLine]", 
    \(\(ordbest = Table[i, {i, 1, ncities}];\)\), "\[IndentingNewLine]", 
    \(\(enbest = en[ordbest];\)\), "\[IndentingNewLine]", 
    \(\(Do[\[IndentingNewLine]If[
          en[choices[\([j]\)]] < enbest, \[IndentingNewLine]ordbest = 
            choices[\([j]\)]; \[IndentingNewLine]enbest = 
            en[choices[\([j]\)]]], \[IndentingNewLine]{j, 1, 
          Factorial[ncities]}];\)\), "\[IndentingNewLine]", 
    \(ordbest\), "\[IndentingNewLine]", 
    \(enbest\[IndentingNewLine]\)}], "Input"]
},
FrontEndVersion->"4.2 for Microsoft Windows",
ScreenRectangle->{{0, 1024}, {0, 685}},
WindowSize->{847, 604},
WindowMargins->{{0, Automatic}, {Automatic, 0}},
Magnification->1.5,
StyleDefinitions -> "NaturalColor.nb"
]

(*******************************************************************
Cached data follows.  If you edit this Notebook file directly, not
using Mathematica, you must remove the line containing CacheID at
the top of  the file.  The cache data will then be recreated when
you save this file from within Mathematica.
*******************************************************************)

(*CellTagsOutline
CellTagsIndex->{}
*)

(*CellTagsIndex
CellTagsIndex->{}
*)

(*NotebookFileOutline
Notebook[{
Cell[1754, 51, 239, 5, 135, "Text"],
Cell[1996, 58, 1347, 25, 387, "Input"],
Cell[3346, 85, 225, 5, 135, "Text"],
Cell[3574, 92, 1308, 27, 345, "Input"],
Cell[4885, 121, 76, 1, 53, "Text"],
Cell[4964, 124, 136, 2, 95, "Input"],
Cell[5103, 128, 251, 6, 94, "Text"],
Cell[5357, 136, 664, 12, 341, "Input"],
Cell[6024, 150, 106, 3, 53, "Text"],
Cell[6133, 155, 127, 3, 57, "Input"],
Cell[6263, 160, 135, 4, 94, "Text"],
Cell[6401, 166, 122, 3, 86, "Input"],
Cell[6526, 171, 130, 2, 63, "Text"],
Cell[6659, 175, 84, 1, 53, "Text"],
Cell[6746, 178, 174, 3, 86, "Input"],
Cell[6923, 183, 912, 17, 393, "Input"],
Cell[7838, 202, 49, 1, 61, "Input"],
Cell[7890, 205, 108, 3, 94, "Text"],
Cell[8001, 210, 1187, 22, 386, "Input"],
Cell[9191, 234, 208, 3, 165, "Text"],
Cell[9402, 239, 122, 4, 94, "Text"],
Cell[9527, 245, 3440, 58, 1021, "Input"],
Cell[12970, 305, 398, 8, 185, "Input"],
Cell[13371, 315, 63, 1, 53, "Text"],
Cell[13437, 318, 177, 4, 94, "Text"],
Cell[13617, 324, 853, 16, 289, "Input"],
Cell[14473, 342, 173, 4, 94, "Text"],
Cell[14649, 348, 1580, 27, 558, "Input"],
Cell[16232, 377, 36, 1, 61, "Input"],
Cell[16271, 380, 618, 11, 401, "Input"]
}
]
*)



(*******************************************************************
End of Mathematica Notebook file.
*******************************************************************)