PGD Home

I have always been interested in Artificial Intelligence, and I spent several years working on AI related projects, including Neural Networks, Genetic Algorithms, and Logical Inference programs, as well as Game AI such as path finding techniques and decision making for games. I spent a lot of time creating “chatterbots”, basically AI programs designed to converse in a realistic manner with a human. These programs proved to be much more difficult than I thought to write, however I did make some good efforts.

I think that when creating a true, learning AI entity (as opposed to a rule-based AI entity, such as those used in most computer games) there are two main approached that can be taken. I call these “Bottom up” and “Top Down”.  I don’t believe these are industry standard terms, or even industry standard concepts, but it is how I learned to look at the field of AI, or at least, the parts of it that I was involved in.

A Top-Down AI program would focus on high level tasks, and be designed to emulate advanced behavour, such as communicating with a human, or playing chess. For example, a Top-Down AI program designed to play chess would have the rules of chess programmed in, and would be then programmed with a set of optimisation strategies for different moves and possibly learning techniques for predicting future moves of the opponent. In essence, this AI entity already “knows” how to play chess, the program just teaches it how to do it more efficiently or more intelligently.

A Bottom up AI program is different. It starts with no knowledge of the problem area, and must learn how to solve the problem completely by itself. For example, an AI program designed to navigate from point A to point B as efficiently as possible would begin with no knowledge of the route, and would then slowly explore and learn different behaviours and patterns as it progresses.

To date, I have concentrated on primarily Top-Down programs, attempting to emulate high level behaviour such as communication, and language skills. I have been interested in developing some Bottom-Up programs for some time, especially after coming across John Conway’s “Game of Life”. This is not an Artificial Intelligence program, but a” cellular automaton” demonstrating emergent behaviour. Having read about this, I had an idea.

I intend to create a virtual biosphere populated by a group of AI entities. Thes entities will begin knowing nothing about the environment (Bottom-Up) and will be programmed to learn and evolve in the same way as a real-life species. I will include variables such as availability of food, and water, predators, weather patterns, temperatures, mating, etc etc. It could be an intersting study in not only Artificial Intelligence, but also evolution and biology.

I intend to use a Genetic Algorithm as the basic for the AI entities. I have used these before, and I think they are well suited to this type of problem. A Genetic Algorithm is basically an AI program which evolves over time, slowly becoming better at solving a given task, in a similiar way to how evolution works in the real world.

To brush up on the subject and polish my skills, I have created a very simple concept test of a Genetic Algorithm. This only took a few hours, but it reminded me of the great potential that these concepts have for AI and problem-solving in general.

The program works by having the user first specify a “Target”, a number between 1 and a max value, also specified by the user. The program will then spawn a population of AI entities (Random Initialisation) and attempt to “guess” this number by first picking a number at random (within the range specified). Then, every “generation”, the entities with the “guesses” which are closest to the target number are chosen as the “Parents” (Selection). The average of these two parents is taken to produce a “child” (Crossover). Then a whole new generation of AI entites is created, with the “guesses” of each entity in the new generation being based on the child, plus or minus a small random amount (Mutation). This program finds the correct number almost all of the time, which is remarkable considering how simple it is!

The main disadvantages of it are, first of all the selection process. The program picks the best two entities from the previous generation, this is far too simple, it would have been better to implement a system like Tournament selection, or something similiar. Secondly, this program relies heavily on Mutation to work properly. Without it, the program would converge after just one generation, since there are only two parents. The child is used as a “seed” to create a new generation, but without mutation, the new generation will all be clones of the child. In most Genetic Algorithms (and in real life) the chances of a random mutation are much, much lower.

I intend to release the program and most of all of the source code in the next day or so, it is probably the simplest GA you can find, so it would be a good starting point for anyone looking to being programming with Genetic Algorithms.