For authors
Search
Search Results
##search.searchResults.foundPlural##
-
SEARCH POPULATION ALGORITHM FOR VLSI ELEMENTS PLACEMENT
B.K. Lebedev , O. B. Lebedev , V.B. Lebedev2020-11-22Abstract ▼The paper considers a population search algorithm for the placement of VLSI components.
By analogy with the process of the emergence and formation of crystals from matter, the process
of generating a solution by sequential manifestation and concretization of the solution based on an
integral placer of alternatives is called the method of crystallization of a placer of alternatives.
The solution Qk of the placement problem is represented as a bijective mapping Fk = A → P, each
element of the set A corresponds to one single element of the set P and vice versa. The
metaheuristic of crystallization of a placer of alternatives underlying the algorithm searches for
solutions taking into account collective evolutionary memory, which means information reflecting
the history of the search for a solution and the memory of the search procedure. A distinctive feature
of the metaheuristic used is that it takes into account the tendency to use alternatives from the
best found solutions. Compact data structures for storing solution interpretations and memory are
proposed. An algorithm associated with evolutionary memory seeks to memorize and reuse ways
to achieve better results. The developed algorithm belongs to the class of population. The iterative
process of finding solutions includes three stages. At the first stage of each iteration, the constructive
algorithm generates nq solutions Qk. The work of the constructive algorithm is based on the
indicators of the main integral placer of alternatives – the matrix R, which stores the integral indicators
of the solutions obtained at the previous iterations. The process of assigning an item to a
position involves two stages. In the first stage, the element is selected, and in the second stage, the
position pj. In this case, the restriction must be fulfilled: each element corresponds to one position
pj. The estimate ξk of the solution Qk and the estimate of the utility δk of the set of positions Pk selected
by the agents are calculated. The work uses a cyclical method of forming decisions.
In this case, the accumulation of estimates of the integral utility δk in the main integral placer of
alternatives R is performed after the complete formation of the set of solutions Q. At the second
stage of the iteration, the estimates of the integral utility δk are increased in the main integral
placer of alternatives − the matrix R. At the third stage of the iteration, the estimates of the utility
δk of the integral placer of alternatives R are reduced by a priori a given value δ*. The algorithm
ends after the specified number of iterations has been completed. Comparative analysis with other
solution algorithms was carried out on standard test examples (benchmarks) of the IBM corporation,
while the solutions synthesized by the CAF algorithm exceed the solution efficiency of the
known methods by an average of 6%. The time complexity of the algorithm is O(n2)-O(n3) -
POPULATION ALGORITHM FOR CONSTRUCTING A TREE OF SOLUTIONS BY METHOD OF CRYSTALLIZATION OF ALTERNATIVES FIELD
B.K. Lebedev , O.B. Lebedev , V. B. Lebedev2020-11-22Abstract ▼In some cases, it becomes necessary to establish a correspondence between the declared
and actual value of a categorical variable on the basis of a set of object characteristics. In this
case, there is a need for a classifier with an optimal sequence of the considered attributes with agiven value of the objective function. The target variable can be: yes, no, variety number, class
number, etc. This paper solves the problem of constructing a classification model in the form of an
optimal sequence of the considered attributes and their values included in the route from the root
vertex to the terminal vertex with a given value of the target variable. If a classifier is required
that includes the possibility of alternative answers, then first, independently from each other, optimal
routes are built for each value of the target variable, and then these routes are combined
("glued") into a single binary decision tree. In the algorithm for constructing a classifier based on
the method of crystallization of a placer of alternatives, each solution Qk is interpreted as an oriented
route Mk on a binary decision tree. Let us call the ordinal number of an element in the directed
route Mk the position siS={si|i=1,2,…,nA}. An element of the route Mk is the pair (xi, ui-),
where xi corresponds to Ai. ui- in the route Mk is an edge outgoing from xi and corresponds to the
value Ai chosen together with Ai. The second index of the element ui- is determined after the choice
of Ai, placed in the position sj+1 adjacent to sj. The work of the decision tree construction algorithm
is based on the use of collective evolutionary memory, which is understood as information
reflecting the history of the search for a solution. The algorithm takes into account the tendency to
use alternatives from the best solutions found. The peculiarities are the presence of an indirect
exchange of information – stigmerges. The totality of data on alternatives and their assessments
constitutes a scattering of alternatives. The key points of the analysis of alternatives in the process
of evolutionary collective adaptation are considered. Experimental studies have shown that the
developed algorithm finds solutions that are not inferior in quality, and sometimes surpass their
counterparts by an average of 3–4 %. The time complexity of the algorithm, obtained experimentally,
lies within O(n2)-O(n3). -
EVOLUTION ALGORITHM FOR PARTITION BY METHOD OF CRYSTALLIZATION OF ALTERNATIVES FIELD
B.K. Lebedev, O.B. Lebedev, Е. О. Lebedevа2020-07-20Abstract ▼The operation of the partitioning algorithm is based on the use of collective evolutionary
memory, which means information that reflects the history of the search for a solution and is
stored independently of individuals. The algorithm associated with evolutionary memory seeks to
memorize and reuse ways to achieve better results. The collective evolutionary memory of the
partitioning algorithm is a set of statistical indicators that reflect, for each implemented alternative,
the number θ of its occurrences in the best solutions at previous iterations of the algorithm
and the number δ indicating the usefulness of the implemented alternative when constructing solutions
at previous iterations of the algorithm. The team does not have centralized management, and
its features are the presence of indirect exchange of information. Indirect exchange consists in
performing certain actions, at different times, during which some parts of evolutionary memory
change by one agent. In the future, this changed information is used by other agents in these parts.
First, at each iteration, a constructive algorithm generates nk solutions Qk. Each solution Qk is a
mapping Fk=V→X, is represented as a bipartite subgraph Dk and is formed by sequentially assigning
elements to nodes. The formation of each solution Qk is performed by the set of agents A,
by means of the probabilistic choice by each agent ai of the node vj. The process of assigning an
element to a node involves two stages. In the first stage, agent ai is selected, and in the second
stage, the node. In this case, the restriction must be fulfilled: each agent of the set A corresponds
to one unique node of the set V. The estimate ξk of the solution Qk and the utility estimate δk of the
set of alternatives implemented by the agents in the solution Qk are calculated. At the second stage,
the agents increase the integral utility of the set of alternatives in the integral placer of alternatives
R* by the value δk. At the third stage, the utility estimates δk of the integral placer of alternatives are
reduced by μ. The paper uses the cyclic method of forming decisions. In this case, the building up of
estimates of the integral utility δk of the set of positions P is performed after the complete formation
of the set of solutions Q at iteration l. Experimental studies were carried out on the basis of formed
test cases with the optimal solution obtained earlier. The results obtained were compared with the
results obtained by other well-known algorithms for dividing circuits into parts. For comparison, a
set of standard benchmarks was formed. After analyzing the results, we can conclude that the proposed
method allows you to get 4–5 % better solutions than its analogues. -
EVOLUTIONARY POPULATION METHOD FOR SOLVING THE TRANSPORT PROBLEM
B.К. Lebedev, О.B. Lebedev, Е.О. Lebedevа2022-11-01Abstract ▼The paper considers an evolutionary population method for solving a transport problem
based on the metaheuristics of crystallization of a placer of alternatives. We study a closed (or
balanced) model of the transport problem: the amount of cargo from suppliers is equal to the total
amount of needs at destinations. The goal of optimization is to minimize the cost (achieving a minimum
of transportation costs) or distances and the criterion of time (a minimum of time is spent on
transportation). The metaheuristics of the crystallization of a placer of alternatives is based on a
strategy based on remembering and repeating past successes. The strategy emphasizes «collective
memory», which refers to any kind of information that reflects the past history of development and
is stored independently of individuals. An ordered sequence Dk of routes is considered as a code
for solving the transport problem. The objects are routes, the alternatives are the set of positions P
in the list, where np is the number of positions in the list Dk. The set of objects Dk corresponds to
the set of all routes. The set of alternative states P of the object corresponds to the set of alternative
options for placing the object in the list Dk. The operation of the population evolutionary algorithm
for the crystallization of a placer of alternatives is based on a collective evolutionary
memory called a placer of alternatives. A scattering of solution alternatives is a data structure
used as a collective evolutionary memory that carries information about the solution, including
information about the realized alternatives of agents in this solution and about the usefulness of
the solution. A constructive algorithm for the formation of a reference plan by decoding the list Dk
has been developed. At each step t, the problem of choosing the next route in the sequence Dk and
determining the amount of cargo transported from the point of departure Ai to the point of destination
Bj along this route is solved. The developed algorithm is population-based, implementing the
strategy of random directed search. Each agent is a code for some solution of the transport problem.
At the first stage of each iteration l, a constructive algorithm based on the integral placer of
alternatives generates nk decision codes Dk. The formation of each decision code Dk is performed
sequentially in steps by sequentially selecting an object and position. For the constructed solution
code Dk, the solution estimate ξk and the utility estimate δk are calculated. An individual scattering
of alternatives Rk is formed and a transition to the construction of the next solution code is formed.
At the second stage of the iteration, the integral placer of alternatives formed at previous iterations
from l to (l-1) is summed with all individual placers of alternatives formed at iteration l.
At the third stage of iteration l, all integral utility estimates r*
αβ of the integral placer of alternatives
R*(l) are reduced by δ*. The algorithm for solving the transport problem was implemented in
C++ in the Windows environment. Comparison of the values of the criterion, on test examples,
with a known optimum showed that in 90% of the examples the solution obtained was optimal, in
2% of the examples the solutions were 5% worse, and in 8% of the examples the solutions differed
by less than 2%. The time complexity of the algorithm, obtained experimentally, lies within O(n2). -
HYBRID METHOD OF ROUTE CONFIGURATION PLANNING ON A TERRAIN MAP UNDER CONDITIONS OF PARTIAL UNCERTAINTY
М. I. Beskhmelnov, B.К. Lebedev, О.B. Lebedev2025-04-27Abstract ▼The paper describes a hybrid algorithm for situational trajectory planning under partial uncertainty for a
two-dimensional space based on the integration of the wave and ant algorithms, which allows constructing trajectories
of minimum length in real time with simultaneous optimization of a number of other quality criteria for
the constructed path. The processes of forming a trajectory section and moving an object along it alternate at
each step. The trajectory is formed sequentially (step by step) at two levels of each step. The local visibility zone
and the region covered by it on the terrain map are formed and oriented relative to the current reference vector.
The first-level procedures sequentially form a chain of pairwise adjacent regions with localized obstacles on the
terrain map in steps. The second-level procedures form a set of trajectories for the passage of a moving object
through a region at a step. When the chain of regions merges, a terrain region is formed through which the trajectory
is laid. The entire trajectory is a set of individual trajectories for the passage of a moving object through
regions connecting its initial position with the target position. The search for a solution is carried out by a population
of agents on a solution search graph. The vertices of the set correspond to the cells of the region. Two
vertices are connected by an edge if the corresponding cells on the terrain model in the form of a discrete working
field are adjacent and the transition of the connection from one cell to another is possible. It should be noted
that the synthesis of the trajectory and the movement of a moving object under uncertainty is a complex task that
requires the integration of various sensor systems, data processing algorithms, path planning algorithms and
motion control systems. The constant development of technologies in the fields of artificial intelligence, machine
vision and robotics allows the creation of increasingly sophisticated autonomous navigation systems. However,
complete autonomy and guaranteed safety of a moving object under any conditions still remain complex tasks
for research. -
BIOINSPIRED SEARCH IN THE COMPLETE GRAPH OF A PERFECT MATCH OF MAXIMUM POWER
B. К. Lebedev, О.B. Lebedev, М. А. Ganzhur, М. I. Beskhmelnov2025-01-30Abstract ▼A reconfigurable architecture of a hybrid multi-agent decision-making system based on swarm algorithm
paradigms has been developed. The reconfigurable architecture allows implementing the following
hybridization methods by tuning: high-level and low-level hybridization by nesting, preprocessor/
postprocessor type, co-algorithmic based on one or several types of algorithms. A methodology for
synthesizing a perfect matching of minimum weight in a complete graph based on the basic principles of
hybridization of search. evolutionary procedures has been proposed. In this paper, the swarm agents are
transforming chromosomes, which are the genotypes of the solution. An ordered list of the set of graph
vertices is used as the solution code. A structure of an ordered matching code has been developed, the
main advantage of which is that one solution (matching) corresponds to one code and vice versa. The
properties of the ordered code have been determined and encoding and decoding algorithms have been
developed. The hybrid system operation starts with the random generation by a swarm of bees of an arbitrary
set of solutions differing from each other in the form of an initial set of chromosomes. The key operation
of the bee algorithm is the study of promising solutions and their neighborhoods in the search space.
A method for forming neighborhoods of solutions with an adjustable degree of similarity and closeness
between them has been developed. At subsequent stages of the multi-agent system operation, solutions are
searched for by procedures built on the basis of hybridization of the swarm and ant algorithms. A distinctive
feature of hybridization is the preservation of the autonomy of the hybridized algorithms. Note that a
single data structure is used to represent solutions in the algorithms, which simplifies the docking of the
developed procedures. An approach to constructing a modified paradigm of a swarm of transforming
chromosomes is proposed. The search for solutions is performed in an affine space. In the process of
searching, permanent transformations (transitions) of chromosomes into states with the best value of the
objective function of the solution (gradient strategy) are carried out. The process of finding solutions is
iterative. At each iteration, the chromosomes are transformed (transitioned) into states with better values
of the objective function of the solution. The purpose of transforming a chromosome that tends to be the
best chromosome into a new state is to minimize the degree of difference by changing the mutual arrangement
of elements in an ordered list, which corresponds to an increase in the weight of the affine
connection. The chromosomes updated after the transformation are, in turn, the base points in subsequent
transformations. As a result of the experiments, it was found that the quality indicators of the developed
algorithms have higher values than in the works presented in the literature. -
DECENTRALIZED CONTROL OF A GROUP OF AUTONOMOUS MOBILE OBJECTS WHEN FORMING A TRAJECTORY OF MOVEMENT
B.К. Lebedev, О.B. Lebedev, М. I. Beskhmelnov2025-01-14Abstract ▼The article considers algorithms for generating unmanned aerial vehicles motion trajectories during
search and rescue and liquidation operations. The methods and algorithms for controlling the motion of a
unmanned aerial vehicles group in formation, when deployed in a line, when deployed in a rank, when
turning, in a column are described. Control is carried out using alternative collective adaptation algorithms
based on the ideas of collective behavior. The operating principles of one adaptation machine are
considered. The purpose of controlling slave robots is to minimize deviations. To implement the adaptation
mechanism, the parameters of the vector are matched with adaptation machines that model the behavior
of adaptation objects in the environment. A structure has been developed for the process of alternative
collective adaptation of parameters that control the motion of a group of unmanned aerial vehicles in
formation. Original rules for controlling parameters have been developed that have a number of advantages
over other methods: complete decentralization of control in combination with dynamic correction
of robot parameters that set the position and orientation of the robot in an absolute coordinate system,
and the linear velocity of the robot, respectively. A structure of a maneuver performed by a robot to correct
parameter deviations is proposed. Control is performed using an alternative collective adaptation algorithm
based on the ideas of collective behavior of adaptation objects, which allows for efficient processing
of emergency situations, such as agent failure, changes in the number of agents due to failure or sudden
acquisition of communication with the next agent, as well as in conditions of measurement errors and
noise that satisfy certain restrictions. -
BIO-INSPIRED DENSE PACKING ALGORITHM TO INCREASE THE EFFICIENCY OF SEMI-LIMITED STRIP CUTTING
B. К. Lebedev, О.B. Lebedev, М.А. Ganzhur2024-10-08Abstract ▼A methodology has been developed for finding solutions to the semi-infinite strip packing problem
based on models of adaptive behavior of biological systems. To reduce the overall labor intensity of the
search procedure, an approach based on decomposition of the problem being solved is proposed.
The packaging is designed for cutting by guillotine cutting of the tape into containers and non-guillotine
cutting of containers into elements. Packaging is carried out by sequentially filling the strip with containers.
The problem of packing rectangles into strips is solved in three stages. At the first stage, the agent
solves the problem of distributing a set A of rectangular-shaped elements in a set of blocks B. The problem
of forming a set of blocks B, including sets of rectangular-shaped elements A, is solved by an algorithm for
one-dimensional packing of elements into identical blocks. At the second stage, the problem of distributing
blocks among containers is solved. All containers have the same width D, equal to the width of the strip.
Each container holds two blocks. The process of distributing blocks into containers is accompanied by a
compaction procedure for each pair of blocks assigned to one container. The purpose of compaction is to
minimize the total area of the container by densely placing the blocks. Compaction is carried out sequentially
in all containers. The problem of distributing blocks into containers is reduced to the problem of
finding the maximum matching of the minimum cost. In contrast to the canonical paradigm of the ant algorithm,
when working as an agent, a clique is built on the solution search graph, on the edges of which a
pheromone is deposited. A technique has been developed for the formation of pheromone points and data
structures of collective evolutionary memory. To conduct objective experiments, well-known test problems
presented in the literature and on the Internet were used. Compared to existing algorithms, a 3-5% improvement
in results was achieved. The time complexity of the algorithm, obtained experimentally, practically
coincides with theoretical studies and for the considered test problems is ≈ О(n2). -
MULTI-STAGE ANT ALGORITHM OF ONE-DIMENSIONAL PACKING BASED ON EFFICIENT DECISION ENCODING METHODS AND TWO-LEVEL EVOLUTIONARY MEMORY
М.А. Ganzhur , B.К. Lebedev , О.B. Lebedev21-372025-10-01Abstract ▼The aim of the work is to develop and study bioinspired search methods for solving problems of one-dimensional packaging in identical containers based on effective algorithms for encoding and decoding solutions, composite criteria and a two-level structure of evolutionary memory. The paper proposes the structure of an ordered code for packing one-dimensional elements into identical containers, the main advantage of which is that one packaging solution corresponds to one code and vice versa. The search procedure is based on the modified metaheuristics of the ant algorithm. At each iteration, the one-dimensional packing algorithm has a multistep structure. The stages are performed sequentially one after the other, starting from the first one. Each stage of the Сk includes procedures performed by the zk agent. The number of stages is equal to the number of agents in the population plus the final iteration stage.
The main task solved by the constructive algorithm at the Сk stage is to construct the Rk code for packing a set of X elements into identical containers. The stage is divided into periods according to the number of lists Xjk generated by the agent zk. The period is divided into stages. In each period, the following tasks are solved sequentially in stages: agent zk constructively generates a set Rk of ordered lists Xjk of onedimensional packaging in identical containers; fjk estimates of the packaging of each container Oj by elements of the list <Xjk> are calculated; the amount of λjk pheromone proportional to the fjk estimate is calculated; the estimate Wk=∑i(fjk) is calculated one-dimensional packing of a set of elements X into H identical containers; pheromone is deposited on the edges of graph G corresponding to the list Xjk in the cells of the accumulative memory matrix E of the second level. After all agents of the zk population Z have formed ordered lists of Rk, the accumulated pheromone is added to the main memory matrix Φ of the first level. For each Rk, the total Fk indicator of the packaging quality of the set of X elements is calculated. The final operation in the iteration is pheromone evaporation on the edges of graph G and fixation of zk with the best Fk. Experimental studies have been conducted to determine the quality of the method's operation on large-dimensional test sets. To compare the developed algorithm with known methods and approximate algorithms, the authors selected several groups of benchmarks from various sources -
METHODS OF DATA COLLECTION BY UAVS WHEN MONITORING HARD-TO-REACH TERRAIN
B.К. Lebedev , О. B. Lebedev2026-04-29Abstract ▼This paper proposes a methodology and method for constructing a model of the study area as a finite set of zones (sections) covering it, characterized by the fact that all sections are rectangular. The paper examines methods for forming a minimal set of sections on a large field that completely cover the accessible territory surveyed by unmanned aerial vehicle (UAV) sensors. The size, orientation, and relative positions of the sections are aimed at minimizing their survey time. In general, a route M is a sequential set of linear segments. Route M is divided into segments using a set of control points P. A methodology and algorithm for constructing an optimal UAV route based on the ant colony method have been developed. Mechanisms for controlling the UAV's movements along the route have been developed. In general, a route M is a sequential set of linear segments. A segment of the UAV's path (trajectory) over a surveyed area of territory being scanned (explored) is called a working segment, while a segment of the UAV's path (trajectory) over a non-scanned (explored) area is called a dummy segment. Generally, a route is an alternating sequence of working and dummy segments, replacing each other. A methodology and algorithm for moving an UAV between reference points of a segment corresponding to reference points have been developed. Two algorithms represent the solution search procedure: Algorithm 1, which describes the behavior of an ant colony; Algorithm 2, which describes the behavior of an agent. An adaptation unit supports the process of moving an UAV along a route in real-world conditions. The adaptation unit's task is to control the UAV's movement along a reference line along the route. The control method involves replanning the motion parameters of an unmanned aerial vehicle (UAV) moving parallel to a reference vector at each moment during flight. Adaptation of the UAV consists of adapting the control parameter values. A structure of maneuvers performed by UAVs to correct parameter deviations is proposed. The adaptation task consists of generating a sequence of adaptive actions in the adaptation machine that extremize the quality indicators of the resulting solutions (adaptation criteria). The adaptation object is a set of continuous flight control parameters: the UAV's deviation from the reference line; the angle between the UAV's motion vector and the reference line of the current segment; and the UAV's flight altitude above the current segment. Adaptation of the UAV consists of adapting the control parameter values
-
SEMI-INFINITE STRIP PACKAGING BASED ON DECOMPOSITION AND HYBRIDIZATION OF BIOINSPIRED METHODS
B. К. Lebedev, О.B. Lebedev, М. А. Ganzhur2023-10-23Abstract ▼In this work, the object of study is the problem of rectangular packing in a semi-infinite
strip. Given a set of rectangles. Given one large object (called a strip), whose width D is given,
and whose height HP is the desired value of the variable. The goal is to minimize the HP height of
a strip containing rectangles placed in the strip without overlapping each other. To solve the
packaging problem, a new hybrid approach is proposed based on the decomposition of the general
packaging problem and hybridization of bioinspired methods, as well as a new hybrid approach to
the decomposition of the general packaging problem. New architecture and methods for solving
the packing problem have been developed, built on the basis of decomposition and hybridization of
swarm methods developed by the authors, using various search strategies, operating in parallel and sequentially and implementing a wider overview of the solution space, which allows for a
higher probability of localizing a global extremum in an acceptable time. A methodology has been
developed for a new direction in searching for solutions to orthogonal packing problems based on
models of adaptive behavior of biological systems. A highly effective hybrid bioinspired method
for solving one-dimensional and rectangular packaging problems has been developed, based on
the decomposition of the problem into many subtasks and the integration of search optimization
methods. New mechanisms for solving the packaging problem are proposed, using mathematical
methods that incorporate the principles of natural decision-making mechanisms. In contrast to the
canonical paradigm of the ant algorithm, the agent forms a partition of the set of rectangular elements
A into subsets Aki on the solution search graph as a solution, where Akj is a subset of elements
assigned by the agent to the block. Search methods have been developed for solving problems
of guillotine and non-guillotine rectangular cutting. To conduct objective experiments, wellknown
test tasks presented in the literature and the Internet were used. Better results were obtained
compared to the tested methods. The theoretical principles proposed in the work for solving
problems of packaging and cutting industrial objects in single production conditions are implemented
in the form of methods, algorithms and application software. Compared to existing algorithms,
a 3-5% improvement in results was achieved. The time complexity of the algorithm, obtained
experimentally, practically coincides with theoretical studies and for the considered test
problems is О(n2). -
OPTIMIZATION BASED ON COMBINING MODELS OF ADAPTIVE BEHAVIOR OF A SWARM OF AGENTS
B.К. Lebedev, О. B. Lebedev, М. А. Ganzhur2023-06-07Abstract ▼A bionic search architecture has been developed to solve the problem of placing VLSI elements
based on the hybridization of the algorithms of a bee colony and a swarm of chromosomes,
which allows you to get out of "local holes" and increases the convergence of the placement algorithm. The initial iterations are implemented by the bee algorithm to provide a broad overview of
the search area, and the final iterations are implemented by the chromosome swarm algorithm,
which ensures the exact localization of the extremum found by the bee algorithm. Agents are represented
as a population of chromosomes, which are genotypes for solving the placement problem.
The paper describes a modified paradigm of a swarm of chromosomes, which, in contrast to the
canonical method, provides the possibility of searching for solutions in the affine space of positions
with integer values of the parameters. In the search population method of optimization by a
swarm of chromosomes, the agents of the population are chromosomes. The chromosome is the
genotype of the optimization object. The essence of the search procedure is the successive change
of the states of the object of optimization (chromosome) by the directed mutation operator and the
search for the optimal state. An affine-relaxation model (ARM) of a swarm of chromosomes is
proposed - this is a graph whose vertices correspond to chromosomes, and arcs correspond to
affine bonds between them. The transition of the chromosome to a new state is carried out using a
relaxation procedure. In the work, the directed mutation operator acts as a means of changing the
solution, the essence of which is to change the integer values of genes in the chromosome. The
purpose of the transition is to reduce the weight of the affine bond between chromosomes. The
mechanisms of the directed mutation operator are described. A modified structure of the bee algorithm
is proposed. For each base chromosome, a probabilistic choice of a set of chromosomes
located in the vicinity of the base chromosome is implemented. It is possible to improve the quality
of the developed algorithm by adjusting the values of the control parameters. The time complexity
of the algorithm for fixed values of the population size and the number of generations is O(n). In
general, the dependence of the running time of the hybrid algorithm is O(n2) – O(n3). -
CO-EVOLUTIONARY PLACEMENT ALGORITHM BASED ON INTERACTION SUBPOPULATIONS DIFFERING IN SEARCH STRATEGIES
O.B. Lebedev, А.А. Zhiglatiy2023-02-17Abstract ▼A new methodology and method for placing VLSI elements has been developed, which differ
in that the solution of the placement problem is based on the use of a fixed order of position selection,
focused on the effective solution of the placement problem, and a heuristic procedure for
distributing elements by positions, which reduces the overall complexity and improves the quality
of the solution. The process of forming a list of positions on the switching field is carried out using
the mechanisms of the wave algorithm. The choice of the final list is based on the principle of constructing
a route with a minimum estimate of the total linear length of distances between route
positions. To solve the placement problem, a search algorithm based on the modified ant colony
method has been developed. To exclude premature convergence and localization of the global
extremum of the problem, the development of the algorithm was carried out on the basis of the coevolutionary
approach. The architecture of the co-evolutionary placement algorithm is developed
on the basis of the ant colony algorithm paradigm. In the search space, sub-populations implement
four optimization strategies in parallel. In the work, the coevolution process is implemented on the
basis of the interaction of subpopulations that differ in search strategies. A distinctive feature of
the co-evolutionary approach used is that subpopulations of solutions are actually virtual. The
process of co-evolution is implemented by one population of agents Z by sequential formation and
merging of virtual subpopulations of solutions into one population. In this paper, the solution of
the placement problem is aimed at improving traceability by minimizing the resources required to
implement connections. A significant contribution to minimizing the spatial and temporal complexity
of the search procedure was made by: the use by virtual sub-populations of a common evolutionary
memory, a common solution search graph, the formation of a single interpretation of the
solution in the form of a route on a complete directed graph with binary directed edges. Testing
was carried out on benchmarks 19s, PrimGA1, PrimGA2. The results compared to existing algorithms
are improved by 7-8%. The probability of obtaining a global optimum was 0.96. On average,
solutions differ from the optimal by less than 1.5%. The time complexity of the algorithm for
fixed values of the population size and the number of generations is O(n). The total time complexity
of the hybrid algorithm is O(n2)−O(n3). -
CONTROLLING THE MOVEMENT OF A GROUP OF UAVS IN COMPLIANCE WITH THE GEOMETRIC STRUCTURE OF THE FORMATION BASED ON ALTERNATIVE COLLECTIVE ADAPTATION
D.V. Kotov, О.B. Lebedev2024-04-15Abstract ▼The main way to solve problems of planning and traffic control is the use of intelligent technologies.
At the same time, intelligent technologies are used to solve the problems of setting and adjusting
control goals and action programs to implement these goals, as well as to form a control
algorithm under conditions of uncertainty caused by various factors in actuators, the motion control
subsystem, and the planning and behavior subsystem. This work is devoted to the actual problem of
mathematical modeling and control theory: the problem of decentralized control of a multi-agent
system consisting of agents modeling the behavior of autonomous robots in order to ensure the movement of a group of robots deployed in a line and in a «convoy» type formation. The paper examines
the results of research in the field of controlling a group of unmanned aerial vehicles, identifies
the types of tasks that can be performed by a group of aerial robots, and highlights the main control
strategies and their features. The general positions necessary for the development of a detailed group
control algorithm have been formed. Each robot must navigate in space autonomously without GPS
using signals from its own camera or lidar (active rangefinder), identify obstacles, build optimal
paths of movement and make decisions aimed at achieving the goal and completing the task. Management
is carried out using an alternative collective adaptation algorithm, based on the ideas of
collective behavior of adaptation objects. To implement the adaptation mechanism, the vector parameters
are matched with adaptation automata that model the behavior of adaptation objects in the
environment. A structure for the process of alternative collective adaptation has been developed,
under the control of which a group of robots moves in formation -
THE PROCEDURE FOR CALCULATING THE DRIVE OF THE WORKING BODY OF A ROBOTIC DEVICE FOR HUMANITARIAN DEMINING
S.S. Noskov, А.Y. Barannik, А.А. Lebedev, A.V. Lagutina2024-08-12Abstract ▼The aim of the study is to develop a methodology that allows us to calculate the main parameters
characterizing the ability of a robotic vehicle equipped with a striker minesweeper to perform humanitarian
demining operations. For this purpose, within the framework of this work, tasks were solved such as
calculating the torque on the shaft of the striker trawl, determining the power of the motor driving the
striker trawl, and calculating the power of the power plant of a robotic vehicle. During the research, the
experience of creating and the main parameters of foreign mine clearance equipment with firing minesweepers
were analyzed – the Hydrema 910 MCV crew mine clearance vehicle, the MV-4 robotic mine
clearance vehicle, the Uran-6 remote-controlled mine clearance vehicle, and the MT-2 remote-controlled
mine trawl. The main features of the working body of the considered machines, namely the firing minesweeper,
were also analyzed. The developed methodology is based on a method for calculating the resistance
force of soil destruction and an explosive object when exposed to a bike, based on the theory of
interaction of working bodies of earthmoving machines, developed by academician N.G. Dombrovsky.
Also, during the development of this technique, the results of work on the calculation of the design of the
striker trawl were used by Croatian specialists Vinkovic N., Stojkovic V. and Mikulic D. At the same time,
calculations were carried out for various soils, which, depending on the resistivity of cutting, are divided
into 4 categories: sandy clay, gravel; dense clay, coal; hard clay with gravel; medium slate, chalk, soft
gypsum stone. The obtained data actually became an array of initial information, which, together with
known physical dependencies, allowed us to form an array of calculation formulas that allow us to calculate
the torque on the shaft of the striker trawl, the power of the motor driving the striker trawl, as well as
the power of the power plant of the robotic means, and thereby solve the scientific problem posed at the
beginning of the study. -
BIOINSPIRED ALGORITHM FOR SOLVING INVARIANT GRAPH PROBLEMS
О.B. Lebedev, А.А. Zhiglatiy2022-11-01Abstract ▼A bioinspired method for solving a set of invariant combinatorial-logical problems on
graphs is proposed: the formation of a graph matching, the selection of an internally stable set of
vertices, and the selection of a graph clique. A modified paradigm of the ant colony is described,
which uses, in contrast to the canonical method, the mechanisms for generating solutions on the
search space model in the form of a star graph. The problem of forming an internally stable set of
vertices in a graph can be formulated as a partitioning problem. At the initial stage, the same
(small) amount of pheromone ξ/m, where m=|E|, is deposited on all edges of the star graph H.
The process of finding solutions is iterative. Each iteration l includes three stages. Agents have
memory. At each step t, the memory of the agent ak contains the amount of pheromone фj(t) deposited
on each edge of the graph H. At the first stage, each agent ak of the population uses a constructive
algorithm to find the solution Ur 0k, calculates the estimate of the solution ξk(Ur
0k) and the value of the degree of suitability of the solution obtained by the agent φk (the amount of pheromone corresponding to the estimate). At the second stage, after the complete formation of solutions
by all agents at the current iteration, the pheromone ωj accumulated in the j-th cell in the
CEPб buffer array is added to each j-th cell of the main array Q2={qj|j=1,2,…,m} of the CEP0
collective evolutionary memory. At the third stage, the general evaporation of the pheromone occurs
on the set of edges E of the star graph H. The time complexity of the algorithm, obtained experimentally,
coincides with theoretical studies and for the considered test problems is O(n2). -
UAV GROUP MANAGEMENT WHEN WORKING OUT OF CRISIS FLIGHT SITUATIONS IN SOLVING TRANSPORT PROBLEMS
А.I. Savelyev, V.V. Lebedeva, I.V. Lebedev, К.V. Kamynin, L.D. Kuznetsov, А.L. Ronzhin2022-04-21Abstract ▼The relevance of the development of algorithms for managing a group of UAVs in the event of
crisis situations that affect the performance of the task is substantiated. An algorithm for autonomous
collective (decentralized) control of a group of UAVs is described when performing the target task of
transporting goods, as well as combined control in the event of crisis situations when the autonomouscontrol mode cannot be fully implemented. The algorithm for working out a crisis situation in case of a
lack of energy resources on board the UAV and the return of group agents to the starting position is
described in detail. The results of modeling the movement of a group of UAVs of multirotor and aircraft
types and working out a crisis situation for managing a group of UAVs based on information about the
reserves of energy or fuel resources are presented. During the experiment, iteratively calculated the
remaining fuel when the UAV moved to the landing point, as well as the amount of fuel available to the
UAV at a given time. As a result of the experiments, it was found that the time for calculating the balance
of the energy resource does not exceed 6.792 ms. If the leader runs out of fuel, the cargo transportation
mission ends ahead of schedule, since it cannot be completed without the participation of the
leader. If several slaves fail, the mission can be continued if their number does not exceed a predetermined
value, which is critical for the continuation of the cargo delivery mission. The results of experimental
studies on modeling the flight of an UAV with a load are presented, during which a flight route
was built that simulates a curvilinear trajectory of movement in urban conditions from the starting point
to the end point, where the UAV is landing and transferring the cargo. In the experiments, the developed
UAV and the onboard fastening system of the thermal container were used. During flight tests, the average
horizontal speed of the UAV was set to 10 m/s. The length of the flight was 5350 m. The flight time
was 13 minutes. 51 seconds. -
DEVELOPMENT OF MODIFIED METHODS AND MODELS OF SEARCH ADAPTATION FOR SOLVING THE PROBLEM OF PLANNING VLSI
O.B. Lebedev, А.А. Zhiglatiy, Е.О. Lebedevа2021-12-24Abstract ▼In this work, to solve the VLSI planning problem, a search algorithm has been developed
based on a modified ant colony method. The task of forming a VLSI plan is reduced to the task of
forming the corresponding Polish expression. The developed method for the synthesis of the Polish
expression includes the construction of a tree of cuts, the choice of the types of cuts (H or V), identification
and orientation of modules. The evolving population is split into pairs of agents. Each
member of the population is a pair of agents working together. In this case, the constructive algorithms
A1 and A2 used by the agents of the pair are different. The problem solved by Algorithm A1
is formulated as the problem of finding a one-to-one mapping Fk=M*→P of the set of modules M
with selected orientations, |M*|=|M| to the set P of positions of the template Sh. In fact, the solution
consists in choosing on the graph G1 a subset of edges E*1E1 included in the corresponding
mapping Fk. In Algorithm A2, the graph G2=(X, E2) is developed as a model of the search space
for solutions for choosing the type, sequence and location of cuts in the pattern Sh.
X={(x1i,x2i)|i=1,2,…,n} the set of vertices of the graph G2, corresponds to the set P of potential
positions of the template Sh for the possible placement of the names of the cut symbols in them.
Each potential position piP of the template Sh is modeled by two alternative vertices (x1i,x2i).
The choice of the vertex x1i when placing the cuts indicates that a cut of type V is placed in position
pi, the choice of vertex x2i indicates that a cut of type H is placed in position pi. Each iteration
l of the general algorithm includes an initial and three main stages. The initial stage is as follows.
Co-evolutionary memory matrices are nullified CEM*1 and CEM*2 are reset to zero. At the first
stage, each pair of agents dk=(a1k,a2k): – with constructive algorithms A1 and A2 he synthesizes
his solution Wk=(E1k
*,Sk); – the Polish expression Shk is formed, corresponding to the solution Wk;
– on the basis of Shk, a tree of sections Tk is formed; – on the basis of Tk, the plan Rk is formed and
the estimate of the solution Fk is calculated; – agents deposit (add) the pheromone to the cells of
the collective evolutionary memory (CEM) matrices CEM*1 and CEM*2 corresponding to the
solution edges Wk=(E1k
*,Sk) in the solution search graphs G1 and G2 in an amount proportional
to the solution estimate Fk. At the second stage, the pheromone accumulated in CEM*1 and
CEM*2 by agents of the population at iteration l is added to CEM 1 and CEM2. At the third stage,the pheromone is evaporated on the edges of the graphs G1 and G2. Tests have confirmed the
effectiveness of the proposed method. The time complexity of the algorithm, obtained experimentally,
coincides with theoretical studies and it is O(n2) for the considered test problems. -
APPLICATION OF COMPUTER VISION TECHNOLOGIES IN VISUAL INFORMATION PROCESSING SYSTEMS
О.B. Lebedev , R.I. Cherkasov254-2762025-11-10Abstract ▼This paper considers the application of artificial intelligence technologies, in particular computer vision, in visual information processing systems. A comprehensive analysis of neural network approaches to solving computer vision problems is carried out, including systematization of key types of problems: image classification, object detection and semantic segmentation. The architectural principles of convolutional neural networks are studied in detail with an emphasis on the mechanisms of spatial feature extraction through convolutional layers, optimization of data representation through pooling operations and feature transformation in fully connected layers. Particular attention is paid to the evolution of object detection methods, where the problem of model selection is considered as an extension of classification due to the integration of spatial coordinate regression, and an assessment of the effectiveness of detectors is carried out based on the IoU, Precision, Recall and F1-score metrics, demonstrating a fundamental trade-off between localization accuracy and processing speed. The YOLOv7 algorithm is presented as an optimal solution for real-time systems. Its architecture is based on splitting the input image into a grid of S×S cells with direct prediction of the bounding box parameters (center coordinates, width, height) and class probabilities for each cell, as well as the use of specialized layers (SPP, PANet) for multi-scale feature aggregation. The structure of the neural network confirms the effectiveness of the approach used, which ensures high performance without critically reducing accuracy in strategically important applications of video surveillance, autonomous systems, and augmented reality. A comparative study of one-stage and two-stage detectors was conducted with an assessment of their performance by key metrics. Particular attention is paid to the practical aspects of using computer vision technologies in real visual information processing systems.
-
JUSTIFICATION OF A COMPLEX OF HUMANITARIAN DEMINING MEASURES. METHODOLOGICAL VIEWS
А.Y. Barannik , А.V. Lagutina , А. А. Lebedev2026-04-29Abstract ▼The need to conduct explosive ordnance clearance operations in liberated territories has necessitated a significant expansion of humanitarian demining capabilities. Particular attention is being paid to increasing the number of highly effective robotic systems capable of searching for and destroying various types of explosive ordnance. The relevance of this study is determined by the fact that the Russian Federation is currently actively developing and producing robotic systems capable of solving these tasks with varying degrees of effectiveness. In many cases, these products are manufactured by companies lacking the necessary experience and, consequently, often failing to deliver the required quality of work. At the same time, the increasing demand for these resources and the increasing funding for their production has made it increasingly important to economically justify both their development and production strategies and the technologies for their application. Based on this, studies were conducted to develop an approach to optimize the allocation of financial resources when planning explosive ordnance clearance activities, identifying the most effective areas for mine clearance development, and improving the organizational structure of units equipped with the appropriate robotic equipment. This approach was based on an assessment of the likelihood of completing explosive ordnance clearance tasks with the assigned forces and resources, as well as an assessment of the costs of performing work included in a set of humanitarian demining activities using robotic equipment. The practical significance of the study lies in the fact that the obtained results will help identify the most cost-effective development directions for robotic humanitarian demining systems and prepare proposals for improving the organizational structure of units that will be equipped with these systems.
1 - 20 of 20 items
