With each adjustment or iteration in the generation of a solution, a choice is made from the set of potential changes to the current solution. This choice ofadjustment is made randomly, regardless of the impact on solution quality. The adjustment is only temporary, however, and is subject to the passing of one or two tests. First, if the adjustment results in an improvement in the quality of the solution, as defined by the objective function value of the search process, the adjustment is formally introduced into the solution. However, if the adjustment results in a decline in solution value quality, a calculation is made based on an annealing function. The function, or annealing acceptance criterion, for a minimization problem is exp[ - (proposed solution value - best solution value)/ temperature]
The function, or annealing acceptance criterion, for a maximization problem is exp[ - (best solution value - proposed solution value)/ temperature]
The only difference between these functions and the original acceptance criteria for an annealing process is that the Boltzmann's constant has been ignored. A uniformly distributed random number between 0 and 1 is drawn from a random number list and compared to the result ofthe function shown above. Ifthe randomly drawn number is smaller than the result of the function, the adjustment is formally introduced into the system. Although the resulting solution is of lower quality than the solution generated previous to the adjustment, the ability to accept inferior adjustments during the solution generation process allows the search process to avoid becoming stuck in local optima. Further, the search process is allowed to explore much more ofthe solution space than a greedy algorithm would be allowed.
Was this article helpful?