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


4.8 Selection Process

Different approaches could be applied in creating the selection process. Any selection principle reflects the definition of the fitness function. Here, two extreme approaches will be analyzed.

Approach 1: Preselection rejection

In the preselection process, all solutions not satisfying some easy-to-test fundamental requirements are rejected. For example, if a generated graph has a node degree less than 2, or if the number of branches in a topology is less than (N-1) (graph tree), it can surely be inferred that these solutions cannot satisfy the network requirement of two independent paths between all node pairs.

Fitness functions are very simple; in the case of cost minimization fc and in unavailability minimization fu, respectively,

The advantage of this approach lies in reducing the number of topologies to be evaluated in detail (shortest path, capacity, cost, and unavailability calculation). For example, for 11 nodes, as used in the case study, the number of acceptable topologies is reduced to 10-4% of all topologies, according to the “graph tree” preselection rule, as mentioned above.

On the other hand, the disadvantages of this approach are poor diversity of solutions in the population, and the very rough distinction between solutions — a solution is either regular, that is, acceptable, or irregular, that is, unacceptable. In the cases where solution limitations are very restrictive, the whole initial population could be rejected, disabling further search. Note that even a bad solution could produce a good offspring.

Approach 2: The use of fitness functions with penalizing

No topology is rejected but, is penalized, if assumptions or dynamic limitations are not satisfied.

The advantage of this approach lies in the great diversity of solutions to be evaluated, increasing the probability of finding different areas of local minima to be tested, in order to select the global one.

The disadvantage of this approach lies in an extensive evaluation time.

Despite higher time consumption than in Approach 1, Approach 2 is selected for optimization application as the more efficient one.

4.9 Optimization Procedure

In order to minimize unavailability–cost pairs, two types of optimization alternate. In odd optimization steps, the network cost is minimized. Fitness function for cost minimization is

where k is the penalty slope and Ulim is the dynamic unavailability upper bound in an odd step, achieved as minimal in previous even step(s). PF is the penalty factor defined as follows:

where PathOver is the sum of all excesses of path length limitation and distances between the node pairs without primary and/or spare paths. CapOver is the sum of capacity demands between the node pairs contributing to the PathOver. In even optimization steps, the unavailability is minimized. Fitness function for unavailability minimization is equal to

The penalty is effective for the costs higher than the cost limit Clim, — the dynamic cost upper bound reached in previous odd optimization step(s).

Note that the genetic material is transferred from one step to the next one, forming initial population.

4.10 Optimization Results

The optimization results refer to the case study of European all-optical network.

The absolute minimum unavailability, as a reference value, was determined from the fully meshed network. The optimization target was to find the topology with the same or very close unavailability value and with cost as low as possible.

The genetic algorithm parameters are chosen as follows: population size = 100, string size = 55, crossover probability = 0.6, mutation probability = 0.05, two point crossover, roulette wheel selection scheme, generation gap = 1, the number of generations per step = 200, elitism.

As a result of optimization running, several quasi-optimal unavailability-cost pairs were obtained. Table 2 shows the results of two GA generated topologies, the minimum cost topology (MinC) and the minimum unavailability topology (MinU) (Figure 16), compared to the reference topology COST 239 (EON) and manually designed grid network (MG) (Figure 17) and fully meshed topology (FM) [15].

Table 2 The comparison of topology performances
  FM EON MG MinC MinU
U     ×10-5 2.502 3.789 4.235 3.130 2.502
C     ×106 4.537 3.765 3.903 3.706 3.793
  CL  ×106 1.441 1.685 1.711 1.576 1.615
  CN  ×106 3.096 2.080 2.192 2.130 2.178
TFCL [km]*44145 14775 11635 14610 19115
No. of links 55 25 22 25 29
dmin 10 4 2 3 4
dmax**10 5 6 7 8
PathOver [km] 0 50 675 0 0

*TFCL - total fiber cable length
**dmin, dmax - the minimum and maximum node degrees.


Figure 16  Minimum Cost (MinC) and Minimum Unavailability (MinU) topologies.


Figure 17  COST 239 case study (EON) and Manual--Grid (MG) topologies.


Previous Table of Contents Next

Copyright © CRC Press LLC