Simulated Annealing<\/strong> is a stochastic global search optimization algorithm.<\/p>\n This means that it makes use of randomness as part of the search process. This makes the algorithm appropriate for nonlinear objective functions where other local search algorithms do not operate well.<\/p>\n Like the stochastic hill climbing local search algorithm, it modifies a single solution and searches the relatively local area of the search space until the local optima is located. Unlike the hill climbing algorithm, it may accept worse solutions as the current working solution.<\/p>\n The likelihood of accepting worse solutions starts high at the beginning of the search and decreases with the progress of the search, giving the algorithm the opportunity to first locate the region for the global optima, escaping local optima, then hill climb to the optima itself.<\/p>\n In this tutorial, you will discover the simulated annealing optimization algorithm for function optimization.<\/p>\n After completing this tutorial, you will know:<\/p>\n Let\u2019s get started.<\/p>\n Simulated Annealing From Scratch in Python This tutorial is divided into three parts; they are:<\/p>\n Simulated Annealing<\/a> is a stochastic global search optimization algorithm.<\/p>\n The algorithm is inspired by annealing in metallurgy<\/a> where metal is heated to a high temperature quickly, then cooled slowly, which increases its strength and makes it easier to work with.<\/p>\n The annealing process works by first exciting the atoms in the material at a high temperature, allowing the atoms to move around a lot, then decreasing their excitement slowly, allowing the atoms to fall into a new, more stable configuration.<\/p>\n When hot, the atoms in the material are more free to move around, and, through random motion, tend to settle into better positions. A slow cooling brings the material to an ordered, crystalline state.<\/p>\n<\/blockquote>\n \u2014 Page 128, Algorithms for Optimization<\/a>, 2019.<\/p>\n The simulated annealing optimization algorithm can be thought of as a modified version of stochastic hill climbing.<\/p>\n Stochastic hill climbing maintains a single candidate solution and takes steps of a random but constrained size from the candidate in the search space. If the new point is better than the current point, then the current point is replaced with the new point. This process continues for a fixed number of iterations.<\/p>\n Simulated annealing executes the search in the same way. The main difference is that new points that are not as good as the current point (worse points) are accepted sometimes.<\/p>\n A worse point is accepted probabilistically where the likelihood of accepting a solution worse than the current solution is a function of the temperature of the search and how much worse the solution is than the current solution.<\/p>\n The algorithm varies from Hill-Climbing in its decision of when to replace S, the original candidate solution, with R, its newly tweaked child. Specifically: if R is better than S, we\u2019ll always replace S with R as usual. But if R is worse than S, we may still replace S with R with a certain probability<\/p>\n<\/blockquote>\n \u2014 Page 23, Essentials of Metaheuristics<\/a>, 2011.<\/p>\n The initial temperature for the search is provided as a hyperparameter and decreases with the progress of the search. A number of different schemes (annealing schedules) may be used to decrease the temperature during the search from the initial value to a very low value, although it is common to calculate temperature as a function of the iteration number.<\/p>\n A popular example for calculating temperature is the so-called \u201cfast simulated annealing<\/em>,\u201d calculated as follows<\/p>\n We add one to the iteration number in the case that iteration numbers start at zero, to avoid a divide by zero error.<\/p>\n The acceptance of worse solutions uses the temperature as well as the difference between the objective function evaluation of the worse solution and the current solution. A value is calculated between 0 and 1 using this information, indicating the likelihood of accepting the worse solution. This distribution is then sampled using a random number, which, if less than the value, means the worse solution is accepted.<\/p>\n It is this acceptance probability, known as the Metropolis criterion, that allows the algorithm to escape from local minima when the temperature is high.<\/p>\n<\/blockquote>\n \u2014 Page 128, Algorithms for Optimization<\/a>, 2019.<\/p>\n This is called the metropolis acceptance criterion and for minimization is calculated as follows:<\/p>\n Where exp()<\/em> is e<\/a> (the mathematical constant) raised to a power of the provided argument, and objective(new)<\/em>, and objective(current)<\/em> are the objective function evaluation of the new (worse) and current candidate solutions.<\/p>\n The effect is that poor solutions have more chances of being accepted early in the search and less likely of being accepted later in the search. The intent is that the high temperature at the beginning of the search will help the search locate the basin for the global optima and the low temperature later in the search will help the algorithm hone in on the global optima.<\/p>\n The temperature starts high, allowing the process to freely move about the search space, with the hope that in this phase the process will find a good region with the best local minimum. The temperature is then slowly brought down, reducing the stochasticity and forcing the search to converge to a minimum<\/p>\n<\/blockquote>\n \u2014 Page 128, Algorithms for Optimization<\/a>, 2019.<\/p>\n Now that we are familiar with the simulated annealing algorithm, let\u2019s look at how to implement it from scratch.<\/p>\n In this section, we will explore how we might implement the simulated annealing optimization algorithm from scratch.<\/p>\n First, we must define our objective function and the bounds on each input variable to the objective function. The objective function is just a Python function we will name objective()<\/em>. The bounds will be a 2D array with one dimension for each input variable that defines the minimum and maximum for the variable.<\/p>\n For example, a one-dimensional objective function and bounds would be defined as follows:<\/p>\n Next, we can generate our initial point as a random point within the bounds of the problem, then evaluate it using the objective function.<\/p>\n We need to maintain the \u201ccurrent<\/em>\u201d solution that is the focus of the search and that may be replaced with better solutions.<\/p>\n Now we can loop over a predefined number of iterations of the algorithm defined as \u201cn_iterations<\/em>\u201c, such as 100 or 1,000.<\/p>\n The first step of the algorithm iteration is to generate a new candidate solution from the current working solution, e.g. take a step.<\/p>\n This requires a predefined \u201cstep_size<\/em>\u201d parameter, which is relative to the bounds of the search space. We will take a random step with a Gaussian distribution where the mean is our current point and the standard deviation is defined by the \u201cstep_size<\/em>\u201c. That means that about 99 percent of the steps taken will be within 3 * step_size<\/em> of the current point.<\/p>\n We don\u2019t have to take steps in this way. You may wish to use a uniform distribution between 0 and the step size. For example:<\/p>\n Next, we need to evaluate it.<\/p>\n We then need to check if the evaluation of this new point is as good as or better than the current best point, and if it is, replace our current best point with this new point.<\/p>\n This is separate from the current working solution that is the focus of the search.<\/p>\n Next, we need to prepare to replace the current working solution.<\/p>\n The first step is to calculate the difference between the objective function evaluation of the current solution and the current working solution.<\/p>\n Next, we need to calculate the current temperature, using the fast annealing schedule, where \u201ctemp<\/em>\u201d is the initial temperature provided as an argument.<\/p>\n We can then calculate the likelihood of accepting a solution with worse performance than our current working solution.<\/p>\n Finally, we can accept the new point as the current working solution if it has a better objective function evaluation (the difference is negative) or if the objective function is worse, but we probabilistically decide to accept it.<\/p>\n And that\u2019s it.<\/p>\n We can implement this simulated annealing algorithm as a reusable function that takes the name of the objective function, the bounds of each input variable, the total iterations, step size, and initial temperature as arguments, and returns the best solution found and its evaluation.<\/p>\n Now that we know how to implement the simulated annealing algorithm in Python, let\u2019s look at how we might use it to optimize an objective function.<\/p>\n In this section, we will apply the simulated annealing optimization algorithm to an objective function.<\/p>\n First, let\u2019s define our objective function.<\/p>\n We will use a simple one-dimensional x^2 objective function with the bounds [-5, 5].<\/p>\n The example below defines the function, then creates a line plot of the response surface of the function for a grid of input values, and marks the optima at f(0.0) = 0.0 with a red line<\/p>\n Running the example creates a line plot of the objective function and clearly marks the function optima.<\/p>\n Line Plot of Objective Function With Optima Marked With a Dashed Red Line<\/p>\n<\/div>\n Before we apply the optimization algorithm to the problem, let\u2019s take a moment to understand the acceptance criterion a little better.<\/p>\n First, the fast annealing schedule is an exponential function of the number of iterations. We can make this clear by creating a plot of the temperature for each algorithm iteration.<\/p>\n We will use an initial temperature of 10 and 100 algorithm iterations, both arbitrarily chosen.<\/p>\n The complete example is listed below.<\/p>\n Running the example calculates the temperature for each algorithm iteration and creates a plot of algorithm iteration (x-axis) vs. temperature (y-axis).<\/p>\n We can see that temperature drops rapidly, exponentially, not linearly, such that after 20 iterations it is below 1 and stays low for the remainder of the search.<\/p>\n Line Plot of Temperature vs. Algorithm Iteration for Fast Annealing<\/p>\n<\/div>\n Next, we can get a better idea of how the metropolis acceptance criterion changes over time with the temperature.<\/p>\n Recall that the criterion is a function of temperature, but is also a function of how different the objective evaluation of the new point is compared to the current working solution. As such, we will plot the criterion for a few different \u201cdifferences in objective function value<\/em>\u201d to see the effect it has on acceptance probability.<\/p>\n The complete example is listed below.<\/p>\n Running the example calculates the metropolis acceptance criterion for each algorithm iteration using the temperature shown for each iteration (shown in the previous section).<\/p>\n The plot has three lines for three differences between the new worse solution and the current working solution.<\/p>\n We can see that the worse the solution is (the larger the difference), the less likely the model is to accept the worse solution regardless of the algorithm iteration, as we might expect. We can also see that in all cases, the likelihood of accepting worse solutions decreases with algorithm iteration.<\/p>\n Line Plot of Metropolis Acceptance Criterion vs. Algorithm Iteration for Simulated Annealing<\/p>\n<\/div>\n Now that we are more familiar with the behavior of the temperature and metropolis acceptance criterion over time, let\u2019s apply simulated annealing to our test problem.<\/p>\n First, we will seed the pseudorandom number generator.<\/p>\n This is not required in general, but in this case, I want to ensure we get the same results (same sequence of random numbers) each time we run the algorithm so we can plot the results later.<\/p>\n Next, we can define the configuration of the search.<\/p>\n In this case, we will search for 1,000 iterations of the algorithm and use a step size of 0.1. Given that we are using a Gaussian function for generating the step, this means that about 99 percent of all steps taken will be within a distance of (0.1 * 3) of a given point, e.g. three standard deviations.<\/p>\n We will also use an initial temperature of 10.0. The search procedure is more sensitive to the annealing schedule than the initial temperature, as such, initial temperature values are almost arbitrary.<\/p>\n Next, we can perform the search and report the results.<\/p>\n Tying this all together, the complete example is listed below.<\/p>\n Running the example reports the progress of the search including the iteration number, the input to the function, and the response from the objective function each time an improvement was detected.<\/p>\n At the end of the search, the best solution is found and its evaluation is reported.<\/p>\n Note<\/strong>: Your results may vary<\/a> given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.<\/p>\n In this case, we can see about 20 improvements over the 1,000 iterations of the algorithm and a solution that is very close to the optimal input of 0.0 that evaluates to f(0.0) = 0.0.<\/p>\n It can be interesting to review the progress of the search as a line plot that shows the change in the evaluation of the best solution each time there is an improvement.<\/p>\n We can update the simulated_annealing()<\/em> to keep track of the objective function evaluations each time there is an improvement and return this list of scores.<\/p>\n We can then create a line plot of these scores to see the relative change in objective function for each improvement found during the search.<\/p>\n Tying this together, the complete example of performing the search and plotting the objective function scores of the improved solutions during the search is listed below.<\/p>\n Running the example performs the search and reports the results as before.<\/p>\n A line plot is created showing the objective function evaluation for each improvement during the hill climbing search. We can see about 20 changes to the objective function evaluation during the search with large changes initially and very small to imperceptible changes towards the end of the search as the algorithm converged on the optima.<\/p>\n Line Plot of Objective Function Evaluation for Each Improvement During the Simulated Annealing Search<\/p>\n<\/div>\n This section provides more resources on the topic if you are looking to go deeper.<\/p>\n In this tutorial, you discovered the simulated annealing optimization algorithm for function optimization.<\/p>\n Specifically, you learned:<\/p>\n Do you have any questions?<\/strong> The post Simulated Annealing From Scratch in Python<\/a> appeared first on Machine Learning Mastery<\/a>.<\/p>\n<\/div>\n Go to Source<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n
![\"Simulated](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2021\/02\/Simulated-Annealing-From-Scratch-in-Python.jpg\")
<\/p>\n
Photo by Susanne Nilsson<\/a>, some rights reserved.<\/p>\n<\/div>\nTutorial Overview<\/h2>\n
\n
Simulated Annealing<\/h2>\n
\n
\n
\n
\n
\n
\n
Implement Simulated Annealing<\/h2>\n
# objective function\r\ndef objective(x):\r\n\treturn 0\r\n\r\n# define range for input\r\nbounds = asarray([[-5.0, 5.0]])<\/pre>\n
...\r\n# generate an initial point\r\nbest = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n# evaluate the initial point\r\nbest_eval = objective(best)<\/pre>\n
...\r\n# current working solution\r\ncurr, curr_eval = best, best_eval<\/pre>\n
...\r\n# run the algorithm\r\nfor i in range(n_iterations):\r\n\t...<\/pre>\n
...\r\n# take a step\r\ncandidate = solution + randn(len(bounds)) * step_size<\/pre>\n
...\r\n# take a step\r\ncandidate = solution + rand(len(bounds)) * step_size<\/pre>\n
...\r\n# evaluate candidate point\r\ncandidte_eval = objective(candidate)<\/pre>\n
...\r\n# check for new best solution\r\nif candidate_eval < best_eval:\r\n\t# store new best point\r\n\tbest, best_eval = candidate, candidate_eval\r\n\t# report progress\r\n\tprint('>%d f(%s) = %.5f' % (i, best, best_eval))<\/pre>\n...\r\n# difference between candidate and current point evaluation\r\ndiff = candidate_eval - curr_eval<\/pre>\n
...\r\n# calculate temperature for current epoch\r\nt = temp \/ float(i + 1)<\/pre>\n
...\r\n# calculate metropolis acceptance criterion\r\nmetropolis = exp(-diff \/ t)<\/pre>\n
...\r\n# check if we should keep the new point\r\nif diff < 0 or rand() < metropolis:\r\n\t# store the new current point\r\n\tcurr, curr_eval = candidate, candidate_eval<\/pre>\n
# simulated annealing algorithm\r\ndef simulated_annealing(objective, bounds, n_iterations, step_size, temp):\r\n\t# generate an initial point\r\n\tbest = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# evaluate the initial point\r\n\tbest_eval = objective(best)\r\n\t# current working solution\r\n\tcurr, curr_eval = best, best_eval\r\n\t# run the algorithm\r\n\tfor i in range(n_iterations):\r\n\t\t# take a step\r\n\t\tcandidate = curr + randn(len(bounds)) * step_size\r\n\t\t# evaluate candidate point\r\n\t\tcandidate_eval = objective(candidate)\r\n\t\t# check for new best solution\r\n\t\tif candidate_eval < best_eval:\r\n\t\t\t# store new best point\r\n\t\t\tbest, best_eval = candidate, candidate_eval\r\n\t\t\t# report progress\r\n\t\t\tprint('>%d f(%s) = %.5f' % (i, best, best_eval))\r\n\t\t# difference between candidate and current point evaluation\r\n\t\tdiff = candidate_eval - curr_eval\r\n\t\t# calculate temperature for current epoch\r\n\t\tt = temp \/ float(i + 1)\r\n\t\t# calculate metropolis acceptance criterion\r\n\t\tmetropolis = exp(-diff \/ t)\r\n\t\t# check if we should keep the new point\r\n\t\tif diff < 0 or rand() < metropolis:\r\n\t\t\t# store the new current point\r\n\t\t\tcurr, curr_eval = candidate, candidate_eval\r\n\treturn [best, best_eval]<\/pre>\nSimulated Annealing Worked Example<\/h2>\n
# convex unimodal optimization function\r\nfrom numpy import arange\r\nfrom matplotlib import pyplot\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn x[0]**2.0\r\n\r\n# define range for input\r\nr_min, r_max = -5.0, 5.0\r\n# sample input range uniformly at 0.1 increments\r\ninputs = arange(r_min, r_max, 0.1)\r\n# compute targets\r\nresults = [objective([x]) for x in inputs]\r\n# create a line plot of input vs result\r\npyplot.plot(inputs, results)\r\n# define optimal input value\r\nx_optima = 0.0\r\n# draw a vertical line at the optimal input\r\npyplot.axvline(x=x_optima, ls='--', color='red')\r\n# show the plot\r\npyplot.show()<\/pre>\n
![\"Line](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/11\/Line-Plot-of-Objective-Function-with-Optima-Marked-with-a-Dashed-Red-Line.png\")
<\/p>\n# explore temperature vs algorithm iteration for simulated annealing\r\nfrom matplotlib import pyplot\r\n# total iterations of algorithm\r\niterations = 100\r\n# initial temperature\r\ninitial_temp = 10\r\n# array of iterations from 0 to iterations - 1\r\niterations = [i for i in range(iterations)]\r\n# temperatures for each iterations\r\ntemperatures = [initial_temp\/float(i + 1) for i in iterations]\r\n# plot iterations vs temperatures\r\npyplot.plot(iterations, temperatures)\r\npyplot.xlabel('Iteration')\r\npyplot.ylabel('Temperature')\r\npyplot.show()<\/pre>\n![\"Line](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/11\/Line-Plot-of-Temperature-vs-Algorithm-Iteration-for-Fast-Annealing.png\")
<\/p>\n# explore metropolis acceptance criterion for simulated annealing\r\nfrom math import exp\r\nfrom matplotlib import pyplot\r\n# total iterations of algorithm\r\niterations = 100\r\n# initial temperature\r\ninitial_temp = 10\r\n# array of iterations from 0 to iterations - 1\r\niterations = [i for i in range(iterations)]\r\n# temperatures for each iterations\r\ntemperatures = [initial_temp\/float(i + 1) for i in iterations]\r\n# metropolis acceptance criterion\r\ndifferences = [0.01, 0.1, 1.0]\r\nfor d in differences:\r\n\tmetropolis = [exp(-d\/t) for t in temperatures]\r\n\t# plot iterations vs metropolis\r\n\tlabel = 'diff=%.2f' % d\r\n\tpyplot.plot(iterations, metropolis, label=label)\r\n# inalize plot\r\npyplot.xlabel('Iteration')\r\npyplot.ylabel('Metropolis Criterion')\r\npyplot.legend()\r\npyplot.show()<\/pre>\n![\"Line](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/11\/Line-Plot-of-Metropolis-Acceptance-Criterion-vs-Algorithm-Iteration-for-Simulated-Annealing.png\")
<\/p>\n...\r\n# seed the pseudorandom number generator\r\nseed(1)<\/pre>\n
...\r\nn_iterations = 1000\r\n# define the maximum step size\r\nstep_size = 0.1\r\n# initial temperature\r\ntemp = 10<\/pre>\n
...\r\n# perform the simulated annealing search\r\nbest, score = simulated_annealing(objective, bounds, n_iterations, step_size, temp)\r\nprint('Done!')\r\nprint('f(%s) = %f' % (best, score))<\/pre>\n# simulated annealing search of a one-dimensional objective function\r\nfrom numpy import asarray\r\nfrom numpy import exp\r\nfrom numpy.random import randn\r\nfrom numpy.random import rand\r\nfrom numpy.random import seed\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn x[0]**2.0\r\n\r\n# simulated annealing algorithm\r\ndef simulated_annealing(objective, bounds, n_iterations, step_size, temp):\r\n\t# generate an initial point\r\n\tbest = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# evaluate the initial point\r\n\tbest_eval = objective(best)\r\n\t# current working solution\r\n\tcurr, curr_eval = best, best_eval\r\n\t# run the algorithm\r\n\tfor i in range(n_iterations):\r\n\t\t# take a step\r\n\t\tcandidate = curr + randn(len(bounds)) * step_size\r\n\t\t# evaluate candidate point\r\n\t\tcandidate_eval = objective(candidate)\r\n\t\t# check for new best solution\r\n\t\tif candidate_eval < best_eval:\r\n\t\t\t# store new best point\r\n\t\t\tbest, best_eval = candidate, candidate_eval\r\n\t\t\t# report progress\r\n\t\t\tprint('>%d f(%s) = %.5f' % (i, best, best_eval))\r\n\t\t# difference between candidate and current point evaluation\r\n\t\tdiff = candidate_eval - curr_eval\r\n\t\t# calculate temperature for current epoch\r\n\t\tt = temp \/ float(i + 1)\r\n\t\t# calculate metropolis acceptance criterion\r\n\t\tmetropolis = exp(-diff \/ t)\r\n\t\t# check if we should keep the new point\r\n\t\tif diff < 0 or rand() < metropolis:\r\n\t\t\t# store the new current point\r\n\t\t\tcurr, curr_eval = candidate, candidate_eval\r\n\treturn [best, best_eval]\r\n\r\n# seed the pseudorandom number generator\r\nseed(1)\r\n# define range for input\r\nbounds = asarray([[-5.0, 5.0]])\r\n# define the total iterations\r\nn_iterations = 1000\r\n# define the maximum step size\r\nstep_size = 0.1\r\n# initial temperature\r\ntemp = 10\r\n# perform the simulated annealing search\r\nbest, score = simulated_annealing(objective, bounds, n_iterations, step_size, temp)\r\nprint('Done!')\r\nprint('f(%s) = %f' % (best, score))<\/pre>\n>34 f([-0.78753544]) = 0.62021\r\n>35 f([-0.76914239]) = 0.59158\r\n>37 f([-0.68574854]) = 0.47025\r\n>39 f([-0.64797564]) = 0.41987\r\n>40 f([-0.58914623]) = 0.34709\r\n>41 f([-0.55446029]) = 0.30743\r\n>42 f([-0.41775702]) = 0.17452\r\n>43 f([-0.35038542]) = 0.12277\r\n>50 f([-0.15799045]) = 0.02496\r\n>66 f([-0.11089772]) = 0.01230\r\n>67 f([-0.09238208]) = 0.00853\r\n>72 f([-0.09145261]) = 0.00836\r\n>75 f([-0.05129162]) = 0.00263\r\n>93 f([-0.02854417]) = 0.00081\r\n>144 f([0.00864136]) = 0.00007\r\n>149 f([0.00753953]) = 0.00006\r\n>167 f([-0.00640394]) = 0.00004\r\n>225 f([-0.00044965]) = 0.00000\r\n>503 f([-0.00036261]) = 0.00000\r\n>512 f([0.00013605]) = 0.00000\r\nDone!\r\nf([0.00013605]) = 0.000000<\/pre>\n
# simulated annealing algorithm\r\ndef simulated_annealing(objective, bounds, n_iterations, step_size, temp):\r\n\t# generate an initial point\r\n\tbest = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# evaluate the initial point\r\n\tbest_eval = objective(best)\r\n\t# current working solution\r\n\tcurr, curr_eval = best, best_eval\r\n\t# run the algorithm\r\n\tfor i in range(n_iterations):\r\n\t\t# take a step\r\n\t\tcandidate = curr + randn(len(bounds)) * step_size\r\n\t\t# evaluate candidate point\r\n\t\tcandidate_eval = objective(candidate)\r\n\t\t# check for new best solution\r\n\t\tif candidate_eval < best_eval:\r\n\t\t\t# store new best point\r\n\t\t\tbest, best_eval = candidate, candidate_eval\r\n\t\t\t# keep track of scores\r\n\t\t\tscores.append(best_eval)\r\n\t\t\t# report progress\r\n\t\t\tprint('>%d f(%s) = %.5f' % (i, best, best_eval))\r\n\t\t# difference between candidate and current point evaluation\r\n\t\tdiff = candidate_eval - curr_eval\r\n\t\t# calculate temperature for current epoch\r\n\t\tt = temp \/ float(i + 1)\r\n\t\t# calculate metropolis acceptance criterion\r\n\t\tmetropolis = exp(-diff \/ t)\r\n\t\t# check if we should keep the new point\r\n\t\tif diff < 0 or rand() < metropolis:\r\n\t\t\t# store the new current point\r\n\t\t\tcurr, curr_eval = candidate, candidate_eval\r\n\treturn [best, best_eval, scores]<\/pre>\n...\r\n# line plot of best scores\r\npyplot.plot(scores, '.-')\r\npyplot.xlabel('Improvement Number')\r\npyplot.ylabel('Evaluation f(x)')\r\npyplot.show()<\/pre>\n# simulated annealing search of a one-dimensional objective function\r\nfrom numpy import asarray\r\nfrom numpy import exp\r\nfrom numpy.random import randn\r\nfrom numpy.random import rand\r\nfrom numpy.random import seed\r\nfrom matplotlib import pyplot\r\n\r\n# objective function\r\ndef objective(x):\r\n\treturn x[0]**2.0\r\n\r\n# simulated annealing algorithm\r\ndef simulated_annealing(objective, bounds, n_iterations, step_size, temp):\r\n\t# generate an initial point\r\n\tbest = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])\r\n\t# evaluate the initial point\r\n\tbest_eval = objective(best)\r\n\t# current working solution\r\n\tcurr, curr_eval = best, best_eval\r\n\tscores = list()\r\n\t# run the algorithm\r\n\tfor i in range(n_iterations):\r\n\t\t# take a step\r\n\t\tcandidate = curr + randn(len(bounds)) * step_size\r\n\t\t# evaluate candidate point\r\n\t\tcandidate_eval = objective(candidate)\r\n\t\t# check for new best solution\r\n\t\tif candidate_eval < best_eval:\r\n\t\t\t# store new best point\r\n\t\t\tbest, best_eval = candidate, candidate_eval\r\n\t\t\t# keep track of scores\r\n\t\t\tscores.append(best_eval)\r\n\t\t\t# report progress\r\n\t\t\tprint('>%d f(%s) = %.5f' % (i, best, best_eval))\r\n\t\t# difference between candidate and current point evaluation\r\n\t\tdiff = candidate_eval - curr_eval\r\n\t\t# calculate temperature for current epoch\r\n\t\tt = temp \/ float(i + 1)\r\n\t\t# calculate metropolis acceptance criterion\r\n\t\tmetropolis = exp(-diff \/ t)\r\n\t\t# check if we should keep the new point\r\n\t\tif diff < 0 or rand() < metropolis:\r\n\t\t\t# store the new current point\r\n\t\t\tcurr, curr_eval = candidate, candidate_eval\r\n\treturn [best, best_eval, scores]\r\n\r\n# seed the pseudorandom number generator\r\nseed(1)\r\n# define range for input\r\nbounds = asarray([[-5.0, 5.0]])\r\n# define the total iterations\r\nn_iterations = 1000\r\n# define the maximum step size\r\nstep_size = 0.1\r\n# initial temperature\r\ntemp = 10\r\n# perform the simulated annealing search\r\nbest, score, scores = simulated_annealing(objective, bounds, n_iterations, step_size, temp)\r\nprint('Done!')\r\nprint('f(%s) = %f' % (best, score))\r\n# line plot of best scores\r\npyplot.plot(scores, '.-')\r\npyplot.xlabel('Improvement Number')\r\npyplot.ylabel('Evaluation f(x)')\r\npyplot.show()<\/pre>\n![\"Line](\"https:\/\/machinelearningmastery.com\/wp-content\/uploads\/2020\/11\/Line-Plot-of-Objective-Function-Evaluation-for-Each-Improvement-During-the-Simulated-Annealing-Search.png\")
<\/p>\nFurther Reading<\/h2>\n
Papers<\/h3>\n
\n
Books<\/h3>\n
\n
Articles<\/h3>\n
\n
Summary<\/h2>\n
\n
\nAsk your questions in the comments below and I will do my best to answer.<\/p>\n