Genetic Algorithm Simulation

Version 1

Version 1 of the simulation has agents trying to find a path from a start position (marked in blue) to a goal (marked in red). An agent is defined simply by a position and a genome. This genome is extremely basic and consists of the move that will be made at each tick. An example genome for a 10 tick generation is ['u', 'd', 'd', 'r', 'u', 'l', 'l', 'd', 'l', 'u']. The simulation runs in generations, and each generation runs in ticks. At each tick, an agent can move either north, south, east, or west. At the end of a generation, each agent is given a score based on how close they are to the goal (ignoring any obstacles). The agents who have the lowest score will survive to the next generation. They will also randomly reproduce with other surviving agents. Offspring are created by splitting the parents' genomes at the same random position. The offspring's genome will consist of the first section of the first parent's genome and the second section of the second parent's genome. This resulting genome will then go through a mutation process, where each individual gene (or move) in the genome has a chance to be replaced with a random move. The simulation ends once the maximum number of generations is reached. In the simulation below, all of these values can be tweaked, and obstacles can be drawn by clicking on the grid.

This simple model obviously has a few drawbacks. For one, because an agent's behavior is based simply on a set of moves that is predetermined, the agent has no way to adapt to its position on the fly. Additionally, the fact that the reward is based on distance ignoring obstacles means that agents can easily be trapped and evolve to be caught in obstacles that allow the agents to get close to the goal without ever being able to reach it. An example of one such trap is shown below.

Sometimes this can be overcome by increasing mutation rate, ticks per generation, number of agents, and so on, but the more complex the traps are the worse the agents tend to evolve around them. This could be addressed by improving the fitness function or giving the agents a more capable "brain".

Version 2 - Neural Networks

Version 2 of the simulation has agents attempting the same task as above, however now the agents are controlled by a neural network. The input to this network is the agent's current position, the goal position, and the grid layout in the surrounding 3x3 area with the agent in the center. The network by default has 12 input nodes, an output layer with 4 nodes (with each node corresponding to a direction to move), and 2 hidden layers with 32 and 16 nodes respectively. As it turns out, these agents tend to have different behaviors than version 1 agents and appear to adapt quicker to changes in the enviornment, however they are not necessarily better than the version 1 agents.

Knapsack Problem

This simulation uses genetic algorithms to come up with a good solution to a given knapsack problem. Because the algorithm is not concerned with finding the absolute best solution and will instead find a very good but possibly not optimal one, the algorithm is much faster since it does not need to check every possible combination of items. Items can be added as candidates with the panels below the game, and items that are selected to be in the knapsack will be highlighted in green once the simulation finishes. More detailed outputs from the simulation can be found in the text box below the settings panels. In the traditional method of solving the knapsack problem, finding the optimal solution for 50 items would take an extremely long time (2^50 operations). In the simulation below, a reasonably good solution for 50 or more items can be found almost instantly.

Warning: for large problems (many generations, many items, etc.) the simulation may take a second to run and will freeze the page while doing so.