popt.update_schemes.cma

  1import numpy as np
  2from popt.misc_tools import optim_tools as ot
  3
  4class CMA:
  5
  6    def __init__(self, ne, dim, alpha_mu=None, n_mu=None, alpha_1=None, alpha_c=None, corr_update=False, equal_weights=True):
  7        '''
  8        This is a rather simple simple CMA class
  9
 10        Parameters
 11        ----------------------------------------------------------------------------------------------------------
 12        ne : int
 13            Ensemble size
 14        
 15        dim : int
 16            Dimensions of control vector
 17        
 18        alpha_mu : float
 19            Learning rate for rank-mu update. If None, value proposed in [1] is used.
 20        
 21        n_mu : int, `n_mu < ne`
 22            Number of best samples of ne, to be used for rank-mu update.
 23            Default is int(ne/2).
 24        
 25        alpha_1 : float
 26            Learning rate fro rank-one update. If None, value proposed in [1] is used.
 27        
 28        alpha_c : float
 29            Parameter (inverse if backwards time horizen)for evolution path update 
 30            in the rank-one update. See [1] for more info. If None, value proposed in [1] is used.
 31
 32        corr_update : bool
 33            If True, CMA is used to update a correlation matrix. Default is False.
 34        
 35        equal_weights : bool
 36            If True, all n_mu members are assign equal weighting, `w_i = 1/n_mu`.
 37            If False, the weighting scheme proposed in [1], where `w_i = log(n_mu + 1)-log(i)`,
 38            and normalized such that they sum to one. Defualt is True.
 39
 40        References
 41        ----------------------------------------------------------------------------------------------------------
 42        [1] Hansen, N. (2006). The CMA evolution strategy: a comparing review. 
 43            In J. Lozano, P. Larranaga, I. Inza & E. Bengoetxea (ed.), Towards a new evolutionary computation. 
 44            Advances on estimation of distribution algorithms (pp. 75--102) . Springer .     
 45        '''
 46        self.alpha_mu       = alpha_mu
 47        self.n_mu           = n_mu
 48        self.alpha_1        = alpha_1
 49        self.alpha_c        = alpha_c
 50        self.ne             = ne
 51        self.dim            = dim
 52        self.evo_path       = 0
 53        self.corr_update    = corr_update
 54
 55        #If None is given, default values are used
 56        if self.n_mu is None:
 57            self.n_mu = int(self.ne/2)
 58        
 59        if equal_weights:
 60            self.weights = np.ones(self.n_mu)/self.n_mu
 61        else:
 62            self.weights = np.array([np.log(self.n_mu + 1)-np.log(i+1) for i in range(self.n_mu)])
 63            self.weights = self.weights/np.sum(self.weights)
 64
 65        self.mu_eff = 1/np.sum(self.weights**2)
 66        self.c_cov  = 1/self.mu_eff * 2/(dim+2**0.5)**2 +\
 67                    (1-1/self.mu_eff)*min(1, (2*self.mu_eff-1)/((dim+2)**2+self.mu_eff))
 68
 69        if self.alpha_1 is None:
 70            self.alpha_1  = self.c_cov/self.mu_eff
 71        if self.alpha_mu is None:
 72            self.alpha_mu = self.c_cov*(1-1/self.mu_eff)
 73        if self.alpha_c is None:
 74            self.alpha_c  = 4/(dim+4)
 75        
 76    def _rank_mu(self, X, J):
 77        '''
 78        Calculates the rank-mu matrix of CMA-ES.
 79        '''
 80        index   = J.argsort() # lowest (best) to highest (worst)
 81        Xsorted = (X[index[:self.n_mu]] - np.mean(X, axis=0)).T # shape (d, ne)
 82        weights = self.weights
 83        Cmu     = (Xsorted*weights)@Xsorted.T
 84
 85        if self.corr_update: 
 86            Cmu = ot.cov2corr(Cmu)
 87        
 88        return Cmu
 89
 90    def _rank_one(self, step):
 91        '''
 92        Calculates the rank-one matrix of CMA-ES.
 93        '''
 94        s = self.alpha_c
 95        self.evo_path = (1-s)*self.evo_path + np.sqrt(s*(2-s)*self.mu_eff)*step
 96        C1 = np.outer(self.evo_path, self.evo_path)
 97
 98        if self.corr_update: 
 99            C1 = ot.cov2corr(C1)
100
101        return C1
102    
103    def __call__(self, cov, step, X, J):
104        '''
105        Performs the CMA update.
106
107        Parameters
108        --------------------------------------------------
109            cov : array_like, of shape (d, d)
110                Current covariance or correlation matrix.
111            
112            step : array_like, of shape (d,)
113                New step of control vector.
114                Used to update the evolution path.
115
116            X : array_like, of shape (n, d)
117                Control ensemble of size n.
118            
119            J : array_like, of shape (n,)
120                Objective ensemble of size n.
121        
122        Returns
123        --------------------------------------------------
124            out : array_like, of shape (d, d)
125                CMA updated covariance (correlation) matrix.
126        '''
127        a_mu  = self.alpha_mu
128        a_one = self.alpha_1 
129        C_mu  = self._rank_mu(X, J)
130        C_one = self._rank_one(step)
131        
132        cov   =  (1 - a_one - a_mu)*cov + a_one*C_one + a_mu*C_mu       
133        return cov