Login / Register  0 items | $0.00 NewWhat is KVR? Submit News Advertise
User avatar
Aleksey Vaneev
KVRAF
 
3216 posts since 7 Sep, 2002

Postby Aleksey Vaneev; Wed Jul 13, 2016 9:27 am Bitmask evolution optimization method from Aleksey Vaneev

I've come up with an interesting and very simple evolutionary optimization method. Since I have not seriously studied the "state of art" of evolution optimization strategies, I may be recreating a prior art. But nevertheless the offered method is quite interesting in itself. You invert a random range of lower bits of parameter values and it just works. I've added a couple of tricks on top of that to increase robustness. Convergence time is quite huge as with most evolutionary optimization methods.

The URL is: https://github.com/avaneev/biteopt
Image
stratum
KVRian
 
1240 posts since 29 May, 2012

Postby stratum; Wed Jul 13, 2016 1:02 pm Re: Bitmask evolution optimization method from Aleksey Vaneev

Just curious, what's the use of this algorithm in music-dsp? Optimize something like this? http://www.convexoptimization.com/wikimization/index.php/Dattorro_Convex_Optimization_of_a_Reverberator
~stratum~
User avatar
Aleksey Vaneev
KVRAF
 
3216 posts since 7 Sep, 2002

Postby Aleksey Vaneev; Wed Jul 13, 2016 1:37 pm Re: Bitmask evolution optimization method from Aleksey Vaneev

stratum wrote:Just curious, what's the use of this algorithm in music-dsp? Optimize something like this? http://www.convexoptimization.com/wikimization/index.php/Dattorro_Convex_Optimization_of_a_Reverberator

It can be used for that as well, if you can formulate the optimization problem as a "cost" function.
Image
stratum
KVRian
 
1240 posts since 29 May, 2012

Postby stratum; Wed Jul 13, 2016 1:57 pm Re: Bitmask evolution optimization method from Aleksey Vaneev

It can be used for that as well, if you can formulate the optimization problem as a "cost" function.


Probably a cost function can be defined for that in terms of "uncoloredness of the impulse response". I didn't read about it much though.
Thanks for sharing the code.

edit: Apparently the link itself states a more important objective.
~stratum~
User avatar
Zaphod (giancarlo)
KVRAF
 
2301 posts since 23 Jun, 2006

Postby Zaphod (giancarlo); Wed Jul 13, 2016 6:59 pm Re: Bitmask evolution optimization method from Aleksey Vaneev

Very good and straightforward, thank you
Miles1981
KVRian
 
1251 posts since 26 Apr, 2004, from UK

Postby Miles1981; Thu Jul 14, 2016 2:29 am Re: Bitmask evolution optimization method from Aleksey Vaneev

Aleksey Vaneev wrote:I've come up with an interesting and very simple evolutionary optimization method. Since I have not seriously studied the "state of art" of evolution optimization strategies, I may be recreating a prior art. But nevertheless the offered method is quite interesting in itself. You invert a random range of lower bits of parameter values and it just works. I've added a couple of tricks on top of that to increase robustness. Convergence time is quite huge as with most evolutionary optimization methods.

The URL is: https://github.com/avaneev/biteopt


Seems to be close to genetic algorithms when you don't keep the ancesters?
User avatar
Aleksey Vaneev
KVRAF
 
3216 posts since 7 Sep, 2002

Postby Aleksey Vaneev; Thu Jul 14, 2016 3:24 am Re: Bitmask evolution optimization method from Aleksey Vaneev

Miles1981 wrote:
Aleksey Vaneev wrote:I've come up with an interesting and very simple evolutionary optimization method. Since I have not seriously studied the "state of art" of evolution optimization strategies, I may be recreating a prior art. But nevertheless the offered method is quite interesting in itself. You invert a random range of lower bits of parameter values and it just works. I've added a couple of tricks on top of that to increase robustness. Convergence time is quite huge as with most evolutionary optimization methods.

The URL is: https://github.com/avaneev/biteopt


Seems to be close to genetic algorithms when you don't keep the ancesters?

Yes, this method does not keep ancestors. But as addition to the strategy it does keep a history of best solutions, and performs crossing-over (by default in 10% of steps). However, this does not always result in a faster convergence.
Image
Miles1981
KVRian
 
1251 posts since 26 Apr, 2004, from UK

Postby Miles1981; Thu Jul 14, 2016 4:24 am Re: Bitmask evolution optimization method from Aleksey Vaneev

OK, so a variation of genetic algorithms.
I tried at some point some comparisons with Numerical Recipes' simulated annealing (which has nothing to do with simulated annealing...), and GA are usually quite fast, even if they don't find the minimum in all cases.

Did you compare your hybridation process (mutate in 90% of the steps) with the usual hybridation process (mutate a proportion of each step, cross over for another proportion and keep another proportion, all depending on the set of best candidates)?
User avatar
Aleksey Vaneev
KVRAF
 
