Continuous Gray code numerical optimisation

[lemontree]

I learned about this simple and interesting algorithm from this paper:
http://www.cs.bham.ac.uk/~jer/papers/ctsgray.pdf

Code: Select all

function continuousGray(x as double,precision as double=20) as double

    dim as double y

    if rnd>.5 then

        y=x+exp(-precision*rnd)

        if y>1.0 then y-=2.0

    else

        y=x-exp(-precision*rnd)

        if y<-1.0 then y+=2.0

    end if

    return y

end function



sub translate(result() as double,vec() as double,minX() as double,maxX() as double)

    dim as integer i

    for i=0 to ubound(result)

        result(i)=minX(i)+.5*(vec(i)+1.0)*(maxX(i)-minX(i))

    next

end sub

    

sub optimize(fn as function(X() AS DOUBLE) AS DOUBLE, minX() as double,maxX() as double,res() as double,iterations as uinteger,p as double=20)

    dim as double vecA(ubound(res)),vecB(ubound(res)),cost,tc

    dim as uinteger i,iter

    randomize timer,3

    for i=0 to ubound(res)

        res(i)=1-2.0*rnd

    next

    translate(vecB(),res(),minX(),maxX())

    cost=fn(vecB())

    for iter=0 to iterations

        for i=0 to ubound(res)

            vecA(i)=continuousGray(res(i),p)

        next

        translate(vecB(),vecA(),minX(),maxX())

        tc=fn(vecB())

        if tc<cost then

            cost=tc

            for i=0 to ubound(res)

                res(i)=vecA(i)

            next

        end if

    next

    translate(res(),res(),minX(),maxX())

end sub



'Demo

' minimum -18.5547... at (9.039, 8.668)    

function test(v() as double) as double

    return v(0)*sin(4*v(0))+1.1*v(1)*sin(2*v(1))

end function



dim x(1) as double=>{0,0}       

dim min(1) as double=>{0,0}         

dim max(1) as double=>{10,10}



optimize(@test,min(),max(),x(),1000,20)

print test(x())

getkey



 

[jdebord]

Thanks. I have downloaded the paper.

This should make a nice addition to FBMath :)

[lemontree]

I've been trying out the Gray code algorithm for a few days now. Hey, it's really amazing. Nearly all genetic algorithms are convergent in nature. Once they start converging that's it, there is no going back and that makes them less than suitable where you want open-ended evolution or co-evolution.
In contrast the Gray code algorithm should be very good for open-ended evolution, co-evolution and in dynamically changing or noisy environments. I am trying out some variations at the moment such as:

Code: Select all

' Written by Sean O'Connor 27 September 2009

function continuousGray(x as double,precision as double) as double

    dim as double y,z

    z=(1+abs(x))*exp(-precision*rnd)

    if rnd>.5 then

        y=x+z

        if y>1.0 then y=x-z

    else

        y=x-z

        if y<-1.0 then y=x+z

    end if

    return y

end function



#macro evaluate(mVec)

    for i=0 to ubound(result)

        result(i)=minX(i)+.5*(mVec(i)+1.0)*(maxX(i)-minX(i))

    next

    cE=fn(result())

    if cE<cost then

        cost=cE

        for i=0 to ubound(result)

            M(i)=mVec(i)

        next

        if cb<>0 then cb(result())

    end if

#endmacro



#macro localOpt(mVec)

    evaluate(mVec)

    cL=cE

    for iter=0 to iterations

        for i=0 to ubound(result)

            T(i)=continuousGray(mVec(i),p)

        next

        evaluate(T)

        if cE<cL then 

            cL=cE

            for i=0 to ubound(result)

                mVec(i)=T(i)

            next

        end if

    next

#endmacro



sub optimize(fn as function(X() AS DOUBLE) AS DOUBLE, minX() as double,maxX() as double,result() as double,_

    iterations as uinteger=20000,p as double=250,generations as uinteger=10000,cb as sub(y() as double)=0)

    dim as double A(ubound(result)),B(ubound(result)),M(ubound(result)),T(ubound(result)),cost,cE,cL

    dim as uinteger i,iter,gen

    randomize timer,3

    for i=0 to ubound(result)

        A(i)=1-2.0*rnd

        B(i)=1-2.0*rnd

        M(i)=1-2.0*rnd

    next

    evaluate(M)

    cost=cE

    for gen=0 to generations

        localOpt(A)

        localOpt(B)

        for i=0 to ubound(result)

            if rnd>.5 then swap A(i),B(i)

        next

    next

    evaluate(M)

end sub

[rdc]

I've been trying out the Gray code algorithm for a few days now. Hey, it's really amazing. Nearly all genetic algorithms are convergent in nature. Once they start converging that's it, there is no going back and that makes them less than suitable where you want open-ended evolution or co-evolution.

That is true for a stand-alone GA,which is why you need to combine the GA with a classifier system. David Goldberg wrote an excellent book on this subject: Genetic Algorithms in Search, Optimization and Machine Learning. A classifier system is an evolutionary system that operates over time and can react to changes in the environment by redefining the rules as needed. Not only is a GA/CS powerful, it is actually quite simple to implement.