Page 37 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2017 4th Student Computer Science Research Conference. Koper: University of Primorska Press, 2017
P. 37
re rand j, j ∈ [1 − 4] represents random number in range 3.3.1 Agent’s population size determination
[0, 1] and Fi(G+1) is in range [0.1, 1]. Constants τ1 and τ2 are
so-called learning rates determining the frequency of updat- In order to ensure that the comparison between different
ing control parameters F and CR, and were set to 0.1. MAS is as fair as possible, we introduce the total population
size NP MAS , that determines the number of vectors in the
Adaptation of control parameters according to Eq. (6)-(7) so-called grand population. Obviously, the MAS-jDE with
is performed after 10 generations in average, and therefore grand population is equivalent to the original jDE using a
has a big influence on mutation and crossover operators. single population. In MAS-jDE, the members of this grand
population are divided among agents evenly. The higher the
3.3 Multi-agent system based on jDE for solv- number of agents in the MAS, the smaller is their population
ing DOPs size. In line with this, the agent’s population size NP is
obtained as:
Multi-agent system based on jDE for solving DOPs (MAS-
jDE) implements system of multiple autonomous agents, NP = NP MAS , (8)
that run autonomously based on jDE algorithm using sepa- N
rated populations of the same size. Multi-agent systems are
systems composed of multiple interfacing intelligent agents. where N represents the number of agents. Because all three
Each agent is a computationally entity like an algorithm mentioned variables have to be integers, not all combinations
that is placed in an environment in order to achieve its ob- of NPMAS and N are feasible.
jectives [12]. In our case, each agent is devoted to search for a
best solution in own region of the whole search space. Using 3.3.2 Environment change detection
the interaction between agents, they are able to enrich their
limited knowledge with informations obtained from other An evolutionary cycle starts after a random initialization
agents in the MAS. and evaluation of agent’s population. The DE mutation
and crossover operate on NP − 1 trial vectors only, because
There are four main issues that must be solved when devel- the last vector is used as a sentinel [8] that never changes.
oping the algorithm: agent’s population size determination, Thus, the sentinel’s fitness function value is changed with the
environment change detection, maintaining the population change of the environment. Therefore, we first check after
diversity and information exchange between agents. Accord- the newly generated population is evaluated, if the fitness
ing to our assumption of fairness, it holds that if system value of sentinel distinguishes from the old value. In this
contains more agents, the population size of each agent is case, we declare that the environment has changed, conse-
decreased. This fact can cause a stagnation problem, where quently reinitialize agent population randomly and evaluate
algorithm gets stuck in a local optimum and can not get the new fitness values for the whole population.
out, due to the lower population diversity. To avoid this
problem, we introduce mechanism for measuring the popu- 3.3.3 Maintaining the population diversity
lation diversity that uses the following principle: When the
diversity of population is insignificant, the MAS-jDE begins The stagnation problem can be evident at the population
migration of individuals between agents. The pseudo-code as whole or at the component level [13]. In MAS-jDE, we
of the algorithm is illustrated in Algorithm 1. detect stagnation by calculating agent’s population diversity
using the following equations [8, 13]:
Algorithm 1 Algorithm MAS-jDE
N PMAS: sum of populations sizes aj(G) = NP −1 xi(,Gj ) , (9)
NP: size of agent’s population i=1
N: number of agents
1: NP = N PMAS/N NP − 1
2: Generate and evaluate all agent’s populations
3: Update global best diversity = D NP−1 (10)
4: while the termination condition is not meet do
5: for each agent’s population i do (x(i,Gj) − a(jG))2,
6: Update parameters F and CR (Eq. (6)-(7))
7: Create trial population j with DE operators mu- j=1 i=1
tation and crossover where aj(G) stores the mean of population in j th dimension.
8: Evaluate j j is in range [1, D], where D is a problem dimension. xi is
9: if environment change detected then an individual in population.
10: Generate and evaluate new population Diversity in population is checked after each generation to
11: else detect stagnation as quickly as possible. If it falls bellow
12: Selection between i and j threshold level, migration between agents starts. Threshold
13: Update global best level must be set high enough, so that agent has enough
14: Check diversity and exchange individuals diversity in population to continue exploring search-space
and low enough, so it can close-in to the optimum.
In the remainder of the paper, the exposed issues of the
proposed MAS-jDE algorithm are discussed in details. 3.3.4 Information exchange between agents
When diversity in population falls bellow threshold, migra-
tion between agents starts (Algorithm 2). Idea is as fol-
lows. Each agent begins exploration in different part of
search space and therefore it’s search is limited to the spe-
cific region. When new vectors are migrated from another
agent, it is expected that the diversity of population will
increase. Thereby, the agent will be attracted to explore
the new promising regions in the search space. Procedure
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference 37
Ljubljana, Slovenia, 11 October
[0, 1] and Fi(G+1) is in range [0.1, 1]. Constants τ1 and τ2 are
so-called learning rates determining the frequency of updat- In order to ensure that the comparison between different
ing control parameters F and CR, and were set to 0.1. MAS is as fair as possible, we introduce the total population
size NP MAS , that determines the number of vectors in the
Adaptation of control parameters according to Eq. (6)-(7) so-called grand population. Obviously, the MAS-jDE with
is performed after 10 generations in average, and therefore grand population is equivalent to the original jDE using a
has a big influence on mutation and crossover operators. single population. In MAS-jDE, the members of this grand
population are divided among agents evenly. The higher the
3.3 Multi-agent system based on jDE for solv- number of agents in the MAS, the smaller is their population
ing DOPs size. In line with this, the agent’s population size NP is
obtained as:
Multi-agent system based on jDE for solving DOPs (MAS-
jDE) implements system of multiple autonomous agents, NP = NP MAS , (8)
that run autonomously based on jDE algorithm using sepa- N
rated populations of the same size. Multi-agent systems are
systems composed of multiple interfacing intelligent agents. where N represents the number of agents. Because all three
Each agent is a computationally entity like an algorithm mentioned variables have to be integers, not all combinations
that is placed in an environment in order to achieve its ob- of NPMAS and N are feasible.
jectives [12]. In our case, each agent is devoted to search for a
best solution in own region of the whole search space. Using 3.3.2 Environment change detection
the interaction between agents, they are able to enrich their
limited knowledge with informations obtained from other An evolutionary cycle starts after a random initialization
agents in the MAS. and evaluation of agent’s population. The DE mutation
and crossover operate on NP − 1 trial vectors only, because
There are four main issues that must be solved when devel- the last vector is used as a sentinel [8] that never changes.
oping the algorithm: agent’s population size determination, Thus, the sentinel’s fitness function value is changed with the
environment change detection, maintaining the population change of the environment. Therefore, we first check after
diversity and information exchange between agents. Accord- the newly generated population is evaluated, if the fitness
ing to our assumption of fairness, it holds that if system value of sentinel distinguishes from the old value. In this
contains more agents, the population size of each agent is case, we declare that the environment has changed, conse-
decreased. This fact can cause a stagnation problem, where quently reinitialize agent population randomly and evaluate
algorithm gets stuck in a local optimum and can not get the new fitness values for the whole population.
out, due to the lower population diversity. To avoid this
problem, we introduce mechanism for measuring the popu- 3.3.3 Maintaining the population diversity
lation diversity that uses the following principle: When the
diversity of population is insignificant, the MAS-jDE begins The stagnation problem can be evident at the population
migration of individuals between agents. The pseudo-code as whole or at the component level [13]. In MAS-jDE, we
of the algorithm is illustrated in Algorithm 1. detect stagnation by calculating agent’s population diversity
using the following equations [8, 13]:
Algorithm 1 Algorithm MAS-jDE
N PMAS: sum of populations sizes aj(G) = NP −1 xi(,Gj ) , (9)
NP: size of agent’s population i=1
N: number of agents
1: NP = N PMAS/N NP − 1
2: Generate and evaluate all agent’s populations
3: Update global best diversity = D NP−1 (10)
4: while the termination condition is not meet do
5: for each agent’s population i do (x(i,Gj) − a(jG))2,
6: Update parameters F and CR (Eq. (6)-(7))
7: Create trial population j with DE operators mu- j=1 i=1
tation and crossover where aj(G) stores the mean of population in j th dimension.
8: Evaluate j j is in range [1, D], where D is a problem dimension. xi is
9: if environment change detected then an individual in population.
10: Generate and evaluate new population Diversity in population is checked after each generation to
11: else detect stagnation as quickly as possible. If it falls bellow
12: Selection between i and j threshold level, migration between agents starts. Threshold
13: Update global best level must be set high enough, so that agent has enough
14: Check diversity and exchange individuals diversity in population to continue exploring search-space
and low enough, so it can close-in to the optimum.
In the remainder of the paper, the exposed issues of the
proposed MAS-jDE algorithm are discussed in details. 3.3.4 Information exchange between agents
When diversity in population falls bellow threshold, migra-
tion between agents starts (Algorithm 2). Idea is as fol-
lows. Each agent begins exploration in different part of
search space and therefore it’s search is limited to the spe-
cific region. When new vectors are migrated from another
agent, it is expected that the diversity of population will
increase. Thereby, the agent will be attracted to explore
the new promising regions in the search space. Procedure
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference 37
Ljubljana, Slovenia, 11 October
