220
A. V. Panteleev and M. M. S. Karane
The hybrid multi-agent method of interpolation search imitates the evolution of
the initial population I 0 = {x
j
, j = 1, 2, . . . , N P|x
j
= (x
j
1 , x
j
2 , . . . , x
j
n )
T
∈ D}
and is an iterative process that explores the set D.
The procedure of finding a solution begins with the generation of the initial population of individuals x
j ( j = 1, N P) on the set D using a uniform distribution. The
first phase of the search is interpolation search. The construction of different interpolation polynomials allows to adapt a locally changing structure of the level surfaces
of the objective function. A different role of leading points is also used to realize
frontal search or deep search of an admissible solution set, thereby, providing additional flexibility of the search strategy. The interpolation polynomials type choice is
optional. Thus, the choice of the interpolation polynomial type and the points, by
which it is formed, implements two types of search: exploration and exploitation.
To implement it, four members P 1 , P 2 , P 3 , P 4 in the population are selected.
Among them P 1 = x
(1) is a leader, and P 2 , P 3 , P 4 are random members of the
population. All four points are different. The Bezier curve is used to process them.
It passes inside the convex hull formed by the selected four points. As t = 0, curve
passes through P 1 , and as t = 1, curve passes through point P 4 . Next, we find the
solution to the parametric optimization problem
x
Bezier4
= arg max
t∈[0,1]
f [(1 − t)
3 P 1 + 3(1 − t)
2 t P 2 + 3(1 − t)t
2 P 3 + t
3 P 4 ], (16.2)
and a new member x
Bezier4 is added to the population.
B-spline curve is used to explore new areas. The curve is formed by four random
members of the population P 1 , P 2 , P 3 , P 4 that are different
x B = arg max
t∈[0,1]
f
1
2
−t (1 − t) 2 P 1 + (2 − 5t 2 + 3t 3 )P 2 + t (1 + 4t − 3t 2 )P 3 − t 2 (1 − t)P 4
.
(16.3)
As a rule, the curve does not pass through any point; it is in the convex hull
generated by four vertices. As a result, one more new member x
B is added to the
population.
The second phase of the search is the migration of the population. The leader is
selected in the population (the best solution) x
(1) . All other members of the population
x
( j)
, j = 2, ..., N P move toward the leader making nstep discrete steps, and half
of these steps being done to the leader, and then as many more steps are taken in
the same direction. The new position of a member of the population is determined
by the best decision reached during this search. The direction of the search is given
by a vector PRTVector, whose coordinates are zero or one. If the coordinate is zero,
the search for this coordinate is not conducted, and if it is one, then it is performed.
Thus, the solution to the problem is sought in all coordinates that are simultaneously
equal to one. The position of the leader in the migration process does not change.
A. V. Panteleev and M. M. S. Karane
The hybrid multi-agent method of interpolation search imitates the evolution of
the initial population I 0 = {x
j
, j = 1, 2, . . . , N P|x
j
= (x
j
1 , x
j
2 , . . . , x
j
n )
T
∈ D}
and is an iterative process that explores the set D.
The procedure of finding a solution begins with the generation of the initial population of individuals x
j ( j = 1, N P) on the set D using a uniform distribution. The
first phase of the search is interpolation search. The construction of different interpolation polynomials allows to adapt a locally changing structure of the level surfaces
of the objective function. A different role of leading points is also used to realize
frontal search or deep search of an admissible solution set, thereby, providing additional flexibility of the search strategy. The interpolation polynomials type choice is
optional. Thus, the choice of the interpolation polynomial type and the points, by
which it is formed, implements two types of search: exploration and exploitation.
To implement it, four members P 1 , P 2 , P 3 , P 4 in the population are selected.
Among them P 1 = x
(1) is a leader, and P 2 , P 3 , P 4 are random members of the
population. All four points are different. The Bezier curve is used to process them.
It passes inside the convex hull formed by the selected four points. As t = 0, curve
passes through P 1 , and as t = 1, curve passes through point P 4 . Next, we find the
solution to the parametric optimization problem
x
Bezier4
= arg max
t∈[0,1]
f [(1 − t)
3 P 1 + 3(1 − t)
2 t P 2 + 3(1 − t)t
2 P 3 + t
3 P 4 ], (16.2)
and a new member x
Bezier4 is added to the population.
B-spline curve is used to explore new areas. The curve is formed by four random
members of the population P 1 , P 2 , P 3 , P 4 that are different
x B = arg max
t∈[0,1]
f
1
2
−t (1 − t) 2 P 1 + (2 − 5t 2 + 3t 3 )P 2 + t (1 + 4t − 3t 2 )P 3 − t 2 (1 − t)P 4
.
(16.3)
As a rule, the curve does not pass through any point; it is in the convex hull
generated by four vertices. As a result, one more new member x
B is added to the
population.
The second phase of the search is the migration of the population. The leader is
selected in the population (the best solution) x
(1) . All other members of the population
x
( j)
, j = 2, ..., N P move toward the leader making nstep discrete steps, and half
of these steps being done to the leader, and then as many more steps are taken in
the same direction. The new position of a member of the population is determined
by the best decision reached during this search. The direction of the search is given
by a vector PRTVector, whose coordinates are zero or one. If the coordinate is zero,
the search for this coordinate is not conducted, and if it is one, then it is performed.
Thus, the solution to the problem is sought in all coordinates that are simultaneously
equal to one. The position of the leader in the migration process does not change.