Введение

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

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

Эволюционное моделирование (ЭМ) представляет собой одно из быстро развивающихся направлений математического моделирования, объединяющее компьютерные методы моделирования эволюционных процессов в естественных (ЕС) и искусственных системах, такие как генетические алгоритмы, эволюционные стратегии, эволюционное программирование и другие эвристические методы. Главная трудность построения вычислительных систем, основанных на принципах эволюции живой природы и применении этих систем в прикладных задачах, состоит в том, что природные системы достаточно хаотичны, а действия исследователей носят направленный характер. Компьютер используется как инструмент для решения определенных задач, которые пользователь формулирует, акцентируя внимание на максимально быстром решении при минимальных затратах. Природные системы не имеют никаких таких целей или ограничений, во всяком случае, они не очевидны. Однако биологические системы обладают свойствами воспроизводства, адаптации, самоуправления, устойчивости, гибкости и многими другими, которые лишь фрагментарно присутствуют в искусственных системах.

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

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

В новом развивающемся научном направлении «эволюционное моделирование» исследуется совместное действие многих интеллектуальных искусственных систем, в результате которого возникают новые знания и новые структуры. Философское определение интеллектуальной искусственной системы, как известно, включает в себя понятие целостности, которое совмещает свойства открытости и закрытости. Для снятия данного противоречия и выхода к синтезу систем в последнее время предлагается триада, обладающая системными свойствами и оказывающаяся простейшей структурной ячейкой интеллектуальной искусственной системы. Комплексы из трех равноправных объектов, находящихся в заданных отношениях, существовали давно: цель-план-стратегия; точность-локальность-простота; ин ду кция-д е ду кция-аб ду кция; изменчивость-наследственность-отбор и др. В триаде пара элементов находится в отношении дополнительности, а третий элемент задает отношение (меру) совместимости. Общей для разных интеллектуальных объектов характеристикой является структура или архитектура интеллектуальной ИС. Это совокупность отношений, т. е. набор знаков или чисел, в который вкладывается определенный смысл. Она характеризуется многоуровневостью, единством и непротиворечивостью.

Новая интеллектуальная ИС создается, а точнее, самоорганизуется, путем эволюции. Тогда решение ИС некоторой задачи соответствует построению определенной математической модели, обладающей нужными свойствами, которых не было сначала. Смысл «существования» таких интеллектуальных ИС сводится к порождению себе подобных систем, которые при благоприятных обстоятельствах дают новое «потомство» до тех пор, пока возникшая популяция альтернативных интеллектуальных ИС существует.

Основное отличие эволюции ИС от эволюции ЕС состоит в наличии у ИС цели, связанной с оптимальным решением определенного класса задач. Здесь важна разработка критериев искусственного отбора, т. е. способов селекции и репродукции (воспроизведения), при которых кроме бесперспективных элементов из ИС удаляются и малоперспективные.

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

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

Процесс создания интеллектуальных ИС имеет множество путей. Аналогично множество альтернативных путей развития имеет и эволюция. Отсюда разнообразие возможных форм ИС, но, как правило, реализуется лишь одна из них. Эволюция подтверждает, что в основе ЕС и ИС заложены модели и аналогии принципа взаимодействия противоположностей ИНЬ-ЯН. Их взаимодействие является причиной изменения и развития природы ЕС. ИНЬ — символизирует неопределенность и неоднозначность, случайные движения, а ЯН — завершенность, реализацию цели и построение целого.

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

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

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

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

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

В монографии проведен анализ теории и практики ЭМ. Рассмотрены пути развития ЕС и интеллектуальных ИС на основе моделей различных эволюций. Установлена связь между эволюцией и синергетикой, при этом рассмотрены вопросы определения порядка из хаоса в моделях ИС. Описаны эволюционные методы и ГА. Приведены новые архитектуры генетического поиска и инструментальные средства ГА. Рассмотрены гибридные

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

Монография структурирована следующим образом.

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

•    модель эволюции Ч. Дарвина — процесс, посредством которого особи некоторой популяции, имеющие более высокое функциональное значение (с сильными признаками), получают большую возможность для воспроизведения потомков, чем «слабые» особи. Такой механизм часто называют методом «выживания сильнейших»;

•    ламаркизм или модель эволюции Ж. Ламарка. Им предложена теория, основанная на предположении, что характеристики, приобретенные особью (организмом) в течение жизни, наследуются его потомками. В отличие от простого ГА данная модель оказывается наиболее эффективной, когда популяция имеет тенденцию сходимости в область локального оптимума;

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

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

•    синтетическая теория эволюции, описанная Н. Дубининым (интеграция различных эволюций, в том числе Ч. Дарвина, Ж. Ламарка и де Фриза). Ее кардинальным положением является признание стоха- стичности процессов мутации и больших резервов рекомбинационной

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

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

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

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

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

Сложные ИС имеют фрактальную структуру, они строятся из универсальных строительных блоков, которые повторяются в различных масштабах. Такие системы инвариантны к анализируемому объекту, способны к самоподобному размножению на различных пространственно-временных

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

В ЭМ особо выделяют генетические оптимизационные алгоритмы как наиболее хорошо исследованный и находящий широкое применение класс методов, сочетающих в себе элементы случайного поиска и эвристических подходов. Эвристики представляют собой некоторую формализацию правил, по которым человек принимает решения и которые являются обобщением его опыта и интуиции. Поэтому теория ГА не является завершенной, она постоянно совершенствуется и развивается. Тем не менее, достигнутые на этом направлении успехи привлекают все большее число исследователей и практиков к разрабатываемым здесь методам. В связи с этим в третьей главе книги рассмотрены основы теории ГА. Началом возникновения ГА считается модель биологической эволюции и методы случайного поиска. ГА — это не просто случайный поиск. Они эффективно используют информацию, накопленную в процессе эволюции. ГА позволяют абстрактно и формально объяснить адаптацию процессов в ЕС и ИС, спроектировать ИС, дают много преимуществ при решении реальных задач. В третьей главе подробно рассмотрен простой ГА, на базе которого создаются все другие типы этих алгоритмов. Сформулирована теория ЭМ, приведены основные правила и аксиомы. Приведена модифицированная теорема ГА, показывающая асимптотическое число схем, выживающих в следующих поколениях.

