Genetic Programming to find the 3D brot

[twinbee]

It's an idea I've had for a while, since finding the holy grail via other means is turning out to be a difficult challenge. Why not 'cheat' to find the Mandalisk?

In reality of course, this is going to be one incredibly difficult challenge in itself. I've had a little experience with genetic algorithms, but GP I need to look into.

That's the easy part.

The fitness function for this is going to be something straight from hell. Even with infinite CPU speed, I'm expecting a giant monolithic function that's very hard to test. Obviously, one would start out experimenting with a 2D version, which itself would be something of a nightmare - we'd want to check for circles surrounding circles, but where a higher fitness is given to particular patterns of circles which more closely resemble the character of the original Mandelbrot. The rough shape isn't what we're looking for, it's the concept of fractal circles surrounding each other.

In the picture below, take a look at A and B. We'll want very high fitness scores for those, but for diagram C, we'd still want a fairly high score, even though some circles are overlapping, disconnected, or are more like blobs than circles.

So if the 2D version is hard enough, the 3D version (testing for spheres surrounding spheres) will be a nightmarish affair, conceptually and in terms of CPU efficiency. It will be so difficult that I've even thought about evolving the fitness function itself.

What do others think - is this an idea with any merit?

[msltoe]

twinbee,

I've thought about this too. It would sure save time.
For a fitness function it could be just a human who rates the quality of the different shapes being generated. Of course, a filter function could be used to throw out obvious "no go's." If the GP could find new wonders besides the Mandelisk, that would be good, too. The Mandelbox is the best example of a new shape that was not Mandelisk-like but turned out to be very interesting to explore.

-mike

P.S. Picture A looks a lot like the snowflake brot I found: http://www.fractalforums.com/theory/juliabulb-with-'octahedral'-transform-~-sphereflake/

[M Benesi]

