Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

MUTATION OPERATOR CHOICE IN EVOLUTIONARY ALGORITHMS

Khabituev B.V. 1 Khaptakhaeva N.B. 2 Sorokovikov P.S. 1 Kononova O.V. 1 Lidzheev A.V. 1
1 Buryat State University
2 East-Siberian State University of Technologies and Management
Nowadays stochastic global optimization methods are often used to solve optimization problems, in particular, various species of evolutionary algorithms. A feature of this approach is a large number of adjustable parameters, which choice can significantly affect the efficiency of finding the minimum. One of the major search engines, provide a study of the search space, wherein a mutation operator. This paper deals with the comparative analysis of the two approaches to the implementation of the mutation operator: the search in a small neighborhood of the current point and uniform redistribution across the search space (one coordinate and the whole point). These approaches are tested in the most general case of the search space – unconstrained optimization with parallelepiped limitations. The tests are considered as functions with different topography.
mutation operator
evolutionary algorithm
global optimization

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

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

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

Заключение

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

Рецензенты:

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

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