5.2. Постановка задачи структурного синтеза моделей сложных систем на основе ЭМ. основные понятия структурного синтеза моделей.

Наиболее употребительной, прочно исследованной на различных популяциях и в различных конкретных задачах является следующая упрощенная схема эволюции: порождение потомков, их оценка и отбор лучших (селекция).

Рассмотрим следующие примеры.

Пример 1. Эволюционная стратегия поиска.

Цель:
Наследственная изменчивость:
Популяция - последовательность ;
Размножение - ;
Соревнование - по значениям Селекция (отбор) - N особей с вероятностью по значениям f(x). Здесь - реализация случайного механизма (мутаций); характеризует интенсивность мутаций. Величина равномернораспределена в интервале [-1;+1].

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

В частности можно предложить такой метод, который получил название “ генетического ”. Здесь, как и прежде, популяция состоит из точек, каждая точка характеризуется не только своим положением, но и дисперсией вероятностного распределения, по которому порождаются потомки. Размножение осуществляется по приведенным в примере 2 формулам. Отличие от примера 1 незначительно, однако введением интенсивности мутации (параметр ) в генотип, с одной стороны существенно разнообразят наследственную изменчивость, а с другой стороны - косвенно вовлекают интенсивность мутаций в отбор. Тем самым параметр определяет главный фактор эволюции - изменения, которые не задаются извне насильственным образом, а регулируются по значениям минимизируемой функции.

Пример 2. “Генетический метод поиска”.

Цель: минимизация f(x)
Наследственная изменчивость:
Популяция - совокупность ;
Размножение - ,
- равномерно распределена в [-1;1];
- равномерно распределена в [0;1];
.
Соревнование - по значениям по значениям
Селекция (отбор) - N особей, наилучших по значениям f(x)

Пример 3 . “Автоматная модель эволюции”.

Цель: минимизация - функции стоимостей предсказания последовательности
Наследственная изменчивость:
Популяция - несколько конечных автоматов;
Размножение - список случайных изменений:

1. убрать состояние;
2. добавить состояние;
3. убрать связь;
4. добавить связь.

Соревнование - по значениям функции .
Селекция - по значениям функции .

Пример 4. Эволюционный синтез структуры.

Цель: многокритериальная многопараметрическая оптимизация

1. добавить d ребер;
2. удалить d ребер.

Соревнование - по значениям функции Q(x,y)
Отбор - по значениям функции Q(x,y)

Заметим, что примеры 3,4 реализуют эволюционные алгоритмы структурного случайного поиска.

Основные понятия эволюционного моделирования (ЭМ).

Формализация класса синтезируемых моделей.

Излагаемая нами формализация базируется на основных моделях системного подхода и анализа, используя категории “объект”, “свойство”, “отношение”.

Структурированная модель F (СМ \\ F) - это совокупность объектов (элементов) со свойствами и отношением между ними s, образующими целостный составной объект, то есть такой, который приобретает свойство , являющееся следствием свойств элементов и отношений, но не присущее этим элементам, взятым в отдельности.

Структурированная модель F осуществляет отображение F входных функций дискретного аргумента t () в выходные функции того же аргумента с помощью набора операторов, из совокупности {f,I} в соответствии с отношением s, которое определяет порядок следования или применения .

Если при отображении СМ F входной функции в выходную используется набор операторов то является суперпозицией функций по отношению 3.

Отношение, фиксирующее наборы функций суперпозиции из совокупности {F,I}(и порядок их следования при формировании выходных функций ) назовем структурой СМ F. Таким образом, поведение структурированной модели F определяется двумя основными компонентами: совокупностью операторов суперпозиции {f,I} и структурой s. В зависимости от конкретного задания типов этих компонент рассматриваются различные классы СМ F

Множество из СМ F называется классом К:({f,I},S) - структурированных моделей с заданной совокупность операторов суперпозиции. Структурированные классы различны, когда различны типы операторов суперпозиции и/или типы структур. Отдельные классы СМ широко известны и хорошо исследованы, к ним относятся:

