Special algorithms and software

In recent years, computer software has been developed that solves general optimisation problems using search and trial and error procedures. In explaining how these algorithms work, it is helpful to use an analogy. Suppose you are trying to find the highest peak in a range of uncharted mountains. And suppose it is very hazy, so that you cannot see very far in any direction. The search procedure would have you start out at some location and examine the terrain around you to find the steepest uphill direction. You then go in that direction for some distance (say, 500 yards), and stop. You again examine the surrounding terrain, pick the steepest uphill direction, and go the indicated distance in that new direction. You continue this process until you reach a point where all directions are downhill. This is the end of your search-you have reached a peak (but not necessarily the highest peak).

The computer SW algorithms work similarly. The steps are:

  1. Start with a trial solution and evaluate it.
  2. Evaluate the "ground" around the trial solution by testing several "close-by" points. Methods differ on how these points are chosen and on how many to choose.
  3. Choose a "direction" to go based on the trial points. Again, methods vary on how this is done. The direction depends on whether it is a maximisation or minimisation problem.
  4. Take a "step" of a specified size in the direction found in step (3). This leads to a new trial solution. The size of the step taken may vary over the search.
  5. Repeat steps (1) through (4), but:
  6. Stop when, in evaluating the "close-by" points, there is no direction that improves the solution. That is, all directions lead downhill if maximising, or uphill if minimising.

There are many general optimisation programs available even on personal computers. In fact, the Solver program also can solve general optimisation problems.

Recently, some even more exotic optimisation procedures have been developed. Genetic search uses a process similar to the way generations of a species might evolve. It starts with a set of trial solutions to the problem. The values of the variables for each trial solution are mapped into a set equivalent to biological hereditary genes. The trial solutions are evaluated, and the better ones are selected. These better solutions are then "mated" with each other, producing the next generation of offspring. That is, the new solutions have "genes" that are genetic combinations of their parents. This second generation of solutions is then evaluated, the better ones selected to be mated for the third-generation offspring. There is an occasional "mutation" of genes (creating a diverse solution). The process is repeated until there is no significant improvement in the best solution. A related search process is called simulated annealing, which generates new solutions similar to the process used in annealing glass or metal.