28 Agent-Based Modeling and Simulation with Swarm
• Nodes to be used
• Design of parameters in the problem
The fitness function evaluates the appropriateness of a solution to the
problem. The design of this fitness function can completely change the ten-
dencies in the solutions tha t will be obtained. Actual examples of the fitness
function will be given later.
Which nodes to use, which is the second factor, is important bec ause it
determines the size of the solution space. For instance, when the tra ining
data in a function regression problem is generated by sin x + x, the solution
generated by GP will not be a good approximation of the training data if
the non-terminal nodes consist only of +, −, ×, and ÷. On the other hand,
using too many nodes would result in the solution space becom ing too big.
This means that mor e calculations are necessary before arriving at a solution.
Therefore, the nodes to be used must be chosen appropriately, no t more and
not less.
The third factor is the choice of parameters in GP, and parameters that
determine the performance of searches in GP include po pulation size, mutation
rate, crossover rate, tournament size (in the case of tournament selection),
and maximum tree depth. Searches in a GA a re typically carried out with a
small number of individuals (∼ 10 0), whereas mo re individuals are used in GP
(generally 1000–10,000 but it depends on the problem). The mutation rate is
the ratio of individuals in the population that mutate and is usually about
0.1–0.2. The crossover rate is a similar parameter, and is typically about 0.8.
GP uses tree structures and therefore the length is not fixed; however, a limit
is usually imposed on the size of the tree structures. The number of nodes
increases ex ponentially in GP due to the bloat phenomenon. Limiting the
maximum depth and maximum number of nodes can prevent the generation
of excessively large tree structures. Solutions are searched in GP after the
above three factors are determined.
Algorithms in GP include the fo llowing steps:
1. Random generation of initial population
M individuals are generated if the number of individua ls in the popula-
tion is M. The initial individuals are generated randomly.
2. Fitness evaluation
Fitness scores are determined by the fitness function fo r all M individ-
uals.
3. Selection
Good solutions a re selected through a predetermined selection algo-
rithm.
4. Mutation and crossover
Mutation and crossover operations are performed on selected good so-
lutions.
Evolutionary Methods and Evolutionary Computation 29
(a) FULL (b) GROW
FIGURE 2.10: Initialization of a tree structure using FULL and GROW
methods.
5. The sear ch ends if the criteria to end the search are satisfi e d; return to
2 if not.
Each step is described in detail b e low.
2.3.3 Initialization of tree structures
In contrast to GAs, GP using tree structures, and thus a uniform distri-
bution of initial individuals, is difficult to achieve.
Metho ds to generate initial individuals in GP usually belong to one of two
types, namely “FULL” (full depth) and “GROW” (growing).
• FULL method
The tree structures can have variable leng th, but a limit is usually im-
posed on the maximum depth of tree structures. The FULL method
randomly selects from non-terminal nodes until the maximum depth is
reached, and then selects from termina l nodes once the maximum depth
is reached (Fig. 2.10(a)). Therefore, terminal nodes only exist at the
maximum depth in the FULL method.
• GROW method
In the FULL method, nodes are selected from no n-terminal nodes only
until the maximum depth is rea ched; however, in the GROW method,
nodes are selected randomly from all nodes until the maximum depth
is reached. Once the maximum depth is reached, nodes are randomly
chosen from ter minal nodes as in the FULL method (Fig. 2 .10(b)).
Using the GROW method only or the FULL method only re sults in biased
initial individuals. FULL structures are less likely to be generated when the
GROW method is used, and most of the structures that can be generated
30 Agent-Based Modeling and Simulation with Swarm
FIGURE 2.11: Initial popula tion obtained with the RAMPED HALF &
HALF method.
with the GROW method are not generated when the FULL method is used.
Uniformity of tree structures can be defined as follows.
• Uniformity of size
Groups where most structures have few nodes and groups where most
structures have many nodes are not considered to have a uniform distri-
bution over the solution space. Groups where tree str uctures of various
sizes are distributed evenly a re mor e prefer able.
• Uniformity of structure
A population where all individuals are complete trees cannot be consid-
ered uniform even thoug h the distribution of size is uniform.
An initialized method called RAMPED HALF & HALF has been proposed,
which is a combination of the GROW and FULL methods.
• RAMPED HALF & HALF method
For a population of M individuals , the population is separated into five
groups of M/5 individuals each with different depths, e.g., 2, 3, 4, 5, and
6. Half o f the individuals in each group are generated with the GROW
method, and the other half with the FULL method (Fig. 2.11).
A uniform distribution of initial individuals is important in evolutionary
computation because a satisfactory solution cannot be reached if the initial
individuals are not uniformly distributed, a s discussed before. T he RAMPED
HALF & HALF method intentionally improves the diversity of the initial
individuals, and using this initialization metho d has been reported to increase
the performance of searches.
Evolutionary Methods and Evolutionary Computation 31
FIGURE 2.12: An example of the wall following problem. The black squares
in the figure are walls, and the gray squares are tiles adjacent to walls.
2.3.4 Fitness evaluation
Fitness evaluation is a procedure to quantify how an individual in GP
(a tr e e structur e ) is adapting to its environment (problem). GP is use d to
generate programs that determine the motion of robots, and various fitness
functions are used depending on the problem in this type of program genera-
tion. One famous benchmarking problem in GP is the wall following pro blem.
In this problem, a program to control a robot is searched such that the robo t
moves as adjac e ntly to a wall as possible in a room with walls, shown in
Fig. 2.12. The fitness in this case is
fitness
j
= (tiles adjacent to a wall that the robot passed)
−(tiles away from a wall that the robot passed)
GP finds a progra m where the robot actually moves along a wall with this
fitness evaluation.
The wall following task and its simulator will be described in detail in
Section 2.3.6.
2.3.5 Crossover and mutation
Mutation in GP, which uses tree structures , is a natural expansion of mu-
tation in the GA. The most general method is the mutation of partial trees.
A node is randomly selected in this mutation method. Next, the partia l tree
where this node is the root node is replaced with a randomly generated par-
tial tree (Fig. 2.13). The changes from mutation in GAs are rela tively small,
whereas the changes in GP are large. For instance, the origina l tree structure
becomes a completely new structure if the root node of the o riginal tree wa s
chosen. Therefore, mutation methods with less impact have been proposed,
32 Agent-Based Modeling and Simulation with Swarm
FIGURE 2.13: Genetic ope rations in GP. The left is a mutation of a partial
tree, and the right is a cro ssover of partial trees.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.