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


Chapter 12
Application of Genetic Algorithms in Telecommunication System Design

V. Sinkovic, I. Lovrek, B. Mikac
Department of Telecommunications
Faculty of Electrical Engineering and Computing
University of Zagreb
Croatia

Many of design problems in telecommunications could be treated as optimization problems that include some kind of searching among a set of potential solutions. The choice of the method depends mostly on the problem complexity. If the number of possible solutions is not too big, one could enumerate them all, evaluate their goal functions, and select the best solution(s). If the function to be optimized is done by a derivative continuous function, analytical methods could be applied. In all other cases, where the problem space is too big and analytical methods are not applicable, some sort of heuristic search for optimal solution could be applied.

Genetic algorithms, to be presented in this chapter, could be classified as guided random search evolution algorithms that use probability to guide their search. Genetic algorithms are created by analogy with the processes in the reproduction of biological organisms. By natural selection or by forced selection in laboratories, new generations of organisms are produced. As a consequence of crossover and mutation processes on chromosomes and genes, the children could possess either better or worse features than their parents. The “better” organisms are those that have a greater chance than the “worse” ones to survive and to produce a new generation.

This chapter deals with the application of genetic algorithms in telecommunications. After a brief introduction into genetic algorithms in Section 1, three applications of genetic algorithms will be discussed. Section 2 describes a method for call and service process scheduling based on genetic algorithm. Section 3 deals with the analysis of call and service control in distributed environment, where a genetic algorithm is used to determine a response time. Section 4 presents an example of genetic algorithm application in optimization problem solving. An example is presented through the case study on availability–cost optimization of an all-optical network.

1. Genetic Algorithm Fundamentals

The functioning of a genetic algorithm (GA) could be described by using specific data structure and by defining the set of genetic operators, as well as the reproduction procedure. In this section the explanations are mostly referred to the restricted class of simple genetic algorithms (SGA) including possible extensions to the more complex ones [1]. The terms used are a mixture taken from both biological and computational domains.

The biological organism to be specified is defined by one or by a set of chromosomes. The overall set of chromosomes is called genotype, and the resulting organism is called phenotype. Every chromosome consists of genes. The gene position within the chromosome refers to the type of organism characteristic, and the coded content of each gene refers to an attribute within the organism type.

In GA terminology, the set of strings (chromosomes) forms a structure (genotype). Each string consists of characters (genes). In SGA the character is two-valued, represented by a bit. In a search procedure, a string represents a full solution and a character (bit) represents a variable to be found, perhaps, as optimal.

The quality of a single solution in GA is determined by a fitness function f. The role of the fitness function could be twofold: to award the goodness of a solution on the one hand, and to punish the solution not satisfying constraints on the other. One solution is better than some other, if it has a higher fitness value. For an optimization procedure, the fitness function is equivalent to the goal function that could have a global optimum and a number of local optima.

In order to provide a reproduction process, producing a new generation of strings from the old one, in SGA the following genetic operators are used: reproduction, crossover, and mutation.

The reproduction operator, as the crucial one in SGA, is based on the string selection from roulette wheel. A string si among the set of all strings, with its cardinal number ns, occupies an angle size αi of the wheel, proportional to its fitness function value fi.

A new generation is produced by repeating gambling as shown in Figure 1, selecting a number at random in the interval (0, 2π), until all strings are selected.

The option–elitism could be applied in which the best string offered to the selection process is transferred directly to the next generation. Note that in algorithms other than SGA, more sophisticated selection techniques are used, such as stochastic reminder selection technique and tournament selection.

Crossover operator provides the exchange of genetic material, represented by a set of characters, between two strings. The part(s) of a string to be exchanged are defined by one or more crossover points. For example, two strings are selected at random for crossing over in randomly selected crossover points (*), as shown in Figure 2. The occurrence of the crossover is defined by crossover probability.


Figure 1  Roulette wheel selection.


Figure 2  Crossover example.

Mutation operator is related to a bit (gene) which could be changed according to the mutation probability. For example, some bits x in a string are selected at random to be mutated, as shown in Figure 3.


Figure 3  Mutation example.


Previous Table of Contents Next

Copyright © CRC Press LLC