Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Example-Balancing Scales

Consider again the scales balancing problem described in Section gif. That is, we are given a set of n weights, tex2html_wrap_inline67201, which are to be placed on a pair of scales in the way that minimizes the difference between the total weight in each pan. Feasible solution to the problem all have the form tex2html_wrap_inline67143, where

displaymath67221

To solve this problem using simulated annealing, we need a strategy for generating random moves. The move generator should make small, random changes to the current solution and it must ensure that all possible solutions can be reached. A simple approach is to use the formula

displaymath68286

where tex2html_wrap_inline68165 is the initial solution, tex2html_wrap_inline68301 is a new solution, tex2html_wrap_inline68303 is a sequence of zeroes and ones generated randomly, and tex2html_wrap_inline61648 denotes elementwise addition modulo two.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.