Definition

The batch allows to execute numerous successive simulation runs. It is used to explore the parameter space of a model or to optimize a set of model parameters.

To use the batch, you must add the

<batch>

</batch>

<?xml version="1.0" encoding="ISO-8859-1" standalone="yes"?>
<mymodel>
	<modelClass name="msi.gama.kernel.Simulation" />
	<global>
		... 
	</global> 

	<environment width="gridsize" height="gridsize">
		...
	</environment>

	<entities>
		...
	</entities>

	<output>
		...
	</output>

	<batch sameSeed="true" repeat="3" stopSimWhen="time > 200">
		<param name="parameter" min="0.05" max="0.7" step="0.01" />
		<param name="another_parameter" values="'a','b','c'" />
		<method name="annealing" temp_init="100" temp_end="1" temp_decrease="0.5" nb_iter_cst_temp="5" minimize="time">
		<file name="ant" rewrite="false" />
	</batch>
</mymodel>

The batch element

The <batch ... > element takes the following three attributes:

• stopSimWhen: (expression) Specifies when to stop each simulations. Its value is a condition on variables defined in the model. The run will stop when the condition is evaluated to true. If omitted, the first simulation run will go forever, preventing any subsequent run to take place (unless a halt command is used in the model itself).
• repeat: (integer) A parameter configuration corresponds to a set of values assigned to each parameter. The attribute repeat specifies the number of times each configuration will be repeated, meaning that as many simulations will be run with the same parameter values. Different random seeds are given to the pseudo-random number generator. This allows to get some statistical power from the experiments conducted. Default value is 1.
• sameSeed: (boolean) If true, the same series of random seeds will be used from one parameter configuration to another. Default value is false.

The param elements

