О сравнении эффективности двух различных методов самонастройки генетического алгоритма

Размещено на http://allbest.ru

Сибирский государственный аэрокосмический университет

имени академика М. Ф. Решетнёва

УДК 519.68

О сравнении эффективности двух различных методов самонастройки генетического алгоритма

Фисак А.В.

Научный руководитель:

проф. Семенкин Е.С.

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

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

В работах Гомеса и Банзафа представлены две схемы динамической самонастройки параметров генетического алгоритма.

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

В методе самонастройки Банзафа, напротив, вероятности не хранятся внутри индивидов и настраиваются на уровне популяции, то есть сразу для всех хромосом.

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

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

- создана программная система, реализующая генетический алгоритм для решения задач условной оптимизации с двумя методами самонастройки операторов;

- исследована эффективность методов в отдельности на наборе тестовых задач условной оптимизации;

- проведено сравнение рассматриваемых подходов с использованием непараметрического критерия Вилкоксона, применяемого при необходимости определить существенно ли различаются средние значения несвязных выборок на уровне значимости б;

- на основе полученных результатов исследования сделаны выводы о целесообразности использования реализованных методов самонастройки.

В программе реализованы три вида селекции: пропорциональная, ранговая, турнирная; три вида скрещивания: одноточечное, двухточечное, равномерное; три вида мутации: слабая, средняя, сильная.

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

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

Так как у нас нет какой-либо априорной информации о том, какой оператор предпочтительнее, то начальные значения вероятностей будут равны между собой.

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

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

Непосредственно применяем выбранные операторы, получаем потомков, случайно выбираем одного из них.

Сравниваем его пригодность с пригодность индивида, которого мы рассматриваем на текущем шаге, если она больше, то перемещаем найденного потомка в следующее поколение, если меньше, то перемещаем исходного индивида.

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

иначе по этим:

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

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

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

При этом вероятности хранятся в отдельном массиве, а не внутри хромосом, и одновременно изменяются для популяции в целом. Они адаптируются на основе информации успешного и не успешного применения операторов по формуле:

где , а , - число, показывающее сколько раз был применен оператор, - количество раз, когда оператор привел к успеху, то есть пригодность потомка оказалась лучше средней пригодности родительских индивидов; , - число операторов.

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

Ниже в таблицы представлена часть результатов полученных в ходе исследования:

Здесь ДШ - динамические штрафы, СШ - смертельные штрафы и ГСЭА - гибридный самонастраивающийся эволюционный алгоритм.

Во втором и третьем столбике число до черты - это усредненная надежность алгоритма по 27 запускам программы, в данном случае каждый запуск программы - это 50 независимых запусков ГА с разными комбинациями операторов селекции, скрещивания и мутации.

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

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

Число индивидов и поколений для первых 7 задач равно 100 и 100 соответственно. Для 8 задачи 75 и 75. Для 9 эти числа также одинаковые и равны 50.

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

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

Размещено на Allbest.ru