1 – Method Similarities

Shelly, is there any idea of reducing the randomness of a time in generic algorithm like say in simulated? >> Well, not limitations that we have shown so far. But the fitness function naturally reduces the randomness as each generation gets closer to the solution. However, we could argue that the method could do better. … Read more

6 – GA Crossover Quiz

Try to apply what you’ve learned so far to complete this iteration of the genetic algorithm. First, fill in the fitness value or the number of non attacking pairs of queens for each board state in the initial population. Then, choose parents according to their fitness score and fill them in this column. Order them … Read more

5 – GA Crossover

Okay, let me handle this one. Given a parent 32752411. Which corresponds to a board that looks like this. We’ve randomly selected the spot between the third and fourth column. To be the crossover point. For the first child, we’ll take the first part of the first parent. Which we’ll mark in blue. Looking at … Read more

4 – Genetic Algorithms

Another specific we need to know before doing our genetic algorithms’ example is that there are 28 possible pairs of attacking queens on this eight by eight board. >> How did you figure that out? >> Well, we have eight queens, and we want to examine every possible pair that could attack each other. So … Read more

1 – Representing n-Queens

We’re going to use the n-Queens problem again to talk about genetic algorithms, but before we do that, we need to create a convention to represent a given board. >> We’ll use the one in the book. Since there can only be one queen in each column, we can encode a board with the number … Read more

2 – Simulated Annealing

Here is the version of the algorithm we’re going to use. Just like hill climbing, we’re going to iterate with simulated annealing, looking for points close to our current position that might have an improved value. However, we’re going to select our next position randomly from the points in the region near us. If a … Read more

1 – Annealing

We’ve been trying to emphasize algorithms that are of a particular importance. >> A star and alpha-beta pruning on the minimax algorithm are some examples. >> Now we’re going to introduce another key concept, simulated annealing. >> Hold on, simulated annealing? That implies that there’s real annealing too. >> That’s right, we’re going to steal … Read more

9 – Hill Climbing Quiz 2 Solution

Particle 1 starts at seven and with a step size of two, it reaches the peak of 10, with one step. Particle 2 starts at eight, it goes towards the peak, but then it oscillates around the peak because the step size is too large. Particle 3 starts at 10, follows this upward gradient, but … Read more

5 – Hill Climbing Quiz Solution

Particle 1 starts at x=1 and follows a positive gradient up, but then it gets stuck at the shoulder where y=2. Particle 2 starts at x=8 and follows a positive gradient up, but it gets stuck at this local maximum at y=6. Particle 3 starts at x=9 and follows the positive gradient in the right … Read more

10 – Local Beam Search

While we´re on this topic, I’d like to talk about local beam search. Because we’ll use it later in the course. >> Okay, it’s your show after all. >> The local beam search, instead of just using one position, which I’ll call particle, just because that’s how I think of it. We’ll keep track of … Read more