Differential Evolution (차분 진화) [algorithm] by 바죠

Differential Evolution 
http://en.wikipedia.org/wiki/Differential_evolution
http://www1.icsi.berkeley.edu/~storn/code.html


컴퓨터 사이언스에서 사용되는 최적화 방법이다함수 미분 없이 함수 최적화할 때 사용하는 방법이다벡터들의 차이에 의존하여 문제를 풀어내는 방법이다(사실 미분 가능한 함수이면 연속함수이다.)  진화 격자 방법은 확률론적 문제 풀이 방식이다이 문제 풀이 방식은 항상 정답을 보장하지 못한다. 다차원 독립변수를 가지는 함수의 최적화에 적용될 수 있다독립변수가 너무 많기 때문에 이런 식의 문제풀이가 가장 유력한 것이 되기도 한다일반적으로 적용할 수 있는 범용성을 가지고 있다.


Differential evolution
방법은 함수가 미분 가능할 필요가 없는 상황에 적합하다물론, 함수가 미분 가능이면 해석적으로 미분한 형태를 이용해서 국소 최적화를 동시에 활용할수 있다일반으로 국소 최적화가 병행될 때, 광역 최적화가 보다 수월하게 진행된다항상 국소 최적화된 해만 고려하는 형식으로 광역 최적화를 진행할 수 있다이러한 방법은 상당한 효율성 향상으로 이어진다반드시 국소 최적화를 해석적인 방법으로 이루어야만 하는 것은 아니다(온도가 0으로 수렴하는 경우에 해당하는 simulated annealing 형식의 Monte Carlo 방식으로진행해도 된다.) 확률론적으로 수행해도 된다. 반드시 LBFGS 같은방법으로 이루어야만 하는 것은 아니다.  Differential evolution은 하나의 병렬 알고리듬이다보다 나은 해를 위해서 집단의 해들을 동시에 고려하고 crossover, mutation을 활용하는 유전 알고리듬과 차이가 없다고 생각해도 무방하다(해를 표현할 때 bit string 대신에 실수를활용한다.) 해를 표현할 때, 1차원으로 배열된 bit string방식으로 표현하지 않는다. 해를 실수형으로 직접 표현한다crossover, mutation하는 보다 직접적인 방법이 제시되어 있다. 많은 경우 그대로 차용해서 사용할 수 있게 해준다. 물론, 풀고 있는 문제에 따라서는 그대로 차용해서 사용할 수 없는 경우가 있을 수 있다.


유전 알고리듬, particle swarm optimization에서처럼 사실상 최고의 병렬 효율성을 기대해도 좋다목적 함수를 계산하는 시간이 오래 걸릴수록 병렬 효율성은 증대될 것이다유전 알고리듬과 차이점이 있다면, 해를 표현하는방법으로 bit string 표현을 사용하지 않는다는 점이다물론, 유전 알고리듬에서도 bit string 표현을고집할 이유는 사실 없다. 다만, 역사적으로 그런 방식으로개발되었다어떻게 하던 1차원적 길이 방식으로 표현하는 것은 가능하다. 물리적이건, 수학적이건 상관없다다만, 문제에 따라서 특정 표현 방식이 선호될 수 있고, 효율성향상으로 연계될 수 있다. 실제 표현형을 사용한다. 또한, 표현형을 직접활용하여 변이, 교차를 동시에 이루어낸다. 따라서, 변이, 교차 실행에서 새로운 형식이수반된다서로 다른 시도 해를 체계적으로 만들어낸다보다 구체적으로 crossover를 할 수 있도록 설계된 방식을 제공한다

사실, 변이, 교차가 각각 중요하다는 것이 유전알고리듬의 결론이다. 이들 둘 중 하나만 사용하면 효율성 향상을 얻을 수 없다는 것이 결론이다
. 그렇다면 실제 문제 풀이에서 어떻게 변이, 교차를 해 낼 수 있는가? 이것은 문제에 따라서 달라지는 것이고, 굉장히 다양한 방법으로 이루어질 수 있다주요 매개변수로서 differential weight, crossover probability가있다.
population size
는 최소 4 이상이어야 한다
그렇지 않으면 안 된다. 하지만, 대부분의 응용계산에서는 이 보다 훨씬 큰 값을 사용하기 때문에이 부분은 전혀 문제가 되지 않는다변이와 교차를 상당한 수준에서 일반적으로 행할 수 있게 해준다실제 표현형을 그대로 사용한다는 특징이 있다. 비교적 간단한 방법으로 교차 및 변이를 동시에 취급하게 해 준다실수 변수를 사용하기 때문에 격차 진화 방법은 매우 현실적인 광역 최적화 알고리듬다소위 bit string 표현보다는 훨씬 현실적인 방법으로 보인다.