3216 posts since 7 Sep, 2002

Postby Aleksey Vaneev; Thu Jul 14, 2016 5:12 am Re: Bitmask evolution optimization method from Aleksey Vaneev

Miles1981 wrote:OK, so a variation of genetic algorithms.
I tried at some point some comparisons with Numerical Recipes' simulated annealing (which has nothing to do with simulated annealing...), and GA are usually quite fast, even if they don't find the minimum in all cases.

Did you compare your hybridation process (mutate in 90% of the steps) with the usual hybridation process (mutate a proportion of each step, cross over for another proportion and keep another proportion, all depending on the set of best candidates)?

So far I made no comparisons to other genetic approaches. What I've discovered is that in my approach simultaneous "mutation" and crossing-over does not work well - in some cases it has benefit, but not always. These operations work independently, but stochastically in tandem reduce convergence time.
Image
User avatar
Aleksey Vaneev
KVRAF
 
3216 posts since 7 Sep, 2002

Postby Aleksey Vaneev; Sat Jul 23, 2016 11:37 am Re: Bitmask evolution optimization method from Aleksey Vaneev

It's quite cool: I was able to simplify the optimizer further, now includes the CBEOOptimizer2 class which does not even require crossing-over and history of best solutions. Yet the convergence time is quite low. However, I can't quite describe why its accidentally discovered mysterious "previous attempt intermix" operation works.

Global optimization is still beyond the reach of this strategy, but maybe I can find some solution eventually.
Image
camsr
KVRAF
 
6628 posts since 16 Feb, 2005

Postby camsr; Sun Jul 24, 2016 9:40 pm Re: Bitmask evolution optimization method from Aleksey Vaneev

What is an evolutionary algorithm? I am none familiar with it.
Image
User avatar
Aleksey Vaneev
KVRAF
 
3216 posts since 7 Sep, 2002

Postby Aleksey Vaneev; Mon Jul 25, 2016 1:09 am Re: Bitmask evolution optimization method from Aleksey Vaneev

camsr wrote:What is an evolutionary algorithm? I am none familiar with it.

Evolutionary optimization strategy means the current solution is "evolved" to the next state from its previous state by means of random operators. These strategies also use crossing-over operation that involves mixing with ancestors or previous best solutions.

Meanwhile, I was able to further improve the strategy. I also made comparisons to Nelder-Mead simplex method, and my strategy proves to be more robust (stably produces a solution from any initial state) and converges 2 times faster when optimizing most functions I've tried. The Nelder-Mead method in half of the cases stopped prematurely producing a sub-optimal solution. So, it's a win.
Image
Miles1981
KVRian
 
1251 posts since 26 Apr, 2004, from UK

Postby Miles1981; Mon Jul 25, 2016 1:52 am Re: Bitmask evolution optimization method from Aleksey Vaneev

Nelder Mead is a local optimization algorithm, whereas GA are global ones. The fact that they are global helps them in tricky valleys of the cost function IMHO, so not really surprised by this result ;)
User avatar
Aleksey Vaneev
KVRAF
 
3216 posts since 7 Sep, 2002

Postby Aleksey Vaneev; Mon Jul 25, 2016 2:34 am Re: Bitmask evolution optimization method from Aleksey Vaneev

Miles1981 wrote:Nelder Mead is a local optimization algorithm, whereas GA are global ones. The fact that they are global helps them in tricky valleys of the cost function IMHO, so not really surprised by this result ;)

GAs are not equally good at global optimization. My strategy also strives to provide the global best solution, it is capable of that. The current problem is that when the global minimum's shape is very narrow and there are many local minimums, the strategy chooses a sub-optimal minimum - it just can't "hit" global minimum's position with a lower cost.

The problematic function I'm not struggling with is
Code: Select all
y = 100 * sqrt( fabs( y - 0.01 * x * x )) + 0.01 * fabs( x + 10 )


Functions I've tried with the Nelder Mead method are mostly local optimization problems. So, the comparison was fair.
Image
resynthesis
KVRist
 
254 posts since 17 Sep, 2007, from Planet Thanet

Postby resynthesis; Mon Jul 25, 2016 2:58 am Re: Bitmask evolution optimization method from Aleksey Vaneev

It's been a while since I looked at this sort of stuff but it's always difficult to be sure of reaching the absolute optimal solution in difficult energy landscapes. I worked with GAs and found in the problem domain I was looking at (load balancing for finite element problems) took quite a bit of tinkering with mutation rates to climb out of local minima. Perhaps some sort of hybrid method would help i.e. use the evolutionary method for a few iterations and then switch to a local optimization scheme to reduce iterations required.
Next

Moderator: Moderators (Main)

Return to DSP and Plug-in Development