Here for your amusement, ridicule, or admiration is the first draft text of my final project proposal for my Artificial Intelligence class. Feel free to offer suggestions, poke fun, or correct my wretched grammar.


Begin
The intention of my final project and the subsequent presentation will be to illustrate the strength of genetic algorithm techniques for searching intractable problem sets. The problem in question is contrived, but is complex enough to be virtually insolvable by conventional search techniques.


The Problem

In order to properly demonstrate the usefulness of genetic algorithms, a problem had to be constructed that was both simple in design yet extremely complex to solve using conventional methods. The design that was created involves a simple game based loosely on Knuth’s PAC-world, which involves an adversarial relationship between two entities whose behavior is determined by fifty simple factors. These entities are pitted against one another in a fight for survival, the result of which is determined only by the subtle interactions between the fifty factors mentioned above. These entities will age, kill one another, give birth, and die of ‘old age’. The entity with the highest population at the end of a fixed amount of time will be declared to have the stronger attributes. The intractable nature of this scenario is in determining the proper combination of attributes that will create an entity capable of surviving against any opponent.


The Entities

The individual entities will each have fifty attributes that will determine their behavior when confronted with certain conditions within the game world.


1. Birth Factors (4 values)
a. These properties determine the behavior of a newly born entity into an empty cell in the world. An entity is born into an empty cell if another entity of the same family is facing that cell and is the stronger species. The Birth Factors determine how this new entity is born, that is, the attributes determine the direction that it will face given its parents age.
2. Replacement Factors (16 values)
a. When a cell in the world is occupied by an entity A and faced by a stronger enemy entity B, then the cell occupied by A is replaced by a newborn entity of type B. The Replacement Factors determine the direction that the newborn will be in given B’s age and the direction of the original A entity that was in the cell.
3. Edge Factors (3 values)
a. When a round ends, any entities facing the edge of the world will be turned according to the Edge Factors and age.
4. Empty Factors (3 values)
a. When a round ends, any entities facing an empty cell in the world and is not being attacked will be turned according to the Empty Factors and age.
5. Friendly Factors (12 values)
a. When a round end, any entities facing an entity of the same family will be turned according to its age and the age of the entity that it faces.
6. Enemy Factors (12 values)
a. When a round end, any entities facing an enemy entity will be turned according to its age and the age of the enemy that it faces.

The combination of all of the factors above coupled with the age of the individuals within the world work to create an incredibly complex problem fro determining powerful combinations of properties.

The Goal

Using the description above, I will attempt to design a genetic algorithm including an appropriate fitness function to attempt to find powerful combinations. This will be done by:
· Creating a strategy for pitting entity families against one another
· Determining the winners after a certain fixed number of rounds
· Combining strong attributes between families in order to attempt to create stronger decedents
· Introducing random mutations to avoid stagnation

The Implementation

The program to perform the project specifications will be written in Common Lisp.

-m