![]() |
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 |
According to the call and service processing concept described in Section 2.1, a model of call and service control is introduced. It consists of a processing system and its environment representing the telecommunication network and its users, as shown in Figure 6. Requests coming from the environment enter the request queue limited to N places. If the number of requests is greater than N, a loss occurs. Requests wait until the processing of the previous request has been completed. After that, all requests from the queue are moved to the task pattern formatting stage where a set of elementary tasks with their precedence relations is associated to every request. Further on, the elementary task scheduling is performed by using GA. Finally, elementary tasks enter processor queues.
Figure 6 Model of call and service control.
The most important parameter describing control system performance is a response time, that is, the time needed to generate response to a processing request. To obtain response time tq, two parameters have to be evaluated: finishing time Ts and waiting time tw. The problem is similar to the problem of multiprocessor scheduling: ts corresponds to the optimal finishing time for a given set of elementary tasks and tw to the time needed to complete the previous set of elementary tasks.
A genetic algorithm is applied for finishing time determination in a simulation method used for the analysis of parallel processing in telecommunications [8, 9, 10, 11]. The method includes three steps: request flow generation, finishing time determination, and response time calculation, that are repeated as many times as pointed out by defined number of simulation samples. The simulation is based on a generation of processing request flow with random structures with respect to the number of ETs and their precedence relations. A stochastic nature of processes is defined with probability functions for arrival characteristics of processing requests, and the number of ETs per request.
Each processing request consists of a certain number of ETs, each ET taking the same processing time Δt, as defined in the previous sections. For example, Figure 7 shows 10 requests represented by the sequence of numbers, where each number describes the number of ETs in each partition and determines how many tasks can be simultaneously processed in each processing phase. For the first request there is a sequence {3, 4, 4, 6, 6, 2}, which means that in the first Δt there are 3 ETs that could be processed in parallel, in the second one there are 4 ETs, etc. The whole request can be processed for at least 6 Δt if there is enough processor capacity in each Δt.
Figure 7 The survey of the genetic algorithm function.
The problem becomes more difficult if more demands with different patterns come at the same time as in this example, where the total number of ETs is given by the sequence {36, 39, 34, 48, 25, 10, 4}. Genetic algorithm will be used to distribute ETs on a certain number of processors (in this example, there are 5 processors) and to get the shortest time to finish all the tasks. One feasible schedule is shown in the same figure.
Before using genetic algorithm, we associate the meanings to the terms as shown in Figure 8.
Task schedule on the single processor forms a processor list that corresponds to the chromosome. The places in the processor lists representing processing phases correspond to the genes, and the number of ETs in the place represents the genetic code. One of possible schedules corresponds to the phenotype. Set of the schedules corresponds to the population on which genetic operations are applied in some steps of the genetic algorithm. In that way, a set of ETs defines a genetic code contained in a gene to be exchanged between schedules, i.e., genetic operations will operate on such ET sets and not on individual ETs. It should be noted that, in the example discussed in Section 2, each individual ET takes the notion of a gene.
Figure 8 Genetic algorithm terminology.
The factors considered for the fitness function are the following: throughput, finishing time, and processor load. Fitness function in this example is based on finishing time. Finishing time FT, for the schedule S at a phase h is defined by
where ftp (Pj) denotes finishing time of the last ET in the processor Pj. If n denotes schedule height, then each phase is denoted by 1 ≤ h ≤ n, and the number of ETs associated to the processor Pj in the phase h is denoted by et (Pj, h), so the expression for the finishing time for the schedule S could be written in the form
In order to get the fitness function that is going to be maximized during the genetic algorithm running, the finishing time function has to be transformed into a maximized form by introducing the value Cmax as the maximum value of the finishing time that occurs at any schedule until the determined moment during the algorithm run. The fitness function is defined as follows:
Thus, the best schedule is the one with the shortest finishing time, i.e., the greatest value of the fitness function.
Previous | Table of Contents | Next |