Генетические алгоритмы
Идея генетических алгоритмов "подсмотрена" у систем живой природы, у систем, эволюция которых развертывается в сложных системах достаточно быстро.
Генетический алгоритм -это алгоритм, основанный на имитации генетических процедур развития популяции в соответствии с принципами эволюционной динамики.
Генетические алгоритмы используются для решения задач оптимизации (многокритериальной), для задач поиска и управления.
Данные алгоритмы адаптивны, они развивают решения и развиваются сами. Особенность этих алгоритмов - их успешное использование при решении сложных проблем.
Пример. Рассмотрим задачу безусловной целочисленной оптимизации (размещения): найти максимум функции 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;