1.2 SaMDE
#The SaMDE Type#
SaMDE is a type to calibrate a model using a genetic algorithm based on the SaMDE(Self-adaptive Mutation Differential Evolution) function described by Fraga, L. M et al. (2010). It returns a SAMDE type with the fittest individual (a Model), its fit value, and the number of generations taken by the genetic algorithm to reach the result. We do not recommend the use of this class for models that include noise.
- fit The best fitness result returned by the SAMDE Algorithm.
- instance The instance of the model with the best fitness.
- generation The number of generations created by the generit algorithm until it stopped.
#Input#
- model A TerraME Model.
- parameters A table with the possible parameter values. They can be values or Choices. All Choices will be calibrated.
- fit A user-defined function that gets a model instance as argument and returns a numeric value of that particular model fitness, this value will be minimized or maximized by SAMDE according to the maximize parameter.
- size The maximum population size in each generation.
- maxGen The maximum number of generations.
- threshold If the fitness of a model reaches this value, SAMDE stops and returns such model.
- maximize An optional paramaters that determines if the fit will be maximized (true) or minimized (false, default value).
#Example# Model to simulate an infection spread in a population:
local infection = Model{
contacts = Mandatory("number"),
contagion = Choice{min = 0, max = 1},
infected = 3,
susceptible = 763,
recovered = 0,
days = Mandatory("number"),
finalTime = 13,
counter = 1,
chart = true,
finalInfected = {},
finalSusceptible = {},
finalRecovered = {},
init = function(self)
self.total = self.infected + self.susceptible + self.recovered
self.alpha = self.contagion * self.contacts / self.total
self.beta = 1/self.days
self.finalInfected[self.counter] = self.infected
self.finalSusceptible[self.counter] = self.susceptible
self.finalRecovered[self.counter] = self.recovered
local graph
if self.chart then
setmetatable(self, nil)
Chart{
data = self,
select = {"inf"},
xAxis = 'counter'
}
end
self.timer = Timer{
Event{action = function()
self.susceptible = self.susceptible - self.alpha * self.infected * self.susceptible
self.infected = self.infected + self.alpha * self.infected * self.susceptible - self.beta * self.infected
self.recovered = self.recovered + self.beta * self.infected
self.counter = self.counter + 1
self.finalInfected[self.counter] = self.infected
self.finalSusceptible[self.counter] = self.susceptible
self.finalRecovered[self.counter] = self.recovered
end}
}
end
}
local fluData = {3, 7, 25, 72, 222, 282, 256, 233, 189, 123, 70, 25, 11, 4}
local fluSimulation = SAMDE{
model = infection,
maxGen = 9,
parameters = {
chart = false,
contacts = Choice{min = 3, max = 50},
contagion = Choice{min = 0, max = 1},
days = Choice{min = 1, max = 20}
},
fit = function(model)
local dif = 0
forEachOrderedElement(model.finalInfected, function(idx, att, typ)
dif = dif + math.abs(att - fluData[idx])
end)
return dif
end}
print("The smallest difference between fluData and the calibrated infection model is: ")
print(fluSimulation.fit)It's available in the package examples folder. #The SaMDE algorithm# A DE algorithm is an efficient and powerful evolutionary algorithm for solving real valued optimization problems. However the success of DE in solving a specific problem depends highly on the appropriated choice of control parameters. Parameter tuning leads to additional computational costs because of time-consuming trial-and error tests. Self-adaptation, in contrast, allows the algorithm to reconfigure itself, automatically adapting to the problem being solved. SaMDE is a Self-Adaptive Differential Evolution with multiple mutation strategies, and it at preserving the essential characteristics of self-adaptation. The paper results suggest that SaMDE is a very promising algorithm.
SaMDE, makes use of multiple mutation strategies, and uses differential evolution itself to self-adapt both the control parameters and the odds of choosing a particular mutation strategy. First of all, in SaMDE, individuals have the following aspect:
xi = xi,1, ..., xi,D, V 1i , ..., V ki , F1i ,CR1i , ..., F ki ,CRki
where xi,d are the problem variables, k is the number of different mutation strategies, V ki ∈ [0, 1] corresponds to a value attributed to the kth strategy (this will be used for the strategy selection), F ki ∈ [0.1, 1] and CRki ∈ [0, 1.0] are the control parameters related to the kth strategy. In the population initialization, the problem variables and parameters are chosen randomly. Then for each individual, first the values V are updated with differential mutation as follows:
V ki = V kr1 + F(V kr2 − V kr3)
With the updated V s , the strategy that will be applied on the current individual is chosen by means of the roulette wheel algorithm, where strategies with bigger values of V are more likely to be chosen. Once the winner strategy w, w ∈ {1, 2, .., k}, is selected their related values F w and CRw are also updated by differential mutation, as follows:
F wi = F wr1 + F(F wr2 − F wr3)
CRwi = CRwr1 + F(CRwr2 − CRwr3)
Then the algorithm continues normally, operating the mutation with the winner strategy and doing the traditional recombination and selection steps. Notice that only the control parameters of the winner strategy should be updated, as they are the only ones to contribute to the trial solution fitness. F = U[0.7,1] in all cases. Although F is an additional parameter of the self-adaptive mechanism, the performance of the algorithm is not very sensitive to this parameter in the indicated range, as shown in the results. For sake of clarity a pseudo-code of SaMDE is presented:
this image was taken from the SaMDE paper Fraga, L. M et al. (2010)
Due to their search diversity, four mutation strategies were selected here, and are described below:
-
rand/1 It is the original differential mutation, usually demonstrates slow convergence speed and bears stronger exploration capability.
vt,i = xt,r1 + F(xt,r2 − xt,r3) -
best/1 Usually has the fastest convergence speed and performs well when solving unimodal problems.
vt,i = xt,best + F(xt,r2 − xt,r3) -
rand/2 In this strategy, the statistical distribution of the summation of all two-difference vectors have a bell shape, that is generally regarded as a better pertubation mode.
vt,i = xt,r1 + F(xt,r2 − xt,r3) + F(xt,r4 − xt,r5) -
current-to-rand/1 It is a rotation-invariant strategy. Its efectiveness has been verified when it was applied to solve multi-objective optimization problems.
vt,i = xt,i + F(xt,r1 − xt,i) + F(xt,r2 − xt,r3)
In order to keep the updated control parameters in the boundaries, the mechanism proposed in was used. In this mechanism the amount of violation is reflected back to the bound, as can be seen in the following equation.
x = 2 × xlow − x if x<xlow
x = 2 × xupp − x if x>xupp
where x represents the updated control parameter, xlow and xupp are the lower and the upper bounds, respectively. The SaMDE algorithm employs different mutation strategies and self-adapts all its important control parameters. The population size is fixed and the parameters are updated before they are used for generating new solutions. This allows the operators to be influenced by the new updated parameter values, allowing them to be indirectly evaluated by the selection operator. All this is done by introducing only one new parameter, F.
SaMDE Paper: Rodrigo César Pedrosa Silva, Rodolfo Ayala Lopes, and Frederico Gadelha Guimarães. 2011. Self-adaptive mutation in the differential evolution. In Proceedings of the 13th annual conference on Genetic and evolutionary computation (GECCO '11), Natalio Krasnogor (Ed.). ACM, New York, NY, USA, 1939-1946. DOI=http://dx.doi.org/10.1145/2001576.2001837