27-08-2012, 11:20 AM
OPTIMIZATION OF LOAD DISTRIBUTION IN LARGE-SCALE NETWORKS WITH FINITE MEMORY USING GENETIC ALGORITHMS
OPTIMIZATION OF LOAD.pdf (Size: 815.89 KB / Downloads: 80)
INTRODUCTION
In recent years, distributed systems (DS) have become popular. A distributed
system is defined as a system involving cooperation among a number of computers in a
network [1]. DS is a piece of software that ensures that a collection of independent
computers appears to its users as a single coherent system [2]. DS features high
performance, high reliability, resource sharing and extensibility [1].
A distributed computing system is one of the types of distributed systems. It
represents a large class of computing systems, from a centralized star computing network
to a completely decentralized computing system. A combination of processing logic,
functions, data and control of the computing system are distributed to a certain extent [3].
“Parallel computing is a method of processing in which different parts of a program run
simultaneously on two or more processors that are part of the same computer” [4].
“Scheduling refers to a set of policies and mechanisms to control the order of
work to be performed by a computer system” [5]. It plays a vital role in large scale
networks. The need for efficient scheduling of the loads, i.e. parallel loads that are
divisible among processors and links is created by the increasing prevalence of
multiprocessors systems and data intensive computing. Recently, Divisible Load Theory
(DLT) has emerged as a powerful means for modeling data intensive computational
problems [6].
LITERATURE REVIEW
This chapter presents literature review pertinent to genetic algorithms. This
includes the fundamentals of genetic algorithms, a running example, and the travelling
salesman problem and performance analysis on TSP.
GA CONCEPTS
In this section we review the fundamentals of Genetic Algorithm (GA). GA is a
computing algorithm built in parallel with the process of evolution. It is used for
searching poorly defined spaces and general spaces. GA is a search algorithm based on
the principles of evolution and natural genetics. GA explains the adaptive process of
natural systems and is used to design artificial systems based upon these natural systems
[12].
Let’s see the concept in biological terms. Gene is the basic units of genetic
storage. Chromosomes are formed by stringing these genes together within the cells.
Between the single cell organisms takes place the simple possible sexual reproduction. A
diploid cell is formed by fusing two cells to produce a cell with two sets of chromosomes.
Then, this diploid cell undergoes meiosis. Meiosis means in the diploid cell, the
chromosomes make an exact copy of it [12].
CASE STUDY
The Standard Genetic Algorithms implements the haploid sexual reproduction
method. In this algorithm, a set of individual binary integers such as 1001010 is called a
population. Each individual represents the chromosome. There is a function that
determines the fitness of each individual, and another function that selects individuals
from the population to reproduce. The two selected chromosomes crossover and split
again. Next, the two new individuals mutate. The process is then repeated a certain
number of times. Let’s see the above functions in detail [12].
The Fitness function determines the fitness of a chromosome, i.e. how well the
chromosome fits the search space or determines the solution. In this algorithm, the fitness
function of possible chromosomes is said to be f [12].
The Selection chooses a pair of chromosomes from the population to reproduce.
This function can be any increasing function, but here, we will consider fitness
proportionate selection, whose selection function is the probability function on the
population {x1… xn} [12].
The Crossover function swaps the genes between the two selected chromosomes
for reproduction. In this case, we will consider only one-point crossover, this process is
simple and standard. An integer i is randomly selected between 1 and n. The crossover
occurs in this place with probability pc. If crossover occurs, then the chunks up to i of the
two chromosomes are swapped. For example, the chromosomes 11111111 when crossed
with 00101010 at i=4 gives the chromosomes 00101111 and 11111010 [12].
CONCLUSION
The problem of scheduling a divisible load onto a set of processors with finite
size buffers in large scale networks using genetic algorithms is investigated. Firstly, we
conducted a simple case study using GA for the travelling salesman problem. This
model is extrapolated to 2 dimensions by giving each city a 2 dimensional coordinate
and then modified the distance calculating function accordingly. The stopping condition,
GA with a threshold equals to zero. This means that, for a GA to terminate there should
be condition, in this case if the delta ((average of ten top chromosomes of past
generation) – (average of ten top chromosomes of present generation)) becomes zero
then GA terminates. The results of this case study are analyzed. We presented the results
on performance analysis, i.e., Delta variation, GA execution time, total generations
before termination and comparison of solutions between ‘Case A’ (GA with a threshold
equals to zero.) and ‘Case B’ (GA without a threshold + 1000 generations. This means
that, there is no such condition like mentioned above in Case A. GA terminates after
1000 generations).