For authors
Search
Search Results
##search.searchResults.foundPlural##
-
SOLUTIONS’ ENCODING IN EVOLUTIONARY METHODS FOR INSTRUMENTAL DESIGN PLATFORM
E.V. Kuliev, А. А. Lezhebokov, М. М. Semenova, V.A. Semenov2020-07-20Abstract ▼The article considers current issues and analyzes the problems of three-dimensional integration
and three-dimensional modeling that arise at the design stage during the solution of the
problem of optimal planning of components of large and extra-large integrated circuits and case
devices of electronic computing equipment. The main advantages of applying the principles of
three-dimensional integration are presented and described in sufficient detail, which allow efficiently
organizing the production of personalized electronics, optimally planning the configuration
of large and ultra-large integrated circuits, taking into account thermal and energy characteristics.
In the course of research, the authors developed an approach to encoding decisions based on
an intelligent mechanism, which is characterized by the presence of built-in means of control of
acceptable decisions. One of such tools that have experimentally proven their effectiveness is the
built-in mechanism of “deadly mutations”, which takes into account the status of genes and predetermined
restrictions on the final configuration of the housing of the designed device. A series of
general approaches and specific algorithms for solving the planning problem based on the results
of research by the author's team and modern approaches to solving NP-complete problems are
proposed. The most important practically significant result of the research of the indicated problem
is the developed software and instrumental design platform in the modern cross-platform Java
programming language. The selected development technology allows you to use all the main advantages
of modern multi-core and multi-processor architectures, to use software multi-threading
to implement parallel schemes for solving combinatorial problems. The software and tool platform
has a user-friendly interface, which allows you to effectively manage the process of solving the
problem of planning the components of large and ultra-large integrated circuits of threedimensional
integration by visualizing key performance indicators of algorithms on graphs and in
text statistics blocks. The developed application software made it possible to carry out a series of
computational experiments based on random data sets, as well as on open-data boron benchmarks
for such tasks. The results of experimental studies have confirmed the theoretical estimates of the
time complexity and effectiveness of the proposed approaches and algorithms, including the genetic
algorithm, which uses the new decision coding mechanism proposed in the work. -
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. -
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) -
DEVELOPMENT OF BIOHEURISTICS FOR CREATING AN INTELLECTUAL SUBSYSTEM FOR MAKING EFFECTIVE DECISIONS OF NP-HARD AND NP-DIFFICULT COMBINATORY-LOGICAL PROBLEMS ON GRAPHS
D. V. Zaruba , E. V. Kuliev , D.Y. Zaporozhets , M. M. Semenova2021-11-14Abstract ▼The article is devoted to the solution of new topical problems that have arisen in the conditions
of the modern development of information and nanometer technologies in the field of design,
as well as the development of new innovative methods that provide effective solutions in polynomial
time. The article deals with the problem of solving NP-hard problems. The description of the
procedure for measuring the complexity of the problem is presented the features of NP-hard and
NP-difficult combinatorial logic problems are described. The main differences between the tasks
are presented, as well as the problems that one has to face when solving this type of task. The general
decision-making scheme is presented, consisting of the problem formulation; decisionmaking;
signal in automatic systems and feedback. At the second stage (formation and selection of
solutions), the solution is based on a bioinspired algorithm for finding solutions to the traveling
salesman problem. To solve this problem, a modified bioinspired algorithm based on the behaviorof an ant colony was developed. Unlike other optimization methods, metaheuristic algorithms can
find global optimal solutions for problems where there are many local solutions due to their random
nature. These reasons have led to the widespread use of such algorithms in solving various
optimization problems. Bioinspired algorithms are becoming a new revolution in the field of solving
optimization problems. The statement of the traveling salesman problem is presented, as well
as the solution of the problem on the basis of the ant algorithm. Algorithms such as genetic algorithms
and PSO can be very useful, but they still have some disadvantages in solving multimodal
optimization problems. These algorithms can find optimal solutions regardless of the physical
nature of the problem. In the framework of experimental studies, the analysis of the work of
bioinspired algorithms was carried out: the algorithm of a flock of bats, the bacterial algorithm
and the ant algorithm. -
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.
1 - 5 of 5 items
