Контрольная работа: Интеллектуальные информационные технологии и системы: генетические алгоритмы
Помимо кроссинговера для решения различных прикладных задач полезными являются такие генетические операции, как мутация, инверсия, транслокация, селекция (инбридинг и гибридизация),генная инженерия.
Под мутацией понимается генетическое изменение, приводящее к качественно новому проявлению основных свойств генетического материала: дискретности, непрерывности или линейности. Свойство дискретности позволяет выделить в исходном генетическом материале отдельные фрагменты, контролирующие те или иные функции. Непрерывность означает, что определённые комбинации генов совместно контролируют некоторую функцию. Линейность проявляется в определённой последовательности генов в пределах группы сцепления.
Процессы мутации ведут к получению более разнообразного генетического материала. В связи с этим применение операции мутации в генетических алгоритмах направлено на получение решений, которые не могут быть улучшены качественно посредством кроссинговера.
Инверсия, транцлокация, транспозиция, делеция и дупликация относятся к разновидностям хромосомной мутации. При инверсии участок хромосомы поворачивается на 1800 . транслокацией называют перенос части одной хромосомы в другую. При перемещении небольших участков генетического материала в пределах одной хромосомы используют термин транспозиция. Делеция – это выпадение отдельных участков хромосом, дупликация – повторение участка генетического материала. Кроме перечисленных, существуют другие разновидности хромосомных мутаций.
Селекция представляет собой форму искусственного отбора, который может быть массовым или индивидуальным. Установлено, что массовый отбор по фенотипу (совокупности всех внешних и внутренних признаков) менее эффективен, чем индивидуальный, когда популяцию делят на отдельные линии, а для размножения выбирают носителей желаемых свойств. Применение процедуры селекции в генетических алгоритмах оптимизации способствует ускорению процесса синтеза искомого решения.
Генная инженерия представляет собой совокупность методов для получения рекомбинантной ДНК и операции над нею. Рекомбинантная ДНК получается путём объединения фрагментов ДНК различных организмов. Использование подходов генной инженерии позволяет в ряде задач значительно быстрее находить желаемое решение.
Механизм эволюции основан на трёх повторяющихся процессах: отборе, амплификации (процесс производства потомков) и мутации. Он используется в качестве механизма случайно направленного комбинаторного перебора при решении задач оптимизации и слабоструктурированных проблем принятия решений.
Генетический алгоритм – это поисковый алгоритм, основанный на природных механизмах селекции и генетики. Эти алгоритмы обеспечивают выживание сильнейших решений из множества сгенерированных, формируя и изменяя процесс поиска на основе моделирования эволюции исходной популяции решений. Генетические алгоритмы сконструированы таким образом, что при генерации каждой новой популяции используются фрагменты исходных решений, к которым добавляются новые элементы , обеспечивающие улучшение решений относительно сформулированного критерия отбора. Другими словами, генетические алгоритмы используют информацию, накопленную в процессе эволюции.
В генетических алгоритмах используются специфические термины, взятые из генетики, которые трактуются следующим образом.
| Генетика | Генетические алгоритмы |
| хромосома | Решение, стринг, строка, последовательность, родитель, потомок |
| популяции | Набор решений (хромосом) |
| локус | Местоположение гена в хромосоме |
| поколение | Цикл работы генетического алгоритма, в процессе которого сгенерировано множество решений. |
| аллель | Значение элемента, характеристики |
| фенотип | Структура |
| эпистасис | Множество параметров, альтернативные решения |
| Скрещивание, рекомбинация, кроссинговер | Оператор рекомбинации |
| мутация | Оператор модификации |
При разработке генетических алгоритмов преследуется две главные цели:
· Абстрактное и формальное объяснение процессов адаптации в естественных системах;
· Проектирование искусственных программных систем, воспроизводящих механизмы функционирования естественных систем.
Основные отличия ГА от других алгоритмов оптимизации:
· Используются не параметры, а закодированная множества параметров;
· Поиск осуществляется не из единственной точки, а из популяции точек;
· В процессе поиска используются значения целевой функции, а не её приращения;
· Применяются вероятные, а не детерминированные правила поиска и генерации решений;
· Выполняется одновременный анализ различных областей пространства решений, в связи с чем возможно нахождение новых областей с лучшими значениями целевой функции за счёт объединения квазиоптимальных решений из разных популяций.
2. Простой генетический алгоритм
Согласно репродуктивному плану Холланда генетические схемы поиска оптимальных решений включают следующие этапы процесса эволюции:
1. конструируется начальная популяция. Вводится начальная точка отсчёта поколений t = 0. вычисляются приспособленность хромосом популяции (целевая функция) и средняя приспособленность всей популяции.
2. устанавливается значение t = t+1. выбираются два родителя (хромосомы) для кроссинговера. Выбор осуществляется случайным образом пропорционально жизнеспособности хромосом, которая характеризуется значениями целевой функции.
3. формируется генотип потомка. Для этого с заданной вероятностью над генотипами выбранных хромосом производится операция кроссинговера. Случайным образом выбирается один из потомков А(t), который сохраняется как член новой популяции. Далее к потомку А(t) последовательно с заданными вероятностями применяются операторы инверсии и мутации. Полученный в результате генотип потомка сохраняется как А(t).
4. обновление текущей популяции путём замены случайно выбранной хромосомы на А(t)/
5. определение приспособленности А (t) и пересчёт средней приспособленности популяции.
6. если t=t, где t – заданное число шагов, то переход к этапу 7, в противном случае – переход к этапу 2.
7. конец работы.
Основная идея эволюции, заложенная в различные конструкции генетических алгоритмов, проявляется в способности "лучших" хромосом оказывать большее влияние на состав новой популяции за счёт длительного выживания и более многочисленного потомства.
Простой генетический алгоритм включает операцию случайной генерации начальной популяции хромосом и ряд операторов, обеспечивающих генерацию новых популяций на основе начальной. Этими операторами являются репродукция, кроссинговер и мутация.