The <param ... /> elements specifies which model parameters will change through the successive simulations. The attribute name is mandatory and must refer to a variable declared as a parameter in the model (a variable with the attribute parameter present. Note: it seems that the value of the attribute doesn't matter.). There are 2 ways to define a number type (int or float) parameter:

• Explicit List:

  <param name="parameter" values="'0.6, 0.75, 0.8, 0.85, 1'">

  </param>

• List with step:

  <param name="parameter" min="0.05" max="0.7" step="0.01">

  </param>

For Strings and Booleans, you can only use the Explicit List.

For every List definition, you may add a random attribute as follows:

<param name="parameter" values="'0.6, 0.75, 0.8, 0.85, 1'" random="3"/>

This defines the parameter as a list of length 3 built with elements taken randomly from the list defined either by the value attribute or by the 3 attributes min, max and step.

Each Batch methods may accept only some kind of definitions and parameter types. See the description of each of them for details. The file element

The <file ... /> element allows to output detailed information about the successive simulations to a file. The file will contain, for each simulation run, the value assigned to the model parameters and the value of the expression specified in the data attribute (if specified). The file format used for the encoding is the CSV (See the wikipedia article). Here is how the attributes go:

• name: (string) The data will be output to a file named name.txt. What to do when such a file already exists is specified by the attribute rewrite.
• rewrite: (boolean) If true, a pre-existing file with an identical name will be overwritten. Otherwise, the date will be added to the filename and the data will be output to this new file.
• data: (Expression) Optional; the value of this expression is added to each line of the log file (i.e. each successive simulation). In the context of an optimization process, by default, this expression is equal to the fitness expression.

The method element

If this element is omitted, the batch will run in a classical way, changing one parameter at each step until all the possible combinations of parameter values have been covered. See #Exhaustive exploration of the parameter space for details.

The optional method element controls the algorithm which drives the batch. It must contain at least a name attribute to specify the algorithm to use, and for an optimization method, a minimize or a maximize attribute defining the expression to be optimized. Each combination of parameter values is tested repeat times. The fitness of one combination is the average of fitness values obtained with those repetitions. There might be additional attributes for tuning the exploration algorithm. See below for a description of the available methods.

It is possible to add a new batch method by writing an appropriate new Java class. See How_to_write_a_batch_method.

Batch Methods

A few batch methods are currently available. Each is described below. It is possible to add a new batch method by writing an appropriate new Java class. See How_to_write_a_batch_method.

Exhaustive exploration of the parameter space

Parameter definitions accepted: List with step and Explicit List. Parameter type accepted: all.

This is the standard batch method. The exhaustive mode is defined by default when there is no method element present in the batch section. It explores all the combination of parameter values in a sequential way.

Example (models/ants/batch/ant_exhaustive_batch.xml)

 <batch repeat="2" sameSeed="true" stopSimWhen="(food_remaining = 0) or (time > 400)">
    <param name="evaporation_rate" values="'0.1, 0.2, 0.5, 0.8, 1.0'" />
    <param name="diffusion_rate" min="0.1" max="1.0" step="0.3" />
    <file name="ant_exhaustive" data="time" rewrite="false" />
 </batch>  

The order of the simulations depends on the order of the param. In our example, the first combinations will be the followings:

• evaporation_rate = 0.1, diffusion_rate = 0.1, (2 times)
• evaporation_rate = 0.1, diffusion_rate = 0.4, (2 times)
• evaporation_rate = 0.1, diffusion_rate = 0.7, (2 times)
• evaporation_rate = 0.1, diffusion_rate = 1.0, (2 times)
• evaporation_rate = 0.2, diffusion_rate = 0.1, (2 times)
• ...

Note: this method can also be used for optimization by adding an method element with maximize or a minimize attribute:

 <batch repeat="2" sameSeed="true" stopSimWhen="(food_remaining = 0) or (time > 400)">
    <param name="evaporation_rate" values="'0.1, 0.2, 0.5, 0.8, 1.0'" />
    <param name="diffusion_rate" min="0.1" max="1.0" step="0.3" />
    <method name="exhaustive" minimize="time" />   
    <file name="ant_exhaustive" rewrite="false" />
 </batch>  

Hill Climbing

Name: hill_climbing Parameter definitions accepted: List with step and Explicit List. Parameter type accepted: all.

This algorithm is an implementation of the Hill Climbing algorithm. See the wikipedia article.

Algorithm:

 Initialization of an initial solution s 
 iter = 0
 While iter <= iter_max, do:
   Choice of the solution s' in the neighborhood of s that maximize the fitness function
   If f(s') > f(s)
     s = s’
   Else
     end of the search process
   EndIf
   iter = iter + 1
 EndWhile

Method parameters:

• iter_max: number of iterations

Example (models/ants/batch/ant_hill_climbing_batch.xml):

 <batch sameSeed="true" repeat="3" stopSimWhen="time > 400">
    <param name="evaporation_rate" min="0.05" max="0.7" step="0.01"/>
    <param name="diffusion_rate" min="0" max="1" step="0.01"/>
    <method name="hill_climbing" iter_max="50" />
    <file name="ant_hill_climbing" rewrite="false" />
 </batch>

Simulated Annealing

Name: annealing Parameter definitions accepted: List with step and Explicit List. Parameter type accepted: all.

This algorithm is an implementation of the Simulated Annealing algorithm. See the wikipedia article.

Algorithm:

 Initialization of an initial solution s 
 temp = temp_init
 While temp > temp_end, do:
   iter = 0
   While iter < nb_iter_cst_temp, do:
     Random choice of a solution s' in the neighborhood of s  
     df = f(s’)-f(s)
     If df > 0 
       s = s’
     Else,
       rand = random number between 0 and 1
       If rand > exp(df/T)
         s = s’
       EndIf
     EndIf
     iter = iter + 1
   EndWhile
 EndWhile

Method parameters:

• temp_init: Initial temperature
• temp_end: Final temperature
• temp_decrease: Temperature decrease coefficient
• nb_iter_cst_temp: Number of iterations per level of temperature

Example (models/ants/batch/ant_simulated_annealing_batch.xml):

 <batch sameSeed="true" repeat="3" stopSimWhen="time > 400">
    <param name="evaporation_rate" min="0.05" max="0.7" step="0.01"/>
    <param name="diffusion_rate" min="0" max="1" step="0.01"/>
    <method name="annealing" temp_init="100" temp_end="1" temp_decrease="0.5" nb_iter_cst_temp="5" minimize="time" />
    <file name="ant_simulated_annealing" rewrite="false" />
 </batch>

Tabu Search

Name: tabu Parameter definitions accepted: List with step and Explicit List. Parameter type accepted: all.

This algorithm is an implementation of the Tabu Search algorithm. See the wikipedia article.

Algorithm:

 Initialization of an initial solution s 
 tabuList = {}
 iter = 0
 While iter <= iter_max, do:
   Choice of the solution s' in the neighborhood of s such that:
     s' is not in tabuList
     the fitness function is maximal for s' 
   s = s’
   If size of tabuList = tabu_list_size
     removing of the oldest solution in tabuList 
   EndIf
   tabuList = tabuList + s
   iter = iter + 1
 EndWhile

Method parameters:

• iter_max: number of iterations
• tabu_list_size: size of the tabu list

Example (models/ants/batch/ant_tabu_search_batch.xml):

 <batch sameSeed="true" repeat="3" stopSimWhen="time > 400">
    <param name="evaporation_rate" min="0.05" max="0.7" step="0.01"/>
    <param name="diffusion_rate" min="0" max="1" step="0.01"/>
    <method name="tabu" iter_max="50" tabu_list_size="5" minimize="time"/>
    <file name="ant_tabu_search" rewrite="false" />
 </batch>

Reactive Tabu Search

Name: reactive_tabu Parameter definitions accepted: List with step and Explicit List. Parameter type accepted: all.

This algorithm is a simple implementation of the Reactive Tabu Search algorithm ((Battiti et al., 1993)). This Reactive Tabu Search is an enhance version of the Tabu search. It adds two new elements to the classic Tabu Search. The first one concerns the size of the tabu list: in the Reactive Tabu Search, this one is not constant anymore but it dynamically evolves according to the context. Thus, when the exploration process visits too often the same solutions, the tabu list is extended in order to favor the diversification of the search process. On the other hand, when the process has not visited an already known solution for a high number of iterations, the tabu list is shortened in order to favor the intensification of the search process. The second new element concerns the adding of cycle detection capacities. Thus, when a cycle is detected, the process applies random movements in order to break the cycle.

Method parameters:

• iter_max: number of iterations
• tabu_list_size_init: initial size of the tabu list
• tabu_list_size_min: minimal size of the tabu list
• tabu_list_size_max: maximal size of the tabu list
• nb_tests_wthout_col_max: number of movements without collision before shortening the tabu list
• cycle_size_min: minimal size of the considered cycles
• cycle_size_max: maximal size of the considered cycles

Example (models/ants/batch/ant_tabu_search_reactive_batch.xml):

 <batch sameSeed="true" repeat="3" stopSimWhen="time > 400">
    <param name="evaporation_rate" min="0.05" max="0.7" step="0.01"/>
    <param name="diffusion_rate" min="0" max="1" step="0.01"/>
    <method name="reactive_tabu" iter_max="50" tabu_list_size_init="5" tabu_list_size_min="2" tabu_list_size_max="10" nb_tests_wthout_col_max="20" cycle_size_min="2" cycle_size_max="20" minimize="time" />
    <file name="ant_tabu_search_reactive" rewrite="false" />
 </batch>

Genetic Algorithm

Name: genetic Parameter definitions accepted: List with step and Explicit List. Parameter type accepted: all.

This is a simple implementation of Genetic Algorithms (GA). See the wikipedia article. The principle of GA is to search an optimal solution by applying evolution operators on an initial population of solutions There are three types of evolution operators:

• Crossover: Two solutions are combined in order to produce new solutions
• Mutation: a solution is modified
• Selection: only a part of the population is kept. Different techniques can be applied for this selection. Most of them are based on the solution quality (fitness).

Representation of the solutions:

• Individual solution: {Param1 = val1; Param2 = val2; …}
• Gene: Parami = vali

Initial population building: the system builds nb_prelim_gen random initial populations composed of pop_dim individual solutions. Then, the best pop_dim solutions are selected to be part of the initial population.

Selection operator: roulette-wheel selection: the probability to choose a solution is equals to: fitness(solution)/ Sum of the population fitness. A solution can be selected several times. Ex: population composed of 3 solutions with fitness (that we want to maximize) 1, 4 and 5. Their probability to be chosen is equals to 0.1, 0.4 and 0.5.

Mutation operator: The value of one parameter is modified. Ex: The solution {Param1 = 3; Param2 = 2} can mute to {Param1 = 3; Param2 = 4}

Crossover operator: A cut point is randomly selected and two new solutions are built by taking the half of each parent solution. Ex: let {Param1 = 4; Param2 = 1} and {Param1 = 2; Param2 = 3} be two solutions. The crossover operator builds two new solutions: {Param1 = 2; Param2 = 1} and {Param1 = 4; Param2 = 3}.

Method parameters:

• pop_dim: size of the population (number of individual solutions)
• crossover_prob: crossover probability between two individual solutions
• mutation_prob: mutation probability for an individual solution
• nb_prelim_gen: number of random populations used to build the initial population
• max_gen: number of generations

Example (models/ants/batch/ant_genetic_algorithm_batch.xml):

 <batch sameSeed="true" repeat="3" stopSimWhen="time > 400">
    <param name="evaporation_rate" min="0.05" max="0.7" step="0.01"/>
    <param name="diffusion_rate" min="0" max="1" step="0.01"/>
    <method name="genetic" pop_dim="5" crossover_prob="0.7" mutation_prob="0.1" nb_prelim_gen="1" max_gen="20" minimize="time"/>
    <file name="ant_genetic_algorithm" rewrite="false" />
 </batch>

How to write a batch method

Introduction

Adding new search methods in GAMA is very simple. We described hereafter the two steps to follow.

Step 1

The first step consists in defining a Java class that extends the abstract class ParamSpaceExploAlgorithm

Two methods must be implemented:

• public void parametrize(Map<String, String> parameters): method called at the initialization of the search method. It allows to load the search method parameter values (according to what the user has defined in GAML). All the parameters are of the String type.
• public Solution findBestSolution(): main search method. It returns the best solution found.

(Protected) Attributes of the ParamSpaceExploAlgorithm class:

• simulation: Simulation, current simulation.
• fitnessFct: FitnessFunction, object that allows to evaluate the fitness of a solution (fitness(Solution sol))
• testedSolutions: Map<Solution, Double>, map containing all the tested solutions and their associated fitness. Each time the fitness method of the FitnessFunction class is triggered, the result is saved in this map.
• variables: HashMap<String, BatchVariable>, map containing the variables (parameters that we explore). Key: name of the variable -> Value: BatchVariable object representing the variable (its current value, its possible values, its neighbor values, etc.).

Step 2

The adding of new search method in GAMA is automatic. It is just necessary to check that the package in which the class is defined is contained in the String table exploAlgoPackages of the BatchManager class. The GAML name of the search method is its class name