[ art /
civ /
cult /
cyb /
diy /
drg /
feels /
layer /
lit /
λ /
q /
r /
sci /
sec /
tech /
w /
zzz ]
archive provided by **lainchan.jp**

[ Return /
Go to bottom ]

File: 1488273280622.png (633.78 KB, 300x227, puddle.jpg)

I'm learing GAs in school.

This thread is meant as a way for anyone interested in learning or sharing about GAs to do so.

I will post my progress here, hopefully this doesn't bother anyone or any rule.

If it does, then please tell me and I will stop.

This thread is meant as a way for anyone interested in learning or sharing about GAs to do so.

I will post my progress here, hopefully this doesn't bother anyone or any rule.

If it does, then please tell me and I will stop.

First I'll outline what I'm doing right now:

Evolving to maximize a function

The basic evolution algorithm has three main bastions:

* The genome

* The reproductive function

* The mutation function

###

The genome:

The way we encode our solution.

In this case we are asking a very simple question:

How to maximize a function

f(x) = (-800 x^2) + 600 x - 8000

here our answer will be a number which we can represent in a genome using a binary representation.

###

The reproductive function:

Once we know our genomic representation and our fitness function (f(x)) we have to decide how to make our subjects "reproduce".

There are several ways of doing this, but the way i've read about so far is the following:

We have some genes. For every pair a die is rolled to see if they will mate.

If we chose to mate them another die is rolled, this determines the "cutoff point" at which our genomes will be swapped.

The new genomes replace the parents.

If the pair does not mate, then the parents pass on to the next generation.

eg: 00000000 mates with 11111111

we roll a cutoff point of 4

resulting children 00001111 11110000

###

The mutation function:

This function is called every time two individuals mate it iterates through the bits of the children and using a random number generator it chooses whether to flip the bit or not.

This function generally should only flip bits on rare occasions.

Evolving to maximize a function

The basic evolution algorithm has three main bastions:

* The genome

* The reproductive function

* The mutation function

###

The genome:

The way we encode our solution.

In this case we are asking a very simple question:

How to maximize a function

f(x) = (-800 x^2) + 600 x - 8000

here our answer will be a number which we can represent in a genome using a binary representation.

###

The reproductive function:

Once we know our genomic representation and our fitness function (f(x)) we have to decide how to make our subjects "reproduce".

There are several ways of doing this, but the way i've read about so far is the following:

We have some genes. For every pair a die is rolled to see if they will mate.

If we chose to mate them another die is rolled, this determines the "cutoff point" at which our genomes will be swapped.

The new genomes replace the parents.

If the pair does not mate, then the parents pass on to the next generation.

eg: 00000000 mates with 11111111

we roll a cutoff point of 4

resulting children 00001111 11110000

###

The mutation function:

This function is called every time two individuals mate it iterates through the bits of the children and using a random number generator it chooses whether to flip the bit or not.

This function generally should only flip bits on rare occasions.

so far I've implemented the mutate function

along with a helper function i called ndice

ndice(n) outputs 1 with a probability of 1/n

Today I'm stopping here.

As of now, when properly run, this code mutates a chromosome of one byte with a proportion of 8/mutfact.

along with a helper function i called ndice

ndice(n) outputs 1 with a probability of 1/n

`/// mutate function`

/// its args:

/// mutfact - mutation factor determines how often we flip a bit

/// *seed - a pointer to a random seed, why a pointer?

/// because I expect to run this code several times per second

/// which means that seeding srand with time(NULL) will not do

/// so I'm making ndice increase my seed by one every run, thus

/// I'm running time(NULL) only once

int mutate(int mutfact, int *seed, int *chromo)

{

int iterator = 0b10000000; // this byte will be used to iterate

// through our chromosome

for (int i = 0; i<8; ++i, iterator >>= 1)

{

if (ndice(mutfact, seed) == 1)

{

*chromo ^= iterator;

}

}

return 1;

}

`/// ndice`

int ndice (int n, int *seed)

{

srand ( *seed );

int dice = rand() % n;

*seed +=1;

if( dice < 1)

{

return(1);

}

else

{

return(0);

}

}

Today I'm stopping here.

As of now, when properly run, this code mutates a chromosome of one byte with a proportion of 8/mutfact.

File: 1488341675514-0.png (87.49 KB, 200x200, GeneticAlgorithmsGaitSynthesisHexapodRobot.pdf)

File: 1488341675514-1.png (1.17 MB, 200x200, ProteinFoldingCellularAutomata3DHPModel.pdf)

I love genetics (currently doing work in bioinformatics) and I really love GAs. Some uses of GAs are simply "find a solution", but others are "keep adapting to dynamic environments" which I think is more interesting. Some domains are just not suited to complex control systems; the system should be able to learn. An example that I thought was exciting was in legged robot movement. With only a fitness function and a gait encoded as a chromosome, the robot could quickly learn to walk. Walking is traditionally challenging in robotics.

