Эволюционный синтез систем объектов

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

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

Информация об изменениях метасистемы (внешней среды) используется для моделирования ее поведения. Результаты моде­лирования позволяют сформировать вектор требований к проек­тируемой системе R(t), который может изменяться во времени. Задача проектирования сложной системы согласно  заключа­ется в синтезе вариантов ее структуры (S₁ S₂, S₃) и выборе вари­анта, который характеризуется совокупностью свойств (P₁ P₂, Р₃), наилучшим образом удовлетворяющих внешним требова­ниям R(t).

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

Рис. 8.5. Схема эволюционного проектирования

Для реализации эволюционного синтеза можно использо­вать идеи генетических алгоритмов, широко применяемые для решения задач оптимизации. Задачи синтеза слож­ных систем существенно отличаются от оптимизационных, по­этому для их решения необходима модификация известных ге­нетических алгоритмов. Это связано с тем, что в синтезе слож­ной системы участвуют объекты с различными структурами описаний, в то время как в процессе оптимизации рассматрива­ются объекты с идентичными описаниями. Другими словами, состав популяции объектов синтеза разнороден, т.е. содержит множество видов, а в процессе синтеза возможно межвидовое скрещивание. Кроме того, описания объектов синтеза пред­ставляют собой наборы структурированных данных различных типов, а не двоичные цепочки генов, как в алгоритмах оптими­зации. Поэтому в процессе синтеза возникает проблема форми­рования структур описаний потомков, а также проблема выбора претендентов для скрещивания, так как кроссинговер возможен только между определенными видами, присутствующими в по­пуляции. В известных генетических алгоритмах проблемы отбо­ра родителей и формирования описаний потомков успешно решаются с использованием механизмов случайного выбора. В за­дачах синтеза применение случайного отбора и комбинирова­ния ограничено.

Рассмотрим основные этапы эволюционного синтеза систем.

Этап 1. Создается популяция исходных объектов синтеза, которая представляет собой множество альтернативных реализа­ций функциональных подсистем (ФПС), наделенных определен­ными свойствами и имеющих требования к своему окружению внутри системы.

Рис. 8.6. Одноуровневая (а) и иерархическая (б) структуры синтезируемых систем

Этап 2. Формулируется набор обобщенных требований к синтезируемой системе, отражающих ее жизнеспособность или эффективность. Если структура системы задана иерархией, то формулируются также требования к подсистемам, имеющим внутреннее строение (подсистемы S₁ S₄, S₁₃).

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

Этап 4. С помощью генетического оператора скрещивания из объектов исходной популяции создаются новые объекты — представители следующей популяции.

Этап 5. Вычисляются значения функции ценности получен­ных вариантов и на их основе производится отбор лучших пред­ставителей из новой популяции.

Этапы 4 и 5 могут повторяться неоднократно до выполнения условия завершения процесса синтеза.

Рассмотрим представление знаний, используемых в процессе эволюционного синтеза систем. Допустим, структура синтезиру­емой системы S задана графом (рис. 8.6, а). Варианты целостно­го объекта (системы) могут содержать не более чем N элементов S_i, i = 1,…,N. Набор информации, используемой для синтеза, мо­жет включать различные характеристики, представленные сово­купностью свойств каждой подсистемы P_Si = {Y_i1,Y_i2,…,Y_iki}, где K_i — число свойств i-й подсистемы, i = 1,…,N. В отличие от тради­ционных бинарных цепочек генов свойства ФПС могут выра­жаться целыми или вещественными числами, а также символь­ными строками. Кроме набора свойств каждая подсистема S_i описывается набором требований к ее внутреннему окружению (к другим элементам), R_Si = {X_i1X_a,…,X_iMi}\ M_i — число требова­ний i-й подсистемы к другим подсистемам. Порядок взаимных требований подсистем можно представить с помощью графа, пример которого приведен на рис. 8.7.

Элементы матрицы В соответствуют числу требований, кото­рые предъявляет элемент, указанный в строке, к элементу, ука­занному в столбце.

