I checked the solution on my machine and it works, the results are consistent with those on README.md. The code runs very fast, in a matter of a few seconds, finding solutions up to size 1000. That is very impressive, so congrats :)

Your program uses an object oriented approach and defines many class properties, among which operators, which makes your objects very complete and organic. Exceptions are also raised in case of wrong usage, which is always nice.

All methods in the code are very well documented, following a specific format for usage, and the explanations are clear.

The code looks correct, with no redundant variables and no unnecessary loops, and it reads clearly. I couldn’t find any issues with it.
Just one small thing I noticed: in the heuristic method of class SolvedProblem you use your flatten method on the state, however you don’t actually use that for calculations. It might be part of an unused piece of code, but I thought I’d bring it to your attention.

All in all, great solution! I’m looking forward to seeing your implementations of other priority functions and see how they compare to this one in terms of performance.

Lab 2: Set Covering with GA Algorithm- Peer Review by Marco Pratticò (s294815)

Hi, I am Marco Pratticò (s294815) and this is my Peer Review.

Overview

The code is well-written and well-organized. I appreciate the use of classes with exhaustive comments and docs. The plots reported are really useful for seeing when the algorithm saturates.

Issues

• In this algorithm, you are accepting non-valid solutions when generating the offspring. The evaluation of non-valid solutions occurs similarly to the valid ones. I think (I tested it but I am not 100% sure) that the algorithm can get stuck on a non-valid candidate with a better fitness value, instead of accepting a valid solution. For example with N = 3, we suppose we I have two candidates: [[1], [2]] and [[1,2,3]] that we call respectively candidate1 and candidate2. We can compute their fitness, according to your definition, using w_coverage * covering_fitness + w_reps * reps_fitness) - w_reps with w_coverage = 0.2 and w_reps = -0.8 (without considering the normalization). For candidate1 we obtain 0.2x2 - 0.8x2 - (-0.8) = -0.4, while for candidate2 we obtain 0.2x3 - 0.8x3 - (-0.8) = -1. Since you are using a sorting function with reverse = True, in the first position of the sorted list we will find candidate1. So, doing fittest.append(self.population[0] - as in your code - you will consider a non-valid solution, instead of considering the optimal solution.

• A problem related to the previous point is that there is the possibility to find a non-valid solution and discarding other valid solutions. For example, for N = 20 and n_generations = 10 you will provide a non-valid solution at the end, while other valid solutions are discarded (I checked this part).

Suggestions

To solve this issue you can act in two ways:

• accepting just the valid offspring, but there is the possibility that you discard almost optimal solutions.
• accepting the non-valid offspring and adding a penalty to them. Please pay attention that acceptance with penalties reduces the risk of this issue but doesn't completely avoid it (I think).

From the graph, we can note that after a certain number of generations the algorithm saturates. The number of "useful" generations changes accordingly with the size of the problem. You can create - empirically - a mathematical function $N_{Gen} = f(N)$ to set the right number of "useful" generations.