Page 35 - 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. 35
ti-agent system based on self-adaptive differential
evolution for solving dynamic optimization problems
Aleš Cˇ ep Iztok Fister
Faculty of Electrical Engineering and Computer Faculty of Electrical Engineering and Computer
Science Science
University of Maribor University of Maribor
ales.cep@um.si iztok.fister@um.si
ABSTRACT triggered events. Consequently, the value of a fitness func-
tion that is optimal at some time, is not necessary optimal
This article presents the multi-agent system based on a self- at another and vice versa.
adaptive differential evolution algorithm for solving dynamic
problems. Characteristics of dynamic problems are that ob- Differential evolution (DE) was proposed by Storn and Price
jective function, with which the quality of solutions is eval- in [11] and is a powerful evolutionary algorithm (EA) fre-
uated, changes over time. These changes can occur either quently used for solving global optimization problems. Its
after some predefined number of generations or, more com- simplicity and effectiveness have been proven in many real-
monly, in each generation, where the online responses are de- world applications. DE emulates natural evolution process
sired by the evolutionary algorithms. In this study, the for- using three operators: mutation, crossover and selection.
mer kind of problems were taken into consideration and were Brest et al [1] proposed jDE algorithm which extends the
solved using multi-agent systems. Each agent in the systems original DE algorithm with self-adaptation of DE control pa-
is implemented as a self-adapted differential evolution with rameters, i.e., the scale rate and the frequency of crossover
constant population size. In our comparative study, multi- rate. This self-adaptation is performed before generating the
agent systems consisting of various population sizes in com- trial vector and therefore it influences creation of new trial
bination with various number of agents were compared, by vectors. These controls parameters are added to a repre-
solving the benchmark functions provided for CEC’09 Com- sentation of individuals and undergo operation of variation
petition on Dynamic Optimization with respect to the same operators (i.e., mutation and crossover) during the evolu-
number of the fitness function evaluation. The main obstacle tionary cycle.
when using smaller populations is to prevent the stagnation
of the population. That was partially overcome by using Morrison [8] presented new EA architecture for solving DOP
additional mechanisms such as: diversity measurement and where he uses so-called sentinels, i.e., individuals in a pop-
information sharing between agents. As a result, the most ulation that are spread across search space whose location
appropriate multi-agent system was searched for, and the does not change. In this way they can be used for detecting
results of the best found multi-agent system were compared changes of environment. Brest et al [2] presented multi-
with the state-of-the-art algorithms. population jDE (jDE*) algorithm with the ageing mech-
anism and the use of archive where they stored the cur-
Keywords rent best individuals after the environment change was de-
tected. There was no information sharing between individ-
Differential evolution, self-adaptive differential evolution, uals. Yang et al [13] proposed an algorithm for improving
multi-agent system, dynamic problems DE with population adaptation approach, where it calcu-
lates the standard deviation of individuals’ in j -th dimen-
1. INTRODUCTION sion at generation G. Halder et al [5] presented an algorithm
CDDE Ar that uses a multi-population method where clus-
Many of real-world problems are dynamic in their nature. ters (sub-populations) are partitioned according to the spa-
Dynamic optimization problems (DOP) [4] can be described tial locations of trial solutions. During the evolution pro-
as problems, where decision maker has to make multiple de- cess, population is periodically divided in different number
cisions over time and the overall performance depends on of clusters which causes certain information sharing dur-
all decisions made in that time. Decisions are made sequen- ing the optimization process. Lepagnot et al [6] presented
tially over time, but it depends on the type of problems, if MLSDO algorithm, which is based on several coordinated
this decisions are made by time triggered (periodic) or event local searches and on the archiving of the found local op-
tima, in order to track them after a change in the objective
function. Novoa et al [9] proposed an algorithm mSQDE-
i, a multi-population algorithm with self-adaptive strategy
for controlling the population diversity and an interaction
mechanism between individuals.
This paper proposes multi-agent system based on self-ada-
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7023-40-4.35-41 35
Ljubljana, Slovenia, 11 October
evolution for solving dynamic optimization problems
Aleš Cˇ ep Iztok Fister
Faculty of Electrical Engineering and Computer Faculty of Electrical Engineering and Computer
Science Science
University of Maribor University of Maribor
ales.cep@um.si iztok.fister@um.si
ABSTRACT triggered events. Consequently, the value of a fitness func-
tion that is optimal at some time, is not necessary optimal
This article presents the multi-agent system based on a self- at another and vice versa.
adaptive differential evolution algorithm for solving dynamic
problems. Characteristics of dynamic problems are that ob- Differential evolution (DE) was proposed by Storn and Price
jective function, with which the quality of solutions is eval- in [11] and is a powerful evolutionary algorithm (EA) fre-
uated, changes over time. These changes can occur either quently used for solving global optimization problems. Its
after some predefined number of generations or, more com- simplicity and effectiveness have been proven in many real-
monly, in each generation, where the online responses are de- world applications. DE emulates natural evolution process
sired by the evolutionary algorithms. In this study, the for- using three operators: mutation, crossover and selection.
mer kind of problems were taken into consideration and were Brest et al [1] proposed jDE algorithm which extends the
solved using multi-agent systems. Each agent in the systems original DE algorithm with self-adaptation of DE control pa-
is implemented as a self-adapted differential evolution with rameters, i.e., the scale rate and the frequency of crossover
constant population size. In our comparative study, multi- rate. This self-adaptation is performed before generating the
agent systems consisting of various population sizes in com- trial vector and therefore it influences creation of new trial
bination with various number of agents were compared, by vectors. These controls parameters are added to a repre-
solving the benchmark functions provided for CEC’09 Com- sentation of individuals and undergo operation of variation
petition on Dynamic Optimization with respect to the same operators (i.e., mutation and crossover) during the evolu-
number of the fitness function evaluation. The main obstacle tionary cycle.
when using smaller populations is to prevent the stagnation
of the population. That was partially overcome by using Morrison [8] presented new EA architecture for solving DOP
additional mechanisms such as: diversity measurement and where he uses so-called sentinels, i.e., individuals in a pop-
information sharing between agents. As a result, the most ulation that are spread across search space whose location
appropriate multi-agent system was searched for, and the does not change. In this way they can be used for detecting
results of the best found multi-agent system were compared changes of environment. Brest et al [2] presented multi-
with the state-of-the-art algorithms. population jDE (jDE*) algorithm with the ageing mech-
anism and the use of archive where they stored the cur-
Keywords rent best individuals after the environment change was de-
tected. There was no information sharing between individ-
Differential evolution, self-adaptive differential evolution, uals. Yang et al [13] proposed an algorithm for improving
multi-agent system, dynamic problems DE with population adaptation approach, where it calcu-
lates the standard deviation of individuals’ in j -th dimen-
1. INTRODUCTION sion at generation G. Halder et al [5] presented an algorithm
CDDE Ar that uses a multi-population method where clus-
Many of real-world problems are dynamic in their nature. ters (sub-populations) are partitioned according to the spa-
Dynamic optimization problems (DOP) [4] can be described tial locations of trial solutions. During the evolution pro-
as problems, where decision maker has to make multiple de- cess, population is periodically divided in different number
cisions over time and the overall performance depends on of clusters which causes certain information sharing dur-
all decisions made in that time. Decisions are made sequen- ing the optimization process. Lepagnot et al [6] presented
tially over time, but it depends on the type of problems, if MLSDO algorithm, which is based on several coordinated
this decisions are made by time triggered (periodic) or event local searches and on the archiving of the found local op-
tima, in order to track them after a change in the objective
function. Novoa et al [9] proposed an algorithm mSQDE-
i, a multi-population algorithm with self-adaptive strategy
for controlling the population diversity and an interaction
mechanism between individuals.
This paper proposes multi-agent system based on self-ada-
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7023-40-4.35-41 35
Ljubljana, Slovenia, 11 October