20.2. Optimisation Strategies

20.2.1. Brute Force
20.2.2. Simulated Annealing
20.2.3. Genetic Algortihm

Of the two phased approach to SATC, the second page - consider candidate solutions has a much larger processing requirement. It's in that stage that high volumes of potential solutions have to be considered, with each point of each solution being used in many error/performance calculations,

The following three strategies were considered for phase 2.

20.2.1. Brute Force

The first strategy considered involved Brute Force. The algortihm steadily progressed through all possible permutations, exhaustively considering performance of each one, and finally producing an optimal result. This straightforward method was easy to implement, and proved useful in the early implementation phases. But, as we strove for greater fidelity in solution produced the grids of candidate start/end points got tighter and tighter, giving an exponential explosion in the volume of processing to be conducted.

20.2.2. Simulated Annealing

After we had reached the limits of how much the Brute Force Algortihm could be performance optimised, we needed to consider optimisation technique in order to get good enough solutions in a reasonable time frame.

The first technique considered was Simulated Annealing. In this technique a function is produced that is able to produce a candidate solution. This function contains a temperature variable. At the start of processing this variable is high, which allows for a great variety of solutions considered. As it cools, it reduces the allowable changes in the solution.

This algorithm gave a significant performance improvement in generating solutions, and carried a lot of hope. But, it fell short in not giving the necessary degree of control when it came to ensuring that consecutive legs were coherent with each other, as explained below in Figure 20.13, “Inconsistent range”.

20.2.3. Genetic Algortihm

Genetic Algortihms were the third optimisation technique considered. They brought the performance improvements of Simulated Annealing with the tight control offered by Brute Force processing. It is described further in the next section.