• классы функций алгебры логики, построенные на различных системах элементарных булевых функций (КНФ и ДНФ). Выражение для соответствующей модели F определяется при этом совершенной КНФ или ДНФ.
• классы ортонормированных функций
• класс неориентированных и ориентированных графов, сети Петри, конечные автоматы (детерминированные и вероятностные) и так далее.

Рис.3 Классификационное дерево структур С-моделей

На рис.3 приведено классификационное дерево структур С-моделей.

Совокупность операторов {f,I} называется функционально полной, если любое отображение F можно представить суперпозицией {f,I} на некоторой структуре .

Класс называется функционально полным, если его совокупность {f,I} является функционально полной системой или содержит функционально полную подсистему.

Совокупность S называется структурно полной, если произвольное отображение F можно представить суперпозицией некоторого набора операторов {f,I} со структурой .

Класс называется структурно полным, если его совокупность S является структурно полной при некотором наборе операторов из .

Утверждение 1: Произвольный класс включает класс тогда и только тогда, когда и .

Таким образом, любой класс К, включающий структурно полный класс, сам является структурно полным. Аналогичное утверждение верно и для функциональной полноты класса.

Утверждение 2: Произвольный класс включает класс тогда и только тогда, когда и .

Класс К называется полным, если он структурно и функционально полный.

Из утверждений 1 и 2 получено следствие: Произвольный класс К является полным, если он содержит хотя бы один и . Итак, полный класс К содержит хотя бы одну СМ F, на которой реализуется отображение y(t)=F(x(t)).

Структурированная модель , реализующая отображение y(t)=F(x(t)), с точностью до называется - приближением структурированной модели

Основные понятия структурного синтеза.

Развиваемый ниже подход направлен на синтез -приближений СМ- на основе варьирования суперпозиций .

Введем необходимые понятия. Будем рассматривать в качестве элементов С-модели любые сущности (объекты), отражающие участие в суперпозициях F той или иной функции из совокупности {F,I}, либо порядок следования этих функций, который фиксируется структурой. В первом случае элементы С-модели являются функциональными, а во втором - структурными. Исходя из общепринятых понятий, структурные и функциональные элементы С-модели делятся на простые и составные (сложные). Составные элементы декомпозируются на простые элементы.

Таким образом, любая модель обладает набором простых и составных, структурных и функциональных элементов; причем для С-моделей одного класса этот набор однотипен. Изменения элементов С-модели базируются наследующих типах действий:

1. устранить один элемент из С-модели и суперпозиции F;
2. добавить один элемент в С-модель и суперпозицию F.

Изменение на элементном материале С-модели называется составным, если оно является композицией простых изменений.

Простые изменения первого типа на структурном элементе называются структурными.

Простые изменения первого типа на функциональном элементе называются функциональными.

Простое изменение второго типа на структурном элементе называется функционально-структурным.

Простое изменение второго типа на функциональном элементе называется структурно-функциональным.

Отметим, что понятие “простое изменение” носит относительный характер и на более детальном уровне декомпозиции простые элементы становятся составными в классе , в котором любая СМ-F представляется суперпозицией функций по структуре , являющейся элементом s.

Пусть поведение произвольной по некоторой совокупности ее выходных функций описывается некоторым критерием Q, экстремальное значение которого соответствует желаемому поведению . Тогда критерий Q задает отношение предпочтения в классе СМ-моделей. , если , где - выход модели , - выход модели .

С-модель называется локально эффективной, если она получена в результате изменений С-модели на основе списка режимов изменений (РИ) и справедливо отношение .

С-модель называется эффективной, если она является -приближением.

В таблице 4 описаны наиболее известные и используемые классы структурированных моделей с указанием литературного источника. Здесь же приведены функциональные базисы (совокупность функций {f,I}) и совокупности структур. Анализ данных табл.4 показывает, что целесообразно различать внутренние и внешние характеристики класса.

Таблица 4.