2 files in total
genetic_alg.py
A PDF that contains your self-assessment & reflection
Log in to Coding Rooms
Navigate to the Assignment of Project 1: Genetic Algorithms
Work through each part of the project and use Coding Rooms to develop your code.
When you're ready to submit, download the 1 file for Gradescope.
Review the solutions to perform a self-assessment and write your reflection.
You may write up your self-assessment and reflection in whatever format is most comfortable for you (written on paper, typed in a Word or Google Doc, etc.), but you must convert it to a PDF before submitting. Please ask if you need help with this!
Submit the PDF to Gradescope and name it SelfAssessmentReflection.pdf.
Homeworks are an opportunity to engage with the material and practice your programming skills. To support you, solutions will be available on moodle. It is your responsibility to engage with them in a way that strategically moves your learning forward. You should:
Attempt the homework without looking at the solutions.
Review the solutions; if you were stuck, you may revise your homework. You may find yourself iteratively reviewing and revising to best support your learning.
When you submit your homework, you will be required to complete a self-assessment and reflection:
Give yourself an assessment mark on the initial attempt:
✘ if you did not complete it
✓- if you completed it, but were very far from the solution
✓ if you completed it and essentially had the solution
✓+ if you completed it correctly, including precise communication
? if you are unsure as to whether or not you completed it
Provide a short reflection as to why you earned that mark, such as:
I did not understand how to get started, and it was too close to the deadline to visit support hours.
I got stumped by a bug where my program entered an infinite loop.
If you used the solutions to revise your work, describe what you needed to change, as in:
I modified the style of my conditional when I saw a simpler approach in the solutions.
I was so stuck that the majority of my submission is based on the solutions.
Ask specific questions on portions that are still confusing, such as:
Why does it cause an error when I returned "1" instead of 1?
[Optional] Provide one hint for the homework (to your past self or future student).
genetic_alg.py
import random
def main():
print( "Genetic Algorithms -- Experiment in Progress" )
def test():
print( "Here is some testing code to play around with." )
randomNum:int = random.randint( 0, 255 )
print( f"The randomNum that was generated is: {randomNum}." )
if __name__ == "__main__":
# main()
test()
Artificial intelligence encompasses a vast area of research and techniques that aim to imbue computers with "intelligence." In this project, we'll focus on a particular approach that takes its inspiration from the evolutionary process. You'll be programming a simple version of genetic algorithms, which seek to improve "intelligence" by employing the principal of "survival of the fittest."
Create an initial population.
We'll maintain a population of 4 individuals, stored in a list.
We'll choose the initial population randomly.
Each individual in the population is composed of a sequence of genes, represented in the population list as a string of length 1 containing a single character.
We'll work with 8 genes, represented as a byte (8 bits!).
A single bit represents a single gene; each gene can either be "off" with a "0" value or "on" with a "1" value.
Choose a fitness function.
We'll use a simple fitness function that counts the numbers of "1" values.
We could think of each gene as encoding whether the individual can eat a certain food in the environment.
More "1"s mean more food and a higher chance of survival!
Specify how to produce the next generation.
We'll generate 6 individuals and choose the fittest 4 to move on to the next generation.
To generate a single individual:
We'll randomly pick 2 individuals from the current population (they might be the same).
We'll perform a single crossover event to select genes from the first parent and join them with genes from the second parent.
We'll perform a mutation event with 2 mutations: one "bad" mutation that forces a random gene to be off, and one "good" mutation that forces a random gene to be on.
We'll run the experiment across 6 generations to observe how the total fitness of the population shifts.
Here's a sample output of what your program will produce. While the characters representing the individuals and the fitness values will be different for you, you should have the same text print out (e.g., "The initial population is...").
The initial population is ['\n', 'Õ', 'Ç', 'x'].
The next generation is ['×', 'Æ', 'Ì', 'Ø'].
The total fitness went from 16 to 18.
The next generation is ['×', 'í', '^', 'Ò'].
The total fitness went from 18 to 21.
The next generation is ['ß', '}', 'm', 'W'].
The total fitness went from 21 to 23.
The next generation is ['\x7f', 'o', '7', 'Ù'].
The total fitness went from 23 to 23.
The next generation is ['û', '~', 'o', '7'].
The total fitness went from 23 to 24.
The next generation is ['Û', 'Û', 'o', '}'].
The total fitness went from 24 to 24.
Here are some videos that walk through the developer phases. The first two are longer, but hopefully will be a helpful reference as you proceed through the project (and can be watched at 2x speed!).
what specifically is being asked of us?
include working examples
how did I break down the approach into steps that map to functions?
how do the functions interact with each other?
the design leads to a skeleton file with stub definitions for the functions
by relying on the design phase, we can zoom in and focus on one function's implementation at a time
this allows us to use abstraction and not be distracted or confused by other parts of the program
we should test the specific function and have examples ready to evaluate whether the function is producing the expected behavior
This is your first project, and the instructions will walk you through a design. You'll be practicing:
writing function definitions from high-level descriptions
type-hinting and using mypy to make sure types are consistent
the iterative process of writing a little code, running your program and debugging
use what you learned in HW 2: xor Cipher to work with function "stubs" that allow the invocation of a function that has not been correctly implemented yet
Be strategic!
This project differs from the homeworks:
You will not have access to solutions for this project.
The Gradescope autograder will not be able to fully test your project.
This is because there are different ways to implement some of the design; with the randomness used in some functions, you may have a correct project that behaves differently than ours.
Be intentional around your approach to working on the project:
Start early!
Ask questions!
Leave time for questions by... starting early :)
When you're stuck, pause and evaluate what could be going on. Remember the self-regulated learning cycle!
Do you have a plan?
Are you evaluating your plan? How will you test your code as you go?
How will you revise? What will you do when you're confused? Stuck?
As with the previous homework, we will specify a design for you; we will tell you what functions to break the problem into and the expected behavior of each.
We'll specify each function's expectations for interaction and behavior.
You will write the corresponding function declarations.
You will also write a stub for the function body so that your code will run without errors (but with incorrect behavior)
The order in which you define your functions does not matter since you are using this approach of a "skeleton" program with stubs. The order that you see on this site corresponds to the steps of the genetic algorithm design process as well as a top-down design (except for the main function, which we keep at the bottom by convention).
Get started with your function stubs
For each of the following, write:
The function declaration with a docstring style comment
A stub body returning a placeholder value of the correct type
Check your types using mypy
Run your code in Python and make sure no bugs have snuck in!
Be careful of indentation!
Write the declaration and stub for a function called initializePopulation that:
expects no parameters
returns a list
has a docstring comment to indicate the behavior:
Create an initial population of 4 random individuals. Each individual should be represented as a single character whose Unicode value's binary number encodes the gene sequence of 0s and 1s.
has a stub body that returns the empty list [] as a placeholder
Write the declaration and stub for a function called randomIndividual that:
expects no parameters
returns a str
has a docstring comment to indicate the behavior:
Generate a random individual, represented as a single character whose Unicode value's binary number encodes the gene sequence of 0s and 1s.
has a stub body that returns the character "A" as a placeholder
Write the declaration and stub for a function called computeTotalFitness that:
expects one parameter named population of type list
returns an int
has a docstring comment to indicate the behavior:
Given a list with 4 elements representing the individuals of a population (each one character whose binary byte represents 8 genes, compute and return the total fitness of the population.
has a stub body that returns the placeholder value -1
Write the declaration and stub for a function called fitness that:
expects one parameter named individual of type str
returns an int
has a docstring comment to indicate the behavior:
Given a character representing an individual gene sequence, compute its fitness by counting the number of 1s in its binary representation.
has a stub body that returns the placeholder value -1
Write the declaration and stub for a function called produceNextGeneration that:
expects one parameters named population of type list
returns a list
has a docstring comment to indicate the behavior:
Given list of 4 strings (each a single character) representing individual gene sequences, produce the next generation of 4 individuals.
has a stub body that returns the placeholder value []
Write the declaration and stub for a function called newIndividual that:
expects one parameters named population of type list
returns a str
has a docstring comment to indicate the behavior:
Given a list of 4 individuals, create a new individual by picking 2 random parents (which might be the same), performing a single crossover and mutating the resulting individual. Returns the character encoded by the decimal value of the gene sequence interpreted as a binary number.
has a stub body that returns the placeholder value "A"
Write the declaration and stub for a function called crossover that:
expects two parameters named parent1Genes of type str and parent2Genes of type str
returns a str
has a docstring comment to indicate the behavior:
Perform a crossover operation of the two parent gene sequences. Assumes both parents are given as strings holding a byte. Pick a random crossover event and keep the first parent's gene up to (but not including) that point; then use the second parent's genes. Return the byte (as a string of length 8) representing the new individual's genes.
has a stub body that returns the placeholder value "00000000"
Write the declaration and stub for a function called mutate that:
expects one parameter named individualGenes of type str
returns a str
has a docstring comment to indicate the behavior:
Given an individual represented as a byte (string of 8 characters of 0s and 1s), perform 2 random mutations: mutate one gene to be a 0 and one gene to be a 1. Return the mutated individual (as a byte/string of 8 characters).
has a stub body that returns the placeholder value "00000000"
Write the declaration and stub for a function called mutateSingleGene that:
expects 3 parameters named individual of type str and mutationIndex of type int and geneValue of type str
returns a str
has a docstring comment to indicate the behavior:
Given an individual represented as a byte (string of 8 characters of 0s and 1s), perform the mutation at the specified mutationIndex to hold the geneValue. Return the mutated individual (as a byte/string of 8 characters).
has a stub body that returns the placeholder value "00000000"
At this point, you should have stub definitions for each of the 9 functions required to perform our simple genetic algorithms experiment. In this part, you'll implement each function as well as the main, testing as you go to check for any bugs you've introduced.
For each function, we have given you high-level pseudocode for how to implement the expected behavior.
Add a line in the test function body that
Invokes the function you are working on.
Prints out the result with a clear message, such as
print( f"Invoking initializePopulation() returned {initializePopulation()}." )
Run the program to make sure you see the stub value print out.
Replace the stub body of the function with the pseudocode.
Unlike HW 2: xor Cipher, each pseudocode step may correspond to multiple lines of code. This can depend on whether you use variables to store data at intermediate steps or perhaps you feel comfortable skipping this when it's not necessary.
You should copy the pseudocode to your program and keep it as a comment. See the Tips below for how to easily comment out lines of code.
You should add comments to help clarify the pseudocode for yourself.
Implement the pseudocode with valid Python code.
Check your types using mypy
Determine what you think the program should print, now that you've implemented the function with (hopefully) correct behavior.
Run your program again to see if the stub value has been replaced by your expected output!
Tips
Don't delete code unless you're 100% confident that it is useless -- comment it out instead!
Most IDEs support this keyboard shortcut to comment out the current line or a selected block of code:
CMD + / [on a mac]
CTRL + / [on Windows]
Be careful of indentation!
Be as rested as possible - little mistakes, like a typo, can create bugs that are sometimes very hard to spot!
Leave time to get help. Another pair of eyes can often spot little bugs, while talking through the task can help identify gaps in your understanding or clarify material.
You have peers, mentors, instructors, drop-in and office hours precisely for this reason!
Since we'll be using the same approach of converting between a single character and a byte holding its binary number representation of the Unicode value, you should copy-paste the code (or solutions) from HW 2: xor Cipher for these two functions:
charToByte
byteToChar
step 1: invoke the randomIndividual function 4 times to generate the individuals
step 2: pack the 4 individuals into a list using the bracket [] notation
step 3: print out the initial population
step 4: return the population list
step 1: invoke randint to generate a random number between 0 and 255, inclusive (meaning that 0 and 255 should be possible to obtain). [These are the smallest and largest decimal values that can be represented by a binary number with 8 bits.]
step 2: invoke the chr function to find the character encoded in Unicode by that number to obtain the represention of the individual
step 3: return the character representing the individual
step 1: compute the fitness of the first individual
step 2: compute the fitness of the second individual
step 3: compute the fitness of the third individual
step 4: compute the fitness of the fourth individual
step 5: add the fitness values of the four individuals
step 6: return the computed total fitness
step 1: convert the individual (which is a character value) to its binary representation as a byte (8 bits of "0" and "1")
step 2: use the string instance method count to find the number of "1"s
step 3: return the number of 1s
step 0: assess the current population by invoking the computeTotalFitness function
step 1: generate a set of 6 new individuals
invoke the newIndividual function 6 times
store these 6 individuals in a list called newPopulation
step 2: select the 4 most fit to move on to the next generation
sort the newPopulation list to get the most fit at the front of the list
invoke the sort method and specify the optional parameters reverse=True and key=fitness
extract the 4 most fit (at the lowest indices)
step 3: print the individuals in the next generation
step 4: compute the total fitness of the next generation
step 5: print out the change in fitness
step 6: return the next generation (list of 4 most fit individuals)
step 1: pick two random parents
generate a random index
access the element at that index to get one parent
generate another random index
access the element at that index to get one parent
step 2: expand both parents into their gene sequences by invoking the function charToByte on each parent to convert them to binary
step 3: perform a crossover to obtain the offspring's gene sequence
step 4: perform a mutatation to obtain the final individual
step 5: interpret the gene sequence byte as a binary number and convert it into a single character encoded by the decimal value (invoke the byteToChar funtion for this)
step 6: return the character representing the individual
step 1: pick random crossover point using the randint function
step 2: use string slicing and concatenation to keep parent 1's genes up to (but not including) the crossover point and gluing on parent 2's genes starting at the crossover point
step 3: return the new individual (as a byte/string of 8 characters)
step 1: perform "bad" mutation by
invoking the randint function to pick a random gene/index
invoking the mutateSingleGene to perform the mutation
step 2: perform "good" mutation by
invoking the randint function to pick a random gene/index
invoking the mutateSingleGene to perform the mutation
step 3: return the mutated individual (as a byte/string of 8 characters)
step 1: use string slicing to extract the genes/substring up to (but not including) the specified mutationIndex
step 2: use string slicing to extract the genes/substring after (but not including) the specified mutationIndex
step 3: glue together the first part of the gene sequence with the single mutated value and the last part of the gene sequence
step 4: return the mutated individual
Now that you've tested each of your 9 functions individually, let's put it all together by implementing our experiment in the main function.
Replace the definition of the main function:
Add a docstring comment that indicates the following behavior:
Run the genetic algorithm over 6 generations, printing out information about each generation to observe the overall fitness trend.
Implements the following pseudocode steps:
step 1: invoke the initializePopulation function to create the initial list of 4 random individuals
step 2: invoke the produceNextGeneration function 6 times to run the algorithm
Whew! You made it and hopefully have a fully functional program!!!
You can play around now and run the program to see how well the genetic algorithm performs!
Does the fitness improve between the initial generation and the final one?
Run it a few times
Do you ever see the fitness decrease during a single generation?
What about from the initial to the final?
If you want to try some other modifications, be sure to create a copy of your program, then experiment away!
Be sure to submit on Gradescope.