• Genetic algorithms represent a set of computional procedures utilizing basics of evolutionary biology. It is a search technique for solving optimization problems. The main idea of this approach is to make use of evolutionary tools such as inheritance, selection, crossover and mutation.
  
  Members shaping a search space of a problem are encoded as strings of characters. At first, a random population of a given number of individuals is generated. A following generation of the population is evolved by using the evolutionary tools. Subsequently a next generation based on the just evolved one is created in the same way. And the process continues, where every other generation aims to get closer to a solution of the problem.

• Nice task illustrating capabilities of genetic algorithms was published as a homework in the course CS 441/541 Artificial Intelligence taught by Melanie Mitchell. The assignement is presented in an unchanged form:


• Robby, the Soda-Can-Collecting Robot. Robby’s job is to clean up his world by collecting the empty soda cans. Robby’s world, illustrated in figure below, consists of 100 squares (sites) laid out in a 10 x 10 grid. You can see Robby in site 0,0. Imagine that there is a wall around the boundary of the entire grid. Various sites have been littered with soda cans (but with no more than one can per site).

• Robby isn’t too intelligent, and his eyesight isn’t that great. From wherever he currently is, he can see the contents of one adjacent site in the north, south, east and west directions, as well as the contents of the site he’s currently in. A site can be empty, contain a can, or be a wall. For example, in figure above, Robby, at site 0,0, sees that his current site is empty (i.e., contains no soda cans), the “sites” to the north and west are walls, the site to the south is empty, and the site to the east contains a can.
  
  For each cleaning session, Robby can perform exactly 200 actions. Each action consists of one of the following seven choices: move to the north, move to the south, move to the east, move to the west, choose a random direction to move in, stay put, or bend down to pick up a can. Each action may generate a reward or a punishment. If Robby is in the same site as a can and picks it up, he gets a reward of 10 points. However, if he bends down to pick up a can in a site where there is no can, he is fined 1 point. If he crashes into a wall, he is fined 5 points and bounces back into the current site. Clearly, Robby’s reward is maximized when he picks up as many cans as possible, without crashing into any walls or bending down to pick up a can when no can is there.
  
  The task is to write code for a genetic algorithm to evolve control strategies for Robby the Robot.

• There is a Status line at the top of the applet. Please notice the line, it informs about current applet’s activity.
• When the applet is working, there is a presentation of genetic algorithm's theory running in its lowermost part. It changes according to a currently running task. You can turn pages by clicking arrow buttons.

Create a new world by setting parameters Population size, Number of sessions and Number of actions per session. Their default values are 200, 50 and 50 (respectively). Do not set Population size > 1000, running time of a computation rapidly increases then. Keep remaining two paramters less than or equal to 100. These settings are binding for all rounds of evolution run in this world. Complete the creation process by clicking a button Create a world. Set evolution parameters Number of generations and Mutation probability. The more generations you set, the longer the evolution takes. It is better to start with lower values and run the evolution more times, if necessary. Leave the Mutation probability less than 0.01. The higher its value is, the more randomly the evolution proceeds and does not lead to desired result. Click a button Evolve to run the evolution. The process of evolution can take some tome. Check interim results published in a textarea. Its one line conforms to one generation. Fitness values of strategies within the generation are sorted from the greatest to the lowest in a direction from left to right. When the evolution is finished, see its results. There is a graph, that figures changes of best strategy’s fitness value in time. The best strategy overall is presented under the graph. The current best strategy is uploaded into a playground visualization in the right part of the applet. Click the button Create a playground to initialize the playground. By clicking Test strategy, Robby starts to move in accordance with uploaded strategy. If he is not stopped by a button Stop testing procedure, Robby performs number of steps determined by parameter Number of actions per session.

• Try another parameters’ settings and observe how the results of evolution change.