Generating new images using Genetic Algorithms
The Gaia program has been developed as a tool to generate new kind of images. Based on the paper Artificial Evolution for Computer Graphics from Karl Sims (Computer Graphics, Volume 25, Number 4, July 1991), it uses the ideas of genetic algorithms and evolution to assist the user in the creation of new images. Every image is generated evaluating a mathematic formula in the real domain. The problem is to find formulas which upon evaluated give us interesting images. We use genetic algorithms to find this formulas.
Starting from a random and simply formula, the program generates multiple variations of the current image modifiing slightly the formula.The new formulas are evaluated and the results presented to the user, which will choose and select the most interesting based on his artistic criterion. The selected formula becomes the new generator and the process is repeated again, closing this way the cycle. We are using the concept of evolution to find new formulas from the current ones, in a way the new formulas become not so simply, and the asociated images quite good looking.
The program can also generate smooth transitions between any images generated in the program. The user selects and source and the target images, and the program finds the frames which will transform the source image in the target image. If the formulas used to compute the images have nothing in common, the transition will be a pure melt, but if the formulas have some similarities, we obtain an interesting transition of forms.
The running times of most of the algorithms used to solve problems are bounded by some polynomial in the size of the input. We call such algothims efficient algorithms, and call the corresponding problems tractable problems. In other words, we say that an algorithm is efficient if its running time is O(P(n)), where P(n) is a polynomial in the size of the input n. Recall that the size of the input is defined as the number of bits required to represent that input. The class of all problems that can be solved by efficient algorithms is denoted by P (for polynomial time). This definition may seem strange: an algorithm that run in time O(n10) is not efficient by any standard, although by the same reason an algorithm that runs in time 109n is not efficient, even though it is lineal.
When a problem is not known to have an efficient algorithm to solve it, it is called an NP-Completeness problem, and the genetic algorithms can be applied to solve this problems in a reasonably running time.
Genetic algoritms borrow many terms from the genetic naturals. Often we call population to a group of solutions, and a solution is named as individual. Every time a new group of solutions is created, we have a new generation.
To solve a problem using genetic algorithms we need:
Once we have pose the problem, all genetic algorithms proceed in a similar way:
Karl Sims explains the concepts of genetic algorithms in his paper Artificial Evolution for Computer Graphics:
The genotype is the genetic information that codes for the creation of an individual. In biological systems, genotypes are normally composed of DNA. In simulated evolutions there are many possible representations of genotypes, such as strings of bynary digits, sets of precedural parameters, or symbolic expressions. The phenotype is the indivual itself, or the form that results from the developmental rules and the genotype. Expression is the process by which the phenotype is generated from the genotype. For example, expression can be a biological developmental process that reads and executes the information from DNA strands, or a set of procedural rules that utilize a set of genetic parameters to create a simulated structure. Usually, there is a significant amplification of information between the genotype and phenotype.
Selection is the process by which the fitness of phenotypes is determined. The likelihood of survival and the number of new offspring an individual generates is proportional to its fitness measure. Fitness is simply the ability of an organism to survive and reproduce. In simulation, it can be calculated by an explicitly defined fitness evaluation function, or it can be provided by a human observer as it is in this work.
Reproduction is the process by which new genotypes are generated from an existing genotype of genotypes. For evolution to progress there must be variation or mutations in new genotypes with some frequency. Mutations are usually probabilistic as opposed to deterministic. Note that while selection is deterministic and is erformed on phenotypes; variation is usually random and is performed on the corresponding genotypes.
The repeated cycle of reproduction with variation and selection of the most fit individuals drives the evolution of a population towards higher and higher levels of fitness.
Sexual combination can allow genetic material of more than one parent to be mixed together in some way to create new genotypes. This permits features to evolve independently and later be combined into a single individual. Although it is not necessary for evolution to occur, it is a valuable practice that can enhance progress in both biological and simulated evolutions.
Looking at the design of Gaia it is possible to identity the previous concepts of genetics algorithms: genotypes, fenotypes, selection, and evolution.
Gaia codes every image generated with a formula and a domain. Both elements are the genotype of the solutions. The formulas are mathematical expressions built from a set of operators and constanst. The expression is stored in lisp format, and tells Gaia how the image should be evaluated. Instead, the domain tells Gaia where the formula should be evaluated. The domain is simply a region of the real plane specified as the limits in both directions. The default domain used is [-1..1] x [-1..1].
These are examples of genotypes:
| Lisp Expression |
Domain |
| (+ (+ (X) (Y)) (Y)) |
[0..1] x [0..1] |
| (gradient (invert (- (0.5) (RAD)))) |
[-1..1] x [-1..1] |
|
(abs (lerp (mynoise (/ (triwave (mod (PHY) -0.190)) (RAD)) (min (RAD) -0.873)) (Y) (X))) |
[-1..1] x [-1..1] |
In Gaia, the fenotypes are the images generated as bitmaps, obtained after evaluating the expressions on the domain. The expressions are compiled and then interpretated.There are some operators which returns an image or another depending on where the expression is evaluated (domain), so the same expression can look very different depending on the domain used. From a simply genotype we can obtain the same image with the desired resolution, because the domain is continuous and is always sampled with as many samples as needed.
Because of the lack of a real fitness function, selecction is performed directly by the user. He will chosse which are the interesting images and which are invalid ones. The program will use the selected images to generate a new population of images modifiying slightly his genotypes. This point differs from other uses of the genetics algorithms, where there is available a fitness function which can automate the process without the need of a user.
There are two ways in which Gaia generate new offspring: Mutation and Sexual Combination.
Mutation generates new genotypes from a single one: the parent. His expression is modified changing some operators, rearraging the order in which operators are coded, etc. This way, the parent and child expressions share the same basic structure, while differ in little (or maybe big) points.
Sexual Combination is the process used to obtain new genotypes from two parents. The idea is to mix the expressions of both parents in a way that some sequences of operators remain the same in the children. This way, the child has some sequences of one parent and some sequences of the other, and the resulting image (after evaluting the new genotype) presents characteristic of both parents.
|
Juan Luis Abadía jlabadia@iua.upf.es Last update 22 July 1997 |
|
[Index] [Next] |