The National Grid Company plc (NGC) and are currently researching the use of genetic algorithms to produce power line maintenance schedules. The technique used to date involved not only a genetic algorithm, but also a `greedy' scheduler. Rather than the genetic algorithm producing a schedule directly, the genetic algorithm produced the sequence of importance of the lines, which the scheduler places in the schedule in turn, basing their positions in the schedule on a problem-based heuristic. The effect of the greedy scheduler is to reduce the size of the problem search space, simplifing the work of the genetic algorithm.
Timetabling investigations have shown that such a large reduction in seach space is not necessary, and a more direct approach of allowing the genetic algorithm to operate on the schedule itself is powerful, particularly due to the fact that a computationally complex scheduling heuristic is not needed.
The objective of this project was to compare the greedy method with a more traditional `direct' approach which has had much success with similaly constrained and sized timetabling problems. This involved the implementation of a program which employed the direct method. Previous investigations have been based upon a simplified model of the NGC network termed the `four node network'. Initially, investigations were continued with this model, testing and improving the direct system so that the parameters used in the algorithm were, if not optimal, at least of reasonable merit in terms of speed and quality of result.
Operators that attained particularly high performance were noted, and their performance rationalised.
A new smart mutation operator was introduced with the direct system, which improved the quality of the solutions found.
This was then followed by a comparison of the two approaches. The results showed the performance of the greedy system to be far superior than that of the direct system, for all operator sets.
Following this, studies were made with the South Wales power line network.. The direct system was optimised for this model, with the operators that performed well with the four node model tending to perform well with the South Wales model, confirming the reasoning behind the rationalisation of earlier observations.
A new elitism operator was introduced with the direct system, which was found to diminish the quality of the solutions offered.
A comparison was again made between the two systems, showing the distinction between the two approaches to be much less pronounced when applied to the larger and more constrained problem. No absolute statement could be made about the superiority of either system with respect to this problem, although suggestions were made that the direct system performed better with more highly constrained problems, and the greedy system with larger problems.