Генетические процедуры синтеза структур

Развитие систем автоматизированного проектирования на современном этапе тесно связано с понятием генетического алгоритма как средства поиска схемотехнических решений.

Впервые такой подход был предложен Е.Л. Глориозовым для синтеза структур цифровых схем. Накопление опыта решения практических задач позволило сформулировать генетическую концепцию поиска новых схемотехнических решений.

В качестве главной проблемы синтеза здесь выступает возрастание дерева возможных решений и исследования методов усечения дерева решений с целью придания поиску узконаправленного характера. Процесс поиска нового технического решения можно рассматривать как некоторый эволюционный процесс, в котором есть механизм сохранения наследственности, механизмы мутации и естественного отбора. В процессе синтеза механизм сохранения наследственности реализуется существованием начального состояния Ф₀ некоторой обобщенной структуры. Механизм мутации этой структуры реализуется с помощью правил или списка возможных структурных изменений. Конкретная реализация этих правил или списка представляет собой множество операторов, преобразующих одно состояние структуры в другое.

Возможны следующие элементарные изменения обобщенной структуры:

добавить вершину;

добавить связь;

убрать вершину;

убрать связь.

Могут быть осуществлены и комбинации элементарных мутаций. Например, добавить несколько связей, убрать связь и вершину.

Основой такого подхода Е.Л. Глориозов выдвигает начальный набор схемотехнических решений конкретной задачи, который позволяет выделить базисные структуры. В этом случае формальная постановка проблемы поиска технических решений для любой предметной области должна предусматривать ряд составляющих.

Первая составляющая предполагает построение некоторой обобщенной структуры, которая обладает свойством полноты. Это свойство состоит в том, что должна иметься гарантия получения любого физически осуществимого решения с помощью строгих формальных процедур. Обобщенная структура представляет собой полный граф, вершины которого являются базисными структурами, а ветви – связями между ними.

Вторая составляющая задачи связана с наличием оператора преобразования, с помощью которого одно состояние обобщенной структуры переходит в другое. Оператор преобразования реализует механизм мутации.

Наконец, необходима мера различия схемных решений или свертка критериев оптимальности.

Рассмотренные понятия оказываются достаточными для построения алгоритма поиска схем. С точки зрения построения оператора преобразования и, следовательно, алгоритма синтеза, важнейшим является дерево инженерных решений в данной предметной области, которое представляет собой множество вершин. Связь между этими вершинами отображает множество операторов . Для схемотехнического проектирования

,(41)

где ₁ – оператор включения базисной структуры между узлами схемы; ₂ – оператор типа базисной структуры; ₃ – оператор ориентации базисной структуры относительно узлов схемы; ₄ – оператор увеличения числа внутренних узлов схемы; ₅ – оператор переопределения входных узлов схемы; ₆ – оператор рассечения узла схемы и образования нового узла; ₇ – оператор, определяющий токовый режим работы узла схемы.

Любая вершина дерева инженерных решений имеет множество признаков

, (42)

где S – чувствительность цепи;G – собственный шум схемы; D – динамический диапазон; I₀ – потребляемый ток.

Дерево инженерных решений может быть построено с помощью анализа существующего набора принципиальных схем.

В рамках предлагаемого подхода формирование составляющих оператора осуществляется на базе арсенала инженерных приемов. Однако в этом случае практически исключаются изоморфные решения, следовательно, упрощаются вычислительные процедуры.