Genetic algorithms to search the Mandelbrot set

  • 12 Replies
  • 576 Views

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • *
  • Fractal Freak
  • **
  • Posts: 679
« on: June 16, 2019, 05:39:43 PM »
I've found a very interesting paper about "Evolutionary exploration of the Mandelbrot set", Daniel Ashlock from 2006 (similar to this thread here https://fractalforums.org/other-artforms/20/evolving-3d-fractals-with-genetic-algorithms/800/msg4102)

I implemented a first version to see what it looks like. The author uses a population of individuals, each a small square in the complex plane and performs several rounds of breeding using a fitness function after selecting some individuals for breeding and mutation.

Interestingly the fitness function works on a 11x11 point grid in the square the indiviual represents, so not the whole image is evaluated for fitness. He suggests three functions (hill, constant, ridge).

Since I am using the internal random number generator and have no idea what its distribution of numbers looks like, I did not expect to reproduce the results (he states using a random generator with a normal distribution).

But it was interesting to see that the three functions at least gave different results.

Here are some examples. Depicted are 9 individuals in each image. Each individual is the best in one run of the program using 10000 mating rounds with an initial population of 100 individuals, from which 7 were randomly selected in each round and put through the fitness test, breeding and mutation.

The interior is uniformly coloured black, the exterior with a direct iteration count coloring.

The const function seems to find only interior, the hill function tends to whole bulbs and the ridge function more to the bulb's boundary (of course, very loosely spoken).

Has anyone done this in more detail and for other fractal types?

Of course, there's lots more to do here (correctness check, trying to exactly reproduce the results with more appropriate random generators, classification of new fitness functions, other fractal types...)



Linkback: https://fractalforums.org/fractal-mathematics-and-new-theories/28/genetic-algorithms-to-search-the-mandelbrot-set/2886/

Offline Sabine62

  • *
  • Fractal Freak
  • **
  • Posts: 713
  • It's just a jump to the left...
    • sabine62.deviantart.com
« Reply #1 on: June 16, 2019, 10:43:21 PM »
Love stuff like this!
In the eighties when computers needed peddles under the desk to get them going and bulky monitors were there in 50 shades of green or amber text, some people I knew from the predecessors of internet  and I wrote to each other little algorithms to have little beasts (8 bits... ) achieve arbitraty 'god'-states through all kinds of strategies and rules, mutating, exchanging bits with each other, etc. How to get from say 01100011 to 11101110... A lot of fun and could be done with basic BASIC and No clue about maths :))

Of course, this is much Much more sophisticated, but looks like it is as much fun ;) and triggered a bit of nostalgia with me  ;D

Thank you for sharing!
To thine own self be true

Offline marcm200

  • *
  • Fractal Freak
  • **
  • Posts: 679
« Reply #2 on: June 17, 2019, 10:16:39 AM »
@sabine: Yes, this random genetics approach is quite appealing. And as I read your post, the bit strings reminded me of the Logo turtle which uses them to change directions (if I recall correctly).

But interestingly the Mandelbrot approach here is not exceptionally computationally expensive (just an 11x11 grid), I wonder if my 80's Amstrad could have handled it (okay, in hours to days, not in minutes, but nevertheless).

Offline gerson

  • *
  • Fractal Flamingo
  • ****
  • Posts: 340
« Reply #3 on: June 17, 2019, 04:41:06 PM »
@marcm200 "Since I am using the internal random number generator and have no idea what its distribution of numbers looks like,"
Maybe you could save the randon's number generated, and after load it to use with the other 2 algoritms and test if it give the same result.
I saw something about genetics and Particle Systems on softology's blog if you are interested. I don't know if refers to the same subjet of yours papers.

Offline marcm200

  • *
  • Fractal Freak
  • **
  • Posts: 679
« Reply #4 on: June 18, 2019, 07:27:47 AM »
@gerson: That's a good idea. I could save the random generator seed (time stamp) to recreate the string of numbers to use in other formulas. But I hope there's not a dependence of the outcome to the actual sequence of "random" numbers, that would be a downfall to implementing genetic algorithms in my system.

Designing some other fitness functions I found three that gave quite a distinct and consistent result. The images show the best individuals of 15 different runs of the program with 10^5 mating events and a population size of 800 individuals. Black is interior, the lighter the gray the faster the escape happens.