x : vector, solution,
독립변수의 개수가 vector의 차원을결정하게 된다.

Differential evolution에서는
y =  a + F(b-c)

처럼 새로운 시도해 y를 만들 수 있음을 제안한다. 이부분은 사실 변이에 해당한다. a, b, c는 서로 다른 해들이다. 또한 추가로 x를하나 더 확보해야 한다. x, a, b, c, 모두 서로 다른 것들이다. 이들 서로 다른 해, a, b, c로부터 새로운 시도 해를 조직적으로 만들어 낸다변이를 만들어 낸다.   여기에 추가로 확보한 해를 사용하여 변이에 이은 교차까지 완료할 수 있다. 이것 때문에, 최소 4 개 이상의 population size가 되어야 한다실질적으로 4 보다 훨씬 큰 population size를취급하기 때문에 사실상 제약이 안 된다추가적인 절차를 통해서 교차를 하는 방법을 지원한다최종 목표는 변이와 교차를 순서적으로 이룩하는 것이다. x, a, b, c 가 서로 다른 해들일 때, y라는 시도 해를 만들어 낸다결국, 변이, 교차를체계적으로 지원한다.

{x, a, b, c} ---> y

x
라는 해에서 또 다른 시도 해를 고려해 볼 수 있다x ---> x' 으로 변환할 때사실 이것이 모든 알고리듬에서 공통으로항상 요구된다가능하면 최대한 일반적인 것이 될 수 있으면 좋다. 특정 공간에 국한 되지 말아야 한다. 광범위하게 이러한 변환을 만들 수 있으면 좋다. 그런데, 일반적인 문제에서 이를 이룩하기는 매우 어렵다. 이는 Monte Carlo 시물레이션의 끝도 없는 숙제 중의 숙제이며광역 최적화 방법에 있어서 핵심 요소 중 하나라고 볼 수 있다. 그 이외의 대부분의 샘플링 문제에서도 공통으로 나타나는 해결해야 할 숙제이다particle swarm optimization 에서는 유전 알고리듬에서와 달리 crossover, mutation을 활용하지 않는다. 하지만, crossover, mutation에 대응하는 부분이 있다.



https://pablormier.github.io/2017/09/05/a-tutorial-on-differential-evolution-with-python/
Eggholder function 최적화가 좀 더 어려운 문제이다.


--------------------------------------------------------------------------------

Genetic Algorithm (GA):
http://incredible.egloos.com/4856511
Particle Swarm Optimization (PSO):
http://incredible.egloos.com/4731015
Simulated Annealing (SA):
http://incredible.egloos.com/4784592
Replica-Exchange Monte Carlo, Replica-Exchange Molecular Dynamics, super simulated annealing (REMD, REMC):
http://incredible.egloos.com/4587643

Conformational Space Annealing (CSA):
http://incredible.egloos.com/6208916

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------


!234567890
       implicit none
       integer ndim,npop
       real*8, allocatable :: x(:,:),xnew(:,:)
       integer ij,kl
       integer i,j
       real ranmar


       ndim=3
       npop=15
       allocate(x(ndim,npop),xnew(ndim,npop))
       ij=111
       kl=112
       call rmarin(ij,kl)
       do i=1,npop
       do j=1,ndim
       x(j,i)=i*10+j
       enddo
       enddo
       write(6,*) x(:,:)


       calldffvltn(ndim,npop,x,xnew)


       write(6,*) xnew(:,:)
       write(6,*)
       write(6,*) xnew-x
       deallocate(x,xnew)
       stop
       end
       subroutine dffvltn(ndim,npop,x,xnew)
       implicit none
       integer ndim,npop
       real*8 x(ndim,npop),xnew(ndim,npop)
       integer iarr(4),jbrr,i,j
       real*8 tmt
       real*8 cr,ff
       real ranmar
