Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,791

ВЫБОР ОПЕРАТОРА МУТАЦИИ В ЭВОЛЮЦИОННЫХ АЛГОРИТМАХ

Хабитуев Б.В. 1 Хаптахаева Н.Б. 2 Сороковиков П.С. 1 Кононова О.В. 1 Лиджеев А.В. 1
1 ФГБОУ ВПО Бурятский государственный университет
2 ФГБОУ ВПО Восточно-Сибирский государственный университет технологий и управления
В настоящее время для решения задач оптимизации часто применяют стохастические методы глобальной оптимизации и, в частности, различные разновидности эволюционных алгоритмов. Особенностью данного подхода является большое число настраиваемых параметров, выбор того или иного набора которых может значительно повлиять на эффективность поиска минимума. Одним из основных поисковых механизмов, обеспечивающих исследование пространства поиска, является при этом оператор мутации. В данной статье производится сравнительный анализ двух подходов к реализации оператора мутации: поиск в небольшой окрестности текущей точки и равномерное перераспределение по всему пространству поиска (одной координаты и всей точки). Данные подходы протестированы на наиболее общем случае пространства поиска – задаче безусловной оптимизации с параллелепипедными ограничениями. При этом в качестве тестовых рассматриваются функции с различным рельефом.
оператор мутации
эволюционный алгоритм
глобальная оптимизация
1. Панченко, Т.В. Генетические алгоритмы : учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. – Астрахань : Издательский дом «Астраханский университет», 2007. – 87 с.
2. Mitchell M. An Introduction to Genetic Algorithms. Cambridge: MIT Press, 1999. – 158 p.
3. Еремеев, А. В. Генетические алгоритмы и оптимизация : учебное пособие – Омск : Изд-во Ом. гос. ун-та, 2008. – 48 с.
4. Емельянов, В.В. Теория и практика эволюционного моделирования / В. В. Емельянов, В. В. Курейчик. – М. : ФИЗМАТЛИТ, 2003. – 432 с.
5. Whitley D. A genetic algorithm tutorial. Statistics and Computing, 1994, №4, P.65-85.
6. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. – Reading: Addison Wesley, 1989.

Рассматривается наиболее общая задача безусловной оптимизации с параллелепипедными ограничениями (1)-(2):

(1)

(2)

В качестве тестовых функций в работе рассматривается небольшой набор функций с различными экстремальными характеристиками (табл.1)

Таблица 1

Набор тестовых функций

Название

 

Функция

Ограничения

Характеристики

1

Sphere

(-5,12; 5,12)

одноэкстремальная, простая

2

Rosenbrock

(-2,048; 2,048)

одноэкстремальная, обширное медленно убывающее «плато»

3

Rastrigin

(-5,12; 5,12)

многоэкстремальная, сложная

4

Schwefel

(-500; 500)

многоэкстремальная, сложная

5

Griewank

(-600; 600)

многоэкстремальная, простая, небольшие локальные минимумы

6

Ackley

(-30; 30)

многоэкстремальная, сложная

Поведение этих функций при представлено в виде карт линий уровня на рис. 1.

Рис. 1. Карты линий уровня тестовых функций ()

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

1. Параметры эволюционного алгоритма

Стохастические методы глобальной оптимизации можно условно разделить на одноточечные и многоточечные (популяционные) методы. Популяционные методы в отличие от одноточечных оперируют множеством точек (популяцией). Частными случаями популяционных методов являются эволюционные алгоритмы, которые моделируют естественный отбор [1; 3]. Общая схема эволюционных алгоритмов показана на рис. 2.

Рис. 2. Общая схема эволюционного алгоритма

В работе используется достаточно стандартный набор параметров алгоритма. В качестве оператора селекции выбран турнирный отбор [1; 5], оператора скрещивания – многоточечный кроссовер с точками разрыва [1; 2]. В новую популяцию отбирается наиболее приспособленных особей из родителей и их потомков, где – размер популяции. Конкретные значения параметров представлены в табл.2.

