Эволюционный алгоритм проектирования комбинационных логических схем

В статье рассмотрена одна из важных задач конструкторского проектирования – задача синтеза комбинационных логических схем. Она относится к классу NP-сложных и трудных задач. В работе описана постановка задачи, предложен эволюционный подход ее решения. Описаны задачи анализа и синтеза при проектировании комбинационных логических схем. Разработан эволюционный алгоритм на основе моделирования эволюции Гуго де Фриза, позволяющий получать наборы квазиоптимальных решений за полиномиальное время. Реализована программная среда на языке С# и проведен вычислительный эксперимент. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов проектирования комбинационных логических схем и их поведение. В лучшем случае временная сложность алгоритмов $\approx O(n\log n)$, в худшем случае — $O(n^2)$.