Theory-Lesson 6 (GAs) Flashcards
INFO ON GAs
1)The fittest survive the longest
2)Characteristics encoded in genes are transmitted to offspring and tend to propagate into new generations.
3)The chromosomes of the offspring are a mix of the parents’. (but some chromosomes are a result of new genes during the reproduction process, also mutation affects the structure of chromosomes)
Key issues of GAs
1)GAs work on function evaluation and do not require derivatives
2)GAs proceed from several points in the DV domain, consequently, the method has a better probability of locating global minimum
3)GAs allow DV spaces consisting of a mix of continuous and discrete variables.
4)GAs use probabilistic transition rules and not deterministic rules
5)GAs can be easily implemented on parallel computers
Procedure of GAs
1)Initialize a population
2)Evaluate each candidate
3) Repeat until a termination condition is satisfied
-Select parents
-Recombine pair of parents
-Mutate the resulting offspring
-Evaluate the new candidates
-Select the fittest individuals for the new generation
Termination conditions of GAs
1)Solution that satisfies minimum criteria
2)Fixed number of epochs reached
3)Allocated budget reached
4)The highest fitness has reached a plateau, it doesn’t getter better with more iterations
What is the probability of crossover on GAs
The probability of crossover on GAs is the probability for two parents to be able to produce offspring. A random number is generated between 0 and 1 and if it lays inside the boundaries of crossover, the two organisms are mated, otherwise, the two parents go into the next generation unchanged. Crossover results in two new child chromosomes which are added to the second-generation pool.
What is the probability of mutation on GAs
A random number between 0 and 1 is generated and if it falls inside the threshold, the children chromosomes are mutated in a random way, by altering the binary coding.
Penalty function for GAs
A penalty term can be added to the function of the OF. In a traditional GA implementation, the fitness is represented by a scalra measure that can be formulated as a proper mathematical combination of objective and constraint functions.
min f* = f + Φ
Φ -> penalty term
Advantages of GAs at MOP
1)Simultaneous search for a set of points approximating Pareto
2)Don’t have to make guesses about which combinations of weights might be useful
3)Makes no assumption about the shape of the Pareto-front-can be convex, continuous etc.
Vector Evaluated Genetic Algorithm (VEGA)
In this method, appropriate fractions of the next generation, or subpopulations, were selected from the whole of the old generation according to each of the objectives seperately.
-Crossover and mutation were applied as usual after combining the sub-populations.
+)Efficient and easy to implement.
-)It doesn’t necessarily produce non-dominated vectors.
-)It doesn’t have an explicit mechanism to maintain diversity.
Dominance-based Ranking
-Dominance rank: by how many individuals is an individual dominated
-Dominance count: how many individuals does an individual dominate
-Dominance depth: at which front is an individual located
In GAs, non-dominated individuals have a higher chance of being selected for the next generation because they have highest fitness values.
Rank assignment on GAs
In the first round, the pareto-optimal points are assigned with rank 1 and fitness=1/rank=1/ Then they are removed from the matrix of DVs and OFs and the procedure continues with the rest ones. The optimal-points from this round are assigned as Rank 2.. This procedure goes on until all individuals are assigned with a rank .
The loop goes on and on , usually until all individuals belong to rank 1 (or reach some other termination condition)
What is the procedure of n-point crossover?
1)Choose n random crossover points
2)Split along those points
3)Glue parts, alternating between parents
4)Generalization of one point
What’s the probability of selection?
pi=Fi / Σ Fi
