Week 1 Introduction PDF

General Information Course: Evolutionary Computation © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 1  Acknowledgement of Country We acknowledge and pay our respects...

General Information Course: Evolutionary Computation © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 1  Acknowledgement of Country We acknowledge and pay our respects to the Kaurna people, the traditional custodians whose ancestral lands we gather on. We acknowledge the deep feelings of attachment and relationship of the Kaurna people to country and we respect and value their past, present and ongoing connection to the land and cultural beliefs. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 2  ACTIVITY 30 seconds (no talking): what is/would be your superpower? © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 3  ACTIVITY 30 seconds (talking): ask your neighbours - for their name - what their superpower is/would be © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 4  Superpower of Many people working in EC: Seeing optimization problems everywhere! Dr. Adel Nikfarjam Slide Idea: Assoc. Prof. Markus Wagner © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 5  Welcome! Adel Nikfarjam(he/him) (Course Coordinator & lecturer) – [email protected] See course contacts on MyUni © 2021 School of Computer Science, University of Adelaide University of Adelaide Evolutionary Computation2 6  Assessment This course has 5 components: – Final exam (hurdle): 40% – Individual Assignment: 20% – 2 Group Assignments : 20% – Workshop Participation: 10% – Quizzes: 10% You are expected to participate in all activities, attend lectures, submit your assignments on time, and most importantly, take part in the final exam. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation7 7  Minimum Performance On each component with a hurdle, you are required to achieve at least 40% of the marks allocated in the component. If your mark for any component with a hurdle is less than 40% of the allocated marks for that component, and your overall mark is greater than 45 F, your overall mark will be reduced to 45 F. To pass the course, you must obtain a passing mark overall and achieve at least 40% of the available marks in components with a hurdle. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation8 8  Late submission policy You should hand your coursework in on time. If you hand in your work late, your mark will be capped, based on how many days late it is. – up to 1 day late — mark reduced to 75%, marks below 75% not affected. – up to 2 days late — mark reduced to 50%, marks below 50% not affected. – up to 3 days late — mark reduced to 25%, marks below 25% not affected. – More than 3 days late — mark is reduced to 0. If you handed in something on time, and it is worth more than something that you handed in late, you will get the higher mark. Hand in early! © 2021 School of Computer Science, University of Adelaide Evolutionary Computation9 9  Repeating Students Students who repeat a course are expected to attempt all of the aspects of the course again. This includes making fresh attempts at all coursework assessment items. You may apply to the course coordinator to have your previous work counted but this is not usually granted. Make sure that you attend all of the lectures, do all of the work and study hard for the exam – you don’t want to get stuck repeating the same course over and over. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation10 10  Assignment Extensions A student may be eligible for assignment extensions based on medical, compassionate, extenuating circumstances A student will be ineligible if their Circumstances: were avoidable and the student had reasonable opportunity to make alternative arrangements; relate to balancing workloads from other units of study, disciplines or faculties; were personal commitments or events such as international travel, holidays or weddings; relate to temporary minor ailments such as colds, minor respiratory infections, headaches or minor gastric upsets; relate to stress or anxiety normally associated with examinations, required assessment Evolutionary tasks or © 2021 School of Computer Science, University of Adelaide Computation any 11 11  Assignment Extensions For extensions, please contact the course coordinator course coordinator email If you think your situation is exceptional, contact your course coordinator ASAP, who will then consult the Head of School. Students who deliberately submit false or fraudulent documentation may be referred to the Student Misconduct Tribunal. You will normally only receive an extension equivalent to the number of days covered by your documentation. Don’t expect to get an extra week because you lost a day. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation12 12  Academic Integrity Useful link: https://www.adelaide.edu.au/student/success/academic-integrity- for-students Academic integrity values - Honesty - being honest about where your ideas come from - Respect - giving credit when you use other people's ideas - Responsibility - taking ownership of your work - Fairness - treating other students and scholars fairly - Trust - doing the right thing, even when nobody is watching - Courage - standing up for what is right The University takes academic integrity very seriously. For the most serious types of misconduct students can be suspended or completely excluded from the University. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation13 13  Types of Academic Misconduct 1/2 Plagiarism, where students present Work for assessment or publication that is not their own, without attribution or reference to the original source. Collusion, where students present Work as independent Work when it has in fact been produced in whole or in part with others (including persons external to the University) unless prior permission for joint or collaborative Work has been given by the Course coordinator, as specified in the Course Outline. Copying, where a student acts in such a way as to seek to gain unfair advantage or assist another student to do so. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation14 14  Types of Academic Misconduct 2/2 Cheating in Examinations means engaging in dishonest practice or breaching the rules during or in relation to Examinations Contract Cheating, where a student submits completed or partially completed Work that a third party has completed for them, regardless of the relationship between the student and the third party or whether the third party is paid or unpaid. This includes the submission of work completed by an AI agent, without the explicit consent of your course coordinator. Misrepresentation, where a student presents untrue information with the intention of deceiving or misleading the assessor. Solicitation, where a student offers or gives money or any item or service to a University staff member or any other person to gain academic advantage for the student or another person. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation15 15  Case 1 (based on real past incidents from UoA) l Ami (not her real name) is sitting her online and open resource exam. The exam asks for a definition of a key term. Ami knows that the correct definition is in her course notes so she opens the notes and cuts and pastes the definition into her exam. She doesn’t acknowledge the course notes. She thinks: “If the question is asking for a definition, it is best to use the proper definition given in the course materials – I don’t want to risk losing marks by paraphrasing or changing the definition in any way”. l Sam (not his real name) is also sitting the same exam. When tackling the same question Sam does a quick internet search and copies the answer directly from a website into his exam. He thinks: “This is an online exam so I don’t need to reference. Referencing is just for assignments” © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 16  l Students who had copied the lecture notes had not breached the policy. So Ami was found not to have committed a breach of the policy. No entry was made in the Academic Integrity Register. l Students who copied from the internet were found to have committed a breach (plagiarism) but this was considered to be as a result of a genuine misunderstanding of the policy. So Sam was found to have committed a breach as a result of a genuine misunderstanding of the policy. Sam lost a few marks from his exam as a penalty. This outcome was recorded on the University’s Academic Integrity Register and will be considered if Sam is ever suspected of breaching the policy again in the future. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 17  Case 2 l Ali, Sasha, Kiki, Kahn, John and Lizzie (not their real names) are enrolled in the same course and need to submit a research proposal. l The friends decide to work together to maximise their chances of finishing the proposal correctly. They get together to discuss their proposals and research ideas and methods. Kiki has done research proposals before and finishes hers first. She shares her proposal with the others. l The course coordinator suspected that one proposal may have been used by the others to frame and base their own proposals (Turnitin similarity report of 22%). The students said that they didn’t understand that it isn’t ok to work together. l Given the circumstances, the academic integrity officer decided that the students had breached the policy (collusion) but through a genuine misunderstanding. The students were allowed to resubmit the assessment. Each student’s name was recorded in the Academic Integrity Register. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 18  Case 3 l Tim (not his real name) posts his assignment to an online job site. l Someone else who is using the site alerts UoA. l Tim did not have a previous record in the Academic Integrity Register. l The academic integrity officer found that Tim had breached the policy (contract cheating) with no genuine misunderstanding and he failed the course. His name was added to the Academic Integrity Register. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 19  Case 4 l Molly and Kane (not their real names) are taking an online exam. l After Molly has finished the exam Molly gets a text from Kane. He says he’s finished the exam too but wants Molly to share her completed exam with him so he can compare their answers. l Kane actually hasn’t finished the exam. He contacted Molly because he didn’t know the answers. l Molly was upset that she was deceived by Kane. Kane was very apologetic. l So Molly was found to have breach of the policy (cheating in exams) but as a result of genuine misunderstanding and was penalised with a loss of 10% of the marks for the assessment. l Kane was found to have a second breach (with no genuine misunderstanding) and received 0% for the assessment. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 20  How to avoid plagiarism/collusion If you get stuck, seek help from the lecturer, tutor or prac demonstrator rather than copying from someone else. Starting your work early will help you to avoid getting stuck at the last minute. When in doubt, ask your lecturer. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation21 21  Guidelines for using AI generated content There are many content generating AI (text, code, solutions): use AI cautiously, understanding its bias and limitations be wary that AI generated content can be dramatically wrong submit content that you have created yourself When in doubt, ask your lecturer. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation22 22  Evolutionary Computation in Adelaide © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 23 Optimisation and Logistics Group University of Adelaide, Australia Prof. Frank Neumann E/Prof. Zbigniew Michalewicz [IEEE Pioneer Award, Science Excellence Award (STEM Professional)] Several PhD students. http://cs.adelaide.edu.au/~optlog Our research agenda: Develop algorithms for problems of high significance Build up a theory that explains how heuristic methods work © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 24  Evolutionary Computation © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 25 Introductory Example Computer-Automated Evolution of an X-Band Antenna for NASA's Space Technology 5 Mission This evolved antenna design is the first computer-evolved antenna to be deployed for any application and is the first computer-evolved hardware in space. PDF: http://www.mitpressjournals.org/doi /pdf/10.1162/EVCO_a_00005 YouTube video: https://www.youtube.com/watch?v= HAjozNpBiL4&t=1261s © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 26  Today’s Contents Positioning of EC and the basic EC metaphor Historical perspective Biological inspiration: – Darwinian evolution theory (simplified!) Motivation for EC Example of an evolutionary algorithm © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 27  Positioning of EC EC is part of computer science EC is not part of life sciences/biology Biology delivered inspiration and terminology EC can be applied in biological research © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 28 The Main Evolutionary Computing Metaphor EVOLUTION PROBLEM SOLVING Environment Problem Individual Candidate Solution Fitness Quality Fitness à chance for survival and reproduction Quality à chance for seeding new solutions © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 29  Brief History 1: the ancestors 1948, Turing: proposes “genetical or evolutionary search” 1962, Bremermann optimization through evolution and recombination 1964, Rechenberg introduces evolution strategies 1965, L. Fogel, Owens and Walsh introduce evolutionary programming 1975, Holland introduces genetic algorithms 1992, Koza introduces genetic programming 1992, Dorigo introduces ant-colony optimisation 1995, Kennedy, Eberhardt and Shi introduce particle swarm optimisation © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 30  Brief History 2: The rise of EC 1985: first international conference (ICGA) 1990: first international conference in Europe (PPSN) 1993: first scientific EC journal (MIT Press) 2020: Transactions on Evolutionary Learning and Optimization (ACM) © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 31  EC in the early 21st Century 3 major EC conferences (GECCO, PPSN, CEC), about 10 small related ones 2 scientific core EC journals (MIT Evolutionary Computation, IEEE Transactions on Evolutionary Computation) and many others uncountable (meaning: many) applications uncountable (meaning: ?) consultancy and R&D firms Em/Prof Zbigniew Michalewicz: 1st company: NuTech (now part of IBM) 2nd company: SolveIT (now part of Schneider Electric) 3rd company: https://www.complexica.com/ © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 32  GECCO 2021 (July) Authors and Countries Top 5 General Chair: Peter A.N. Bosman China 123 Editor-in-Chief: Gabriela Ochoa Local Chair: Tobias Friedrich USA 119 Germany 86 UK 84 France 65 33 Total authors: 1025 Total countries: 52 © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 33  GECCO 2024 General Chair: Peter A.N. Bosman Editor-in-Chief: Gabriela Ochoa Local Chair: Tobias Friedrich © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 34  GECCO 2024 General Chair: Peter A.N. Bosman Editor-in-Chief: Gabriela Ochoa Local Chair: Tobias Friedrich © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 35  GECCO 2024 General Chair: Peter A.N. Bosman Editor-in-Chief: Gabriela Ochoa Local Chair: Tobias Friedrich © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 36  Darwinian Evolution 1: Survival of the fittest All environments have finite resources (i.e., can only support a limited number of individuals) Life forms have basic instincts/lifecycles geared towards reproduction Therefore some kind of selection is inevitable Those individuals that compete for the resources most effectively have an increased chance of reproduction Note: fitness in natural evolution is a derived, secondary measure, i.e., we (humans) assign a high fitness to individuals with many offspring (?) © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 37  Darwinian Evolution 2: Diversity drives change Phenotypic traits: – Behaviour / physical differences that affect response to environment – Partly determined by inheritance, partly by factors during development – Unique to each individual, partly as a result of random changes “Suitable” phenotypic traits: – Lead to higher chances of reproduction – Can be inherited then they will tend to increase in subsequent generations, leading to new combinations of traits … © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 38  Darwinian Evolution: Summary Population consists of a diverse set of individuals Combinations of traits that are better adapted tend to increase representation in population Individuals are “units of selection” Variations occur through random changes yielding constant source of diversity, coupled with selection means that: Population is the “unit of evolution” Note the absence of a “guiding force” © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 39  Monkey King: find the treasure on the highest mountain y x © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 40  Monkey King: find the treasure on the highest mountain y x © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 41  Monkey King: find the treasure on the highest mountain y x © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 42  Monkey King: find the treasure on the highest mountain y x © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 43  Monkey King: find the treasure on the highest mountain y x © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 44  Example with two traits © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 45  Example with two traits © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 46  Adaptive landscape metaphor (continued) Selection “pushes” population up the landscape Genetic drift: random variations in feature distribution (+ or -) arising from sampling error can cause the population to “melt down” hills, thus crossing valleys and leaving local optima © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 47  Motivations for EC: 1 Nature has always served as a source of inspiration for engineers and scientists The best problem solver known in nature is: – the (human) brain that created “the wheel, New York, wars and so on” (after Douglas Adams’ Hitch- Hikers Guide) – the evolution mechanism that created the human brain (after Darwin’s Origin of Species) Answer 1 à neurocomputing Answer 2 à evolutionary computing © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 48  Motivations for EC: 2 Developing, analysing, applying problem solving methods a.k.a. algorithms is a central theme in mathematics and computer science Time for thorough problem analysis decreases Complexity of problems to be solved increases Consequence: Robust problem solving technology needed © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 49  Problem type 1: Optimisation We have a model of our system and seek inputs that give us a specified goal For example – time tables for university, call centre, or hospital – design specifications, etc. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 50  Problem type 2: Modelling We have corresponding sets of inputs & outputs and seek model that delivers correct output for every known input For example: evolutionary machine learning © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 51  Problem type 3: Simulation We have a given model and wish to know the outputs that arise under different input conditions Often used to answer “what-if” questions in evolving dynamic environments, e.g. Evolutionary economics, Artificial Life © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 52  Evolutionary Algorithms: Overview Recap of Evolutionary Metaphor Basic scheme of an EA Basic Components: – Representation / Evaluation / Population / Parent Selection / Recombination / Mutation / Survivor Selection / Termination Example: eight queens © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 53  Recap of EC metaphor A population of individuals exists in an environment with limited resources Competition for those resources causes selection of those fitter individuals that are better adapted to the environment These individuals act as seeds for the generation of new individuals through recombination and mutation The new individuals have their fitness evaluated and compete (possibly also with parents) for survival. Over time Natural selection causes a rise in the fitness of the population © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 54  Recap 2: EAs fall into the category of “generate and test” algorithms They are stochastic, population-based algorithms Variation operators (recombination and mutation) create the necessary diversity and thereby facilitate novelty Selection reduces diversity and acts as a force pushing quality © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 55  General Scheme of EAs © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 56 Pseudo-code for typical EA © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 57  What are the different types of EAs Historically different flavours of EAs have been associated with different representations – Binary strings: Genetic Algorithms – Real-valued vectors: Evolution Strategies – Finite state Machines: Evolutionary Programming – LISP trees: Genetic Programming These differences are largely irrelevant, best strategy – choose representation to suit problem – choose variation operators to suit representation Selection operators only use fitness and so are independent of representation © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 58  Representations Candidate solutions (individuals) exist in phenotype space They are encoded in chromosomes, which exist in genotype space – Encoding : phenotype => genotype (not necessarily one to one) – Decoding : genotype => phenotype (must be one to one) Chromosomes contain genes, which are in (usually fixed) positions called loci (sing. locus) and have a value (allele) In order to find the global optimum, every feasible solution must be represented in genotype space © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 59  Evaluation (Fitness) Function Represents the requirements that the population should adapt to a.k.a. quality function or objective function Assigns a single real-valued fitness to each phenotype which forms the basis for selection – So the more discrimination (different values) the better Typically we talk about fitness being maximised – Some problems may be best posed as minimisation problems, but conversion is trivial © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 60  Population Holds (representations of) possible solutions Usually has a fixed size and is a multiset of genotypes Some sophisticated EAs also assert a spatial structure on the population, e.g., a grid. Selection operators usually take whole population into account i.e., reproductive probabilities are relative to current generation Diversity of a population refers to the number of different fitnesses / phenotypes / genotypes present (note not the same thing) Onlineclicker.org: < to be revealed in 2 minutes > What is best: 1. ”Small” populations? (e.g. 10 individuals) © 20212. School”Large” of Computerpopulations? (e.g. 10 000 individuals) Science, University of Adelaide Evolutionary Computation 61  Population Holds (representations of) possible solutions Usually has a fixed size and is a multiset of genotypes Some sophisticated EAs also assert a spatial structure on the population, e.g., a grid. Selection operators usually take whole population into account i.e., reproductive probabilities are relative to current generation Diversity of a population refers to the number of different fitnesses / phenotypes / genotypes present (note not the same thing) Onlineclicker.org: 8889 What is best: 1. ”Small” populations? (e.g. 10 individuals) © 20212. School”Large” of Computerpopulations? (e.g. 10 000 individuals) Science, University of Adelaide Evolutionary Computation 62  Parent Selection Mechanism Assigns variable probabilities of individuals acting as parents depending on their fitnesses Usually probabilistic – high quality solutions more likely to become parents than low quality – but not guaranteed – even worst in current population usually has non-zero probability of becoming a parent This stochastic nature can aid escape from local optima © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 63  Variation Operators Role is to generate new candidate solutions Usually divided into two types according to their arity (number of inputs): – Arity 1 : mutation operators – Arity >1 : Recombination operators – Arity = 2 typically called crossover There has been much debate about relative importance of recombination and mutation – Nowadays most EAs use both – Choice of particular variation operators is representation dependant Question Which one is more important? (Crossover or Mutation) © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 64  Mutation Acts on one genotype and delivers another solution Element of randomness is essential and differentiates it from other unary heuristic operators Importance ascribed depends on representation and dialect: – Binary GAs – background operator responsible for preserving and introducing diversity – EP for FSM’s/continuous variables – only search operator – GP – hardly used May guarantee connectedness of search space and hence convergence proofs Question How about TSP tours? (Travelling Salesperson Problem) © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 65  Recombination/Crossover Merges information from parents into offspring Choice of what information to merge is stochastic Most offspring may be worse, or the same as the parents Hope is that some are better by combining elements of genotypes that lead to good traits Principle has been used for millennia by breeders of plants and livestock Question How about TSP tours? (Travelling Salesperson Problem) © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 66  Survivor Selection a.k.a. replacement Most EAs use fixed population size so need a way of going from (parents + offspring) to next generation Often deterministic – Fitness based : e.g., rank parents+offspring and take best – Age based: make as many offspring as parents and delete all parents Sometimes do combination (elitism) Quick Question Why is Survivor Selection needed? © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 67  Initialisation / Termination Initialisation usually done at random – Need to ensure even spread and mixture of possible allele values – Can include existing solutions, or use problem-specific heuristics, to “seed” the population Quick Question Seeding: what are disadvantages? Termination condition checked every generation – Reaching some (known/hoped for) fitness – Reaching some maximum allowed number of generations – Reaching some minimum level of diversity – Reaching some specified number of generations without fitness improvement © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 68  Please download and install the Slido app on all computers you use What are the disadvantages of using existing solutions, or use problem-specific heuristics, to “seed” the population ⓘ Start presenting to display the poll results on this slide. Example: the 8 queens problem Place 8 queens on an 8x8 chessboard in such a way that they cannot check each other © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 70  Please download and install the Slido app on all computers you use Which one is good solution presentation for the 8 Queens Problem? ⓘ Start presenting to display the poll results on this slide.  The 8 queens problem: representation Phenotype: a board configuration Genotype: Obvious mapping a permutation of the numbers 1 - 8 1 3 5 2 6 4 7 8 © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 72  The 8 queens problem: fitness evaluation Penalty of one queen: the number of queens she can check. Penalty of a configuration: the sum of the penalties of all queens. Note: penalty is to be minimized © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 73  The 8 queens problem: mutation Small variation in one permutation, e.g.: swapping values of two randomly chosen positions, 1 3 5 2 6 4 7 8 1 3 7 2 6 4 5 8 © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 74  The 8 queens problem: recombination Combining two permutations into two new permutations: choose random crossover point copy first parts into children create second part by inserting values from other parent: in the order they appear there beginning after crossover point skipping values already in child 1 3 5 2 6 4 7 8 1 3 5 4 2 8 7 6 8 7 6 5 4 3 2 1 8 7 6 2 4 1 3 5 © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 75  The 8 queens problem: selection Parent selection – Pick 5 parents and take best two to undergo crossover Survivor selection (replacement) – When inserting a new child into the population, choose an existing member to replace by: – sorting the whole population by decreasing fitness – enumerating this list from high to low – replacing the worst individual in the population © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 76  The 8 queens problem: summary Note: this is only one possible set of choices of operators and parameters © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 77  The 8 queens problem: example solution Phenotype: a board configuration Genotype: Obvious mapping a permutation of the numbers 1 - 8 2 4 6 8 3 1 7 5 © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 78  *** SUMMARY *** 1) This course is special… for many reasons. 2) Iterative algorithms, like evolutionary algorithms, let us explore search spaces in a “generate and test” manner. © 2021 School of Computer Science, University of Adelaide Evolutionary Computation 79