francescosorrentino/computational-intelligence---22-23

Public repository for laboratories and stuff of Computational Intelligence course.

Computational Intelligence course repository - Francesco Sorrentino

01URROV course repository of the Master Degree of Computer Engineering - AI & DA, PoliTo

Hello everyone! If you are here it means you are the professor or another student, probably.

Here a short guide to the repository, feel free to see and comment if you want, advices are always appreciated.

---

Poetry

The files:

poetry.lock
pyproject.toml

are used for the virtual enviroment of poetry.

---

Labs

Laboratories are organized in folders named "lab" followed by its number: here the list with a small description:

• lab1: set covering problem using tree/graph search.
• lab2: set covering problem using evolutionary algorithms (GA).
• lab3: playing Nim with different agents (hard-coded, evolved rules, min-max, reinforcement learning)

computational-intelligence---22-23's Issues

Rastrigin review

I take a look to your rastrigin soluton using evlutionary algorithms.

I've changend from axis=-1 to axis=-1 because I was getting an error while drawing the figure. By the way, your solution seems correct, and reach the maximum for the sphere. This is the output(i've modified it to print also the final point):

Solution starting from =[0.37454012 0.95071431]: solution point = [4.80484565e-07 6.70097760e-07], z =-6.798964253089707e-13

the final point it's closer enough to (0, 0)

Review Lab3 - Edoardo Alberti

Considerations

The code is well written and the README file is very explanatory!

In general the lab was carried out very well and there are not many things to say. Below a short report for each task

3.1

The hard coded strategy is simple and effective. Nothing to say about it!

3.2

Testing three different strategy was a great effort and you also obtained very good results but i have two things to say:

• I think that for the strategy #.1 alpha and beta are sometimes useless in the sense that the internal hard coded strategy may influence the results
• The strategy #.2 learns to exploits xor operations over and and or and i think that it is a very cool way to proceed (given that the optimal algorithm is based on xor too)

3.3

Very good minmax with a very well done apha-beta pruning. Again, nothing to say about it!

3.4

Exploring different strategies other than the one showed in class is a very efficient way to learn new concepts and the way they work! I think that you did a very good job given the results that you were able to obtain. (also thanks for the reference, i will dig into it ASAP!)

Lab2 Review using Issues by Diego Gasco (s296762)

SET COVERING WITH GENETIC ALGORITHM

GENERAL

Hi Francesco! I viewed and tried your solution for the review!
The Genetic Algorithm that you implemented is very interesting and I found some correlations with problems that I had also in my code.

MAJOR

• At the beginning I did the same tournament as your, but then I'have noticed that, for crossover operation where we need two genomes, it can be better to take two individuals without putting the first again in the list (in other words, doing peaks with no repetitions).
• I saw that your mutation rate is too small, so you trusted more the crossover operation. I know that mutation could not improve too much the searching of a solution. In my case I didn't accept new genomes that after mutations are already present in the population and I mutate them again, but this operation slow down a lot my algorithm!
• The fitness parameters, number of repeated elements and number of covered elements, are the same as I used. I think that this is one of the best heuristics that we can use with this problem.
• I appreciated a lot your shuffle function within the crossover! It adds a sort of driven-randomly approach to the algorithm and that is amazing.
• As you wrote on the README, I also faced the problem of time computation for small and high values of N. It seems that our solutions reward more the problems with middle-high N, in terms of computational time.
• One thing that I can prompt to you is to use a different data structure for the genome, just for not storing all the sets taken, but only a reference . You wrote that one possible alternative solution could be a list of integers in range [0,1], and this is basically what I've done with boolean. Another improvement could be to do a list of bit.
• If you need to do intersections as you did with the specific function, it can be cleaner to work with sets that have specific function to do that.

MINOR

• The only thing that I can suggest you to improve in your code is to add more comments.
  This is not a terrible issue obviously, but can be useful for the reading!

CONCLUSIONS:

Your solution is very good and performs well, in terms of results obtained, either for small and high values of N!
Great job :)

Peer Review by Francesco Fiorella (s303922)

The search algorithm

Overall, I like how you adapted the algorithm to this problem. I like the fact that you tried to implement the A* with different unit cost, at least to try finding a solution for higher N. Maybe there is a better heuristic function, but I myself have not been able to find it.
Storing the path is not useful, along with storing all the parent states.

A small "solution check" could have been included in the last part of the search algorithm:

if State == None:
   logging.info("Solution not found")
else:
   [...]

In this way, the algorithm does not assume that a solution can always be found and the logging is notified accordingly.

In the definition of the heuristic function you wrote: len(range(N)) - len(number_set(state)); however, len(range(N)) is basically equal to N.

The State

The use of the State type is ok, but it could have been more efficient by using "set" as data type.

Lab 2 Review by Sidharrth

Hi Francesco,

Here is my quick review pertaining to your approach to Lab 2.

Positives (both cosmetic and logical):

