IX Международная студенческая научная конференция Студенческий научный форум - 2017

Статья подготовлена в качестве курсовой работы в рамках курса «Machine Learning. Обучающиеся технические системы» (Научный руководитель к. т. н., доцент В. И. Воронов). В ней рассмотрено применение генетического алгоритма для решения задачи нахождения минимума функции Розенброка в среде разработки Matlab.

Применение генетических алгоритмов

Генетические алгоритмы впервые были опубликованы в 1975 году[1]. С этого времени генетические алгоритмы являются перспективным способом разрешения научных и технических проблем.

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

Генетические алгоритмы оптимизации применяются если:

• сложно или невозможно сформулировать задачу в виде, пригодном для аналогичных алгоритмов оптимизации;

• стоит задача оптимизации недифференцируемой функции;

• стоит задача глобальной оптимизации (процесс поиска экстремума) при наличии нескольких экстремумов.

Нахождение глобального минимума функции Розенброка является трудоёмкой задачей, и некоторые алгоритмы оптимизации не справляются с поставленной задачей (например, метод Хука-Дживса находит локальный минимум и останавливается на этом). Но если задача не требует строго нахождения глобального минимума, т.е. если достаточно найти приемлемое (удовлетворяющее заданной погрешности) решение–генетический алгоритм будет являться эффективной процедурой поиска, конкурируя с другими методами, которые не используют знания о пространстве поиска[2].

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

Принцип работы ГА можно описать по схеме, представленной на рис.1.

Рис.1 Блок-схема работы генетического алгоритма[3]

Рассмотрим подробнее основные этапы алгоритма[4]:

Начальная популяция

На начальной стадии выполнения генетического алгоритма случайным образом инициализируется определённая популяция хромосом. Каждая хромосома это случайная L-битная строка, где L — длина кодировки хромосомы. Каждая хромосома является одним из решений поставленной задачи.

Оператор кроссинговера является основным генетическим оператором, за счет которого производится обмен генетическим материалом между особями. Моделирует процесс скрещивания особей.

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

Рис.2 Оператор кроссинговера

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

Рис.3 Оператор мутации

Критерий окончания процесса

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

Для нахождения минимума функции Розенброка рассмотрим эту функцию.

Функция Розенброка — невыпуклая функция, используемая для оценки производительности алгоритмов оптимизации, предложенная Ховардом Розенброком в 1960 году[5]. Эта функция имеет крайне пологий изогнутый овраг, что сильно затрудняет поиск. Благодаря "неприятным" для методов поиска экстремума особенностям функция Розенброка часто используется для испытания сходимости различных алгоритмов и для их сравнения. График функции Розенброка представлен ниже на рис. 4.

Рис.4 График функции Розенброка

Определим минимум функции Розенброка, определяемой как:

(1)

Как видно из графика (рис. 4), функция Розенброка содержит несколько локальных минимумов. Однако функция имеет только один глобальный минимум, который находится в точке с координатами (1;1). Значение функции в этой точке f.

Для запуска пакета GeneticAlgorithmTool следует в командной строке MATLAB выполнить команду gatool. После этого запустится пакет генетических алгоритмов и на экране появится основное окно утилиты (рис. 5).

Рис. 5 Окно утилиты Genetic Algorithm Tool

Для решения задачи были заполнены поля Numberofvariables (число независимых переменных для функции пригодности) и Fitnessfunction (подлежащая минимизации функция). Также был создан указатель на М-файл функции.

M-файл для данной функции представлен на рис. 6 и расположен в одной из папок доступа MatLAB.

Рис. 6 M-файл с целевой функцией

Функция минимизации в данном случае двумерна и имеет имя rozenbr_fun(рис. 7).

Рис. 7 Пример заполнения полей

Также имеется возможность улучшить результаты расчета путем установки в опции Hybridfunction требуемой гибридной функции fminunc (рис. 8).

Рис. 8 Улучшение результата с помощью гибридной функции

Также были выбраны значения параметров, таких как вероятность кроссинговера (1%) и размер начальной популяции (1000 хромосом). Для данной задачи результаты представлены на рис. 9. Минимум функции достигается в точке с координатамиx₁=0,99974 и x₂=0,99947.

Рис. 9 Результаты выполнения алгоритма

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

Таблица 1.

Результаты эксперимента по нахождению минимума

		Размер начальной популяции
		10	50	100	500	1000
Вероятность кроссинговера	1	x1=0,80265 x2=0,73159	x1=0,83825 x2=0,75487	x1=0,89658 x2=0,80745	x1=0,96345 x2=0,92533	x1=0,99974 x2=0,99947
	0,5	x1=0,89412 x2=0,79839	x1=1,06943 x2=1,15123	x1=1,11176 x2=1,23422	x1=0,99127 x2=0,98113	x1=1,01228 x2=1,02327
	0	x1=1,04834 x2=1,11749	x1=0,90014 x2=0,80324	x1=0,94989 x2=0,89437	x1=0,96814 x2=0,93647	x1=1,01856 x2=1,03574

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

Графическое решение приведено на рис. 10.

Первый график (FitnessValue) отображает изменение значение целевой функции. Начиная с 40 популяции, алгоритм сошелся к решению. На втором графике (Currentbestindividual) изображена наилучшая особь. Третий график (AverageDistance) соответствует изменению расстояния между особями в поколениях.

Рис. 10 Графическое решение задачи нахождения минимума

Заключение

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

Список источников и литературы

1. Холланд Дж. Х., Адаптация в естественных и искусственных сетях, Издательство Мичиганского Университета, 1975.

2. http://algolist.manual.ru/ai/ga/ga1.php

3. http://www.machinelearning.ru/wiki/index.php?title=Генетический_алгоритм

4. Генетические алгоритмы, Гладков Л.А., Курейчик В.В., Курейчик В.М.,М.: ФИЗМАТЛИТ, 2006.

5. Rosenbrock, H.H. (1960). «An automatic method for finding the greatest or least value of a function». TheComputerJournal : 175–184.

Код для цитирования: Скопировать