1 Q1

1.1 Implementation Genetic Algorithm

  • Pseudocode Procedure

    • START
    • Generate the initial population
    • Compute fitness
    • REPEAT
      • Selection
      • Crossover
      • Mutation
      • Compute fitness
      • UNTIL population has converged
    • STOP

2 Q2

2.1 No Crossover & Mutation Simulation

  • In following non-overlapped painting figure, it indicates that there exits locations that does cannot be painted with painter_play(rules,room) function. This is the drawback of painter_play(rules,room).

  • 100 x 100 Empty Room

  • https://youtu.be/0y88A6gsSpc

2.2 Crossover + Mutation Simulation

  • Single Crossover produces offspring by recombining two parent chromosomes

  • Assumption :

    • Crossover operation is executed with the probability
    • Crossover point is randomly chosen
    • The strings are swapped with respect the crossover point between the two parents

2.3 Code: Crossover and Mutation

2.4 Results Q2

  • The results outputs with or without single crossover and mutation show that there exits a lots of corner room space that cannot be painted with this paint_play alogrithm.

3 Q3

3.1 Results Q3

  • The following plot is 100x 100 empty room simulation with and without crossover + mutation. They show that
    • for short-run generation simulation, there exit a very big jump (or fluctuation) of average effiicency fitness scores for all two cases.
    • for long-run generation simulation, there exits equilibrium average effiicency fitness scores for all two cases.
    • for short-run generation simulation with crossover + mutation, there is relatively jump ( or fluctuation) average effiicency fitness scores. This big jump or functation is due to the pre-determined rule-based chromosomes , crossover and mutation.
  • https://youtu.be/8fE7eHpMMwE

3.1.1 Suggestions

  • The following two plots shows that

    • by changing the crossover point with a fixed mutation = 0.2 , the short-run average efficiency fitness score will increases sharply
    • by changing the mutation probability with a fixed crossover point = 45, the short-run average efficiency fitness score will increases sharply

  • To improve the average efficiency fitness score, I suggest to implement adaptive evulationary change the crossover point and mutation probability with interaction to the empty room local position environment.

4 Q4

4.1 Simulation I: No Crossover + No Mutation

4.2 Simulation II: Random Crossover + Random Mutation

4.3 Simulation III: Comparsion

4.4 Simulation IV: Comparsion

4.5 Results of Q4

  • In simulation III of a 100 x100 Furnished Room,

    • the Average Efficiency with random crossover and random mutation is worser than that of without crossover and mutation in the short-run generations.

    • the Average Efficiency with random crossover and random mutation is better than that of without crossover and mutation in the long-run generations.

    • there exit a turning point of the Average Efficiency with against without random crossover and random mutation.

  • In simulation IV with random crossover and random mutation,

    • the Average Efficiency of a 100 x100 Furnished Room is always better than that of a 100 x100 Empty Room.

    • there does not exit a turning point of the Average Efficiency for furnished room and empty room with random crossover and random mutation.

  • No matter of furnished room or empty room with or without random crossover and random mutation, these four combinations indicated there still exists a lots of areas being not painted in short-run generation.

  • The average efficiency for all combinations is decreasing with increasing generation runs. This is the main drawback of genetic algorithm.