#evolutionary algorithm

[mermaidindustries]

THE DEVELOPER SPENT ALL TODAY IMPLEMENTING A SHADER FOR A VISUAL EFFECT AND WHEN IT WAS DONE IT TURNED OUT TO LOOK EXTREMELY BORING SO IN A FIT OF PIQUE SHE ADDED ONE ROUND() CALL AND ALL OF A SUDDEN IT LOOKED AWESOME

[sibaku]

Pokemon evolution(ary algorithm)!

For some details on the algorithm and implementation, see below ^^

Once upon a time I saw some images generated with basic shapes that tried to approximate some given image. Because I like the style, I made something like that myself. Problem was: There aren’t many good libraries to perform drawing shapes that also handled transparency and per-pixel operations. Coding all of that myself was too much work, so I used the easiest solution: JavaScript. Problem was... JavaScript is slow. Drawing a few hundred triangles and then comparing the resulting image to another given image was a lot of work, even using multiple workers to distribute it. I got maybe 5-10 images per second  that way. The algorithm I use is pretty simple but slow... so it took hours for at least some reasonable results.

A few days ago I decided to revisit this thing with the help of my trusty GPU. Basically I redid everything so it runs completely on the GPU. I now have about 600 images per second!

Here you can see some of my most liked pokemon :)

Following are some more details on how it works:

The algorithm: Take a set of triangles. Each consisting of three 2D vertices and a color with transparency. Now you draw them all. Now you compare the resulting image with the one you want to approximate. This can be done for example by comparing each pixel and adding the squared differences of each color channel (squaring makes everything positive, which is good, and also is a nice and smooth function). If the result is better than your current best, use this new one as your new best. Now you go over your triangles and with some probability change their vertices or colors. Then repeat from the drawing phase. This is a simple hill climbing algorithm. If you are more precise, this isn’t really a evolutionary/genetic algorithm, as there isn’t a population with stuff like crossover happening. But being a bit more informal here (and for the title to make sense :D) I will still call it evolutionary. Just think of it as having a single individual reproducing. Only the best will survive and live as long as it stays the best, outliving all its children. Each generation mutates slightly and has to adapt to the environment. So I would say the naming is at least a bit justified.

The implementation: If you want to do something like this, here is the general recipe. You generally want to avoid transferring data from your CPU to the GPU and back, as copying stuff needlessly is not good. My implementation uses OpenGL, but you may choose any other API, as long as it provides compute shaders and writeable buffers (you could of course emulate that with textures or other techniques, but that would require some more thinking). You put all your triangle data in a buffer. I use one vec2 buffer for the positions (length = triangles*3) and one vec4 buffer for colors (length = triangles). Those buffers are bound as a shader storage buffer object (SSBO) and can be accessed by all shader stages. One Compute shader updates the triangles. Each work item processes one triangle. The only important thing here is, that you have to implement your own pseudo-random number generator. Probably the best way is to upload some initial random seeds and then use a simple linear-congruental generator (https://en.wikipedia.org/wiki/Linear_congruential_generator). I use a more involved Tau-step generator, which is probably overkill, but I had it l lying around (used it in monte-carlo simulations, where the randomness is a bit more important).

The drawing phase can be very simple. Just bind your SSBOs as vertex buffer objects and draw with triangles mode. Or the more complicated (which I did for some reason, probably because of some other code I used elsewhere...): Draw n=triangles instanced points. Use a geometry shader to generate a triangle for each point from the buffers. Then just render normally. Will probably change that and hope to see some improvements. The result is rendered in a frame buffer object with attached color texture.

The next step is just some screen quad/triangle shader comparing each pixel of the input image with the rendered one and calculating the difference. This is again put in a frame buffer object texture.

The important part is the error calculation. If you use some kind of sum of values, which is probably reasonable, you have the problem of it being more of a sequential algorithm. Luckily there is a parallel sum algorithm (for example here https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html). If you render the drawing in a frame buffer object, you can bind the output texture as an image and use it for read/write operations. Thinking about the image being just rows (or columns) layed out sequentially, it is easy to transfer the 2D image sum problem to a 1D one corresponding to the algorithm.

A simple shader with only one dispatch item just copies the result into another SSBO, where the current maximum is also stored.

Next compute shader goes over all triangles. If old error in the SSBO is larger than the current one, this will just copy the contents of the current triangle buffer to the “best” buffer.

Only copy to CPU and back operation I do is to download the error and draw the image on the screen and for some error difference output it as a file. Then upload the buffer with the updated current best  error.

And that was basically all, in short form of course. You can of course do a lot better. Much to optimize, maybe use a real evolutionary algorithm, etc... But this was more or less a short two evening project, so it’s alright for now ^^

[heyguysiwrotesomething]

[ihaveaplan]

Acquired Intelligence & Adaptive Behaviour Week 3 - 3

Overview

1. What is evolution

2. Evolutionary Algorithms

3. Related terminology and concepts

- Fitness function

- Genotype and phenotype

4. Artificial Evolution vs Design

5. Examples

*References

- blog

- An Introduction to Genetic Algoirthms - Melanie Mitchell

1. Evolution

- For evolution to occur, you need a population of individuals that:

- has variation

- undergoes selection

- reproduces with heredity

1) Artificial Evolution

