Hey, everyone, and welcome back to this class natural language processing in Python.
In this lecture, we will continue looking at our code to implement a cipher, a decryption algorithm.
This particular lecture will focus on implementing the evolutionary algorithm we discussed previously.
To initialize the algorithm, we must create a DNA pool containing 20 DNA strings.
So first, we initialize a variable called DNA pool and make that an empty list.
Then we do a loop that iterates at 20 times inside the loop.
We create a DNA string, which is just a list containing the lowercase alphabet.
Then we shuffle the DNA string to get a random mapping, and then we append this to our DNA pool.
So by the end of this loop will have 20 random DNA strings.
Next, we have a function to evolve offspring.
This takes in two arguments an existing DNA pool and the number of children that each individual will
create inside the function will initialize the offspring list to be an empty list.
Then we'll do a nested loop on the outer loop we lived through each parent in the DNA pool, on the
inner loop.
We'll iterate through the number of children that we need to create in order to create the child.
Well, we want to do is a random swap.
So first, we need to make a copy of the parent so that we don't overwrite it.
Next, we choose to random iness J and K, which will be the two positions that we want to swap.
These are just two random numbers between zero and 25 inclusive.
Next, we do this which.
First of all, a signed copy at Position J to a variable called Temp Next will assign copy at Position
K two Position J, then will assign temp to copy at Position K finally will append this mutated copy
into our list of offspring.
When we've completed the loop, we combine the offspring list with the parent list and then return that
as the final population.
Next, we have our main loop that actually runs the genetic algorithm.
There are some initialization variables before we enter the loop, so let's look at these numbers will
be the number of iterations of the loop to do so.
That's currently 1000.
That's the number of generations of offspring that we want to evolve.
Next, we initialize an array called scores, which will store the average score at each iteration of
the loop.
Alternatively, you could store the maximum score, but I didn't decide to do that.
Next, we want to keep track of some things the best DNA, which corresponds to the best map, which
corresponds to the best score.
Best score is initialized to minus infinity, which is the minimum possible score.
Next, we enter the main loop, which runs nanometers times inside the loop.
We first check if it's the first iteration or not.
If it is, then I will be zero and there's no need to create new offspring yet because we haven't yet
evaluated them.
If it's not the first iteration, then we need to create new offspring by calling the function we defined
earlier.
Evolve offspring.
Next, we want to calculate the score for each DNA string in our DNA pool.
So we start by initializing a dictionary called DNA to score.
The key to this dictionary will be the DNA string and the value will be at score.
Then we lived through each DNA string in the DNA pool.
Inside the loop, we convert our DNA string into a mapping that we can use to decode the ciphertext.
So this just loops through letters one and the DNA string in corresponding order, building a map the
same way we did at the beginning of this script.
The only difference now is that this is supposed to be a reverse mapping.
In fact, it doesn't really matter what the keys are.
As long as they stay consistent.
Next, we call the function and decode message to decode the ciphertext using the current map.
Then we pass this decoded message into the function and get sequence probe, which returns the log likelihood
of this decoded message.
Next, we store the score in our dictionary DNA to score.
Recall that DNA is currently a list of characters, but lists are not allowed as dictionary keys.
Therefore, we have to convert it to a string by calling the joint function.
Next, we check of the score we just found is better than our best score so far.
If it is, then we assign all the current values to be the best values.
So best DNA becomes current DNA, best map becomes current map, and best score becomes the current
score.
When we're outside the loop, we can calculate the average score of the population and store that in
our array of scores.
We would like to plot this later to see how the algorithm progressed.
Next, remember our principal survival of the fittest in this section of the code, we would like to
sort our current population by their score.
We only want to keep the most fit individuals.
In this case, I've chosen to keep the top five.
We can do this by using the sorted function in the sorted function allows you to sort a dictionary by
its values.
We pass in the key argument as X1, meaning that we care about the value and not the key of the dictionary
as the sorting key.
So the word key here is kind of an overloaded term because it really means two different things.
So whether you mean the sort key for the sorting algorithm or the key of the dictionary, so pay attention
to context there.
We also pass in reverse equals true because we want to sort by score in descending order.
What we get out of this is a list of two polls where each tuple contains a DNA string and its corresponding
score, and they are all sorted then to find the parents of the next generation.
We take the first five elements of this sorted list and keep only the keys which correspond to the DNA
strings.
Lastly, we have some debug stuff, so every few steps we print out the iteration number, the current
score and the best score so far.
And so this is a printout of the last time I ran this algorithm.