Attached a couple papers that I liked. Have fun, OP. I'll be keeping an eye on this thread.

>>22331

fascinating contribution my friend.

Attached a couple papers that I liked. Have fun, OP. I'll be keeping an eye on this thread.

>>22331

fascinating contribution my friend.

>>22323

GA's are fun. Most suprising thing I did was generate a sorting algorithm by creating my own language where programs can easily be represented as genomes whose operations perform actions on an array. The algorithms aren't efficient of course, and they'd turn out to be pretty bizarre at times (yet still work). I can post some examples if anyone's interested.

GA's are fun. Most suprising thing I did was generate a sorting algorithm by creating my own language where programs can easily be represented as genomes whose operations perform actions on an array. The algorithms aren't efficient of course, and they'd turn out to be pretty bizarre at times (yet still work). I can post some examples if anyone's interested.

Good idea for a thread, I'm definitely interested in anything people can share.

I used to be really into GAs. But they are inferior to other approaches to AI, such as machine learning. I guess, they're biggest strong point is that they can be useful even when little is known about the problem. But they can get pretty resource intensive very fast.

>>22346

https://gfycat.com/ScaryGrossCrayfish

One of the more weird ones. It doesn't fully sort the list but it's good enough to have a very high fitness. Keep in mind that you're watching 120k operations per second there.

https://gfycat.com/ScaryGrossCrayfish

One of the more weird ones. It doesn't fully sort the list but it's good enough to have a very high fitness. Keep in mind that you're watching 120k operations per second there.

I've used GAs for complex engineering problems, in my case specifically compressor endwall contouring. Full 3D CFD, including secondary flow, so the optimum I found was very non-intuitive. 24 hours of runtime (on 122 cores) did better than six weeks of engineers trying their hand at it. I felt on top of the world.

>>22347

By machine learning what do you mean exactly?

Do you mean neural networks with backprop, or something more general?

btw GAs can be combined with NNs.

here is one paper talking about the subject

http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf

By machine learning what do you mean exactly?

Do you mean neural networks with backprop, or something more general?

btw GAs can be combined with NNs.

here is one paper talking about the subject

http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf

Work has been slow but It's always nice.

` ``int reproduce(int *gen1, int *gen2)`

{

// randomly select a point in the genes for splicing

int cutoff = rand() % 8;

int t = 255; // translator, tool to scan the genes; 1111 1111 in binary

printf("reproducing, cutoff = %d\n", cutoff);

for (int i=0; i < cutoff; i++)

{

t >>= 1;

}

printf("t = : ");

printb(t);

printf("\n");

// store the value of the original genes before we mod them

int a = *gen1;

int b = *gen2;

*gen1 = (a & t) | (b & ~t);

*gen2 = (a & ~t) | (b & t);

return 0;

}

>>22356

Sorry, I should have asked what you were trying to do. All I meant was that in general, if you are interested in AI, machine learning is a much more exciting and promising area area. Since there is many approaches to machine learning, I was perhaps being to general in comparing it to GAs.

