Стр. 62 - СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА И ПРИНЯТИЯ РЕШЕНИЙ
Упрощенная HTML-версия
[
Введите текст]
60
СИСТЕМЫИСКУССТВЕННОГО ИНТЕЛЛЕКТА И ПРИНЯТИЯ РЕШЕНИЙ.
ОПТИМИЗАЦИЯ БАЗ ЗНАНИЙ НЕЧЕТКИХ ЭКСПЕРТНЫХ СИСТЕМ
туально для решаемой задачи, так как определение неприспособленности каж-
дой особи требует вычисления сложной функции ошибки по большому числу
примеров из обучающей выборки. При этом потенциальная проблема проявле-
ния "застоя" в эволюции, т.е. сохранения набора генотипов практически неиз-
менным, решается за счет "щадящего" рангового вероятностного обора и более
высокой интенсивности мутации, чем в классическом ГА.
Теперь рассмотрим принципиальные отличия двух типов скрещивания,
примененных в разработанном ГА, и особенности их действия при решении за-
дачи параметрической оптимизации нечеткой сети логического вывода. Во мно-
гих источниках
отмечают, что двухточечное скрещивание в большинстве
случаев применения классического ГА является более эффективным, чем одно-
точечное. Теоретическое обоснование данного утверждения базируется на рас-
смотрении так называемых схем (scheme).
Схема – множество хромосом, содержащих одинаковые двоичные значения
в определенных позициях генотипа, т.е. обладающих некоторыми общими свой-
ствами. При рассмотрении схем используется расширенный алфавит {0, 1, *},
здесь символ * в конкретной позиции означает, что допустимо любое значение –
0
или 1. Например, схеме [0*10] соответствуют две возможные хромосомы:
[0010]
и [0110].
Схема
S
характеризуется порядком
o(S)
и охватом
d(S)
.
Порядок схемы – это
количество постоянных позиций в схеме (содержащих 0 или 1). Для схемы из
предыдущего примера
o(S)
= 3. Охват схемы – расстояние между первым и по-
следним постоянным символом. Для предыдущего примера
.
Для классического ГА Дж. Холландом была сформулирована теорема о
схемах
:
схемы малого порядка, с малым охватом и с приспособленностью
выше среднего формируют показательно возрастающее количество своих пред-
ставителей в последующих поколениях генетического алгоритма
.
На ее основе
была выдвинута гипотеза о строительных блоках
:
генетический алго-
ритм стремится достичь близкого к оптимальному решения за счет комбини-
рования хороших схем (с приспособленностью выше средней) малого порядка и
малого охвата
.
Однако применение модифицированных генетических операто-
ров позволяет изменить описанную тенденцию. Например, равномерное скрещи-
вание (когда выбор предка из родительской пары для передачи значения в каж-
дой позиции хромосомы производится случайно и независимо) одинаково влияет
на выживание схем с разным охватом, а определяющим остается только порядок
схемы. Поэтому на многих сложных задачах лучшие результаты показывает ГА
с равномерным скрещиванием.
Возвращаясь к сравнению одноточечного скрещивания с двухточечным,
отметим, что одноточечное скрещивание чаще приводит к разрушению схем с
большим охватом. Например, схема [0****0] при скрещивании пары, в которой
одна из родительских хромосом принадлежит данной схеме, а другая – схеме
314 )(
=−=
Sd
