| Popis: |
A hybrid algorithm is proposed for locating basic standard library elements in the design of topology of a semi-custom VLSI using the one-dimensional packaging method based on the integration of swarm and genetic algorithms. In the work, as a solution interpretation - a data structure that carries information about packaging (placement), a sequence of elements (priority list) is used, which determines the order of their packaging. As a decoder, the standard packaging procedure (SPP) is used. The interpretation of the placement problem, which is generated by the swarmand genetic algorithms, is an ordered list that includes all cells, with its division into parts. Each part includes vertices corresponding to elements placed in a ruler (block). The number of parts serves as an estimate of the solution. The interpretation of the solution generated by the algorithms is the chromosome, whose structure is identical to the list structure. The list is divided into parts as a result of decoding. We describe the search procedures in the decision space, the mechanisms of behavior of the modernized swarm of particles and genetic search. In contrast to the canonical paradigm of the swarm algorithm, an approach to constructing a modified particle swarm paradigm is proposed, which makes it possible to simultaneously use chromosomes with discrete integer parameter values in a genetic algorithm and in a particle swarm algorithm. The operator of a directed mutation (ОDМ), the essence of which consists in changing the integer values of genes in the chromosome, acts as an analogue of speed when moving. In contrast to the canonical paradigm of the swarm algorithm, an approach to constructing a modified particle swarm paradigm is proposed, which makes it possible to simultaneously use chromosomes with discrete integer parameter values in a genetic algorithm and in a particle swarm algorithm. As an analogue of speed when moving particles, there is a directed mutation operator (ОDМ), the essence of which is to change the integer values of genes in the chromosome. This reduced the combinatorial complexity of the problem. This reduced the combinatorial complexity of the problem. For the experiments were used well-known test problems presented in the library of OR-objects - (ORLibrary Beasley). The temporal complexity of the algorithm, obtained experimentally, coincides with theoretical studies and for the considered test problems it is O (n2)-O (n3). The developed algorithm allowed us to obtain optimal solutions for all tasks of the set. |