Таблица 2

Набор параметров эволюционного алгоритма

Параметр

Значение

Комментарий

Размер популяции, p

10

Размер популяции постоянен.

Размер турнира

3

 

Число точек разрыва, k

3

Точки разрыва выбираются случайным образом.

Число родителей

5

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

Число потомков

5

Вероятность мутации

0,9

Мутация с указанной вероятностью применяется только к потомкам.

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

Таблица 3

Рассматриваемые операторы мутации

Обозначение

Описание

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

, где – случайный выбор точки в шаре случайного радиуса с центром в точке , .

, – случайный выбор точки в шаре случайного радиуса с центром в точке , .

2. Вычислительные эксперименты

Для каждой функции из набора (табл.1) запуск алгоритма производится многократно с каждым из предложенных операторов мутации. Далее подсчитываются основные статистики по запускам: минимальное, максимальное и среднее значения, а также стандартное отклонение достигнутого в запуске минимума (табл.4). Число запусков для каждого оператора принято равным 100. Для обеспечения равных условий для операторов запуски производятся из одних и тех же случайно выбранных в области определения функции стартовых точек. В целях практического применения дальнейших результатов, размерность задач будем достаточно велика и равна 100.

Таблица 4

Результаты вычислительных экспериментов

ЦФ

Оператор мутации

Мин.

Макс.

Ср.

Откл.

Sphere

6,97174

16,2056

10,71143

1,847116

26,4792

91,4995

49,01797

14,35962

1,00054

2,92091

1,760349

0,421124

Rosenbrock

507,839

998,887

717,2272

94,61012

226,28

762,596

470,2759

105,0812

190,9086

749,4405

442,535

106,0173

Rastrigin

154,342

228,234

192,9653

16,14206

596,606

975,477

738,9297

66,74251

651,564

1014,63

791,7729

67,33052

Schwefel

3917,42

6780,4

5243,746

607,2343

31650,9

38756,4

35095,86

1437,317

17126,38

29057,2

23423,26

2388,355

Griewank

23,2801

53,4758

36,9514

5,655961

1733,1

2644,06

2190,205

204,0956

4,243146

11,47681

6,497328

1,333431

Ackley

7,01081

9,30805

8,184293

0,460141

18,7743

19,3845

19,10561

0,127096

19,12104

19,98783

19,63224

0,158928

Усредненные по 100 запускам результаты отложены в виде графиков на рис.3. По оси абсцисс указано число этапов генетического алгоритма (число поколений), по оси ординат – средняя приспособленность популяции. За одно поколение целевая функция вызывается 15 раз. По оси ординат указано значение достигнутого минимума.

Рис. 3. Усредненные результаты запусков

На основе полученных результатов можно сделать следующие выводы:

1) на сложных многоэкстремальных функциях (Rastrigin, Schwefel и Ackley) оператор мутации показывает лучшие результаты;

2) на менее сложных функциях (Sphere, Rosenbrock и Griewank) операторы мутации и показывают похожие результаты, лучшие, чем у оператора .

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

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

Заключение

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

Рецензенты:

Ширапов Д.Ш., д.ф.-м.н., профессор, ФГБОУ ВПО Бурятский государственный университет, г. Улан-Удэ;

Дамбаев Ж.Г., д.т.н., профессор, ФГБОУ ВПО Бурятский государственный университет, г. Улан-Удэ.


Библиографическая ссылка

Хабитуев Б.В., Хаптахаева Н.Б., Сороковиков П.С., Кононова О.В., Лиджеев А.В. ВЫБОР ОПЕРАТОРА МУТАЦИИ В ЭВОЛЮЦИОННЫХ АЛГОРИТМАХ // Современные проблемы науки и образования. – 2014. – № 6.;
URL: http://science-education.ru/ru/article/view?id=15732 (дата обращения: 08.12.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074