The main idea of artificail evolution is to simulate the imortant parts of evolution, to 'harness the creative power of evolution'. To get the computer to build such things, we have to build things beyond design. -> Intelligent behaviour rather than intelligent solutions

2) Evolution -> Evolutionary Algorithm

- In natural evolution, the accumulation of beneficial mutations can reproduce better adapted organisms.

- An evolutionary algorithm (EA), also known as a genetic algorithm (GA) is an attempt to capture this 'improvement of a system' that is the result of natural evolution.

3) Evolutionary Algorithm

- Simulates a population of 'individuals' that:

- reproduce with heritability

- are mutated to produce variation

- are selected on some measure of fitness

*Example:

- Evolution (directed accumulatio nof blind variation) is quite different form rational desgin.

- Human desgin tends to break systems down into components. These are themselves then broken down into subcomponents etc., until basic components are understood. (e.g. modern aeroplane or space craft design)

(1) Advantages

- They introduce different biases than those in place in typical human design.

- Allow us to consider alternative ways to 'solved a problem', other than how a human might have.

- Can be used to automate design:

- Engine design

- Scheduling problems

- Container load optimisation

(2) Different Biases

- Unlike typical human design, GAs are not biased against 'cheap tricks' - i.e. non-intuitive short-cuts to solving problems for hierarchical desgin.

- But they have their own biases.

- There must be an evolutioanry path to any solution given by a GA. (Consider how a bacterium could not evolve in one step (generation) into an elephant.)

- The biases of GAs are not easy to identify. They are influenced by how the genotype is related to the phenotype, how mutation takes place - lots of different, subtle things.

*Engine Design example:

(3) Genotype / Phenotype

- Genotype: the genetic materail, passed down from one generation to the next the order of the nucleotide on DNA, e.g. AGGCACATT...

- Phenotype: what undergoes selection, 'what the genotype codes for'. Typically the body and the brain in artificial evolution.

(a) In Engineering

- Genotype: (the encoding of the information) the angle of each aerofoil. E.g. g0 = [a1 a2 a3 a4 ... a8]

- Phenotype: (what the information encodes) the shape of the wing

(4) Fitness

- In the natural world, the fitness of an organism is determined by many complex interacting factors: predator, prey coevolution, sexual selection, competition with ocnspecifics, luck, etc.

- But evolution =/= evolutionary algorithms. In GAs, there is often a clearly deifned 'fitness function' guidign evolution towards a predetermined objective.

*Fitness in the aerofoil model is the amount of drag on the wing due the airflow.

(5) Evolutionary Strategy

*pseudo code:

[tahtallmijhar]

تحت المجهر: ماهي علوم الكمبيوتر و الخوارزمية التطورية ؟

عندما يتحدث الناس عن علوم الكمبيوتر, هذه الأيام ، فإنهم يتحدثون عن شيء أكثر تحديدًا، مثل العمليات التي تغذي أخبار, وسائل التواصل الاجتماعي لدينا.. فهل هذا كل ما نستفيد منها...

ماهي علوم الكمبيوتر و الخوارزمية التطورية ؟ - تحت المجهر

[modumax-blog]

I created my own version of Nicolas Tollervey’s ‘wordolution’ algorithm. This is an evolutionary algorithm which evolves words.

Starting with sets of randomly chosen letters, the algorithm selects the sets which are most like the ‘target species’ - the word you want the algorithm to produce. This way, over each generation, the sets of letters evolve into the target species. Then the algorithm stops and displays how many generations it took to get there.

I made this to get some first-hand experience at creating evolutionary algorithms. Although I didn’t use any of his code, Nicolas Tollervey came up with the concept (as far as I know), and I want to thank him for sharing it. I learned about the algorithm through this video: https://www.youtube.com/watch?v=OTHggyZAot0&index=2&list=LLiuzGi3LUDOAoHErlcdHFYw&t=1891s

[directive01]

Evolving sequences

[curiousaboutcreativity]

In the early 1990s, both Karl Sims and William Latham (with Stephen Todd) followed in the footsteps of scientist Richard Dawkins by combining evolutionary techniques and computer graphics to create artistic images of great complexity [...]. In the succeeding decades, a generation of artists/researchers have recombined, modified and extended these techniques, beginning the exploration of possible applications of evolution to aesthetic design. (3)

Lewis M. 2008. Evolutionary Visual Art and Design, in J. Romero & Machado P. (ed.) The Art of Artificial Evolution: 3-37. Berlin: Springer.