Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications 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


3.4 Genetic Operators

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:

(1)  The mutation is going to be performed by choosing a phase at random between the first and the last phase in the best schedule.
(2)  The processors with the highest and the lowest load (number of ETs) are determined in the chosen phase.
(3)  The ETs are redistributed between these processors in a way that half of them are allocated to each one.


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.

3.5 Complete Algorithm and Analysis Results

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

Copyright © CRC Press LLC