Fractal algorithm basics

This post is meant to be the first in a serie about the basic working of what I now call "Fractal Growth based algorithms", including not only the "Fractal AI" I am working on, but also methods for function optimisation or even my biggest experiment, the "quantum physics simulator" showed in previous posts.

Why are those methods relevant?

I have a strong feeling that those methods could be revolutionary in several aspects and serve as a base for new mathematical tools based on the power of fractals: I think they have the power to dilute some NP problem into P, and even more interesting, into O(n), making some hard problem to become "not so hard" anymore.

Nature is made up of fractals, as Maldelbrot showed us: a tree is a fractal, the coast line is a fractal, a mountain is also a fractal, etc. but we only use fractals for drawing fractals... it is the "lovely cat generator" of modern maths.


How powerful are they? Well, you all know how intrincated the Mandelbrot set is, but the formula that defines it is just "Z(n+1)=Z(n)²-1". Isn't it a miracle that such a small formula can generate one of the most complicated geometry humanity knows?

What if all the complicated world we live in also have a small "fractal generator formula"? I really think it is the case, and it is a nice personal amusement to purse this idea.

Note: For the math audience, please keep in mind they are not real fractals, just pseudo-fractals, as we are not going to let it evolve infinitely up the the smaller scales. All "fractals" found in nature are pseudo-fractals as well, as there are always "forbidden scales" (in the worst case, the Plank scale), so it is just a "wording issue".

The basic idea

I have tried to write this post several times, more or less formally, using maths or a real world example, and finally I have decided to use my first "mental image" as it was the root of all the subsequent refinements: a pot of plants.

Imagine you are a plant pot that is randomly placed on a big field. You can have up to four seeds growing up at any given moment, and those four plants can grow up only to a size limit, so the sum of the sizes of the four plants is hard limited to, let say, 100 active branches.

Your goal is to be placed, in the long therm (but as soon as possible), in the most "sunny" part of this unknown field.

To make it more interesting, we will assume the pot can move slowly in any direction when no plants are growing, so after a full "season" of growing up your plants, you need to decide where are you going to move before the next season start. This is the main role of the pot intelligence: to pick up a direction in witch to move during those periods.

But the pot is "blind", it can not just have a look around and take an easy decision, so you need to plan a good strategy that doesn't use sight or any similar "super power". You just have one tool: growing up the plants.

So the pot decides to use the following strategy: It will place each of the four seeds pointing in a different direction, let say north, south, east and west, so the first branches of each seed will point exactly in that direction.

After the season is over, the four plant will dry and die. You just need keep four new seeds to be able to repeat it all in the next season, but apart from it, now you have to decide on the direction you want to move the pot.

So you measure the width of each of the four initial branches, now evolved into big trucks. Some would be bigger than others, as the plant that grows into a better zone of the field (a more sunny area) will tend to grow up faster.

I made this drawing to illustrate the idea:

A four trucks pot, top view

But this can only be made at the cost of drying some other branches! As the pot can only hold 100 branches at a time, when a branch of a given plant bifurcates, some other branch from the other 99 will dry. In the long term, the best placed plant will have more active branches than the rest, giving you a rough idea of with direction is better to go.

So imagine those four trucks have widths of 12, 20, 215 and 50 (mm² if you need a scale). They all sum 287 if I am not mistaken, so their relative sizes are: 12/287, 20/287, 215/287 and 50/287.

Now you have four directions and four normalised coefficients, and making a simple weighted average will give you a nice direction for the pot to move.

In the next season, the pot will hopefully be in a slightly better position than before, but this is a continuous process so the pot will just start a new season: plant four seeds, wait for them to dry, weight the four resulting plants, and move accordingly, over and over again, in the hope that this simple strategy will lead it to the best possible position: the most sunny spot.

Translating into a real problem

The general idea is layed out, and this simple schema can be used, among other things, to try to globally maximise a given scalar function, you just need to rename the elements.

-The "field" is the domain of the function you want to maximise. For instance, it can be a two parameter function f(x,y)=z with x and y in the range -100 to +100.

-The "sunny" value in a point is, obviously, the z value of the function, so "sunny" is translated into "f(x,y).

