IMPLEMENTATION OF GA TO JSSP

From the earlier said operational parameters, we took the real-value encoding in which the job numbers are encoded to form the string which will give the sequence of machining order. i.e., each chromosome represents a legal solution to the problem and is composed of a string of genes. In our application, each solution is encoded as a string of job sequence. For example, the string “235641” represents for a job sequence of job 2 is processed before job “3”, job “3” is processed before job “5” and so on. The requirement is that repeating a job in a sequence is not allowed and all jobs should appear in the sequence.

For the crossover we preferred the one point method since it is simple and easy to implement and it is robust. In case of mutation the swap mutation is used, which play the major role to avoid the convergence. Termination condition used is Fixed Generation Termination. In general the roulette wheel selection is used for the maximize problem so here we used the rank selection with the fitness function as said above.

Configuration of Operational Parameters with which application runs 

Population Size	Number of chromosomes in the population is 30
Crossover	Probability of crossover’s tossing head is 0.6
Mutation	Probability of Mutation’s tossing head 0.2
Fitness	Subjective Fitness of Makes-span
Selection	Linear Ranking selection
Termination Condition	After 100 Generations

References:

Book Reference: David Edward Goldberg (1989), “Genetic Algorithms in Search, Optimization and Machine Learning” Addison-Wesley.

Citation Needed: Scheduling Problem For A Single Flexible Manufacturing machine, Nguyen Van Hop, Industrial Engineering Program, Sirindhorn International Institute of Technology, Thammasat University

Related Posts:

• ABSTRACT
• INTRODUCTION
• Genetic Algorithm
• Mechanism
• History
• Biological Background
• Parameters

Table of Contents

© 2006 Kumaravel & Project Team

---

If references link found broken see the below e-printed version of webpage

Note: e-printed version of the webpage, are just for the reference and it was not owned by blog author. It had be created using the Open Source PDFCreator, which is environment friendly to save paper.

---

Operational Parameters of Genetic Algorithm

As said earlier the following are genetic parameters which are similar to Biological background of the nature.

• Chromosomes
  
• Fitness
  

Evolutionary Steps of Genetic Programming -2

The evolutionary steps of genetic programming are as follows:
1. Randomly create an initial population (generation 0) of individual computer programs composed of the available functions and terminals.
2. Iteratively perform the following sub-steps (called a generation) on the population until the termination criterion is satisfied:

Evolutionary Steps of Genetic Programming -1

Genetic programming typically starts with a population of randomly generated computer programs composed of the available programmatic ingredients. Genetic programming iteratively transforms a population of computer programs into a new generation of the population by applying analogs of naturally occurring genetic operations. These operations are applied to individuals selected from the population. The individuals are probabilistically selected to participate in the genetic operations based on their fitness. The iterative transformation of the population is executed inside the main generational loop of the run of genetic programming.

Related Posts:

• ABSTRACT
• INTRODUCTION
• JOB SHOP SCHEDULING
• Search Methods and Optimization Techniques
• Genetic Algorithm
• Mechanism of GA

Table of Contents

© 2006 Kumaravel & Project Team

Mechanism of GA

A GA is an algorithm that operates on a principle, a combination of natural selection and procreation permits the development of living species that are highly adapted to their environments.

When applied to a problem the standard genetic algorithm proceeds as follows: an initial population of individuals i.e., a set of solutions for the given problem represented by chromosomes, is generated at random or heuristically.

At every evolutionary step, known as a generation, the individuals in the current population are decoded and evaluated according to some predefined quality criterion, referred to as the fitness function.

To form the next generation, individuals are selected according to their fitness. Then some or the entire existing individual of the current population is replaced with the newly created individuals.

Creation of new individuals is done by crossover and mutation operations which motivated by a hope that the new population will be better than the old one. Many selection procedures are currently in use, one of the simplest being Holland's original fitness proportionate selection, where individuals are selected with a probability proportional to their relative fitness.

This ensures that the expected number of times an individual is chosen is approximately proportional to its relative performance in the population. Thus, high-fitness individuals stand a better chance of “reproducing”, while low-fitness ones are more likely to disappear.

This is repeated until some condition such as number of populations or improvement of the best solution is satisfied. If the GA has been designed well, the population will converge to an optimal solution to the problem.

Convergence is the progression towards increasing uniformity. However, it is important not to forget that GA are stochastic iterative processes and they are not guaranteed to converge; hence, the termination condition may be specified as some fixed, maximal number of generations or as the attainment of an acceptable fitness level.^†

References

†“Genetic Algorithms”, Burhaneddin SANDIKCI, http://www.ie.bilkent.edu.tr/~lors/ie572/burhaneddin_html/IE572_GA.html

http://www.ie.bilkent.edu.tr/~lors/ie572/burhaneddin.pdf

Related Posts:

• ABSTRACT
• INTRODUCTION
• JOB SHOP SCHEDULING
• Search Methods and Optimization Techniques
• Some other Optimisation methods
• Genetic Algorithm
• Darwin's Theory of Natural Selection

Table of Contents

© 2006 Kumaravel & Project Team

---

If references link found broken see the below e-printed version of webpage

Note: e-printed version of the webpage, are just for the reference and it was not owned by blog author. It had be created using the Open Source PDFCreator, which is environment friendly to save paper.

---