![]() |
Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications
by Lakhmi C. Jain; N.M. Martin CRC Press, CRC Press LLC ISBN: 0849398045 Pub Date: 11/01/98 |
Previous | Table of Contents | Next |
Reproduction
Reproduction is the basic genetic operator. Reproduction forms a new generation by choosing those individuals from the old population that have the highest value of the fitness function. The choice is based on the fact that the individuals with the highest value of the fitness function have greater chances to survive in the next generation. In our application it means that better task schedules have higher value of the fitness function and, because of that, they have to be preserved in the next generation. The choice is made by the roulette wheel selection technique. Since the schedules with a higher value of the fitness function take a greater part of the wheel, they have a higher probability to be chosen in the next generation. Also, an elitism procedure can be added, so that the best schedule from the old generation always moves into the new generation without a random choice.
Crossover
Two schedules A and B from the population are taken, as defined in Figure 9. Two new schedules C and D can be made by changing the parts of the schedules A and B according to the following crossover procedure:
A site (phase) h that divides processor lists into two parts is chosen randomly.
The left parts of the schedules remain unchanged, and the right parts are subjected to the crossover in such a way that the right part of the schedule A becomes the right part of the schedule B and vice versa.
Mutation
Mutation is considered as a stochastic alternation of the genetic code value in selected places in the schedule. Some modifications in the mutation operation defined in Section 1 are proposed because GA used for finishing time determination manipulate the ET sets. The modified procedure follows:
Figure 9 Crossover operation.
An example is shown in Figure 10. The second processor list has the lowest load (2 ETs) and the last one has the highest load (10 ETs). The total number of ETs (12) is redistributed on these processors by using mutation. The resulting schedule has 6 ETs in processors affected by this genetic operator.
Figure 10 Mutation operation.
The flow chart of the complete genetic algorithm, whose parts have been described previously, is shown in Figure 11.
The start is defined by assigning the number of the generations explored by a genetic algorithm.
Afterward, the generation of the initial population is performed randomly, according to the assigned number of processors and the number of schedules in a population. Also, mutation and crossover probabilities, that are going to be used later, are defined.
After that, a fitness function is calculated for all schedules in the population.
For the schedule with the highest value of the fitness function, an operation of the modified mutation is done with the assigned probability that improves the best schedule.
The reproduction, the key operation of the genetic algorithm, follows. A new population, having the same number of schedules as the old one, is obtained. The best schedule is moved directly from the old generation into a new one.
Afterward, a new population is subjected to the crossover operation with assigned probability. Fitness function calculation shows the features of a new generation.
A resulting generation containing the best schedules is obtained when the defined number of generations is reached. After fulfilling convergence criterion, the algorithm terminates.
For the illustration of the genetic algorithm analysis in the given examples, an obtained finish time is considered as a complement of the fitness function in certain iterations.
A series of experiments was done to evaluate a performance of the genetic algorithm itself. Different problems, from regular to a heavy request flow, including request bursts were analyzed. Also, the initial population with respect to generated strings (schedules) and size has been evaluated. The comparison criterion was the best string in the population (the string with the lowest finishing time). An example of the analysis with different initial populations will be discussed here.
The analysis, shown in Figure 12, is done for three different initial populations (2, 10, and 20 strings) for a maximum number of generations, GEN = 100. The simulation method including GA has been programmed in Mathematica.
The best schedule and corresponding finishing time are simulation results. Note that the optimum (FTopt = 41 Δt) is not reached with the defined initial populations and the number of generations (FT = 48 Δt).
Figure 11 Flow chart of the genetic algorithm.
Parallel processing of calls and services in telecommunications is a stochastic process itself. This section presents the analysis of call and service control by using genetic algorithm the method based on stochastic approach as well.
Systematic experiments have shown that GA approach offers a framework suitable for estimating performance of the parallel processing of calls and services in telecommunications and the associated control system.
Figure 12 Finishing time vs. number of generations in GA application.
Previous | Table of Contents | Next |