I suppose they really are for different things. If you want to find a creative solution to a problem (particularly one that you don't understand well ), then GAs might be worth it.

Sorry, I should have asked what you were trying to do. All I meant was that in general, if you are interested in AI, machine learning is a much more exciting and promising area area. Since there is many approaches to machine learning, I was perhaps being to general in comparing it to GAs.

I suppose they really are for different things. If you want to find a creative solution to a problem (particularly one that you don't understand well ), then GAs might be worth it.

File: 1488581838104-0.png (8.66 MB, 200x200, Algorithms from and for Nature and Life.pdf)

File: 1488581838104-1.png (4.43 MB, 200x200, Genetic Programming Theory and Practice X.pdf)

File: 1488882210690.png (8.43 KB, 128x128, final1.txt)

So I've put all functions together, the program was buggier than expected, but it's late and I believe it works for what it's meant to be (homework).

More testing is required, but I've learned a lot about C in the way.

I've tested this thing with simple functions such as:

f(x) = x;

f(x) = -x;

f(x) = 255 - x;

As of now, the program maximizes these functions correctly.

I've yet to test it with non-linear functions, but for now I'm cooked, steamed and tired.

(uploaded file as txt because lainchan soykafs the bed with .c)

More testing is required, but I've learned a lot about C in the way.

I've tested this thing with simple functions such as:

f(x) = x;

f(x) = -x;

f(x) = 255 - x;

As of now, the program maximizes these functions correctly.

I've yet to test it with non-linear functions, but for now I'm cooked, steamed and tired.

(uploaded file as txt because lainchan soykafs the bed with .c)

File: 1489124253834.png (742.8 KB, 200x113, Mjc5MzcyNA.gif)

Posting this in case someone is interested in seeing a fairly recent robot that uses an evo alg for complex movement of very sophisticated tentacles.

http://spectrum.ieee.org/robotics/robotics-hardware/robot-octopus-points-the-way-to-soft-robotics-with-eight-wiggly-arms

http://spectrum.ieee.org/robotics/robotics-hardware/robot-octopus-points-the-way-to-soft-robotics-with-eight-wiggly-arms

I'll be participating in a programming contest in a week that has been pretty much "write 5 GAs in 5 hours" in the recent years. I might try and translate the tasks to post them here, if anyone would be interested.

>>22328

I once used a GA to approximate a sine function with a polygonal chain.

I then noticed that if I use srand() and rand() function to generate which part of a chromosome will take part in reproduction and which chromosome will be mutated then the algorithm found its "best" solution very quickly and wasn't able to improve it in the next generation. I think the problem was that all my population was very similar (thanks to rand() function giving me similar output over a few iterations) and it wasn't able to generate a better result by crossing the best results in the population.

But if I modified the program to read random data from /dev/random or /dev/urandom I was able to get better approximation of the sine function (the algorithm didn't get stuck so fast).

You might want to try it yourself, maybe it will improve the results you get from the algorithm.

I once used a GA to approximate a sine function with a polygonal chain.

I then noticed that if I use srand() and rand() function to generate which part of a chromosome will take part in reproduction and which chromosome will be mutated then the algorithm found its "best" solution very quickly and wasn't able to improve it in the next generation. I think the problem was that all my population was very similar (thanks to rand() function giving me similar output over a few iterations) and it wasn't able to generate a better result by crossing the best results in the population.

But if I modified the program to read random data from /dev/random or /dev/urandom I was able to get better approximation of the sine function (the algorithm didn't get stuck so fast).

You might want to try it yourself, maybe it will improve the results you get from the algorithm.

>>22460

If I remember correctly I had 10 solutions in every generation. A solution was just a table of 20 points which represents a polygonal chain.

At every generation I picked 5 best solutions and tried to generate 5 new additional solutions from the 5 best I had. To generate a new solution I took 2 solutions from the 5 best I had and picked randomly the points from one or another to create 20 points of a new solution. After that I could mutate every point by moving it up or down by a fraction of it Y value.

I don't remember how often the mutation did take place but I know that choosing the right amount chance of mutation is crucial. Make it to common and your new solutions will be just random. Make it very unlikely to mutate and the mutation will never matter.

Unfortunately I don't have that code anymore so I can't be more specific.

If I remember correctly I had 10 solutions in every generation. A solution was just a table of 20 points which represents a polygonal chain.

At every generation I picked 5 best solutions and tried to generate 5 new additional solutions from the 5 best I had. To generate a new solution I took 2 solutions from the 5 best I had and picked randomly the points from one or another to create 20 points of a new solution. After that I could mutate every point by moving it up or down by a fraction of it Y value.

I don't remember how often the mutation did take place but I know that choosing the right amount chance of mutation is crucial. Make it to common and your new solutions will be just random. Make it very unlikely to mutate and the mutation will never matter.

Unfortunately I don't have that code anymore so I can't be more specific.

>>22460

>>22462

And yes, I mean that rand() didn't produce as random result as I expected and because of this many of the solutions in the next generation become similar.

If I wanted to generate 5 new solutions using 5 best solution from the old generation then I had to take at least one solution twice while creating a new generation. Let say I have three solution A,B,C. It often happend that if I mixed solution A with B (to generate solution D) and then A with C (to generate solution E) the rand(). function picket the same points from solution A to create solution D and E. After a while all solution in my population were very similar.

>>22462

And yes, I mean that rand() didn't produce as random result as I expected and because of this many of the solutions in the next generation become similar.

If I wanted to generate 5 new solutions using 5 best solution from the old generation then I had to take at least one solution twice while creating a new generation. Let say I have three solution A,B,C. It often happend that if I mixed solution A with B (to generate solution D) and then A with C (to generate solution E) the rand(). function picket the same points from solution A to create solution D and E. After a while all solution in my population were very similar.

File: 1490757273920.png (5.04 KB, 67x118, out.tar.gz)

I haven't abandoned yet, I was working on a "hybrid generic algorithm" as my professor calls it.

A hybrid genetic implements a genetic algorithm but uses external knowledge of the problem to make the search more efficient.

Here is the code, now it's python..

I learned that maybe C isn't as bad as some make it out to be.

A hybrid genetic implements a genetic algorithm but uses external knowledge of the problem to make the search more efficient.

Here is the code, now it's python..

I learned that maybe C isn't as bad as some make it out to be.

>>22708

I haven't described the problem that this solves.. it solves this

https://en.wikipedia.org/wiki/Eight_queens_puzzle

Only that it works for n > 8 as well.

I haven't described the problem that this solves.. it solves this

https://en.wikipedia.org/wiki/Eight_queens_puzzle

Only that it works for n > 8 as well.