4/12 First Generation, Fitness Function, and Selection!

Done:

It's been a very eventful week! I am happy to say that my progress now includes significant algorithm additions!

First, I got my first populations up! I did, thankfully, end up using "join." I needed to make the tiles tuple into a list so I could change its tile properties. All I changed was the image object (stored in the tile objects) to whichever one I wanted, and now everything stayed the same (e.g., tile number, coordinate, etc.), but the image fed to "join" would be different!

At first, when I started with the simple test case of changing one tile, I had a sizing issue. This was fixed via resizing the initial disk images. For now, I decided to hardcode the tile image sizes because it splits the static 300x200 evenly. I can change it later on.

Then I tried individual populations with randomized tile placements. This makes use of my randomize work I did last week, looping through both that list and the tile object list and replacing the latter's current image with the former's current image.

I went on to get my first generation! Of course, it only has four populations, so I could easily display them. Looking sweet!

The fitness function was next. I coded it to do a pixel-by-pixel comparison. Each pixel that is correct increments a counter. For it to be correct, the R, G, and B all have to match exactly. Given I am dealing with the same initial and final image (albeit, the former with randomized tile placements), I can do an exact match. Later on, if I get to the advanced case of different pictures, I'll have to do something else, like a tolerance level.

Anyway, I ran into an issue where the original and manipulated images were yielding similar results. My only guess was that it was a shallow copy issue since changing one changed the other. Thanks to Dr. D, we were able to verify that the "list" constructor makes a shallow copy if fed a tuple. Once I did a deep copy (through a library), the issue was resolved!

Then I refined it to add up all the tiles of a population and calculate an average per tile. I don't know if this is a permanent decision, but it makes the numbers more manageable. Note that perfection would be 3000 pixels.

After that, I was onto selection. This has been very theory and calculation heavy, as there are many decisions to make. I know I want to do elitism, picking the 20% (for now) best out of the current generation. I refreshed on the different selection methods and thought about implementing some version of the roulette wheel. Unfortunately, after many theoretical attempts, I realized any application of it for my project would result in a time complexity of O(n^2), which is abysmal.

I finally went over to the bracket method, which simply compares a few items at a time and has the largest move on. As long as I keep the list random, it should work fine. I spent some time thinking about how to code the finding of elites. I would not want to pop them out of the list, as that would change the indexes, thereby losing the correlation with the tiles. I am currently comparing the time complexities of two methods. Both would make a copy list, but one would use Max (O((3n x E) + n)) and the other would sort and pop (O(n+ nlogn+E+(n x E))). I am assuming nlogn for the sort based on the unproven but probable point that Python sorts use TimSort, which is a stable version of merge sort.

For the rest of selection, I am still sketching out some ideas.

Next Steps:

Once I settle on ideas for both of those questions, I will test it in a test file using int lists. If it works there, I will try to implement it.