Главная страница Задание на ТИИД Текущая работа
Ссылки по тематике работы Сайты студентов ГИП-99 Написать письмо

1. Содержание

  1. Содержание
  2. Генетические алгоритмы
    1. Введение
    2. Операторы ГА
      1. Селекция
        1. Метод рулетки
        2. Турнирный отбор
      2. Скрещивание
      3. Мутация
    3. Алгоритм работы ГА
    4. Область применения
  3. Основы генетического программирования

    2. Генетические алгоритмы

    2.1. Введение

    Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационные методы, впервые предложенные Холландом в 1975 году. Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином.

    "Особи" - популяции, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах.

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

    Компоненты ГА:

    1. Хромосома - решение рассматриваемой проблемы. Состоит из генов
    2. Начальная популяция хромосом
    3. Набор операторов для генерации новых решений из предыдущей популяции
    4. Целевая функция для оценки приспособленности решений

    Для применения ГА к задаче, необходимо выбрать метод кодирования решений. Используется двоичный код и рефлексивный код Грея.

    2.2. Операторы ГА

    2.2.1. Селекция

    Оператор селекции осуществляет отбор хромосом в соответствии со значениями их функции приспособленности. Существуют два типа оператора селекции: рулетка и турнир.

    2.2.1.1. Метод рулетки

    Отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине , вычисляемой по формуле:

    При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью.

    2.2.1.2. Турнирный отбор

    Реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k = 2.

    2.2.2. Скрещивание

    Оператор скрещивания осуществляет обмен частями хромосом между двумя (может быть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным. Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l - 1 точек разрыва. Точка разрыва - участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

    2.2.3. Мутация

    Стохастическое изменение части хромосом. Каждый ген строки, которая подвергается мутации, с некоторой вероятностью (обычно очень маленькой) меняется на другой ген.

    2.3. Алгоритм работы ГА

    2.4. Область применения

    Генетические алгоритмы использовались при создании других вычислительных структур, например, автоматов или сетей сортировки. Использовались при проектировании нейронных сетей или управлении роботами. Они применялись при моделировании развития в различных предметных областях, включая биологические (экология, иммунология и популяционная генетика), социальный (экономика и политические системы) и когнитивные системы.

    Наиболее популярное приложение генетических алгоритмов - оптимизация многопараметрических функций.

    Не во всех случаях ГА работаю эффективно. Как узнать, является ли ГА хорошим методом для решения конкретной задачи? Не существует строгого ответа. По данным экспертов - если пространство поиска, которое предстоит исследовать, - большое, и предполагается, что оно не совершенно гладкое и унимодальное (т.е. содержит один гладкий экстремум) или не очень понятно, или если функция приспособленности с шумами, или если задача не требует строго нахождения глобального оптимума - т.е. если достаточно быстро просто найти приемлемое "хорошее".

    Если же пространство поиска небольшое, то решение может быть найдено методом полного перебора, и можно быть уверенным, что наилучшее возможное решение найдено, тогда как ГА мог с большей вероятностью сойтись к локальному оптимуму, а не к глобально лучшему решению.

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

    3. Основы генетического программирования

    Идею генетического программирования (ГП) - впервые предложил Коза в 1992 году, опираясь на концепцию ГА. В отличие от ГА в ГП все операции производятся не над строками, а над деревьями. При этом используются такие же операторы, как и в ГА: селекция, скрещивание и мутация.

    В ГП хромосомами являются программы. Программы представлены как деревья с функциональными (промежуточные) и терминальными (конечные) элементами. Терминальными элементами являются константы, действия и функции без аргументов, функциональными - функции, использующие аргументы.

    Пример - функция 2+x*4/7, представленную на рисунке. Терминальные элементы T = {2,x,4,7}, функциональные F = {+,*,/}.

    Для того чтобы применить ГП к какой-либо проблеме, необходимо определить:

    1. Множество терминальных элементов
    2. Множество функциональных элементов
    3. Меру приспособленности
    4. Параметры, контролирующие эволюцию
    5. Критерий останова эволюции
    Главная страница Задание на ТИИД Текущая работа
    Ссылки по тематике работы Сайты студентов ГИП-99 Написать письмо
    Сайт создан в системе uCoz