Transcript pga-new

USING PARALLEL GENETIC ALGORITHM IN A
PREDICTIVE JOB SCHEDULING
By:
Amseena Mansoor
Rayan Alsemmeari
Introduction
• Literature survey
• Why does Genetic Algorithm work?
• Parallel Genetic Algorithm
• Predictive Job Scheduling System
• Conclusion
Literature Survey
Types of scheduling:
1. System level scheduling
2. Application level scheduling
System level Scheduling
• The scheduling system will analyze load situation of each
node and choose one node to run the task.
• The scheduling system has to realize the load balancing
and increase the throughput and resource utilization
under restricted condition, when the system is heavily
loaded
Application level scheduling
•If multiple task arrive during a unit scheduling
time slot, then scheduling system will be responsible to
allocate an appropriate number of jobs to each node in
order to finish these jobs under a defined objective.
•The objective is usually the minimal average execution
time. This scheduling policy is application- oriented. So,
this schedule is called application level scheduling.
Genetic Algorithm
• Powerful search technique based on mechanics of
biological evolution
• Used to solve a difficult problem in many disciplines
• Can provide efficient and effectives techniques for
optimization and machine leaning applications
Basic Principle of GA
•In GA, It is necessary to select a specific number of inputs
• For instance, x1, x2 ... xn which belong to the input space
X.
•Each input in the GA terminology called an organism or
chromosome.
• The set of chromosomes is designated as a colony or
population.
•Computation is done over epochs.
•In each epoch the colony will evolve according to specific
rules reminiscent of biological evolution.
Genetic Algorithm
G.A phases
1. Initial Population
2. Evaluation of fitness function
3. Parent selection
4. Crossover operation
5. Mutation
Initial Population
• G.A begins with a set of k randomly generated states
• These states are satisfactory to the problem
• The representation of solutions should be encoded as
1. Real numbers
2. Binary encoding
3. List of rules
(1,2,….9)
(0s,1s)
(R1,R2,R3)
Evaluation of fitness function
• To each chromosome xi, we assign a fitness value that is
the function of xi(f(xi))
• Fitness: string
value
• Properties: best string
highest fitness function
• If s1 is better than s2
f(s1)> f(s2)
Parent selection
• Stronger individual chromosomes with fitness values
closer to the colony optimal will have greater chance to
survive across epochs and to reproduce than weaker
individuals which will tend to die.
Crossover operation
•The important step in the algorithm is reproduction or
breeding which happens once per epoch.
• The content of the two chromosomes participating in
reproduction are literally merged together to form a new
chromosome that a child.
•This heuristic allows us to possibly combine the
best of both individuals to yield a better one
Crossover operation
• How does the crossover wok?
• Single point crossover
• Multi point crossover
• Uniform crossover
Mutation
•Perform exploitation on the current best strings (performs
random local search)
•Let e an element of the string
e
10011010
• The value of e, ᵾ e € string is changed with some
probability p (usually low)
10001010
8 queen puzzle example
Why does genetic algorithm work?
Genetic Algorithm application level scheduling algorithm
generates the initial population, evaluates each individual’s
fitness, and performs genetic operations on the Individuals
with high fitness such copying, crossover and mutation, to
generate a new population. The genetic process continues
with the new population until a nearly optimal jobs
assignment strategy is obtained. Finally, the jobs are
assigned to each node based on the strategy
The parameters in job scheduling
• Total execution time is the time between the beginning of
execution of the first job of a series and completion of the
last job.
• Average turnaround time is the average, for each job
from when the job arrives to when the job finished
What is PGA?
• Parallel implementation of GA
• Provide considerable gains in terms of performance and
scalability
• It can easily implemented on network of heterogeneous
computers or in parallel mainframes
GA can be parallelized depends on
1.how fitness is evaluated and mutation is applied
2.if single or multiple subpopulation are used
3.if multiple populations are used, how individuals are
exchanged
4.how selection is applied
The advantages of using PGA
• Parallel search from multiple points in a
space
• Works on a coding of the problem.
• Independent of the problem.
• It can change solutions to the problem.
• Better search even if no parallel hardware is used.
• Higher efficiency than sequential Genetic Algorithms.
• Easy cooperation with other search procedures.
PGA Taxonomy
a. Master-Slave Parallelization
b. Subpopulation with migration
c. Overlapping subpopulation
d. Massively parallel genetic algorithm
e. Dynamic demes
f. Parallel steady-state algorithm
g. Parallel messy genetic algorithm
Master-Slave Parallelization
• One of the first successful applications of parallel GA.
• This is also called global parallelization, master-slave
model or distributed-fitness evaluation
• The evaluation of the individuals are performed in parallel
Master-Slave Parallelization
• The selection and mating is done globally
• Each individual may compete and mate with any other
Master-Slave Algorithm
• Master stores the population
a. executes the Genetic operators
b. distributes individuals to the slaves.
• The slave evaluates the fitness of the individual
a. reports the fitness value to the master
Predictive Job Scheduling System
• A model of the scheduling algorithm
• The scheduler can learn from the previous experiences.
• Selection and crossover are considered in the entire
population; each individual may compete and mate.
Predictive Job Scheduling System
• A binary encoding is used to convert the scheduling
•
•
•
•
•
•
problem to chromosomes
Each chromosome has genes.
The efficiency may be high if the same jobs have to be
scheduled.
The scheduler starts with no prior information about the
jobs at first
After each allocation the information is stored to the
history base.
The job of specific requirement comes again a different
combination is tried according to the resource availability
if the execution time is lower then it is recorded. This is
called the learning phase.
Predictive Job Scheduling System
If a new job which has not yet scheduled by the
scheduler, then the system is put to a brief
learning phase again.
The encoding process is done by assuming that a
chromosome has the following gene structure.
Chromosome {gene1, gene2, gene3}
Gene1 is the job identifier.
Gene2 is the resource identifier.
Gene3 is the node identifier
Predictive Job Scheduling System
• The fitness function f is the execution time of
that job at the node.
• The population generation is done by assigning binary set
values for each of the genes.
• Job A may be encoded as 00 and job B may be encoded
as 01 and so on.
• The same method can be used to represent all genes.
Predictive Job Scheduling System
• The sample population may have individuals such as 00
01 10.
• After the population is built in the learning phase, the
fitness of the individual is recorded as the execution time
of the job at the node.
• The next time the same job is to be Scheduled
the history information is checked
Predictive Job Scheduling System
• a new gene combination is found and job
scheduled and the fitness recorded.
• After time T the genetic operator of crossover is applied
and the individuals of the same job type are selected for
crossover.
The proposed algorithm
Procedure for the learning phase
{
Create the population by encoding the problem.
Add chromosome to the history if it does not exist in the
history
Else
Try a different combination of genes.
}
If job details available in history
Then
The proposed algorithm
If the resource availability
Then send the job to the node
Else
Try a different resource if it is available.
Else
Initiate the learning procedure
After time T apply the Genetic Operators on the
history information.
Conclusion
The Genetic Algorithm Scheduling increase execution time
at first and then, improved as time progressed. The future
work may involve the different and more efficient methods
of encoding a problem and different genetic operators and
methods.
References
• [1] Yang, Hongquiang, Joshua, Adaptive grid
• job scheduling with genetic algorithm, Elsevier
• Future Generation Computer Systems 2005.
• [2] D.E Goldberg, “Genetic Algorithm in Search,
• Optimization and Machine Learning “, Prentice
• Hall of India, 2004.
• [3]R.Stuart, N.Norvig, ”Artificial Intelligence A Modern
Approach”, Pearson Education,Inc.
Thank You for listening to us!!!!!