New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Evolutionary Computation

by: Khalil Conroy

Evolutionary Computation CAP 5512

Khalil Conroy
University of Central Florida
GPA 3.76


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in System Engineering

This 31 page Class Notes was uploaded by Khalil Conroy on Thursday October 22, 2015. The Class Notes belongs to CAP 5512 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 34 views. For similar materials see /class/227220/cap-5512-university-of-central-florida in System Engineering at University of Central Florida.

Similar to CAP 5512 at University of Central Florida

Popular in System Engineering


Reviews for Evolutionary Computation


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15
Evolutionary Computation Lecture 1 January 2007 Ivan Garibay igaribaycsucfedu Lecture 1 What is Evolutionary Computation Evolution Genetics DNA Historical Perspective Genetic Algorithm Components Individuals Populations Fitness Selection Genetic Operators Example 1152007 University of Central Florida School of EECS Introduction Motivation learn from nature Nature evolve strikingly complex organisms in response to complex environmental adaptation problems with apparent ease Localize and extract principles from nature Apply them to design algorithms 1152007 University of Central Florida School of EECS Evolution Charles Darwin 1859 On the origin of species by means of natural selection Reproduction does not produce a perfect copy always minor variations mutations Some variations are advantageous some are not Individuals with advantageous variations are more likely to survive and reproduce natural selection or the survival of the fittest The variations and inheritable Species are continuously adapting to their environment 1152007 University of Central Florida 4 School of EECS Genetics Science of heredity Gregor Mendel 1865 units of inheritance Genes traits Organisms form by cells Each cell has information necessary to construct a new organism genome Genome set of chromosomes Chromosome set of genes Genes are DNA segments associated with a characteristic ie eye color Allele is a particular gene value blue black etc 1152007 University of Central Florida 5 School of EECS Rethinking Evolutionary Computation DNA Information DNA molecule is an information structure Store information digitally chain of nucleotides Nucleotide deoxyribose sugar phosphate Nitrogenous base Nitrogenous bases Adenine Thymine Cytosine Guanine DNA is an amazingly efficient highly specialized structure for information storage replication expression and evolution 1152007 University of Central Florida School of EECS Historical perspective Evolutionary Computation l Evolutionary Strategies Rechenberg 1965 Population of two On1y mutation Rea1 value parameter optimization 1152007 Evolutionary Programming Fogel Owens and Walsh 1966 On1y mutation oEvolving Finite State Machines University of Central Florida School of EECS Genetic Algorithms Holland 1975 Population based Crossover and mutation Study adaptation Schema Theorem GA terminology from biology Chromosome string gene Po ulatlon p IndIVIdual Fitness based gt Selection Crossover Mutation Genetic Operators Generat39on Generation i1 1152007 University of Central Florida School of EECS Simple Genetic Algorithm procedure GA begin initialize population While termination condition not satis ed do begin evaluate current population members select parents from current population apply genetic operators to selected parents set offspring equal to current population end end 1152007 University of Central Florida School of EECS Genetic Algorithm Components Population of individuals Fitness Function Selection Function Genetic Operators 1152007 University of Central Florida School of EECS 10 Individuals m gene b1ooo111oo11o1o1111ooo1 allele Each individual represent a candidate solution String of 1 s and 0 binary representation Could take any other form tree integers etc Needs to be decoded to have meaning Genotype to Phenotype 1152007 University of Central Florida 11 School of EECS Rethinking Evolutionary Computation Problem Representation Gm 6 Z0 pWO 6 Different representations W are different problems for Genome DNA gt Organisms a GA Computational gt Instance of a Evolution Problem into a instance of a Structure Solution solution B S g ggijjgfggg Representation is very Important Logo instructions gt Antena De ne the Space to be explored Define the space structure variations are meaningful 1152007 University of Central Florida 12 Problem specific School of EECS Binary Representation 1000101 101101111 param 1 param 2 pararn 3 param 4 Example encoding 4 parameters Param1 value 1000 8 Param2 value 1011 11 Etc 1152007 University of Central Florida 13 School of EECS Fitness function Problem specific component Function takes as input an individual chromosome Function return a numerical value that determines how good the individual is Natural Selection fitness function environment Genetic Algorithm fitness function is user de ned Typically higher is better 1152007 University of Central Florida 14 School of EECS Selection Survival of the fittest Select the best individuals Based on fitness function Drives exploitation exploit good genes found so far Multiple Types Proportional Rank Tournament most used 1152007 University of Central Florida 15 School of EECS Fitness proportional Selection Holland 1975 Expected number of times an individual is selected to reproduce is proportional to its fitness relative to the total population fitness PSI fi fsum where fi is the fitness of individual iand fis the sum of fitness of all individuals in a pop Actual number of offspring may be far from expected number 1152007 University of Central Florida 16 School of EECS Rank Selection Similar to Proportional Proportional to their rank instead PSI rI rsum Rank selection is weaker than proportional in diverse populations Rank is stronger than proportional in converged populations 1152007 University of Central Florida 17 School of EECS Tournament Selection Select two individuals 2 Generate a random number r 0 S r S I 3 If r lt k select the better of the 2 individuals else select the worse of the 2 individuals l x Where k is a parameter Computationally efficient Previous methods require 2 passes Compute sum Calculate expected number of offspring Rank selection also requires a sort 1152007 University of Central Florida 18 School of EECS Genetic Operators Crossover Biologically inspired Combine genes from two individuals to form an offspring sexual reproduction Mutation Biologically inspired DNA is copied with errors mutations Most of the time mutation problem Some times advantage 1152007 University of Central Florida 19 School of EECS Onepoint Crossover Simplest form of crossover Advantage Fairly large change in individuals with very little disruption of information Parent 111 11100 110001100ffspring 1 gt Parent 2 01 00110 011111000ffspring 2 Crossover point 1152007 University of Central Florida 20 School of EECS Other Crossover Ops Two point select two points and exchange middles Uniform with probability px exchange or not each bit 1152007 University of Central Florida 21 School of EECS Mutation Single parent operator 11011oo llOllIOO Mutation rate M is per bit Mutation rate per individual M L individual length As a start M 1L per bit lssues Low mutation rate minimal exploration High mutation rate too disruptive 1152007 University of Central Florida 22 School of EECS Initialization Initial Populations are randomly generated Binary case are all randomly generated binary strings 1152007 University of Central Florida 23 School of EECS GA Convergence OneMax problem Example FUH 150 Best fitness 39 14D 6 ii H Hi quot 3939393939393939 quotIquot gt M Average fitness 120 100 m m a E 80 J ED 4U 20 Standard deviation D A 50 O 150 200 Generations 115hw WWW v WNW WNW 24 School of EECS Termination Criteria Found solution Number of generations Stagnation no more fitness improvement 1152007 University of Central Florida 25 School of EECS A GA by hand OnemaX problem Maximize the number of ones Population 0 Fitness 0 11001111 6 1 00100010 2 2 11100100 4 3 10011000 3 4 01100100 3 5 00001001 2 206 333 1152007 University of Central Florida School of EECS A GA by hand OnemaX problem Maximize the number of ones Population Fitness Selected parents llOOllll 11100100 00100010 11001111 11100100 11001111 10011000 01100100 01100100 11001111 00001001 OOlOOOlO University of Central Florida SchoolofEECS A GA by hand OnemaX problem Maximize the number of ones Selected parents X After crossover M 2 11180100 4 3 11101111 7 O 110 1111 6 11000100 3 0 11001111 6 6 11001100 4 011001 0 3 01100111 2 0 11001111 6 5 11001010 5 1 00100 10 2 00100111 0 1152007 University of Central Florida School of EECS A GA by hand OnemaX problem Maximize the number of ones After crossover M After mutation Fitness 11101111 7 11101110 6 11000100 3 11010100 4 11001100 11001100 4 01100111 2 01000111 4 11001010 5 11001110 5 00100111 0 10100111 5 286 467 1152007 University of Central Florida School of EECS A GA by hand OnemaX problem Maximize the number of ones Population 01 Fitness Population 1 l 1 Fitness 0 11001111 6 11101110 6 1 00100010 2 11010100 4 2 11100100 4 11001100 4 3 10011000 3 01000111 4 4 01100100 3 11001110 5 5 00001001 2 10100111 5 206 333 286 467 1152007 University ofCentral Florida School of EECS 1152007 Questions University of Central Florida School of EECS 31


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.