В главе четыре рассмотрены инструментальные средства ЭМ, в которых используется ряд методов одномерного градиентного поиска, а также статистических методов оптимизации. В рамках одномерного поиска описаны следующие методы: пассивный; последовательный; дихотомии; Фибоначчи; золотого сечения; поиск в глубину, в ширину, с возвращением, с использованием И-ИЛИ деревьев и метод горизонта. Последовательный поиск выполняется путем перебора значений целевой функции (ЦФ) для нахождения оптимального значения. Метод дихотомии реализуется за счет механизма обычного перебора возможных точек разрыва. Он аналогичен методу деления отрезка пополам для нахождения точки, в которой ЦФ имеет локальный оптимум. Для определения глобального оптимума ЦФ в оптимизационных задачах в главе предлагается:

•    использовать комбинированные методы одномерного и градиентного поиска и статистических методов оптимизации;

•    учитывать знания о решаемых задачах, позволяющие связать возможные значения ЦФ с известными значениями в точках реализованных испытаний;

•    изменять начальную точку спуска методом проб и ошибок, градиентными методами, совместными методами оптимизации и локального поиска;

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

•    использовать совместные схемы поиска с ГА.

Рассмотренные методы могут выполняться не только на основе случайного поиска, но и с использованием эвристик. Основными стратегиями взаимодействия поиска и ЭМ служат стратегии «поиск-эволюция», «эволюция-поиск», «поиск-эволюция-поиск», «эволюция-поиск-эволю- ция» и другие. Элементы поиска в указанных стратегиях можно наращивать иерархически в зависимости от наличия вычислительных ресурсов и времени, заданного для получения окончательного решения.

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

В шестой главе исследуются оптимизационные задачи на графах, такие как задачи разбиения, размещения, раскраски вершин графов, нахождения пути коммивояжера, построения деревьев Штейнера, трассировки соединений, построения клик, независимых подмножеств, покрывающих деревьев, определения планарности и изоморфизма графов. Для решения указанных задач применяются различные методы ЭМ. Рассмотрены нечеткие модифицированные алгоритмы их решения. Описаны итерационные методы парных и групповых перестановок, методы по с л е д овате льного приближения, релаксации, поиска в глубину и ширину, направленного перебора и другие, а также эвристики, использующие различные методы статистической оптимизации. Эти эвристики представлены методами отжига, генетического поиска и их модификациями. Применяется группировка сильно связанных вершин в кластеры с дальнейшим сбором этих кластеров в заданные части разбиения, а также использование фрактальных множеств для группирования сильно связанных вершин. Рассмотрены последовательный ГА разбиения, алгоритм разбиения графов на части на основе модифицированной агрегации фракталов. Проанализировано использование итерационного разбиения гиперграфа и ГА дихотомического разбиения графа. При решении проблем разбиения графов на части рассмотрены задачи группирования элементов, обладающих одинаковыми свойствами.

При решении задач, связанных с размещением вершин графа на плоскости, применены классический ГА и принципы метагенетической оптимизации. При размещении вершин графа на плоскости в решетке заданной конфи

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

При построении покрывающих (остовных) деревьев графа с дополнительными вершинами (деревьев Штейнера) предложена упрощенная эвристическая процедура, основанная на горизонтальных и вертикальных «столбах» Штейнера. На основе этой процедуры описан ГА построения прямоугольных деревьев Штейнера.

Рассмотрена постановка задачи и описаны различные алгоритмы проектирования БИС и печатных плат — трассировки соединений. Основное внимание уделено задаче двухслойной канальной трассировки. Рассмотрены модифицированные ГА двухслойной канальной трассировки для цепей стандартной и различной ширины.

Проанализированы алгоритмы решения задачи о коммивояжере. Разработана стратегия решения таких задач на основе ГА и жадных эвристик.

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

Описаны четыре стратегии построения независимых подмножеств и клик графа. Первая стратегия основана на построении и анализе строительных блоков для создания независимых подмножеств или выделения клик графа. Вторая стратегия использует алгоритмы поиска в ширину. Третья стратегия предусматривает последовательный анализ всех вершин в глубину до получения семейства независимых подмножеств или клик графа. Четвертая стратегия является комбинацией первых трех.

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

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

Методы исследования рассмотренных в шестой главе задач и их результаты описаны в главе семь. Здесь приведены количественные и качественные оценки ГА при проведении различных серий испытаний. Приведены экспериментальные исследования комплексов эволюционных алгоритмов. Выполнено некоторое сравнение решений, полученных с использованием ЭМ со стандартными решениями.

В восьмой главе рассмотрены примеры решения практических задач на основе методов ЭМ. Среди них рассмотрены примеры решения задач плоского раскроя материалов, одномерной и двумерной упаковки блоков, определения пути коммивояжера, трассировки сверхбольших интегральных схем. Применение разработанных триединых концепций принятия решений позволяет получать решения указанных задач с локальными опти- мумами за полиномиальное время. Далее в главе приводятся результаты исследований, связанные с применением гибридных систем на основе ЭМ и имитационного моделирования для решения задач плоского и двумерного раскроя, динамического планирования поставок продукции на склад, краткосрочного планирования работы производственного участка.

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