#2 Lab2 Review

[vmask25]

Hi! I’m Simone and I’m relatively new to Python actually so I’ll try my best to understand your code, but if I miss something or write something wrong feel free to answer and correct me.

You structured your solution using a dedicated class, like in a fully object oriented language so it’s really ordered and clear. Your cross-over is not a 1-cut or 2-cut like I’ve seen in many other colleagues’ solutions, but it’s a uniform crossover, nice idea! We didn’t try it! Even if for higher values of N it doesn’t find good solutions (I don’t know if I missed something while copying your code in order to try it on my PC but with N=500 it explodes to w=12598), I think this program is very well done and can be easily improved with some small changes, and the effort spent here is evident. Really compliments!

Major:

• starting with a population made of individuals that already have “a lot” of taken lists can slow down the process at the beginning (slows down the convergence to the optimal), in the sense that taking each of the “problem_size” lists with a probability of 50% leads to have a lot of collisions e.g. in the case of N=5, in which only 3 lists out of the 25 lists are necessary to cover the N numbers in an optimal way, doing a 50% probability ends up in having a lot of initial individuals that takes nearly 12 lists out of the 25 problem lists. Beginning with a lower number of taken lists could reduce the time to converge to the optimum. In our solution e.g. me and my teammates put only one “bit” to 1, at random, in each individual, and all the others to 0, at the beginning. It could also be improved further maybe by starting with more than 1 (maybe proportionally to the problem size or to N because this extreme of putting just one bit to 1 can slow down the process too), but not too many like in the 50% probability case => The following generations need to work a lot, mutating and “cross-overing” a lot to remedy to this high presence of 1s, and this could also be one of the reasons why with higher values of N it cannot find solutions with fewer collisions (lower weight). I quickly tried to apply this reasoning in your code (putting just one random bit to 1 in each individual at the beginning) and the results for N=500 went down to w=1641 and for N=1000 your modified program gives w=3788, which are not bad results at all;

Suggestions:

• in the “fitness_eval” function the computation of covered numbers could be slightly improved maybe, I just discovered the code of one of our colleagues in which he uses the “reduce” function like in big data problems when handlings a lot of elements (https://github.com/dfm88/computational_intelligence_2022/tree/main/lab2) and he uses also an itertools function called “compress()” that takes the original list and the “masking bitmap” and returns what you call “all_values” automatically (https://www.geeksforgeeks.org/python-itertools-compress/), maybe in the end internally it does the same thing but surely could speed up the coding (and you can re-use it also in the final “get_solution” function);
• in the init function inside the loop for generating the initial population you append one individual at a time and perform a sorting operation after appending each individual calling “sort_population()” each time, isn’t it more easy/fast to do it just once at the end?
• you could remove duplicates from the initial list of lists, this was not explicit in the lab text, but as the Professor made in his solution, you can remove duplicated lists in the initial list of lists to have a smaller problem size to work with (reducing computational heaviness and time);
• I don’t know if you already followed the last lessons but just to highlight this, the Professor problem generation function sets the seed that leads the randomness of the entire program, so the Professor recently posted a new version of his function in which he saves the state before setting the seed, calculates the list of lists and then restores the initial state before returning the list, in order not to have always the same results at each execution of the program (maybe you already noticed that);
• if at each generation you check that the fitness tuple is (N, -N) you can understand that you already found the best/optimal solution so it’s useless to go on with the generations (or at least if your goal is not to explore all the search space but just to find the optimal solution in the shortest possible time). Anyway, with this seed of 42, it works only with low values of N like 5, 10, because already with 20 the optimal solution is 23 long so given that with a small N the program is already very fast this can be considered as a detail, furthermore with low values of N I think a combinatorial approach is not that heavy and assures you to get the real optimal solution.

Minor:

• in the “fitness_eval” function you compute each time the length of the genome using len(genome), actually you already have that information in self.problem_size given that you are using an object oriented pattern, it could simplify a little avoiding the len(..) function;
• the line “if random.randint(1, 10) < 10*self.mutation_chance:” with a mutation_chance of 0.2 is not actually the same of doing “random.random() < self.mutation_chance” without an additional multiplication?

In the end I would say that what I wrote is written with all the respect and understanding of the effort you put in this laboratory, hoping this review could help you too, very nice job!

[feurode46]

Hi Simone! Thank you so much for your detailed review and kind words. Your tips are very useful and I think you fixed THE biggest problem in my code which I couldn't figure out, which is the initial population selection. I had tried to implement mechanisms like removal of duplicates and checking if the solution is optimal, but I figured they didn't really matter for high values of N. However, just for completeness, I think I should at least implement the proper stopping condition. Again, thank you so much for your feedback!