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

lainchan archive - /λ/ - 22323



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

No.22323

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.

  No.22324

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.

  No.22328

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

/// 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.

  No.22329

>>22328
I forgot to describe what *chromo is when being input into mutate.
It is a pointer to a chromosome, which the function will change as a side effect.

  No.22331

>>22328
>C++ style comments
>multiline
why u do dis?

  No.22338

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.

  No.22339

>>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.

  No.22341

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

  No.22346

>>22339

please do share with us!

  No.22347

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.

  No.22350

>>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.

  No.22351

>>22350
Neat. Could you share the actual algorithm?

  No.22352

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.

  No.22354

>>22331
I don't know if your comment is serious or not.
I format comments in a manner I find aesthetic, same as my parens.

I'd love to see your style of coding. :)

  No.22355

>>22352
Awesome, this is what draws me towards GAs, they can find answers that clear logical thinking might not.

  No.22356

>>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

  No.22357

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;
}

  No.22361

>>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.

  No.22362

>>22338
Thanks for the articles m8.

I agree that adapting to dynamic environments is part of what makes GAs so interesting.
It allows us to probe into places where traditional coding cannot.

  No.22363

>>22361
Yup, I've delved into machine learning for a bit, so that's why I asked what you meant specifically.
I created this thread because as I said, I'm studying Genetic Algorithms in school. What I'm posting is my progress on school work.
Nothing too exciting, but it's an introduction. :)

  No.22365

>>22350
Did you evolve some which were more efficient?

  No.22370

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)


  No.22417

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)

  No.22418

>>22370
thanks for these, btw

  No.22419

>>22417
a couple of details, the program takes three arguments, not two, the last, unlisted argument is the mutation factor.
whatever number you input, chromosomes will have 8/input chances of mutating.

  No.22423

>>22356
i'm very interested in that combination (GAs with NNs). he's got a point though, convolutions are cheap. makes me wonder if anyone's figured out how to model gene propagation with an integral equation or something.

  No.22441

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

  No.22442

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.

  No.22451

>>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.

  No.22459

>>22442
I'd be very thankful if you could.

  No.22460

>>22451
Interesting.. how did you implement your mutation function?
I'm not sure I understand what you're saying..
Are you saying that srand() and rand() didn't cut it as Random Number Generators for your algorithm?

  No.22462

>>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.

  No.22463

>>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.

  No.22467

>>22463
I think this may be because of how you were seeding rand().. maybe.

  No.22708

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.

  No.22709

>>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.