Fractal search/optimization

[twinbee]

Does anyone here have background on or interest in computerized search (specifically, global optimization in non-convex landscapes). One may use techniques such as hill climbing, genetic algorthims, simulated annealing, ant colony, particle swarm etc...).

It sounds complicated, and the methods can be, but the concept is really simple: input various parameters into a function, and tailor them such so that the output of the function is maximum.

[lycium]

sure, all that falls under the banner of numerical methods, one of my specialties

why do you ask?

[twinbee]

Yay, this could be interesting.

Basically, I have created/rediscovered a rather simple technique of search through arbitrary dimensions. I say "created/rediscovered" because although I have looked fairly far and wide and can't see anything similar, the idea is fairly simple. The idea is based on a fractal - one in particular - the Sierpinski Carpet.

To me, it seems very efficient, at least for many/most types of real-world/mathematical search landscapes. Think of a binary chop, but extended to 2 or more dimensions. Each dimension is explored, and according to the quality of the point, that area is explored more/less thoroughly. But it not only takes into account the quality of that point, but also its level of depth, where higher levels (i.e. more thoroughly explored) get penalized accordingly. All points will get explored eventually (branch off), but each are given a priority which is constantly updated throughout the search.

Any idea what I'm looking at here?

[lycium]

sure, it's essentially constrained global search problems. methods like lagrange multipliers from multivariate calculus are good when working analytically/algebraically and interval analysis is used in numerical situations.

[cKleinhuis]

ehrm, i know them, and rarely know them a bit better, the problem is always - when dealing with fractals - the rough surface on different scales you aproximate
 

[twinbee]

Okay, but does the "binary chop" or "sierpinski carpet" version (which is basically powers of 3) for this constrained search have a name as such? It seems like the "merge sort" of optimization - I'd sorta be surprised if it didn't have a name as it's so simple really.

Just to be sure, here's a sample pic (it's possible to meddle with various parameters inside the algorithm by exponentiating etc., but you'll get the idea)...

The dots represent the points explored so far. Brighter grey patches are explored more thoroughly.



Is it popularly used? Have you guys ever seen an implementation of it or even used it?

Also, how efficient is this "sierpinski carpet" search compared to most algorithms out there? I know there's "no such thing as a free lunch", but I mean tested on most real-life data or simple mathematical functions. (I have a theory that perhaps the best way to build the most all-purpose optimization algorithm is to test it on multiple fractal terrain maps).

[twinbee]

I got that 50 meg vid downloaded - very interesting, though from what I understand, it's looking at each function individually and using some process of elimination which isn't quite what I'm doing (right?). Its "dissection search" seems very much like what I was talking about though.

I even put the formula into my own program, and it came up with the same results as the vid with the small red blobs representing the 4 solution points. I'm using a colour map which is more easily visualized than their 3D height map in many ways. (By the way, one thing I forgot to say which may not be obvious is how the dots in the image below are built up at first with points at roughly in thirds across each dimension of the entire range. These main section then split into thirds, and so on...).



However, instead of working on each function seperately, I combined one to produce a master quality evaluation (trying to get both to zero as much as possible). So instead of what the video uses:

x*sin(y) - cos(x)*y-5.0 = 0
x*x + cos(y)-8.0 = 0

...and working on each function individually, I'm simply using:

f(x,y) = abs(x*sin(y)-cos(x)*y-5.0)        +         abs(x*x+cos(y)-8.0)

...and trying to minimize f as much as possible. Any idea how (in)efficient 'my' technique is compared to their 'elimination' method?

[cKleinhuis]

hi, have you heard about neural gas method ?
http://en.wikipedia.org/wiki/Neural_gas

example program
http://www.neuroinformatik.ruhr-uni-bochum.de/ini/VDM/research/gsn/DemoGNG/GNG.html

the neural gas is also aproximating a function, it is related to self organizing maps ... but can handle complex shapes