I'm not sure exactly what you mean by the Mandalisk, but it sounds like you are pursuing the 3d Mandelbrot?  (Mandalisk sounds cool)....

  Anyways, I pretty much think it's already been found....  and it's just the bulb (although specific varieties are "more correct").  There is great variety for even the z^2 bulb (this is a complex compound version, faster run times, just uses 2 complex variables instead of one, it's easy to see the mathematical relationship to the 2d version):


check out other images here

  You just have to color it correctly, first attached file has a coloring formula for ChaosPro.  Might want to try it with the benesi set simplified formulas for the complex compound coloring scheme.  Try the 5d set complex compound with colormode=complex 3 (or other) and r2mode= r2 mode 1 for an interesting looking thing.  5d Mandelbulb is not implemented in the 5d set yet....   Rename the formulas by removing the .txt extension then drop 'em in your ChaosPro formula directory (folder).

[kram1032]

Genetic programming to find the mandelbrot? Awesome idea
However, I guess the only true fittness function that will work will be the actual human perception. And that's hard for several reasons:

- Highly subjective
- limited to 2D projections/cutthroughs, except you build a dynamic hologram on the fly (would be incredible aweseome But I guess, beyond all real possiblity...)
- no way, you could examine big parts of the sphere mass with zooms to know if it's close or not in the details in any short time, and
- even if you only go for the overall shape: It's SlOOOOW and tedious.
(The human perception fittness curve algorithm will not be exponential, but the slow, semi-chemical computing implementation will make it look like that.)

What *might* be possible, is to use a generic fitness function that at first just randomly throws out examples and you can see both the taken and then thrown-away ones.
Then, you basically rank the outputs without even knowing, which the fitness function had chosen. And based on that, it tries to become more and more confident with its picks. After some time (maybe some tenthousand images or so), it will be nearly confident enough to make its own picks.

Doing it first for a 2D set will be crucial, I guess, to at least be able to hope for any sign of covergence

So basically a fitnessfunction that is you, which controlls a fitnessfunction that changes itself based on genetic algoritms, which then controls the actual fractal/approximation of a fractal.

[twinbee]

Yes, using a human to assess the fitness function sounds good - I forgot about that idea from before. There was even an article from Slashdot about a website with an applet that evolved a function to create pictures that people thought looked 'good'. Same principle here. And yep, we can discover unseen shapes!

The only problem is that if we ever find it, the math could quite easily cover a few pages if we let this thing run havoc!

P.S. Picture A looks a lot like the snowflake brot I found: http://www.fractalforums.com/theory/juliabulb-with-'octahedral'-transform-~-sphereflake/

Heh, yep. Also like this:
http://img383.imageshack.us/img383/893/sphereflake02hd3.jpg

I'm not sure exactly what you mean by the Mandalisk, but it sounds like you are pursuing the 3d Mandelbrot?

Yep, just another name for it, since Mandelbulb has been used up already

I'll have to create an artist's impression of what I think a zoom-in will look like sometime. It'll be 10x weirder than one can imagine though.

However, I guess the only true fittness function that will work will be the actual human perception. And that's hard for several reasons:

- Highly subjective

We'll be looking out for anything resembling spheres surrounding spheres and recursive definitions thereof. Maybe a 3D cardioid too.

limited to 2D projections/cutthroughs,

Well, a light-sourced 3D shaded render will give a pretty good idea of what it should look like. No real need for cutthroughs imo, though that could help I guess in the assessment.

- even if you only go for the overall shape: It's SlOOOOW and tedious.

Not with a GPU

(The human perception fittness curve algorithm will not be exponential, but the slow, semi-chemical computing implementation will make it look like that.)

I'm unsure how many generations would be required to make it look good. So yeah, there's a chance that we still may need to define a fitness function for speed.

Then, you basically rank the outputs without even knowing, which the fitness function had chosen. And based on that, it tries to become more and more confident with its picks. After some time (maybe some tenthousand images or so), it will be nearly confident enough to make its own picks.

So that's essentially evolving the fitness function I think...

Doing it first for a 2D set will be crucial, I guess, to at least be able to hope for any sign of covergence

Yes using the 2D Mandelbrot as a testing ground would be helpful. We'd start out with nothing, or maybe with the Mandelbrot template but without the rotation function, and work from there.

I was actually thinking of only evolving the rotation function for when we try to evolve the Mandalisk (so the rest of the Mandelbrot-esque code is already in place).

So basically a fitnessfunction that is you, which controlls a fitnessfunction that changes itself based on genetic algoritms, which then controls the actual fractal/approximation of a fractal.

Grand That itself could be recursive, a fitness function which helps define a fitness function which controls a fitness function etc. (head explodes).

[kram1032]

I always wanted to program a fittnessfunction for a generic world (Not that I have the actual skills for that^^)
Like actual real evolution: Some small goals are tried to be fullfilled:
-get food
-reproduce
-survive
What is considered as food doesn't matter. It should be kept generic. How awesome would be a computer game, where you don't only have your average villian and NPCs but next to that actual evolving species which just try to survive - and might happen to think of you as food on the way...
They'd try to learn and get your tactics down and finally they'd be the way more dangerous threat than your main villian. Therefore, they also harm him, as they're totally neutral

Ok, way offtopic for the Mandelisk part but that'd probably need just such a recursive fitness function.

Or maybe an operating system (emulated of course, so that it doesn't destroy anything from your true OS^^) that starts out as tinyOS + genetic algorithm and tries to improve itself, based on what you do and on bugs that are randomly caused. When ever something bad happens, you say "BAD SYSTEM!" or "DARN BUG!" and when something good happens, you say "good system *pat*" - might be tedious but in theory, after some time you have a very nice custom system that works just as you need it, lol.

[KRAFTWERK]

I love this! 

What about the "MandelGrail"   

[Softology]

I considered this myself early when the first variations of the Mandelbulb cropped up.

The selection method can be the human user.  You generate (for example) a grid of 12 or so triplex fractal images.  The human clicks which of them they think are good candidates and then clicks a evolve button.  The program then generates maybe 4 new random images, 4 mutated images (take the current "gene pool" formulas and mutate them slightly) and 4 bred images (take formulas from the gene pool and cross breed etc).  Repeat until something new/pleasing appears.  This saves you trying to write complex code to get the computer to determine what is a good image.

I have done a lot of this with 2D images and the results are promising.  If I had the time and patience to write a formula parser for triplex algebra I would give it a go for sure.

Here is a quick PDF overview of the genetic methods I have experimented with over the years for 2D images.
http://softology.com.au/geneticart.zip
Extending to 3D would be awesome.

Jason.

[M Benesi]

  Jason,

  You don't need anything too complex to do triplex "algebra".  You simply require:

A) a square root function to calculate a magnitude:
  r1= sqrt(y^2+z^2)

B) a complex power function:
  complex_1= (x + i r1)^n
  complex_2= (y + i z)^n

C) a real power function:
  r3=r1^-n       (you are applying the magnitude of y and z two times (once in each complex number), so need to divide it out once)

D) the ability to directly access the real and imaginary components of the complex numbers:
  new x = real part of complex 1   + x pixel value  OR  x Julia seed   (for Julias use the seed, Mandys use the pixel value)
  new y = imaginary part of complex_1 * real part of complex 2 * r3  + y pixel value  OR  y Julia seed
  new z = imaginary part of complex_1 * imaginary part of complex 2 * r3  + z pixel value  OR  z Julia seed

  No trig required....  and the non trig version is faster computationally than calculating arg/atan2, cos, sin, etc.  Not to mention it's easier to see how to extend this to higher dimensions: each dimension gets another complex component...

[cortexman]

You should start with simple fitness functions and then slowly make them more complex as needed.

Rather than relying on perceptual fitness functions I suggest you come up with some relatively simple heuristics.

For instance, can you use the fractal dimension? I read on these forums that you could estimate it for a given brot using a box counting technique.

[Power 8]

Very interesting idea using genetics...

There's a guy called William Latham who worked on evolutionary 3D shapes in the 80s and 90s.
 Not necessarily fractal images, but a similar line of thought as in this thread. Maybe you guys know about his work.
If you don't here's a link to a page on his website, with the human as a "gardener" choosing which are "good" and "bad" shapes:
http://www.doc.gold.ac.uk/~mas01whl/themes/gardener.htm

There are also other interesting images and videos on his website.