Генетические алгоритмы в изобретательских задачах
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
популяции. Каждый элемент этой популяции Рi,как правило, представляет собой одну или несколько хромосом, или особей, или индивидуальностей (альтернативных упорядоченных или неупорядоченных решений). Хромосомы состоят из генов (элементы, части закодированного решения), и позиции генов в хромосоме называются лоци или локус для одной позиции, т. е. ген - под-элемент (элемент в хромосоме), локус - позиция в хромосоме, аллель - значение гена.
Гены могут иметь числовые или функциональные значения. Обычно эти числовые значения берутся из некоторого алфавита. Генетический материал элементов обычно кодируется на основе двоичного алфавита {0,1},хотя можно использовать буквенные, а также десятичные и другие алфавиты. Примером закодированной хромосомы длины семь на основе двоичного алфавита может служить хромосома рi = (0001101).Элементы в ГА часто называют родителями. Родители выбираются из популяции на основе заданных правил, а затем смешиваются (скрещиваются) для производства детей (потомков). Дети и родители создают новую популяцию. Генерация, т. е. процесс реализации одной итерации алгоритма, называется поколением.
Эволюция популяции согласно - это чередование поколений, в которых хромосомы изменяют свои значения так, чтобы каждое новое поколение наилучшим способом приспосабливалось к внешней среде. В интеллектуальной ИС общая генетическая упаковка называется генотипом. В ЕС организм формируется посредством связи генетической упаковки с окружающей средой и называется фенотипом.
Каждый элемент в популяции имеет определенный уровень качества, который характеризуется значением ЦФ (в литературе иногда называется функция полезности или пригодности - fitness). ЦФ используется в ГА для сравнения решений между собой и выбора из них лучших. Основная задача генетических алгоритмов состоит в оптимизации целевой функции. Другими словами, ГА анализирует популяцию хромосом, представляющих комбинацию элементов из некоторого множества, и оптимизирует ЦФ, оценивая каждую хромосому. Генетические алгоритмы манипулируют популяцией хромосом на основе механизма натуральной эволюции.
Каждая популяция обладает наследственной изменчивостью. Это означает, что имеет место случайное отклонение от наиболее вероятного среднего значения ЦФ. Отклонение описывается нормальным законом распределения случайных величин, но, в отличие от ЕС, наследственная изменчивость не затухает, как всякая флуктуация. При этом наследственные признаки закрепляются, если они имеют приспособительный характер, т. е. обеспечивают популяции лучшие условия существования и размножения.
Так же как процесс эволюции начинается с начальной популяции, так и алгоритм начинает свою работу с создания начального множества конкурирующих между собой решений оптимизационной задачи. Затем эти родительские решения создают потомков путем случайных и направленных изменений. После этого оценивается эффективность решений, и они подвергаются селекции. Как и в ЕС, здесь действует принцип выживания сильнейших, наименее приспособленные решения погибают, а затем процесс повторяется вновь.
ГА в зависимости от размера популяции разделяют на:
.стационарного состояния;
.поколенческие.
В стационарных ГА размер популяции является входным постоянным параметром, задаваемым ЛПР. В поколенческих ГА разрешается увеличивать или уменьшать размер популяции в каждой последующей генерации. Следует отметить, что речь в основном идет о появлении Np + N1 потомков (N1>> 1), прежде чем начинает реализовываться оператор отбора, устраняющий N1хромосом с меньшей ЦФ. Вопросы удаления лишних хромосом, как в стационарных, так и в поколенческих ГА, основаны на нескольких эвристиках:
.случайное равновероятное удаление хромосом;
.удаление N1 хромосом, имеющих худшее значение ЦФ;
.удаление хромосом на основе обратно пропорционального значения ЦФ;
.удаление хромосом на основе заданной турнирной стратегии.
Можно предложить еще ряд эвристик удаления, но удаление худших хромосом может привести к преждевременной утрате разнообразия и, следовательно, к попаданию ЦФ в локальный оптимум. Оставление в популяции большого числа хромосом с плохой ЦФ приведет к слепому поиску.
Выделяют три особенности алгоритма эволюции:
.каждая новая популяция состоит только из жизнеспособных хромосом;
.каждая новая популяция лучше (в смысле ЦФ) предыдущей;
.в процессе эволюции последующая популяция зависит только от предыдущей.
Традиционные оптимизационные алгоритмы для нахождения лучшего решения используют большое количество допущений при оценке ЦФ. Эволюционный же подход не требует таких допущений. Это расширяет класс задач, которые можно решать с помощью эволюционного моделирования. Согласно существующим исследованиям можно сказать, что эволюционные методы иГА позволяют решать те проблемы, решение которых традиционными оптимизационными алгоритмами затруднительно.
ГА дает ряд преимуществ при решении практических задач. Одно из таких преимуществ - это адаптация к изменяющейся окружающей среде. В реальной жизни проблема, которая была поставлена для решения изначально, может претерпеть огромные изменения в процессе своего решения. При использовании традиционных методов все вычисления приходится начинать заново, что приводит к большим затратам машинного времени. При эволюционном подходе популяцией служит БЗ, которую можно анализирова?/p>