In the previous pages we analysed the performance of several implementations of the Ant Colony System (ACS) tested on sample single machine job scheduling problems. This section investigates the performance of another meta-heuristic, known as Bayesian Optimisation Algorithm (BOA). As with ACS, several different BOA implementations were tested. Of the three different implementations, only one matched the BOA algorithm as described earlier. This implementation involved learning the best Bayesian network using the Bayesian Dirichlet (BD) metric. The other two implementations deviated slightly from the original BOA algorithm, using a fixed Bayesian network rather than attempting to learn the network that best fits the population. The reason behind testing implementations that use fixed networks is to avoid the computationally expensive generation of all possible Bayesian networks for a given population and the calculation of the BD metric for each of these networks, as it is cubic in the number of jobs. Because of this, the number of incoming edges to each node has been limited to 2. In addition, the BD metric assumes that the data is complete, i.e. all possible solutions are represented in the population, which will not be the case here, so what is decided by the metric to be the Bayesian network that best describes the current population may not be an accurate representation of the relationships between jobs in that particular problem.
The heuristics used to create the initial population were the same for all three implementations. A third of the population was generated using the shortest setup time heuristic, a third using the job due date heuristic, and the final third were completely random schedules. The two fixed network implementations used a one-predecessor and a two-predecessor fixed networks respectively. In the one-predecessor fixed network implementation the next job in the schedule is decided probabilistically based only on the previous job. Note that this is the same as what Ant Colony System is doing, and therefore this implementation was expected to perform equally to the ACS implementations described in the previous chapter. In the two-predecessor BOA implementation, the next job in the schedule is decided based on what its two immediate predecessors are, and since this version keeps more information about the relationships between jobs than the one-predecessor version, it was expected to perform better than that version as well as the ACS implementations. The best results were expected from the learning network BOA implementation, as it was expected to find the Bayesian network which best describes the relationships between the jobs. As you can see from the tables summarising the results, they were not quite as expected.
The three different BOA implementations were tested on the same single machine job scheduling problems used in the previous section. All three implementations of BOA had an initial population of 2000, and went through 200 generations of generating 50 new solutions and placing them back into the population, meaning that in total 12000 schedules are generated, compared to ACS tests where 1000000 million schedules were generated. An overview of the results obtained by each of the methods when tested on the sample problems can be found in tables 4, 5 and 6.
Single-predecessor Fixed Network BOA - BOA-1P
Even though this implementation is doing the same work as the Ant Colony System implementations in the previous pages, the results obtained were in general worse. In most cases BOA-1P performed considerably worse than all three implementations of ACS described in the previous chapter. However, there were some exceptions. The single-predecessor BOA proved to be more reliable than the ACS-H1 implementation which uses shortest setup time as a heuristic. This was expected, as BOA-1P uses the job due date heuristics to generate some of the initial population. This resulted in BOA-1P always finding solutions for problems W20.1 and W30.1, where ACS-H1 could not find any. BOA-1P also had a higher success rate in finding solutions to the RBG16.a and RBG16.b problems. However, in all of these problems the average (and best) solution found by BOA-1P was worse than that found by ACS-H2, which uses only the job due date as the heuristic. One thing that was clearly shown in testing of BOA-1P is that it has very quick convergence rate. Also, it can be seen that the results will largely be influenced by the quality (and diversity) of the initial population.
Two-predecessor Fixed Network BOA - BOA-2P
As expected, this implementation of BOA performed better than the one-predecessor version. Of course, the extra work done by the algorithm resulted in a substantial time complexity increase. On the other hand, overall the results obtained were not as good as the ACS results, even though they were expected to be better. An explanation for this is that, again, only 12000 schedules were generated in total (2000 initial schedules + 200 generations of 50 new schedules), which cannot compare to the million schedules generated by ACS implementations in the previous chapter. However, because a Bayesian network is calculated for the two predecessors rather than one, a lot more work is being done and this implementation is much slower than the ACS implementations and BOA-1P (which is essentially the same as ACS). For example, the times taken were from 5 seconds for the 8 job problems to around 7 minutes for the 30 job problems. This is obviously much slower than the ACS implementations and it would take far too long to test this implementation of BOA with the same number of new schedules as ACS. However, considering that only 12000 schedules were generated, and also that no backtracking was used, this implementation has performed quite reasonably.
Learning Network BOA
This implementation of BOA was expected to give the best results, but have the worst computational complexity because of the work required to construct all possible Bayesian networks and evaluate them using the BD metric. As described already in section 2, when the best network is being searched for, once for every generation, every possible network that can be created by adding an edge to the current network (starting with an empty network) is created and evaluated using the BD metric. The best network, according tot the metric, is picked and again all possible networks from that network are created. This is repeated until no more edges can be added. Although it was not implemented here, in some versions of BOA edge reversals and removals are also supported, which further complicates things. This results in extra time complexity for generating all possible networks. In addition, the BD metric is cubic in the number of possible values of the variables. The creators of the method \cite{PGCP99} have tested their method on problems where only binary variables were used. Here the variables can take the value of any job ID, so the BD metric is cubic in the number of jobs. The results obtained by this learning network BOA implementation were not significantly better than those obtained by BOA-2P and were still not as good as the ACS results, but the computation time had doubled compared to BOA-2P. With these results it can be said that unless a better method of estimating the network is found, the results of this implementation do not justify the extra cost of learning the network.