The upper left depicts a 3D view of the fitness function (the bar height of the 11x11 grid
represents the iteration count the fitness functions desires at that point).

The W-function finds mostly valleys, the slope-function finds smaller bulbs on the border of larger ones and the EcoRI-function finds highly branching structures.

What I learnt so far, is, that having big plateaus in the fitness function (e.g. a constant function) finds almost exclusively interior, therefore new grids will have a large difference between the smallest and the greatest grid height.


Offline Sabine62

  • *
  • Fractal Freak
  • **
  • Posts: 713
  • It's just a jump to the left...
    • sabine62.deviantart.com
« Reply #5 on: June 18, 2019, 09:40:06 AM »
@marcm200 Logo-turtles! Yes! Got it for my daughter in those days... good gracious, I feel so old now (for a sec or two!)  :)) :)) :))

Thanks for also posting the 3D-view of the fitness-conditions, I always find it easier to understand something a bit better when I can visualize it  :thumbs:


Offline Spyke

  • *
  • Strange Attractor
  • ******
  • Posts: 98
    • Spyke Art
« Reply #6 on: June 20, 2019, 07:13:12 PM »
I played with genetic programming for fractals back in the late 90s and early 00s. My approach was substantially different.

For the evolution I tried to allow everything to mutate, not just the view port / magnification. The formula itself would mutate, as would the color palette and color method. Maximum iteration and escape threshold would mutate. In fact, the "formula" was a mini-program most of these things ceased to exist as separate entities.

I had a collection of metrics which were used to evaluate fitness. I intentionally call them metrics, to emphasize that they are initially non-judgmental. Separately a criteria for "good" is set, which is then used to measure fitness and drive the evolution. The metrics themselves, as well as the target fitness criteria would also evolve.

The metrics were all based on the colors in the final image. There was no peeking inside in the evaluation step. Average color, and color standard deviation were a couple. I had a class of metrics which took the color difference between points with a specified relative pixel coordinate  separation. A histogram is built with a number of preset buckets. I figured with appropriate setting of the separation vector and buckets for this histogram this would identify images that are too noisy or too uniform.

I had two absolute metrics, one was rendering time. Anything exceeding a set threshold was immediately removed from the population.

The other was motivated by the observation that the evolution would get stuck at a local maxima. All survivors look like the parent, and soon the population is a bunch of clones. So I added the rule that any next generation survivor must have at least a minimum difference from everything else in the population.

The fitness criteria would mutate via a god mode. Initially it is random as is everything else. I would interrupt the evolution, look at the current population and give each image a thumbs up or down. The fitness criteria is adjusted, again through a series of random mutations on both the target and the metrics, and the mutation that best separates the good from the bad is used until the next coming of the deity.

I found an archive of my web page from 2002. It had some of the later images from this process. Note, that since the "fractal" formula mutates, and I had set up an anything-goes environment, the results are distinctly non-fractal. Here are some examples that have survived my haphazard archival system for almost two decades.

Earl Hinrichs, offering free opinions on everything.

Offline marcm200

  • *
  • Fractal Freak
  • **
  • Posts: 679
« Reply #7 on: June 21, 2019, 09:07:00 AM »
That's a very broad range of evolvable variables you examined. Must have taken quite a long time to find the resulting images. Did you investigate how the final images changed if one parameter was constraint or initially set not to evolve?

I had two absolute metrics, one was rendering time. Anything exceeding a set threshold was immediately removed from the population.
That's an interesting rule. I image it drove the population away from pure interior (of an M-set) or slow-computing Julia sets (near a parabolic point) ?

So I added the rule that any next generation survivor must have at least a minimum difference from everything else in the population.
Was the difference decreasing with evolution time ? If not, I would image that the outcome of a simulation was rather largely dependent on the number of breedings.


Offline gerson

  • *
  • Fractal Flamingo
  • ****
  • Posts: 340
« Reply #8 on: June 21, 2019, 06:45:48 PM »
@Spyke images seems to be postprocessed by photoshop's plugins. Very good.

Offline Spyke

  • *
  • Strange Attractor
  • ******
  • Posts: 98
    • Spyke Art
« Reply #9 on: June 21, 2019, 10:33:17 PM »
 