Рис. 8.7. Пример графа взаимных требований подсистемы

Первый индекс любого требования  совпадает с индексом подсистемы, которая выдвигает это требование, второй индекс является порядковым номером требования в списке требований  Граф требований хранится в матричном представлении (В).

Важным моментом является установление соответствия меж­ду свойствами ФПС и требованиями, которые к ней предъявля­ются со стороны других подсистем. С этой целью заполняются матрицы соответствия для каждой подсистемы  Эти матрицы являются промежуточным представлением объектов синтеза, удобным для дальнейшей обработки. Например, матрица соот­ветствия для ФПС  имеет вид

В первой строке такой матрицы записываются индексы свойств рассматриваемой подсистемы, в остальных (N-1) строках — индексы требований, которые другие подсистемы выдвигают к соответствующим свойствамВ матрицах соответствия могут присутствовать столбцы, в которых не записано ни одного требо­вания. Это значит, что данное свойство не влияет на совмести­мость элементов внутри системы. Оно, например, может являть­ся характеристикой качества подсистемы. В процессе синтеза для каждой матрицы  создается копия, в которую записываются конкретные значения требований выбранных альтернативных реализаций Последние строки этих матриц служат для записи значений обобщенных требований к  свойству подсисте­мы  со стороны всех остальных элементов, которые вычисля­ются после подстановки значений. Описания альтернативных ре­ализаций ФПС удобно представить с помощью таблиц следую­щего вида:

Таким образом, альтернативные реализации каждой ФПС описываются парой таблиц, в которых хранятся конкретные зна­чения свойств  и требований  Значениями свойств явля­ются числа или текстовые данные, значениями требований — ра­венства или неравенства. При таком представлении принимается допущение о том, что наборы свойств и требований для всех аль­тернативных реализаций  подсистемы имеют одинаковые раз­мерности  Общее число свойств или требований подсис­темы можно получить путем объединения соответствующих ха­рактеристик альтернативных реализаций При проверке на удовлетворение требованиям конкретных альтернатив действуют следующие правила. Если альтернатива обладает свойством, к которому не предъявляется требований, то результат проверки считается удовлетворительным. Если у альтернативы отсутствует свойство, к которому предъявляются требования со стороны других подсистем, то результат проверки требований будет отрица­тельным.

Множество векторов свойств и требований подсистем набор матриц соответствия  а также таблицы свойств и требований реализаций ФПС составляют совокупность исходных данных об объектах эволюционного синтеза.

Этапы 2 и 3 эволюционного синтеза связаны с построением функции ценности синтезируемых вариантов, которая должна отражать их жизнеспособность. Для построения такой функции необходимо сформулировать внешние требования к проектируе­мой системе где М — количество внешних требований. Эти требования обычно сопряжены с выполнением определенного набора функций и заданным уровнем качества системы в целом. Требования к синтезируемой системе могут представлять собой выражения, включающие операции  max, min и др. Операндами таких выражений являются свойства целостной системы константы  отражающие специфику требований, а также имена и значения свойств ФПС. В процессе синтеза необходимо сформировать вектор свойств целостной системы который является функцией ее структуры (т.е. свойств элементов и связей между ними), и установить способы вычисления компонентов этого вектора на основе информации о составе конкретных вари­антов. Значения свойств целостной системы можно получить различными способами. При морфологическом подходе к синтезу  характеристики, представленные количественными оценка­ми, получаются с помощью аддитивной или мультипликативной свертки.

Логический подход к синтезу предусматривает применение формул логики предикатов (правил) для формирования характе­ристик целостного объекта на основе свойств элементов, что рас­ширяет возможности представления знаний, но требует допол­нительной информации.

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

Последние три формулы для вычисления интегральных свойств представляют собой записи продукционных правил в ви­де фраз Хорна. При такой форме записи в левой части правила (до стрелки) записывается заключение, а в правой — условие. На­пример, последнее правило следует интерпретировать так: уста­новить значение свойства  равным если реализацией ФПС  не является . Предпоследняя запись предусматривает при­сваивание другого значения свойству в том случае, если в качестве  выбрана реализация

