Задача проектирования заключается в создании модели некоторой системы, которая будет способна выполнять предписанные функции с заданным уровнем качества. Требования, предъявляемые к проектируемой системе, формируются вне ее, в метасистеме более высокого уровня, которая также является антропогенной развивающейся системой.
Следовательно, формируемые в ней цели и требования к системе более низкого уровня (подсистеме) могут изменяться с течением времени. В связи со сказанным задачи проектирования и перепроектирования экономических систем являются динамическими задачами принятия проектных решений в условиях неопределенности, поэтому им органически присущи многовариантность, многокритериальность, открытость (постоянный обмен информацией с внешней средой) и адаптивность (способность изменять свои свойства и структуру при изменении факторов внешнего окружения). Эффективное решение подобных задач основано на применении принципов эволюционного проектирования (рис. 8.5).
Информация об изменениях метасистемы (внешней среды) используется для моделирования ее поведения. Результаты моделирования позволяют сформировать вектор требований к проектируемой системе R(t), который может изменяться во времени. Задача проектирования сложной системы согласно заключается в синтезе вариантов ее структуры (S1 S2, S3) и выборе варианта, который характеризуется совокупностью свойств (P1 P2, Р3), наилучшим образом удовлетворяющих внешним требованиям R(t).
Эволюционный подход к синтезу заключается в построении целостной системы из более простых частей с позиций теории развития, а именно: сложная система синтезируется из элементов под контролем факторов внешней среды, при этом структура системы и состав элементов подбираются так, чтобы обеспечить максимальное удовлетворение внешних требований (естественный отбор).
Рис. 8.5. Схема эволюционного проектирования
Для реализации эволюционного синтеза можно использовать идеи генетических алгоритмов, широко применяемые для решения задач оптимизации. Задачи синтеза сложных систем существенно отличаются от оптимизационных, поэтому для их решения необходима модификация известных генетических алгоритмов. Это связано с тем, что в синтезе сложной системы участвуют объекты с различными структурами описаний, в то время как в процессе оптимизации рассматриваются объекты с идентичными описаниями. Другими словами, состав популяции объектов синтеза разнороден, т.е. содержит множество видов, а в процессе синтеза возможно межвидовое скрещивание. Кроме того, описания объектов синтеза представляют собой наборы структурированных данных различных типов, а не двоичные цепочки генов, как в алгоритмах оптимизации. Поэтому в процессе синтеза возникает проблема формирования структур описаний потомков, а также проблема выбора претендентов для скрещивания, так как кроссинговер возможен только между определенными видами, присутствующими в популяции. В известных генетических алгоритмах проблемы отбора родителей и формирования описаний потомков успешно решаются с использованием механизмов случайного выбора. В задачах синтеза применение случайного отбора и комбинирования ограничено.
Рассмотрим основные этапы эволюционного синтеза систем.
Этап 1. Создается популяция исходных объектов синтеза, которая представляет собой множество альтернативных реализаций функциональных подсистем (ФПС), наделенных определенными свойствами и имеющих требования к своему окружению внутри системы.
Рис. 8.6. Одноуровневая (а) и иерархическая (б) структуры синтезируемых систем
Этап 2. Формулируется набор обобщенных требований к синтезируемой системе, отражающих ее жизнеспособность или эффективность. Если структура системы задана иерархией, то формулируются также требования к подсистемам, имеющим внутреннее строение (подсистемы S1 S4, S13).
Этап 3. Формируется функция ценности вариантов проектируемой системы, позволяющая оценивать степень соответствия сгенерированных объектов заданному набору внешних требований. При иерархическом представлении задается набор таких функций.
Этап 4. С помощью генетического оператора скрещивания из объектов исходной популяции создаются новые объекты — представители следующей популяции.
Этап 5. Вычисляются значения функции ценности полученных вариантов и на их основе производится отбор лучших представителей из новой популяции.
Этапы 4 и 5 могут повторяться неоднократно до выполнения условия завершения процесса синтеза.
Рассмотрим представление знаний, используемых в процессе эволюционного синтеза систем. Допустим, структура синтезируемой системы S задана графом (рис. 8.6, а). Варианты целостного объекта (системы) могут содержать не более чем N элементов Si, i = 1,…,N. Набор информации, используемой для синтеза, может включать различные характеристики, представленные совокупностью свойств каждой подсистемы PSi = {Yi1,Yi2,…,Yiki}, где Ki — число свойств i-й подсистемы, i = 1,…,N. В отличие от традиционных бинарных цепочек генов свойства ФПС могут выражаться целыми или вещественными числами, а также символьными строками. Кроме набора свойств каждая подсистема Si описывается набором требований к ее внутреннему окружению (к другим элементам), RSi = {Xi1Xa,…,XiMi}\ Mi — число требований i-й подсистемы к другим подсистемам. Порядок взаимных требований подсистем можно представить с помощью графа, пример которого приведен на рис. 8.7.
Элементы матрицы В соответствуют числу требований, которые предъявляет элемент, указанный в строке, к элементу, указанному в столбце.
Рис. 8.7. Пример графа взаимных требований подсистемы
Первый индекс любого требования совпадает с индексом подсистемы, которая выдвигает это требование, второй индекс является порядковым номером требования в списке требований Граф требований хранится в матричном представлении (В).
Важным моментом является установление соответствия между свойствами ФПС и требованиями, которые к ней предъявляются со стороны других подсистем. С этой целью заполняются матрицы соответствия для каждой подсистемы Эти матрицы являются промежуточным представлением объектов синтеза, удобным для дальнейшей обработки. Например, матрица соответствия для ФПС имеет вид
В первой строке такой матрицы записываются индексы свойств рассматриваемой подсистемы, в остальных (N-1) строках — индексы требований, которые другие подсистемы выдвигают к соответствующим свойствамВ матрицах соответствия могут присутствовать столбцы, в которых не записано ни одного требования. Это значит, что данное свойство не влияет на совместимость элементов внутри системы. Оно, например, может являться характеристикой качества подсистемы. В процессе синтеза для каждой матрицы создается копия, в которую записываются конкретные значения требований выбранных альтернативных реализаций Последние строки этих матриц служат для записи значений обобщенных требований к свойству подсистемы со стороны всех остальных элементов, которые вычисляются после подстановки значений. Описания альтернативных реализаций ФПС удобно представить с помощью таблиц следующего вида:
Таким образом, альтернативные реализации каждой ФПС описываются парой таблиц, в которых хранятся конкретные значения свойств и требований Значениями свойств являются числа или текстовые данные, значениями требований — равенства или неравенства. При таком представлении принимается допущение о том, что наборы свойств и требований для всех альтернативных реализаций подсистемы имеют одинаковые размерности Общее число свойств или требований подсистемы можно получить путем объединения соответствующих характеристик альтернативных реализаций При проверке на удовлетворение требованиям конкретных альтернатив действуют следующие правила. Если альтернатива обладает свойством, к которому не предъявляется требований, то результат проверки считается удовлетворительным. Если у альтернативы отсутствует свойство, к которому предъявляются требования со стороны других подсистем, то результат проверки требований будет отрицательным.
Множество векторов свойств и требований подсистем набор матриц соответствия а также таблицы свойств и требований реализаций ФПС составляют совокупность исходных данных об объектах эволюционного синтеза.
Этапы 2 и 3 эволюционного синтеза связаны с построением функции ценности синтезируемых вариантов, которая должна отражать их жизнеспособность. Для построения такой функции необходимо сформулировать внешние требования к проектируемой системе где М — количество внешних требований. Эти требования обычно сопряжены с выполнением определенного набора функций и заданным уровнем качества системы в целом. Требования к синтезируемой системе могут представлять собой выражения, включающие операции max, min и др. Операндами таких выражений являются свойства целостной системы константы отражающие специфику требований, а также имена и значения свойств ФПС. В процессе синтеза необходимо сформировать вектор свойств целостной системы который является функцией ее структуры (т.е. свойств элементов и связей между ними), и установить способы вычисления компонентов этого вектора на основе информации о составе конкретных вариантов. Значения свойств целостной системы можно получить различными способами. При морфологическом подходе к синтезу характеристики, представленные количественными оценками, получаются с помощью аддитивной или мультипликативной свертки.
Логический подход к синтезу предусматривает применение формул логики предикатов (правил) для формирования характеристик целостного объекта на основе свойств элементов, что расширяет возможности представления знаний, но требует дополнительной информации.
Эволюционный подход к синтезу допускает применение разных способов получения параметров: это могут быть математические и алгоритмические функции, логические формулы, правила, а также комбинированное представление. Выбор конкретного способа зависит от количества и качества доступной информации. При недостатке знаний для вычисления параметров могут использоваться аддитивный или мультипликативный обобщенный критерий. Процедура вычисления компонентов вектора свойств для варианта системы может выглядеть, например, следующим образом:
Последние три формулы для вычисления интегральных свойств представляют собой записи продукционных правил в виде фраз Хорна. При такой форме записи в левой части правила (до стрелки) записывается заключение, а в правой — условие. Например, последнее правило следует интерпретировать так: установить значение свойства равным если реализацией ФПС не является . Предпоследняя запись предусматривает присваивание другого значения свойству в том случае, если в качестве выбрана реализация
После того как сформирована процедура получения значений параметров целостной системы, значения функции ценности вариантов можно вычислить как обобщенную меру сходства вектора внешних требований iсо свойствами конкретного варианта . Для построения функции ценности применяются меры сходства, описанные в разд. 8.5. Самый простой способ формирования интегрального значения функции ценности — это вычисление среднего арифметического мер удовлетворения всех требований для варианта системы:
Если требования имеют разную значимость, вводятся весовые коэффициенты w = {wuw2,-..,wK} и функция ценности приобретает вид
Если структура проектируемой системы задана иерархией (см. рис. 8.6, б), необходимо сформировать функции ценности для всех подсистем, имеющих сложную внутреннюю структуру.
Рассмотрим процедуру соединения N элементов с разными описаниями, соответствующую оператору скрещивания в генетических методах поиска оптимальных решений. Заметим, что в данном случае потомок происходит от N родителей. Отбор кандидатов для скрещивания основан на вычислении степени удовлетворения взаимных требований соединяемых ФПС. Для каждого i-ro элемента синтезируемой системы вычисляется мера удовлетворения требованиям остальных элементов, претендующих войти в комбинацию, в соответствии с формулами
или
Здесь — мера сходства свойства i-й ФПС с объединенным набором требований к ней со стороны остальных элементов; — нормированные весовые коэффициенты требований к свойству i-й ФПС. Обобщенная оценка степени удовлетворения взаимных требований элементов в варианте системы вычисляется либо как среднеарифметическое, либо как среднегеометрическое в зависимости от выбранного принципа компромисса, т.е.
или
Аддитивная функция принимает нулевое значение только в том случае, если все ФПС, вошедшие в вариант, не удовлетворяют требованиям друг друга. Мультипликативная функция принимает нулевое значение, когда в комбинацию входит хотя бы один элемент, для которого— 0, поэтому вторая функция более эффективна для поиска вариантов с высокой степенью согласия между участниками (ФПС). При использовании аддитивной функции проверку на наличие внутренних противоречий следует проводить с использованием некоторого порога В случае применения мультипликативной функции проверка может выполняться по условию
Таким образом, для любого генерируемого варианта системы вычисляется значение функции и на его основе принимается решение о возможности существования данной комбинации ФПС. Если решение отрицательное, то не проводится вычисление свойств варианта т.е. фактически он не порождается и не включается в новую популяцию. В противном случае формируется описание полученного варианта с использованием соответствующей процедуры вывода интегральных свойств, и он участвует в последующем отборе, который осуществляется на основе значений функции отражающей жизнеспособность целостной системы во внешней среде. Таким образом, выполняется скрещивание N разнородных объектов с учетом их способности к соединению. Следует отметить, что в данном случае не происходит никакого обмена фрагментами хромосом, как в генетических алгоритмах, так как описания объектов являются структурированными, разнородными, и поэтому взаимный обмен фрагментами таких описаний лишен какого-либо смысла.
В зависимости от объема знаний о проектируемой системе и от ее сложности эволюционный синтез можно проводить в различной последовательности. В случае одноуровневого представления проектируемой системы (см. рис. 8.6, а) алгоритм синтеза включает следующие шаги.
1. Подготавливается и вводится исходная информация, содержащая описания ФПС наборами свойств и требований, граф взаимных требований ФПС и матрицы соответствия требований свойствам. В базу знаний системы эволюционного синтеза помещается процедура (грамматика) вычисления параметров синтезируемой системы через параметры составляющих элементов. Пользователь должен также сформировать набор внешних требований к синтезируемой системе.
2. Генерируется вариант из N реализаций функциональных подсистем, выбранных случайным образом из соответствующих множеств. При небольшой мощности множеств альтернативных реализаций ФПС генерируется множество всех возможных вари антов целостной системы путем полного перебора.
3. Вычисляются оценки меры удовлетворения требований для каждой подсистемы 0, формируется описание комбинации Vq путем объединения описаний элементов. В описание также включаются индексы вошедших подсистем. Значение Glq включается в описание комбинации. Если Gq = 0, то комбинация исключается из рассмотрения и осуществляется возврат на шаг 3.
6. Формирование свойств нового объекта с использованием заданных грамматических правил и набора его требований к окружению путем объединения требований «родителей».
7. Формирование новой популяции вариантов, прошедших проверку на шаге 5. При этом возможно применение дополни тельного условия отбора на основе обобщенной оценки по критериям качества.
8. Проверка на выполнение требований объектов новой популяции к внутреннему окружению. Если не все требования удовлетворены, то объект участвует в дальнейшем синтезе. Осуществляется переход на шаг 3, где происходит поиск кандидатов для скрещивания, управляемый невыполненными требованиями. В противном случае — переход к следующему шагу.
9. Проверка на полноту функций, которые должна выполнять синтезируемая система. Если описание сгенерированного вари анта содержит все заданные функции, описание полученного объекта включается в популяцию готовых вариантов и осуществляется переход на шаг 12. В противном случае — переход на следующий шаг.
10. Возврат на шаг 3, где генерируются новые объекты путем присоединения элементов исходной популяции к членам новой популяции (процесс управляется графом требований).
11. Повторение шагов 3 — 10 до выполнения условия окончания синтеза. Таким условием является завершение обхода графа требований, включая отдельные вершины.
12. Отбор вариантов из популяции целостных систем, проводимый на основе значений функции ценности Fq. Если jто описание варианта Vq записывается в файл результатов. В задачах небольшой размерности имеет смысл сделать полный перебор, иначе осуществляется случайный отбор заданного количества ва риантов с максимальными значениями функции Fq.
Если структура синтезируемой системы задана иерархией {см. рис. 8.6, б), то формируется множество популяций, соответствующих вершинам графа, имеющим исходящие дуги. Оценочные функции для подсистем, генерируемых в таких узлах, могут строиться или на основе сходства заданных требований со свойствами, или на основе обобщенной оценки по критериям качества. В любом случае необходимо сформировать вычислительные процедуры для получения параметров подсистем, имеющих сложное внутреннее строение. Вопрос о наследовании свойств в процессе эволюционного синтеза решается на этапе представления знаний. При синтезе экономических систем свойства составляющих элементов могут наследоваться, утрачиваться или вычисляться заданным способом. Применение аналогов операций мутации, репродукции, инверсии и т.д. в процессах эволюционного проектирования возможно в принципе, но на сегодняшний день не представляется нам целесообразным, так как трудно найти естественное объяснение произвольному изменению свойств объектов, из которых синтезируется система, в процессе ее проектирования. Помимо этого, реализация упомянутых операторов проблематична в связи со сложностью представления информации об объектах синтеза, а также может привести к трудно предсказуемым последствиям на этапе вывода свойств целостной системы и при интерпретации результатов. Использование названных приемов может иметь определенный смысл при формировании и исследовании множества объектов синтеза.
Метод эволюционного синтеза можно применить, например, для решения задачи, рассмотренной в разд. 8.5. Это целесообразно, если при проектировании структуры системы(см. рис. 8.1) существует большое количество альтернативных реализаций подсистем Тогда необходимо сформировать функцию ценности генерируемых вариантов, которая будет отражать эффективность системы в целом. Заметим, что использование в качестве функций ценности мер сходства позволяет оценивать проектируемый объект по множеству критериев качества без усреднения значений показателей. Такие функции на основе выбранного принципа компромисса вычисляют обобщенную меру близости полученного варианта к заданным внешним требованиям. Главной проблемой в этом случае является формирование правил вычисления свойств целостной системы в процессе ее синтеза из элементов. Интегральными показателями качества проектируемой системы могут служить оценки прибыли, рентабельности, спроса и другие, которые можно получить на основе информации, характеризующей конкретные реализации ФПС, например, мощность производства .спрос на конкретный вид продукции Pi(X2/), объем возможных инвестиций и процентная ставка стоимость технологий срок освоения технологий стоимость материалов и электроэнергии (см. табл. 8.1 -8.7).
Применение процедур эволюционного синтеза существенно облегчает анализ полученных вариантов, так как выходные результаты работы программы содержат только совместимые варианты, наиболее близкие к заданным требованиям. Следует отметить, что, в отличие от проектирования технических объектов, в задачах проектирования экономических систем допустимо и часто желательно построение вариантов, содержащих в своем составе не по одной альтернативной реализации ФПС, а по нескольку (диверсификация продукции, привлечение многих партнеров). Подобная постановка задачи приводит к значительному увеличению количества возможных вариантов и вызывает необходимость изменения процедур вывода свойств целостной системы с тем, чтобы учесть наличие многоальтернативных ФПС. В таких случаях целесообразно применять двухэтапную процедуру синтеза, позволяющую снизить размерность исходной задачи. На первом этапе проводится синтез моноальтернативных вариантов проектируемой системы и отбирается подмножество наилучших. Второй этап заключается в построении вариантов многоальтернативных систем на основе множества структур, отобранных на первом этапе. При этом используется модифицированная процедура вывода свойств целостной системы, в которой учитывается наличие множества элементов, принадлежащих к одному классу ФПС.