Evolutionary algorithm for designing combinational logic circuits

The article describes one of the most important tasks of the design engineering task of synthesis of combinational logic circuits. It belongs to a class of NP-complex and difficult tasks. This paper describes the formulation of the problem. We propose an evolutionary approach for solving this problem. The article describes the tasks of analysis and synthesis in the design of combinational logic circuits. We have developed an evolutionary algorithm based on the modeling of the evolution of Hugo de Frieze, allowing a set of quasi-optimal solutions in polynomial time. Implemented software environment for the C# language and a computational experiment and conducted a series of tests and experiments have refined theoretical estimates of the time complexity of algorithms for designing combinational logic circuits and their behavior. In the best case time complexity of algorithms $\approx O(n\log n)$, in the worst case — $O (n^2)$.