После того как сформирована процедура получения значений параметров целостной системы, значения функции ценности ва­риантов можно вычислить как обобщенную меру сходства векто­ра внешних требований iсо свойствами конкретного варианта . Для построения функции ценности применяются меры сходства, описанные в разд. 8.5. Самый простой способ форми­рования интегрального значения функции ценности — это вы­числение среднего арифметического мер удовлетворения всех требований для  варианта системы:

Если требования имеют разную значимость, вводятся весо­вые коэффициенты w = {w_uw₂,-..,w_K} и функция ценности приоб­ретает вид

Если структура проектируемой системы задана иерархией (см. рис. 8.6, б), необходимо сформировать функции ценности для всех подсистем, имеющих сложную внутреннюю структуру.

Рассмотрим процедуру соединения N элементов с разными описаниями, соответствующую оператору скрещивания в гене­тических методах поиска оптимальных решений. Заметим, что в данном случае потомок происходит от N родителей. Отбор кан­дидатов для скрещивания основан на вычислении степени удов­летворения взаимных требований соединяемых ФПС. Для каж­дого i-ro элемента синтезируемой системы вычисляется мера удовлетворения требованиям остальных элементов, претендую­щих войти в комбинацию, в соответствии с формулами

или

Здесь — мера сходства  свойства i-й ФПС с объединенным набором требований к ней со стороны остальных эле­ментов; — нормированные весовые коэффициенты требований к  свойству i-й ФПС. Обобщенная оценка степени удовлетво­рения взаимных требований элементов в  варианте системы вычисляется либо как среднеарифметическое, либо как среднеге­ометрическое в зависимости от выбранного принципа компро­мисса, т.е.

или

Аддитивная функция  принимает нулевое значение только в том случае, если все ФПС, вошедшие в вариант, не удовле­творяют требованиям друг друга. Мультипликативная функция принимает нулевое значение, когда в комбинацию входит хотя бы один элемент, для которого— 0, поэтому вторая функция более эффективна для поиска вариантов с высокой степенью со­гласия между участниками (ФПС). При использовании аддитив­ной функции проверку на наличие внутренних противоречий следует проводить с использованием некоторого порога В случае применения мультипликативной функции проверка может выполняться по условию

Таким образом, для любого генерируемого варианта системы  вычисляется значение функции  и на его основе принимается решение о возможности существования данной комбинации ФПС. Если решение отрицательное, то не проводится вычисление свойств варианта т.е. фактически он не порождается и не включается в новую популяцию. В против­ном случае формируется описание полученного варианта с ис­пользованием соответствующей процедуры вывода интегральных свойств, и он участвует в последующем отборе, который осуще­ствляется на основе значений функции  отражающей жизне­способность целостной системы во внешней среде. Таким обра­зом, выполняется скрещивание N разнородных объектов с уче­том их способности к соединению. Следует отметить, что в дан­ном случае не происходит никакого обмена фрагментами хромо­сом, как в генетических алгоритмах, так как описания объектов являются структурированными, разнородными, и поэтому вза­имный обмен фрагментами таких описаний лишен какого-либо смысла.

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

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

2. Генерируется вариант  из N реализаций функциональных подсистем, выбранных случайным образом из соответствующих множеств. При небольшой мощности множеств альтернативных реализаций ФПС генерируется множество всех возможных вари­ антов целостной системы путем полного перебора.

3. Вычисляются оценки меры удовлетворения требований для каждой подсистемы 0, формируется описание комбинации V_q путем объединения описаний элементов. В описание также включают­ся индексы вошедших подсистем. Значение G^l_q включается в опи­сание комбинации. Если G_q = 0, то комбинация исключается из рассмотрения и осуществляется возврат на шаг 3.

6. Формирование свойств нового объекта с использованием заданных грамматических правил и набора его требований к окружению путем объединения требований «родителей».

