WIX3001 Lecture 6 Principles of GA.pptx

Soft Computing Slide

1. WIX3001 Soft Computing Lecture 6: Principles of Genetic Algorithms Dr. Liew Wei Shiung FSKTM Block B 2-22 [email protected]

2. Principles of Genetic Algorithms Genetic Algorithm variants Genetic Programming

3. Genetic Algorithm variants Messy GA Adaptive GA Parallel GA Independent Sampling GA Real-Coded GA

4. GA Glossary Chromosome A set of genes / parameters representing a complete solution to a problem being optimized. Population A set of chromosomes. Fitness Function The function used for evaluating how well a chromosome solves the optimization problem. Outputs a fitness score . Generation A complete cycle where the population of chromosomes is evaluated, and a new population is created using selection, reproduction, and mutation. Selection / Rejection Selects or rejects chromosomes from the population. Elitism is when the best chromosomes carry over to the next generation. Reproduction Combining two or more chromosomes to create a new chromosome. Mutation Changing the value of one or more genes in a chromosome. Convergence When the GA finds the global optimum or the fitness no longer improves.

5. Messy GA Traditional GA: fixed-order genes. Messy GA: variable-length, position-independent genes. Each gene is appended with an index. Positions of the genes in the chromosome can be swapped without changing the meaning of the chromosome. Why? Irregular-length solutions.

6. Messy GA: Representation

7. Messy GA: Genetic Operations Crossover: cut and splice

8. Messy GA: Potential Problems Over-Specification: more than one gene with the same index. Positional preference: choose the first or last. Performance preference: choose the best. Under-Specification: one or more indices are missing. Random. Optimization.

9. Adaptive GA Traditional GA: fixed population size, crossover rate, mutation rate. Adaptive GA: variable population size, crossover rate, mutation rate. Example: Mutation+ if population converges; Mutation- if population diverges. Why? Control the rate of searching and rate of convergence. Exploration: unknown solution space. Exploitation: known solution space.

10. Adaptive GA: How to Detect Convergence? Criterion : Max fitness – Avg. fitness Convergence Divergence Selection ++ Keep more local optima from known areas -- Keep more solutions from unknown areas Crossover ++ Look for more unknown areas -- Narrow down searching in known areas Mutation ++ Look for more unknown areas -- Narrow down searching in known areas

11. Adaptive GA

12. Parallel GA Parallel Chromosomes Fitness test multiple chromosomes simultaneously. Parallel Populations (i.e. Island Model) Optimize multiple populations simultaneously. Limited migration between populations. Diversity.

13. Independent-Sampling GA Traditional GA: search solution space by generating offspring with selection, crossover, mutation. ISGA: search solution space using independent sampling. Independent sampling phase. Breeding phase. Why? Better population diversity. Adaptive mechanism. Fewer parameters to tune.

14. Independent-Sampling GA Population initialization and fitness testing as normal. Independent Sampling: Generate offspring chromosome, one gene at a time, by independent sampling. Evaluate new offspring. If fitness score is higher than the lowest population fitness, replace the low-fitness chromosome with the offspring. Breeding: Select two parent chromosomes (i.e. using tournament fitness). Generate offspring using crossover, and then fitness test. Replace parents if offspring have higher fitness.

15. Real-Coded GA Traditional GA: uses binary genes. Real-coded GA: uses real floating value genes. Why? Better precision. Solve optimization problems with continuous variables and solution space.

16. Genetic Algorithm variants GA Variant Advantages Disadvantages Messy Overlapping genes can handle problems with high epistasis Non-binary encoding scheme Each gene can contribute to multiple traits, which can be difficult to interpret Adaptive Adapt to changing problem landscapes More efficient than fixed-parameter GAs in some cases Requires a self-adaptive mutation rate, which can be complex to implement Parallel Speed up the optimization process by utilizing multiple processors or machines Handle large-scale optimization problems Requires a suitable parallelization technique and infrastructure Synchronization and communication overheads may affect performance Independent Sampling Reduce the risk of getting stuck in local optima Increase the diversity of the final solution Requires multiple independent runs, which can be time-consuming Final solution may not be as good as that of a single run Real-Coded Handle continuous variables and improve search efficiency for certain problems Produce more accurate solutions than binary-coded GAs for certain problems Requires a larger search space, which can be computationally expensive More complex to implement than binary-coded GAs

17. Genetic Programming: Principles GP uses natural evolution principles for different problem domains. Multiple individuals form a population. Individuals can reproduce. Reproduction transfers traits from parents to offspring. Many factors affect the survival of individuals. Natural selection favours fit individuals. GP evolves computer programs to solve problems, i.e. automatic programming.

18. Genetic Programming: Program Program using tree structure representation. Each node can be: Arithmetic function (i.e. addition, subtraction). Logical function (i.e. AND, NOT). Terminal : input variables, constants. Tree structure : depth, complexity, branches.

19. Genetic Programming Initialize population of computer programs. Fitness test each program. Performance: does the program run? How well does it solve the problem? Complexity: how big is the program? How long does it run? Create new offspring program: Selection: choose two or more parent programs. Crossover: randomly swap nodes between parents. Mutation: change a node to another type of node. Architecture: modify the architecture of the offspring.

20. Genetic Programming: Characteristics Human-competitive. High-return. Routine. Machine intelligence.

21. Genetic Programming: Characteristics Human-competitive :

22. Genetic Programming: Characteristics High-Return : described using “artificial-to-intelligence ratio”. Artificial: how much of the program is automated. Intelligence: how much of the program requires human intervention. Examples: Deep Blue chess computer. High A: very good at playing chess. High I: requires years of development by a dedicated team. Results: low A-to-I ratio.

23. Genetic Programming: Characteristics Routine : how well does the program handle new problems intra-domain, and inter-domain, with minimal human intervention. Machine Intelligence : how well does the program fulfil the three principles inspired by Turing: Logic-driven search: search algorithms, constraints, rule-based systems. Cultural search: previously acquired knowledge is stored and used for solving future problems, i.e. knowledge-based expert systems. Genetic or evolutionary search: evolve newer, better solutions from existing solutions.