Must have taken quite a long time to find the resulting images.

Marc, it did not take long. Or should I say long is relative, it is not an interactive endeavor. The program would run when my computer would otherwise be idle. Overnight and when I was at work. In the morning and after work I would examine the results and do some culling. There was always something new and interesting. (At least that is what I remember, this was 20 years ago.)

 
That's an interesting rule. I image it drove the population away from pure interior (of an M-set) or slow-computing Julia sets (near a parabolic point) ?

It did more, and it was quite necessary. The formula mutation process did not limit the iteration count, in fact it did not require a limit, and could produce an infinite loops. I did have one short cut, first it would compute a 10x10 image. If that took too long, or if all 100 pixels were the same, then that item was discards. I was making 800x600 images back then to show, I recall doing something like build 1/2 or 1/4 size (400x300 or 200x150) for the analysis, then only creating the 800x600 for the survivors.
Did you investigate how the final images changed if one parameter was constraint or initially set not to evolve?
No, I think I felt that the more the better. My goal was not to explore fractals as such. I was just to create images that I thought was interesting. Because of the god step, the evolution pretty much proceeds in whatever direction the programmer's tastes lead. It was my original intention to have the evolution lead me to something unique, and then I would take that formula and start working with it manually. But the evolution quickly led to large, unmanageable and incomprehensible formulas. I had no idea how to start tweaking them.

Was the difference decreasing with evolution time ?
Yes, I suspect that in the evolution step there are a lot of ways to change the genotype without changing the phenotype. In this project for instance the formula could have conditional branch that is never taken, any mutation on that branch still produces the same image. So these phenotype clones crowd out the rest of the population. There is a similar phenomena in biology, most of our DNA is non coding DNA. https://en.wikipedia.org/wiki/Non-coding_DNA which does not produce proteins.

@Spyke images seems to be postprocessed by photoshop's plugins. Very good.

Gerson: I am not quite sure what you mean. The images are raw "fractals" generated by this image evolution system. There is no post processing. Or perhaps you mean that if they look like photoshop then the image evolver is doing a good job.

Offline gerson

  • *
  • Fractal Flamingo
  • ****
  • Posts: 340
« Reply #10 on: June 21, 2019, 11:30:55 PM »
@Spyke yes, good job, I knew that is raw, just comparing it effects with some plugins...

Offline marcm200

  • *
  • Fractal Freak
  • **
  • Posts: 679
« Reply #11 on: June 27, 2019, 08:29:10 PM »
I was trying to build a fitness function that finds (mostly) minibrots. Here's the best I could come up with so far. It's an exponential function declining more rapidly to one side and keeping a fairly high middle line - trying to mimic the minibrot/filament iteration pattern.

Function is: Target iteration at grid u,v (11x11 points)=maxit * exp(-0.25*u²-4*v²) with u,v equally spaced in [-1..+1] x [-1..+1].

However it's not quite what I hoped for. It finds half the times minis but in a very broad size range. Does anyone know of a better function?

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1442
    • mathr.co.uk
« Reply #12 on: July 02, 2019, 10:27:17 AM »
https://imagej.net/Directionality a flat directionality histogram is a good metric for many-armed spirals (at least with distance estimation colouring)


clip
Genetic algorithms to search the Lyapunov space

Started by marcm200 on Fractal Mathematics And New Theories

0 Replies
155 Views
Last post July 04, 2019, 12:14:55 PM
by marcm200
clip
Evolving 3d Fractals with Genetic Algorithms

Started by ansr23 on Other Artforms

3 Replies
877 Views
Last post January 29, 2019, 11:57:11 AM
by mrrudewords
xx
Automating search for neat Mandelbrot fractals with entropy

Started by Adam Majewski on Fractal Mathematics And New Theories

0 Replies
245 Views
Last post May 11, 2018, 09:02:03 PM
by Adam Majewski
xx
No search engine?

Started by AnJo888 on Off Topic

4 Replies
370 Views
Last post June 04, 2018, 04:03:49 PM
by Caleidoscope
xx
Mandelbrot Burning Ship Mandelbrot Mandelbrot hybrid 3

Started by claude on Fractal Image Gallery

0 Replies
359 Views
Last post January 17, 2018, 12:26:38 AM
by claude