Search Process Using Genetic Algorithms

 Random Samples 

The above diagram shows that the Hybrid optimisation can be improved upon. However, computation-wise it demands many more simulations. The good news is that the majority of the simulations are "redundant". We are interested only in those which are close to the optimal curve (if that indeed is the optimal one). So, if we could "get rid" of them we would be able to study the process with considerably cheaper computational cost. The next step is to sample significantly less points in the Resources space and instead of proceeding to sample randomly, we use GA to create more new points as descendants of existing ones. These descendants are the result of bringing together two points, where the closer a point is to the optimum the better chance it has to be selected for reuse. The GA "pushes" the density towards lower Unavailability and cheaper Cost. By doing so, it is expected that less calculations will have to be carried out since most of the "unnecessary" ones are unlikely to take part. Still, one of the underlying principles of GA is that there should not be deterministic decisions when selecting new points, but to give some chance to the "less promising" points. This prevents degeneration or dead-ends in the process.

Recall that in the current example problem there are 25 different entries, each of which can vary between zero to its maximum, we break down this vector to a binary vector which represents the same values. Therefore, each resource will thereby be allocated with a stack of binary bits, where the number of bits of every resource should cover the corresponding maximum allocation⁽⁴⁾ (sufficiency), and all the stacks together create a string of binary values. The next step is ranking the strings according to a criterion. There are many ways to determine the criterion by which the strings should be sorted. At this stage we attribute each allocation with a "mark" which is derived from the simulation. The mark is a relative (normalised) function value, of the Resources allocationof each string (spares allocation in binary units) in the form:

, where cl is a the normalising constant

such that

Hence, the set can be regarded as set of probabilities of mutually exclusive and complementary events such that it is possible to sample a string from the entire population with probability for the j^{th- />} string.Next, two strings are selected, with the condition that they are different, and merged as described below.

Then we select for both strings, the place at which they will cut. If each string is built up from Z binary elements, then the current sampling is with uniform distribution between 1 to Z-1. Let the cut point be M, then we cut both strings to two pieces, piece A from 1 to M and piece B from M+1 to Z. We then switch between piece B of the two strings and create two new-born strings. We repeat this process until we have created an equal number of strings as per the original population (we maintain the same number in the population), and simulate for each new-born string. We should say that a genuine parent can be sampled multiple times as long as it does not get merged with itself. By this method (see more in Goldberg, 1989), the population will evolve to obtain results more and more toward lower Unavailability and lower Cost at the same time (note that these two objectives are in competition). Figure 7 shows the results of the above described GA process for the same model:

Figure 7: Unavailability in the Resources space produced by GA, from which the resulting Pareto Front is compared with the Hybrid Curve, and T is added again.

Figure 7 clearly shows that the space has been extended. As explained above, this is caused by the replacement of the allocation vector with binary one which covers more values. It is clearly seen that less "wasteful" samples were carried out and that the population approaches massively towards better (lower) Unavailability and to lower Cost. Still, these results are not completely satisfying and we believe can be improved upon. Two main factors can be suggested for improvement: changing the determination of and attempting to increase the dispersion of the points. This requires a further study that may consider other search methods, such as the Ranking method.

 Summary