Понятия и определения теории генетических алгоритмов

. случайное равновероятное удаление хромосом;

. удаление N1 хромосом, имеющих худшее значение ЦФ;

. удаление хромосом на основе обратно пропорционального значения ЦФ;

. удаление хромосом на основе заданной турнирной стратегии.

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

Выделяют три особенности алгоритма эволюции:

. каждая новая популяция состоит только из «жизнеспособных» хромосом;

. каждая новая популяция «лучше» (в смысле ЦФ) предыдущей;

. в процессе эволюции последующая популяция зависит только от предыдущей.

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

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

При решении практических задач с использованием ЭМ, необходимо выполнить следующие четыре предварительных этапа:

1. выбрать способ представления решения;

2. разработать операторы случайных изменений;

. определить законы выживания решения;

. создать начальную популяцию.

Рассмотрим некоторые особенности выполнения этих этапов.

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

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

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