-The "pot" represent the actual position (x,y) where you think the global maximum can be, or the point you are actually seeking for it more precisely. Initially it is a random position in the function domain, or a random place in the field.

-The "ranches" represent the fractal we will use to make our decision.

-The "trucks" represent the four main directions you could go, or a base of the space of decisions, if you prefer.

-The "widths" of the four truck represent the score assigned to each of the base directions you can take.

-The "weigthened direction" is the direction the algorithm will move the actual "best position so far" (the pot) on the next iteration.

Similar translations can be made for the AI, where the pot is the actual position of the agent, the four initial directions correspond to the + and - push on the two degrees of freedom (in the rocket example), and the final decision is how strong will you finally push the joystick left, right, up or down.

Not all the problems can fit this schema, there are some more complicated fractals that could be used for other purposes, but they will always share the same basic principles outlined here.

The plant growth

This far we just assumed the plant will grow up like it does in nature, but this is the "fractal part" of the idea, and we need to elaborate it a little more before understanding the whole process and being able to code and test.

We are going to imagine the process day by day, assuming some simplifications, and keeping in mind two basic facts: the pot can only hold a given number of active branches at a given moment.

We will call "active branches" to the baby branches only, the ones that appeared yesterday, assuming the other older parts are now semi-dried and serves only as a conduit to make the nutrients reach the very tip of every branch, so the plant can have a big number of "old branches" but only 100 new ones.

So initially you have four active branches, and in the first day each one will grow in a given initial random direction as commented above. Once they are in its new positions, each one of the active branches will collect an amount of sun light, the "sunny" value in its new position.

Those energies are collected by each branch, and then, in the following day, the branch semi-dries and a new baby branch emerges and continue its travel, carrying the collected energy with it.

After some days, a branch could accumulate more energy it can hold. Like a battery reaching it maximum capacity, this branch can not hold more sun energy, and in this moment, the branch will decide to bifurcate.

The first thing this branch needs to bifurcate is to ask the pot for more resources for it. If the pot can hold 100 active branches and initially it had only 4, then the pot will just give some of the available resources to it. This mean that two empty (with no sun energy on them) baby branches will emerge, so you will have 5 active branches on the next day.

When the number of baby branches reach the pot limit of 100, the pot can not allow a new branch to just pop up. You may stop the fractal in this point as I tried in my first tests showed in the video below, but this would limit the reach of the fractal, but we can use a better approach: a randomly chosen baby branch is chosen and completely dried, so now they are 99 and there is room for the new one. I will show it on another post with its corresponding video.

The main "nice effect" of this random selection is that now you can make the fractal grow indefinitely in time, and also that, on the long term, worst placed plants (the ones pointing to not so sunny areas) will have much less active branches that the best ones, and will eventually dry and cease to grow, so after a full season is simulated, the number of branches in the fractal history that started growing on one directions will be be a very clear clue to where to head to: it will tell you the weight we should assign to each available direction when deciding on the pot moving direction.

Here you can see a screen recorder video of this first approach at work. I intentionally left the internal param selection used: "Memory for 512 branches" is our 100 branches limit, "Step" is how far a branch travels in one day, and "Energy" is the amount of solar energy a branch needs to accumulate before being bifurcated.

As you can see, the "thing" works and goes straight to the maximum, but also it is limited in range and has another weak points, but all of them can be addressed with some small changes.

The little details

This algorithm correspond to the very first implementation of fractal growth I ever used, more than a year away. The basic structure haven't changed too much from this point, but every little detail on it has been revisited and reformulated using a variety of methods.

The selection of the branches to be cloned at each tick (each day) is by far the most important one, but also the selection of the companion branch that will be dried in the process, or the way you average all the resulting trunk widths.

There are also plenty of additions you can use to make the fractal grow in the way you selected for solving a given problem, being the most important one the "exclusion principle" commented on a previous post, representing the fact that hundreds of baby branches can not live in the same squared mm, they will not receive all the sun light present there as other branches will cover it, meaning branches on very dense areas must be more prone to be dry out when a more fortunate one do clone.
 
At the end of the day, we have a basic structure for algorithms that are based on fractal growth instead of classic maths, with a lot of details to be redefined and adapted to the different scenarios.

Those details represent the "growth laws" the fractal will obey and will ultimately determine how useful the resulting algorithm is for a given task.