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

 

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

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

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

Данные алгоритмы адаптивны, они развивают решения и развиваются сами. Особенность этих алгоритмов - их успешное использование при решении сложных проблем.

Пример. Рассмотрим задачу безусловной целочисленной оптимизации (размещения): найти максимум функции f(i), i - набор из n нулей и единиц, например, при n = 5, i = (1, 0, 0, 1, 0). Это очень сложная комбинаторная задача для обычных, "негенетических" алгоритмов. Генетический алгоритм может быть построен на основе следующей укрупненной процедуры:

1. Генерируем начальную популяцию (набор допустимых решений задачи) - I0 = (i1, i2, :, in), ij {0,1} и определяем некоторый критерий достижения "хорошего" решения, критерий остановки , процедуру СЕЛЕКЦИЯ, процедуру СКРЕЩИВАНИЕ, процедуру МУТАЦИЯ и процедуру обновления популяции ОБНОВИТЬ;

2. k = 0, f0 = max{f(i), i I0};

3. выполнять пока не( ) :

· с помощью вероятностного оператора (селекции) выбираем два допустимых решения (родителей) i1, i2 из выбранной популяции (вызов процедуры СЕЛЕКЦИЯ);

· по этим родителям строим новое решение (вызов процедуры СКРЕЩИВАНИЕ) и получаем новое решение i;

· модифицируем это решение (вызов процедуры МУТАЦИЯ);

· если f0 < f(i) то f0 = f(i);

· обновляем популяцию (вызов процедуры ОБНОВИТЬ);

· k = k + 1

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

Процедура СЕЛЕКЦИЯ может из случайных элементов популяции выбирать элемент с наибольшим значением f(i).

Процедура СКРЕЩИВАНИЕ (кроссовер) может по векторам i1, i2 строить вектор i, присваивая с вероятностью 0.5 соответствующую координату каждого из этих векторов - родителей. Это самая простая процедура. Используют и более сложные процедуры, реализующие более полные аналоги генетических механизмов.

Процедура МУТАЦИЯ также может быть простой или сложной. Например, простая процедура с задаваемой вероятностью для каждого вектора меняет его координаты на противоположные (0 на 1, и наоборот).

Процедура ОБНОВИТЬ заключается в обновлении всех элементов популяции в соответствии с указанными процедурами.

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

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

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

 








Дата добавления: 2016-06-24; просмотров: 437;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.