1. The README was well-documented and I was able to come close to your best results when running the notebook locally with the specified hyperparameters.

2. The shuffling after the intersection seems to add a sort of random diversity to the evolved set, so that is great. I'll take inspiration from this. However, I don't fully understand the mechanism of the shuffle function. It would be great if I could read some comments or if the variables $a$, $b$ and $c$ could be renamed.

3. The hyperparameters like offspring size were varied for different sizes of N, which was the same thing I did. I was wondering if there was an intuition for choosing certain values. This could be explained in the README.

Some things to look at:

1. Mutations are rarely applied in each generation (at an extremely low probability of 0.001). I recall there was a discussion on the Telegram group about the detrimental effect mutating had on the final solution, so I understand why you might have done this. However, I found that mutating in early generations helps improve exploration power.

2. A constant tournament_size of 2 is used for all values of N. Although early papers suggested the use of a constant, indiscriminate tournament size, recent papers like Yuri et al. advocated for adapting this parameter. I also used a constant size in my work, but this is something we can look at.

3. In the instances where mutation is done, only one type of mutation is used. You could try a diverse mix of mutation strategies like flipping, inversion, scrambling, etc. Since mutations haven't worked too well for you so far, the choice of strategy and aggression could be something to explore.

4. Runtime is rather slow for large values of $N$, which was the same case for me. This could also be because of the large number of generations (2000) the solution has to iterate through.

All in all, good job.

Peer review lab2 by Leonardo Rolandi (s301216)

Very clear explanation of the algorithm on the README, and interesting ideas for improving it and nice self-awareness.
For me your code, even if performs well for low Ns, have some problems.
First of all parameters are not functions of N, so the algorithm doesn't scale well, and it is missing the metric used to evaluate the performances on terms of time and computation effort (for example the count of the calls of the fitness function).
Then there isn't clever rappresentation of the problem (instead of putting entire lists inside individuals, you could have only inserted the indeces of the lists to save some memory, and results would have been the same.)
Remarkable the attempt to exit from local minimum thanks to the low selective pressure and the large population and lots of offspings, but i think that due to a not optimal decision of the type of genome and to the very low randomness things didn't work very well. There is randomness only in mutation and not in custom crossover, but the ratio between the two is less than 0.001, so random changes almost never happen.

def cross_over(g1, g2):
    g3 = intersection(g1,g2)
    g3 = shuffle(g1,g2,g3)
    return g3

def mutation(genome):
    mutation = random.choice(all_lists)
    if mutation in genome:
        genome.remove(mutation)
    else:
        genome.append(mutation)
    return genome

At the end the algorithm doesn't perform well for high Ns, and this is a pity 'cause in practice this is the range where GAs are more useful

Lab1 Review by Francesco Sattolo

Design considerations

• There is no need to compute the whole path up to the solution since we are only interested in the final state. For this reason we can avoid keeping track of parent states
• The State class is not really needed to represent the problem, a set/list of tuples would provide a lower overhead, increasing performances
• The number of steps, visited states and nodes processed is not consistent between different runs
• The program gets stuck in an infinite loop in case a solution does not exist

Implementation considerations

• There is no need to use numpy arrays since no specific function was used
• All .copy_data() invocations can be replaced with just .data, saving time, without compromising functionality
• In the h function, len(range(N)) can be simplified to just N
• The number_set function

def number_set(x):
#compute the set of number in the sequence.
y=set(range(0))
for _ in x._data.tolist():
	if type(_) == list :
		y = y.union(_)
	else:
		y = y.add(_)

return y

can be simplified to

def number_set(x):
y=set()
for _ in x.data.tolist():
	y = y.union(_)
return y

In fact:

• set(range(0)) is simplified to just set()
• accessing the protected attribute of the state x._data which is considered a bad practice, since attributes starting with _ are considered protected in python, so it is better to access x.data
• the else section is never executed

Peer Review by Leonardo Rolandi (s301216)

The algorithms you used are an excellent trade-off between results and computation time, letting the user to choose what to utilize according to his needs (A* star for a precise solution and greedy for a very fast one). The code also is very clear, and the small but big difference between those two approaches is shown and explained very well.
def h(state): return len(range(N)) - len(number_set(state))

"""A* approach""" final = search( INITIAL_STATE, goal_test=goal_test, parent_state=parent_state, state_cost=state_cost, priority_function=lambda s: state_cost[s] + h(s), unit_cost=lambda a: len(a), all_list=all_list, )

""" Greedy approach""" final = search( INITIAL_STATE, goal_test=goal_test, parent_state=parent_state, state_cost=state_cost, priority_function=lambda s: state_cost[s] + h(s), unit_cost=lambda a: 1, all_list=all_list, )
Small issues are that, in my opinion, you made the structure of the code too standard, basing yourself a little too much to the code shared in class. Simply because it wasn't really necessary to define a new class for the state, and as a result that complicated insted of simplify the data exchanging between collections and structures,
But congratulations for the great algorithms