Page 36 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2017 4th Student Computer Science Research Conference. Koper: University of Primorska Press, 2017

ve differential evolution (MAS-jDE) for solving DOP.
These are a class of problems, where the environment
changes over time. Autonomous agents that are capable
of detecting these changes on their own, try to solve DOP
by using jDE and maintaining various sized populations.
An evolutionary progress can typically stagnate when us-
ing agents with smaller populations. Therefore, we tried to
prevail this problem by implementing two mechanism: de-
tection of stagnation by calculating population’s diversity
and migration of individuals between agents. Experiments
with various configurations of multi-agent systems were con-
ducted, where the number of agents and the population sizes
were varied. Indeed, these both parameters were selected
such that the algorithms in each configurations spent the
same number of the fitness function evaluations. In this
way, fair comparison between different MAS-jDE configu-
rations can be expected. Additionally, the performance of
the proposed algorithm MAS-jDE was also compared to the
others state-of-the-art algorithms for solving DOP.
The remainder of the paper is organized in the following
way. Section 2 describes the DOPs. Section 3 describes the
original DE, its extension jDE and the proposed MAS-jDE
algorithm. Section 4 illustrates the results of experiments
that were conducted and provides discussion on them. Fi-
nally, Section 5 concludes this paper with summarizing the
performed work and outlining directions for the future work.
2. PROBLEM DEFINITION
This paper is devoted to solving DOPs. Li et al. in [7]
defined these kind of problems as follows:
DOP = f (x, φ, t), (1)
where DOP is the dynamic optimization problem, f is an
evaluation function, x is a feasible solution in the solution set
X, φ (so called change type) is a system control parameter
determining the solution’s distribution in the fitness land-
scape and t is real-world time. Changes in environment can
be results of a change of system control parameters describ-
ing environment state or a change in evaluation function.
These changes can occur either after some predefined num-
ber of generations or, more commonly, in each generation,
where the online responses are desired by the evolutionary
algorithms.
The goal of the algorithm for solving DOP is to detect the
change of environment and find the new optimum. Problem
frequently occurring in evolutionary algorithms for DOP is a
stagnation of population. Evolutionary process moves popu-
lation to or very near to the local or global optimum, which
causes a very small diversity of the population. When it
comes to environmental change, the population with small
diversity cannot explore search space efficiently enough. Usu-
ally this could mean, that the algorithm will not be able to
find the next global optimum.
3. THE PROPOSED ALGORITHM
The proposed MAS-jDE algorithm combines a knowledge
from two domains: evolutionary algorithms (EAs) [3] and
multi-agent systems (MAS) [12]. In line with this, three
algorithm are described at first, i.e., differential evolution
(DE), followed by self-adaptation differential evolution (jDE)
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference
Ljubljana, Slovenia, 11 October
that is an extension of DE. Finally, the proposed MAS-jDE
is presented from the multi-agent aspect.
3.1 Differential evolution
DE [11] is a well established EA, developed by Storn and
Price [11]. It is a population-based algorithm, whose popu-
lation is defined as a set of real-valued vectors representing
different solutions of the problem:
xi = {xi,1, xi,2, . . . , xi,D}, (2)
for i = 1, . . . , NP , where NP represents the population size
and D is the dimensionality of the problem. Like in other
EAs, the first step in DE is a random initialization of the
population. Until the termination condition is satisfied, the
population undergoes operation of three evolutionary op-
erators by creating trial vectors: mutation, crossover and
selection.
Mutation creates mutant vector vi(G+1) from parent’s popu-
lation. Different mutation DE strategies have been used in
literature [10, 11], but in original article [11] authors used
the so-called ’DE/rand/1/bin’:
vi(G+1) = xr(G0 ) + F · (x(rG1 ) − xr(G2 )), (3)
where r0, r1 and r2 represent random integer numbers in
range [1, NP ], where it holds r0 = r1 = r2, and the scale
factor is a real number in range F ∈ [0, 2].
Crossover operator introduces a little diversity in the pop-
ulation of solutions. It creates a trial vector ui(,Gj+1) from a
combination of elements from either the mutation vector or
the corresponding parent vector as:
vi(,Gj +1)
u(i,Gj+1) = xi(,Gj ) if rand (0, 1) ≤ CR or j = jrand , (4)
otherwise,
where the crossover rate is defined in range CR ∈ [0, 1) and
determines a probability of creating a trial vector from the
mutation vector. Index jrand is randomly selected integer
defined in range [1, D] that is used to ensure that the al-
gorithm makes at least one change in trial vector regarding
previous generation.
Selection compares the results of fitness function from newly
created trial vector u(i,Gj+1) and parent vector x(i,Gj). If the
problem is minimization problem, it is defined as follows:
x(iG+1) = ui(G+1) if f (ui(G+1)) ≤ f (x(iG)) (5)
x(iG) otherwise.
The fitness function depends on the problem to be solved.
3.2 Self-adaptive DE
Brest et al. [1] presented self-adaptive differential evolution
algorithm (jDE), where control parameters Fi and CRi are
added to representation of individuals and adapted during
the evolution process using following equations:
Fi(G+1) = Fl + rand1 · Fu if rand 2 < τ1, (6)
Fi(G) otherwise,
CRi(G+1) = rand3, if rand4 < τ2, (7)
C Ri(G) otherwise,
36