Задачи искусственного интеллекта 7 Тест по теме «История развития искусственного интеллекта» 9 (стр. 12 из 24)
4) если не выполняется условие прекращения селекции (наступление вырождения), переход на п. 1, иначе лучший классификатор объявляется искомым решением задачи идентификации;
· эволюционное (генетическое) программирование (данные, которые закодированы в генотипе, могут представлять собой команды какой-либо виртуальной машины, в простейшем случае ничего не меняется в генетическом алгоритме, но тогда длина получаемой последовательности действий (программы) получается не отличающейся от начальных, современные алгоритмы генетического программирования распространяют генетические алгоритмы для систем с переменной длиной генотипа);
· генетические алгоритмы.
Генетические алгоритмы
«Отцом» генетических алгоритмов по праву считается Д. Холланд, метод вначале назывался репродуктивным планом Холланда. В дальнейшем генетические алгоритмы развивались в работах учеников Холланда: Д. Голдберга . и К. Де Йонга, - именно в них и закрепилось название метода.
Генетические алгоритмы – это раздел эволюционного моделирования, заимствующий методические приемы из теоретических положений генетики.
Генетические алгоритмы – адаптивные методы поиска, которые используются для решения задач функциональной оптимизации. Представляют собой своего рода модели машинного исследования поискового пространства, построенное на эволюционной метафоре. Характерные особенности: использование строк фиксированной длины для представления генетической информации, работа с популяцией строк, использование генетических операторов для формирования будущих поколений.
Генетические алгоритмы оперируют совокупностью особей (популяцией), которые представляют собой строки, кодирующие одно из решений задачи. Этим метод отличается от большинства других алгоритмов оптимизации, которые оперируют лишь с одним решением, улучшая его.
Генетические алгоритмы применяются для решения следующих задач:
· оптимизация функций;
· разнообразные задачи на графах (задача коммивояжера, раскраска и т.д.);
· настройка и обучение искусственной нейронной сети;
· задачи компоновки;
· составление расписаний;
· игровые стратегии;
· аппроксимация функций;
· искусственная жизнь;
· биоинформатика.
Преимущества генетических алгоритмов:
1) универсальность;
2) высокая обзорность поиска;
3) нет ограничений на целевую функцию;
4) любой способ задания функции.
Недостатки генетических алгоритмов:
1) относительно высокая вычислительная стоимость;
2) квазиоптимальность.
Когда надо использовать генетический алгоритм: много параметров, плохая целевая функция, комбинаторные задачи.
Когда не надо использовать генетический алгоритм: задача хорошо решается традиционными методами, требуется высокая точность решения.
Схема функционирования генетического алгоритма
Из биологии известно, что любой организм может быть представлен своим фенотипом, который фактически определяет, чем является объект в реальном мире, и генотипом, который содержит всю информацию об объекте на уровне хромосомного набора. При этом каждый ген, то есть элемент информации генотипа, имеет свое отражение в фенотипе. Таким образом, для решения задач необходимо представить каждый признак объекта в форме, подходящей для использования в генетическом алгоритме. Все дальнейшее функционирование механизмов генетического алгоритма производится на уровне генотипа, позволяя обойтись без информации о внутренней структуре объекта, что и обуславливает его широкое применение в самых разных задачах.
В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака. Для кодирования ген в бинарной реализации генетического алгоритма часто используют код Грея (см. пример в таб.3).
Таблица 3. Пример фенотипа
| Признак | Двоичное значение признака | Десятичное значение признака |
| Признак 1 | 0011 | 3 |
| Признак 2 | 1100 | 12 |
| Признак 3 | 1110 | 14 |
| Признак 4 | 0111 | 7 |
| Признак 5 | 1001 | 9 |
После определения фенотипа генетический алгоритм функционирует по следующей схеме действий (рис. 15).
Рис. 15Схема функционирования генетического алгоритма
1. Формирование начальной популяции.
2. Оценка особей популяции.
3. Отбор (селекция).
4. Скрещивание.
5. Мутация.
6. Формирование новой популяции.
7. Если популяция не сошлась, то 2, иначе – останов (прекращение функционирования генетического алгоритма).
Формирование начальной популяции
Стандартный генетический алгоритм начинает свою работу с формирования начальной популяции — конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью простых приближенных алгоритмов. Выбор начальной популяции не имеет значения для сходимости процесса, однако формирование "хорошей" начальной популяции (например, из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума. Если отсутствуют предположения о местоположении глобального оптимума, то индивиды из начальной популяции желательно распределить равномерно по всему пространству поиска решения.
Популяция инициируется в начальный момент времени t=0 и состоит из k особей, каждая из которых представляет возможное решение рассматриваемой проблемы. Особь представляет собой одну или несколько хромосом (обычно одну). Хромосома состоит из ген, - т.е. это битовая строка (хромосомы не ограничены бинарным представлением, есть реализации генетического алгоритма, построенные на векторах вещественных чисел). Гены располагаются в различных позициях хромосомы, и принимают значения, называемые аллелями.
Оценка особей популяции
Для решения задачи с помощью генетического алгоритма необходимо задать меру качества для каждого индивида в пространстве поиска. Для этой цели используется функция приспособленности (fitness function). Функция приспособленности должна принимать неотрицательные значения на ограниченной области определения, при этом совершенно не требуются непрерывность и дифференцируемость, значение этой функции определяет, насколько хорошо подходит особь для решения задачи.
В задачах максимизации целевая функция часто сама выступает в качестве функции приспособленности, для задач минимизации целевую функцию следует инвертировать. Если решаемая задача имеет ограничения, выполнение которых невозможно контролировать алгоритмически, то функция приспособленности, как правило, включает также штрафы за невыполнение ограничений (они уменьшают ее значение).
Отбор (селекция)
На каждом шаге эволюции с помощью вероятностного оператора селекции (отбора) выбираются два решения-родителя для их последующего скрещивания. Среди операторов селекции наиболее распространенными являются два вероятностных оператора пропорциональной и турнирной селекции. В некоторых случаях также применяется отбор усечением.
Пропорциональный отбор (Proportional selection)
Каждой особи назначает вероятность Ps(i), равную отношению ее приспособленности к суммарной приспособленности популяции. Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i).
Простейший пропорциональный отбор - рулетка - отбирает особей с помощью n «запусков» рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью.
Турнирный отбор
Турнирный отбор реализуется следующим образом: из популяции, содержащей m особей, выбирается случайным образом t особей и наиболее приспособленная особь записывается в промежуточный массив (между выбранными особями проводится турнир). Эта операция повторяется m раз. Строки в полученном промежуточном массиве затем используются для скрещивания (случайным образом). Размер группы строк, отбираемых для турнира, часто равен 2. В этом случае говорят о двоичном/парном турнире.
Отбор усечением
Данная стратегия использует отсортированную по убыванию популяцию. Число особей для скрещивания выбирается в соответствии с порогом TÎ[0;1]. Порог определяет, какая доля особей, начиная с самой первой (самой приспособленной), будет принимать участие в отборе. В принципе, порог можно задать и равным 1, тогда все особи текущей популяции будут допущены к отбору. Среди особей, допущенных к скрещиванию случайным образом m/2 раз, выбираются родительские пары, потомки которых образуют новую популяцию.
Ранговый отбор
Этот вид отбор подразумевает следующее: для каждой особи ее вероятность попасть в промежуточную популяцию пропорциональна ее порядковому номеру в отсортированной по возрастанию приспособленности популяции. Такой вид отбора не зависит от средней приспособленности популяции.
Элитный отбор
Элитные методы отбора гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции. Наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла, как другие, через процесс отбора, кроссовера и мутации. Элитизм может быть внедрен практически в любой стандартный метод отбора. Использование элитизма позволяет не потерять хорошее промежуточное решение, но в то же время из-за этого алгоритм может "застрять" в локальном экстремуме. В большинстве случаев элитизм не вредит поиску решения, и главное - это предоставить алгоритму возможность анализировать разные хромосомы из пространства поиска.