!      ff :  differential weight
!      cr :  crossover probability
       xnew=x
       do i=1,npop
       if(npop >=4 )then
       iarr(1)=dble(ranmar())*npop+1
  111  continue
       iarr(2)=dble(ranmar())*npop+1
       if(iarr(2) == iarr(1)) goto 111
  112  continue
       iarr(3)=dble(ranmar())*npop+1
       if(iarr(3) == iarr(1) .or. iarr(3) ==iarr(2)) goto 112
  113  continue
       iarr(4)=dble(ranmar())*npop+1
       if(iarr(4) == iarr(3) .or. iarr(4) == iarr(2).or. iarr(4) == iarr(1)) goto 113
       print*, i
       jbrr=dble(ranmar())*ndim+1 ; cr=ranmar() ;ff=2.d0*dble(ranmar())
       do j=1,ndim
       tmt=ranmar()
       if(jbrr == j .or. tmt <= cr)then
       xnew(j,i)=x(j,iarr(2))+ff*(x(j,iarr(3))-x(j,iarr(4)))
                                  endif
       if(jbrr /= j .and. tmt > cr)then
       xnew(j,i)=x(j,iarr(1))
                                  endif
       enddo
                   else
       tmt=-1.d0
       do j=1,ndim
       if(tmt < abs(x(j,i))) tmt=abs(x(j,i))
       enddo
       tmt=tmt/10.d0
       do j=1,ndim
       xnew(j,i)=x(j,i)+(ranmar()-0.5)*tmt
       enddo
                   endif
       enddo
       end

---------------------------------------------------------
       do klo1=1,nsteps
       do klo2=1,nfactor
       call random_number(cr)
       call random_number(cf) ; cf=cf*2.d0
       do j=1,npop
   10  continue
       call random_number(zzi) ; j1=1+zzi*npop
       if(j1 == j) goto 10
   11  continue
       call random_number(zzi) ; j2=1+zzi*npop
       if(j2 == j1 .or. j2 == j) goto 11
   12  continue
       call random_number(zzi) ; j3=1+zzi*npop
       if(j3 == j2 .or. j3 == j1 .or. j3 == j) goto 12
       call random_number(zzi) ; i0=1+zzi*ndf
       do i=1,ndf
       call random_number(zzr)
       if(zzr < cr .or. i  == i0)then
       vvv(i,j)=xxx(i,j1)+cf*(xxx(i,j2)-xxx(i,j3))
                                 else
       vvv(i,j)=xxx(i,j)
                                 endif
       if(abs(vvv(i,j)) > abs(amp))then
       call random_number(tmp) ; vvv(i,j)=2.d0*(tmp-0.5d0)*amp
                                   endif
       enddo
    
       test0=objft(vvv(1,j))
       if(test0 < epbest(j))then
       epbest(j)=test0 ; pbest(:,j)=vvv(:,j)
       xxx(:,j)=pbest(:,j)
                            endif
       enddo
       test0=minval(epbest)
       do j=1,npop
       if(abs(test0-epbest(j)) < 1.d-9)then
       gbest(:)=pbest(:,j) ; pvecbest=gbest
                                       endif
       enddo
       enddo
       enddo
---------------------------------------------------------


---------------------------------------------------------------------------------------------------------------------
근본적으로 유전 알고리듬(genetic algorithm)과 differential evolution 알고리듬의 차이는 없다

실수형으로 이루어진 벡터량으로 해를 표현하고, 좀 더 일반적인 그리고 기계적인 crossover, mutation방법을 소개한다. 유전 알고리듬(genetic algorithm)의 핵심 요소들 교차, 변이, 선택, 대치의 기본 개념을 그대로 활용한다. 당연하게도 다수의 해들을 동시에 고려한다. 국소 최적화 알고리듬을 활용하면 더욱더 효율적인 알고리듬이 될 수 있다. Nelder-Mead, BFGS 알고리듬을 사용할 수 있다.
---------------------------------------------------------------------------------------------------------------------


cf.

 http://www.hvass-labs.org/


핑백


최근 포토로그