Evolutionary Computation - Ex 2

About the code

Question 1

• On the "best fitness" curve, both fitness-proportionate ("roulette-wheel") selection and tournament selection gave good results - converged quickly to the function's zero. Rank selection gave poor results.
• On the "average fitness" curve, tournamet selection gave the best results, fitness proportionate selection gave poorer results, and rank selection gave even worst.
• We came to the following conclusions:
  • Fitness-proportinate selection gives high priority to the best individuals, so they are selected more frequently to produce offsprings (by crossover). This is the reason for the fast convergence of the "best fitness" curve. However, the lower fitnessed individuals get selected rarely, causing the selection pool to consist only on a portion of the population. This way, the variety of the genes in the population is low, so the average fitness converges slowly.
  • Tournament selection examines individuals from the entire population, regardless of their fitness value, but in most cases selects the best fitnessed one. This is the reason for the fast convergence of the "best fitness" curve. On the other hand, on some cases low fitnessed individuals does get selected - thus maintaining high variety of genomes in the population. This selection methed differs from fitness proportionate method by allowing low fitnessed individuals to get selected more easily, so they are able to contribute their properties to the next generations.
  • Rank selection seems to over-compensate the low fitnessed individuals, letting them to be selected much more frequently than they really should. By this, the convergence rate of both curves is slow and unconsistant.

Question 2

• Repesentation: a genome consists of 10 binary digits. The i'th digit of the genome (i=1..10) represents card i's pile: 0 indicates pile0, 1 indicates pile1.
• Fitness: we have tried the simplest fitness function: the fitness is the absolute distance from the desired value.
  Formally:
  
  This fitness function lead to quite good results, so we haven't looked for a better fitness function. We have, though, tried to "fine tune" this function by weighting the different parts of the sum, with no remarkable achievments.

• Bitwise mutation with P_m=0.01.
• Signle-point crossover with P_c=0.7.
• Tournament selection with k=0.75.
• We have found that elitism mechanism improved the results drastically. Our elitism consists of keeping the two best-fitnessed genomes in the population, and passing them to the next generation as-is. We have plotted the results with and without the elitism to emphasize the benefit of this mechanism. We assume that other (maybe better) fitness functions could give better results without the elitism, but we are satisfied with the results we've got.
• The average fitness of the last generation is 0.68..., so we know for a fact that the problem was solved in some cases (fitness=0 means that the piles were orginazed exactly as requested).
  

Question 3

• The genome is an array of N cells (N=10, 20, 30, 40, 50), each cell contains an integer between 0 to N-1.
• The fitness method was chosen to be the number of possible attacks, when a single attack option counted only once. An "attack option" is described as:
  • Two queens in the same row
  • Two queens in the same diagonal
  We have slightly ignored the chess rules - consider the following situation:
  
  Queen A threatens queen B, and queen B threatens queen C, but since they are all on the same line, we include also the A - C attack option, so the total fitness of this situation is 3.
  We have tried the "real" chess fitness function, but no significant changes in the results were noticed.
• We have tested two different representation methods:
  • "Ordinal representation": Using TSP's ordinal representation. The value of each cell represents the number of "steps" to move in a cyclic, ordered list of row numbers (more descriptions at Q4). This method doesn't allow two queens to be at the same row, so any represented board doesn't include a situation in which a queen can attack another queen by moving straight (only diagonal attacks). This representation method can be translated into a permutation of the numbers 0...N-1.
  • "Position representation": genome[i]=j (the value of the i'th cell in the genome is j) means that there is a queen at column i, row j. This method allowes two or more queens to be in the same row, so it gives more freedom to the placement of queens on the board.
  We have found that the ordinal representation was a better method for small boards, but as the boards got larger, the position representation became the preferred representation method. We assume that the ordinal method enforces many constaints, so it might be more difficult for the GA to escape local minima. On the other hand, on small boards the ordinal method acts better, since there are less local minimas (the "zero generation" covers larger portion of the solution space), and applying the constraints help the GA to converge to the best solution more quickly.
• The crossover operator was chosen to be a standard single-point crossover operator (works on cells, not on bits).
• The mutation operator is a version of bitwise mutation, where instead of flipping a single bit, it assings a random value between 1 to N to the mutated cell. This method is suitable for both representation methods we have used.
• We have used local search mechanism, which slightly improved the results. See Q4 for full description of this mechanism.
• We have used tournament selection, with k=0.9 (90% of cases in which the best fitnessed genome will win the match). We have tried also rank selection and a version of roulette-wheel selection, but they gave poor results.

• P_m=0.01.
• P_c=0.7, with local search of N=10.
• Population size = 100.
• Generations = 100.
• Elitism - two best individuals move to the next generation

Question 4

• The genome is represented as an array of 24 cells (integers). Each cell may contain any positive number.
• To transform a genome to a path representation, we have used the ordinal representation: Each cell in the genome repesents the number of "steps" to move in a cyclic, ordered list of the cities. A city that have been visited (by the previous genome cells) is marked, so a "step" will go over it. In this way, we eliminate duplicate cities in the route. Since the list is cyclic, there is no upper limit for the cell values of the genome.
• We have not forced the starting city to be Tel-Aviv, since the route is cyclic.
• Fitness value is simply the total distance traveled, according to the given chart.
• Selection method was chosen to be tournament selection of m=2, with 90% of best genome to be selected, 10% of worst genome to be selected.
• The crossover operator chosen to be a double-point crossover. We have found that this type of crossover is slightly better than the single-point version. We assume that double-point crossover can make "precise cuts" in the genome, thus preserving good schemas better.
• The mutation operator is a switch mutation: The algorithm is simple: choose two random cells in the genome and switch between them. We have found that this mutation method was better than the standard bitwise mutation, at least in our test cases.
• In addition, we have found out that local search mechanism improves the results drastically. We implemented two versions of local search:
  • Crossover local search: when applying crossover on two genomes, perform N crossovers on them, and choose the best one (lowest fitness value).
  • Mutation local search: when applying the mutation on a genome, perform N mutations on it and choose the best one.
• As usual, we used an Elitism of the two best individuals in each generation.

• P_m=0.01, with mutation local search of N=10.
• P_c=0.9, with crossover local search of N=30.
• Population size = 100.
• Generations = 1000.
• All other improvements and features - as described above.

• The best tour was found in a separate run, over a long, long coffee break. The order of cities is:
  
  • Tel-Aviv
  • Petach-Tikva
  • Lod
  • Ramla
  • Rehovot
  • Ashdod
  • Ashkelon
  • Beer-Sheva
  • Arad
  • Sdom
  • Eilat
  • Ein-Gedi
  • Jerusalem
  • Beth-Shean
  • Afula
  • Nazareth
  • Tibirias
  • Metula
  • Zefat
  • Nahariya
  • Haifa
  • Zichron
  • Hadera
  • Nathania
  • Back to TA...
• Total distance: 1251 Km
• Execution parameters are similar to the GA described above, with the following modifications:
  • Generations=3000
  • Population=500
  • Crossover local search of N=50
  • Mutation local search of N=30
  • Bitwise mutation - similar to the one described in Q3
  Since this execuation took approx. 45 minutes, we haven't choose it to be the configuration to be reapeated for 10 times...