7. Формирование новой популяции вариантов, прошедших проверку на шаге 5. При этом возможно применение дополни­ тельного условия отбора на основе обобщенной оценки по крите­риям качества.

8. Проверка на выполнение требований объектов новой попу­ляции к внутреннему окружению. Если не все требования удов­летворены, то объект участвует в дальнейшем синтезе. Осуществ­ляется переход на шаг 3, где происходит поиск кандидатов для скрещивания, управляемый невыполненными требованиями. В противном случае — переход к следующему шагу.

9. Проверка на полноту функций, которые должна выполнять синтезируемая система. Если описание сгенерированного вари­ анта содержит все заданные функции, описание полученного объекта включается в популяцию готовых вариантов и осуществ­ляется переход на шаг 12. В противном случае — переход на следующий шаг.

10. Возврат на шаг 3, где генерируются новые объекты путем присоединения элементов исходной популяции к членам новой популяции (процесс управляется графом требований).

11. Повторение шагов 3 — 10 до выполнения условия оконча­ния синтеза. Таким условием является завершение обхода графа требований, включая отдельные вершины.

12. Отбор вариантов из популяции целостных систем, прово­димый на основе значений функции ценности F_q. Если jто описание варианта V_q записывается в файл результатов. В задачах небольшой размерности имеет смысл сделать полный перебор, иначе осуществляется случайный отбор заданного количества ва­ риантов с максимальными значениями функции F_q.

Если структура синтезируемой системы задана иерархией {см. рис. 8.6, б), то формируется множество популяций, соответствую­щих вершинам графа, имеющим исходящие дуги. Оценочные функции для подсистем, генерируемых в таких узлах, могут стро­иться или на основе сходства заданных требований со свойства­ми, или на основе обобщенной оценки по критериям качества. В любом случае необходимо сформировать вычислительные про­цедуры для получения параметров подсистем, имеющих сложное внутреннее строение. Вопрос о наследовании свойств в процессе эволюционного синтеза решается на этапе представления зна­ний. При синтезе экономических систем свойства составляющих элементов могут наследоваться, утрачиваться или вычисляться заданным способом. Применение аналогов операций мутации, репродукции, инверсии и т.д. в процессах эволюционного проек­тирования возможно в принципе, но на сегодняшний день не представляется нам целесообразным, так как трудно найти есте­ственное объяснение произвольному изменению свойств объек­тов, из которых синтезируется система, в процессе ее проектиро­вания. Помимо этого, реализация упомянутых операторов про­блематична в связи со сложностью представления информации об объектах синтеза, а также может привести к трудно предсказу­емым последствиям на этапе вывода свойств целостной системы и при интерпретации результатов. Использование названных приемов может иметь определенный смысл при формировании и исследовании множества объектов синтеза.

Метод эволюционного синтеза можно применить, например, для решения задачи, рассмотренной в разд. 8.5. Это целесообраз­но, если при проектировании структуры системы(см. рис. 8.1) су­ществует большое количество альтернативных реализаций под­систем  Тогда необходимо сформировать функцию ценности генерируемых вариантов, которая будет отражать эффективность системы в целом. Заметим, что использование в качестве функ­ций ценности мер сходства позволяет оценивать проектируемый объект по множеству критериев качества без усреднения значе­ний показателей. Такие функции на основе выбранного принци­па компромисса вычисляют обобщенную меру близости полу­ченного варианта к заданным внешним требованиям. Главной проблемой в этом случае является формирование правил вычис­ления свойств целостной системы в процессе ее синтеза из эле­ментов. Интегральными показателями качества проектируемой системы могут служить оценки прибыли, рентабельности, спроса и другие, которые можно получить на основе информации, ха­рактеризующей конкретные реализации ФПС, например, мощ­ность производства .спрос на конкретный вид продукции Pi(X_2/), объем возможных инвестиций и процентная став­ка  стоимость технологий  срок освоения техноло­гий стоимость материалов и электроэнергии (см. табл. 8.1 -8.7).

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