Survival of the Fittest: Natural Selection with algorithms

Date: 2015-10-07; view: 458.

Genetic Algorithms

Выживает самый приспособленный: естественный отбор алгоритмов

Brian Connolly

Survival of the Fittest: Natural Selection with algorithms

НАУЧНОГО ТЕКСТА ПО СПЕЦИАЛЬНОСТИ

КОНТРОЛЬНЫЙ ПИСЬМЕННЫЙ ПЕРЕВОД

Barra de Tijuca

This was a new city built 20km outside Rio. Its aim was to reduce pressure on housing in Rio. By 2000, 140,000 people lived in the new city. It was a completely self-contained city with its own shops, schools, medical facilities, etc. However, the houses in the new city were only really accessible for the rich and now Barra de Tijuca even has its own favelas.

MSDN Magazine http://msdn.microsoft.com/en-us/magazine/cc163934.aspx#S7

Выполнил:

магистрант кафедры АССОИ

Васильева Ольга Ивановна

Проверил:

доцент кафедры иностранных языков

Булатова Ирина Михайловна

Казань 2012

Brian Connolly

This article discusses:

Genetic programming definition

Breeding new algorithm generations

Cross breeding

Mutations

Increasing fitness

Genetic programming (GP) is one of the most useful, general-purpose problem solving techniques available to developers. It has been used to solve a wide range of problems, such as symbolic regression, data mining, optimization, and emergent behavior in biological communities.

GP is one instance of the class of techniques called evolutionary algorithms, which are based on insights from the study of natural selection and evolution. Living things are extraordinarily complex, far more so than even the most advanced systems designed by humans. Evolutionary algorithms solve problems not by explicit design and analysis, but by a process akin to natural selection.

An evolutionary algorithm solves a problem by first generating a large number of random problem solvers (programs). Each problem solver is executed and rated according to a fitness metric defined by the developer. In the same way that evolution in nature results from natural selection, an evolutionary algorithm selects the best problem solvers in each generation and breeds them.

Genetic programming and genetic algorithms are two different evolutionary algorithms. Genetic algorithms involve encoded strings that represent particular problem solutions. These encoded strings are run through a simulator and the best strings are mixed to form a new generation. Genetic programming, the subject of this article, follows a different approach. Instead of encoding a representation of a solution, GP breeds executable computer programs.

In this article I'll take a simple GP problem from the seminal textbook on the subject: John Koza's Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, 1992). The problem is to develop an artificial ant that will efficiently walk a grid that has a weaving trail of food on it. The objective is to breed the ant that will gather the maximum amount of food in the minimum number of steps.

I'll develop a UI that displays the problem grid and allows the user to control GP execution. The UI can be used to study the successive generations of ants. Any ant from any generation can be selected for study. Its generated C# code can be viewed, and the trail that it walked can be displayed on the grid.

The internal process works off of a base class that represents the problem. In this case, I developed a base ant class that implements the fundamental operations and state of an ant. The GP algorithm is used in order to breed new subclasses of this problem class. The algorithm uses the code document object model (CodeDOM) to generate a subclass and an Execute method implementation that represents a possible strategy for an ant.

This implementation is generic in the sense that it is driven entirely by a master "problem" class (the base Ant class). A developer can specify a new GP problem class that is modeled after the Ant class. For example, this might be a class representing the allowable functions for a symbolic regression problem. Since the internal GP processing doesn't have any special-purpose ant logic, the same architecture could be used to solve that problem as well.

I developed this implementation to demonstrate that the Microsoft® .NET Framework provides all of the tools that you need to do genetic programming. While this implementation meets all of the essential requirements to qualify as genetic programming, in its present state there is plenty of room for the solution to be augmented and improved. For example, complex selection, mutation, and pruning techniques could be used to explore the solution space far more thoroughly than does this simple example. But since they are essentially just mathematical refinements of the basic algorithm, this article demonstrates that .NET-based GP implementations can reach that level of sophistication.

In this article, I will describe the sample GP problem we'll be working with and will walk through the class relationships and the key implementation code. I'll also give you an overview of genetic programming and show you how ants can be evolved to walk a more complex trail, as well as how you can make changes to the problem class to make new operations available.