Оператор мутации вносит случайные изменения в хромосомы, расширяя область пространства поиска.
Многократное применение операторов редукции, отбора, скрещивания и мутации способствует улучшению качества каждой отдельной хромосомы и, как следствие, популяции в целом, отражая основную цель генетического алгоритма – повышение качества начальной популяции. Основным результатом работы генетического алгоритма является хромосома конечной популяции, на которой целевая функция принимает экстремальное значение.
Генетические алгоритмы являются стратегическим подходом к решению проблемы, который необходимо адаптировать к конкретной предметной области путем задания параметров и определения операторов генетического алгоритма. При этом генетический алгоритм становиться сильно привязанным к рассматриваемой предметной области и может быть совершенно бесполезен для решения задач в другой предметной области [32].
От удачного выбора параметров, операторов и вида хромосом зависят устойчивость и скорость поиска – основных показателей эффективности генетического алгоритма. Скорость определяется временем, необходимым для достижения алгоритмом одного из указанных выше критериев останова. Устойчивость – это способность генетического алгоритма увеличивать качество популяции и выходить из локальных экстремумов.
Для увеличения скорости генетические алгоритмы могут подвергаться распараллеливанию как на уровне организации работы алгоритма, так и на уровне его реализации на ЭВМ.
На уровне организации работы распараллеливание осуществляется за счет структурирования популяции, которое может осуществляться двумя способами.
Первый способ называется "концепция островов" и заключается в разбиении популяции на классы (демосы), члены которых скрещиваются только между собой в пределах класса, лишь изредка обмениваясь хромосомами на основе случайной выборки. Второй способ называется "концепция скрещивания в локальной области" и заключается в задании метрического пространства на популяции, хромосомы которой подвергаются скрещиванию только с ближайшими соседями.
Что касается распараллеливания на уровне реализации, то как указанные выше процессы скрещивания пар родителей, так и процессы вычисления значений целевой функции и применения оператора мутации к хромосомам можно реализовать одновременно на нескольких параллельно работающих процессорах или системах.
Устойчивость поиска зависит от параметров операторов генетического алгоритма [33].
Для оператора скрещивания таким параметром служит степень отличия потомков от родительских хромосом: чем больше это отличие, тем устойчивей поиск, но скорость поиска меньше (лучший результат достигается за большее время).
Для оператора мутации параметром, влияющим на устойчивость поиска, служит вероятность его применения: малая вероятность обеспечивает устойчивый поиск и не приводит к ухудшению качества хромосом.
Оператор отбора связан с устойчивостью поиска следующим образом: постоянный выбор сильнейших хромосом обычно приводит к сходимости к локальному экстремуму, а выбор слабых хромосом – к ухудшению качества популяции. Аналогичное утверждение справедливо и для оператора редукции.
Что касается влияния размера популяции на устойчивость генетического алгоритма, то увеличение числа хромосом в популяции расширяет область поиска, но при этом время от времени полезно редуцировать популяцию до первоначального размера, иначе скорость генетического алгоритма резко упадет. Подобные алгоритмы называются поколенческими [34].
Развитие поколенческих алгоритмов привело к появлению адаптивных генетических алгоритмов, изменяющих свои параметры в процессе работы. Возникла концепция nGA, представляющая многоуровневые генетические алгоритмы, в которых нижний уровень улучшает популяцию, а верхний – оптимизирует параметры нижнего уровня, ориентируясь при этом на его скорость и устойчивость.
1.2.3 Системы, основанные на продукционных правилах
В системах продукций знания представляются с помощью наборов правил вида: "если А, то В". Здесь А и В могут пониматься как "ситуация-действие", "причина-следствие", "условие-заключение" и т.п. Часто правило-продукцию записывают с использованием знака логического следования: А Þ В.
В общем случае продукционная система включает следующие компоненты:
– базу продукционных правил;
– базу данных (рабочую память);
– интерпретатор.
Множество продукционных правил образует базу правил, каждое из которых представляет обособленный фрагмент знаний о решаемой проблеме. Психологи называют такие фрагменты чанками (от англ. chunk). Считается, что чанк – это объективно существующая единица знаний, выделяемая человеком в процессе познания окружающего мира.
Предпосылка правила часто рассматривается как образец. Образец – это некоторая информационная структура, определяющая обобщенную ситуацию окружающей действительности, при которой активизируется правило. Рабочая память отражает конкретные ситуации, возникающие во внешней среде. Информационная структура, представляющая конкретную ситуацию внешней среды в рабочей памяти, называется образом [35].
Интерпретатор реализует логический вывод. Процесс вывода является циклическим и называется поиском по образцу. Рассмотрим его в упрощенной форме. Текущее состояние моделируемой предметной области отражается в рабочей памяти в виде совокупности образов, каждый из которых представляется посредством фактов. Рабочая память инициализируется фактами, описывающими задачу. Затем выбираются те правила, для которых образцы, представляемые предпосылками правил, сопоставимы с образами в рабочей памяти. Данные правила образуют конфликтное множество. Все правила, входящие в конфликтное множество могут быть активизированы. В соответствии с выбранным механизмом разрешения конфликта активизируется одно из правил. Выполнение действия, содержащегося в заключении правила, приводит к изменению состояния рабочей памяти. В дальнейшем цикл управления выводом повторяется. Указанный процесс завершается, когда не окажется правил, предпосылки которых сопоставимы с образами рабочей памяти [36].
Таким образом, процесс вывода, основанный на поиске по образцу, состоит из четырех шагов:
– выбор образа;
– сопоставление образа с образцом и формирование конфликтного набора правил;
– разрешение конфликтов;
– выполнение правила.
Широкое применение продукционных моделей определяется следующими основными достоинствами:
– универсальностью (практически любая область знаний может быть представлена в продукционной форме);
– модульностью (каждая продукция представляет собой элемент знаний о предметной области, удаление одних и добавление других продукций выполняется независимо);
– декларативностью (продукции определяют ситуации предметной области, а не механизм управления);
– естественностью процесса вывода заключений, который во многом аналогичен процессу рассуждений эксперта;
– асинхронностью и естественным параллелизмом, который делает их весьма перспективным для реализации на параллельных ЭВМ.
Однако продукционные системы не свободны от недостатков:
– процесс вывода имеет низкую эффективность, так как при большом числе продукций значительная часть времени затрачивается на непроизводительную проверку условия применения правил;
– проверка непротиворечивости системы продукций становится весьма сложной из-за недетерминированности выбора выполняемой продукции из конфликтного множества.
В системах, основанных на правилах, часто акцент делается на системах прямого логического вывода. Например, в качестве правил и начальных фактов используется ряд примеров, что позволяет встроить систему с правилами в более крупную систему и задействовать ее для создания системы управления сенсорами, устойчивой к ошибкам [37].
1.2.4 Нечеткая логика
Ту роль, которую в классической теории множеств играет двузначная булева логика, в теории нечетких множеств играет многозначная нечеткая логика, в которой предположения о принадлежности объекта множеству, например Быстрый("Порш"), могут принимать действительные значения в интервале от 0 до 1. Возникает вопрос, а как, используя концепцию неопределенности, вычислить значение истинности сложного выражения, такого как Не(Быстрый("Шевроле")).
По аналогии с теорией вероятности, если F представляет собой нечеткий предикат, операция отрицания реализуется по формуле Не(F)=1–F.
Но аналоги операций конъюнкции и дизъюнкции в нечеткой логике не имеют никакой связи с теорией вероятностей [38]. Рассмотрим следующее выражение: ""Порш" является быстрым, представительским автомобилем".
В классической логике предположение (Быстрый("Порш")) И (Представительский ("Порш")) является истинным в том и только в том случае, если истинны оба члена конъюнкции. В нечеткой логике существует соглашение: если F и G являются нечеткими предикатами, то f(FÙG)(X)=min(fF(X), fG(X)).
Таким образом, если Быстрый("Порш")=0,9 и Представительский("Порш")=0,7, то (Быстрый("Порш"))И(Представительский ("Порш")) = 0,7.
А теперь рассмотрим выражение (Быстрый("Порш")) И Не(Быстрый("Порш")). Вероятность истинности этого утверждения равна 0, но в нечеткой логике значение этого выражения будет равно 0,1. Какой смысл имеет это значение? Его можно считать показателем принадлежности автомобиля к нечеткому множеству среднескоростных автомобилей, которые в чем-то близки к быстрым, а в чем-то – к медленным.