Генетические алгоритмы
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
Северо-Кавказский федеральный университет
Автор:
Немков Роман Михайлович
Год издания: 2021
Кол-во страниц: 102
Дополнительно
Пособие представляет собой лабораторный практикум, составленный в соответствии с рабочей программой дисциплины. Предназначено для студентов бакалавриата, обучающихся по направлению подготовки 09.03.02 Информационные системы и технологии, направленности (профилю) «Прикладное программирование в информационных системах». В работе изложены основные понятия генетических алгоритмов; рассмотрены примеры программирования таких алгоритмов. Структурно каждая тема состоит из краткого изложения теоретического материала, необходимого для ее выполнения, указаний по порядку выполнения работы, заданий для самостоятельного выполнения, контрольных вопросов и тестовых заданий.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «СЕВЕРО-КАВКАЗСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Р. М. Немков
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
УЧЕБНОЕ ПОСОБИЕ (ЛАБОРАТОРНЫЙ ПРАКТИКУМ)
Направление подготовки
09.03.02 Информационные системы и технологии
Профиль подготовки
Прикладное программирование в информационных системах»
Бакалавриат
Ставрополь
2021
УДК 004.94(075.8)
ББК 32.97 я73
Н50
Печатается по решению редакционно-издательского совета Северо-Кавказского федерального университета
Немков Р. М.
Н50 Генетические алгоритмы: учебное пособие (лабораторный практикум). - Ставрополь: Изд-во СКФУ, 2021. - 102 с.
Пособие представляет собой лабораторный практикум, составленный в соответствии с рабочей программой дисциплины. Предназначено для студентов бакалавриата, обучающихся по направлению подготовки 09.03.02 Информационные системы и технологии, направленности (профилю) «Прикладное программирование в информационных системах».
В работе изложены основные понятия генетических алгоритмов; рассмотрены примеры программирования таких алгоритмов. Структурно каждая тема состоит из краткого изложения теоретического материала, необходимого для ее выполнения, указаний по порядку выполнения работы, заданий для самостоятельного выполнения, контрольных вопросов и тестовых заданий.
УДК 004.94 (075.8)
ББК 32.97 я73
Рецензенты:
канд. техн, наук, доцент Е. И. Николаев, канд. физ.-мат. наук, доцент Е. И. Новикова
© ФГАОУ ВО «Северо-Кавказский федеральный университет», 2021
СОДЕРЖАНИЕ
Предисловие..................................................4
1. Знакомство с мастером gatool в Matlab.................6
2. Решение задачи о расстановке 8 ферзей с помощью генетического алгоритма. Часть 1. Создание популяции...........................17
3. Решение задачи о расстановке 8 ферзей с помощью генетического алгоритма. Часть 2. Ранжирование особей..........................24
4. Решение задачи о расстановке 8 ферзей с помощью генетического алгоритма. Часть 3. Скрещивание и мутация........................35
5. Решение задачи о расстановке 5 ферзей с помощью генетического алгоритма. Часть 1. Создание популяции...........................48
6. Решение задачи о расстановке 5 ферзей с помощью генетического алгоритма. Часть 2. Ранжирование.................................57
7. Решение задачи о расстановке 5 ферзей с помощью генетического алгоритма. Часть 3. Скрещивание..................................66
8. Решение задачи о 16 конях. Часть 1. Создание популяции и покрытие................77
9. Решение задачи о 16 конях. Часть 2. Скрещивание..................................87
Список литературы.........................................100
Предисловие
Генетический алгоритм (англ, genetic algorithm) - это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ, evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Цель преподавания дисциплины - формирование профессиональной компетенции (ПК-12, ОПК-1) будущего бакалавра по направлению подготовки 09.03.02 Информационные системы и технологии.
Задачи, решаемые в процессе преподавания дисциплины:
1. Знакомство с основами генетических алгоритмов: основные понятия, операции, применяемые в генетических алгоритмах, основные этапы стандартного генетического алгоритма (порядок применения операций).
2. Ознакомление с реализацией генетического алгоритма на примере оптимизационных задач с использованием любого языка программирования.
3. Знакомство с основами использования генетических алгоритмов в среде Matlab.
Для успешного освоения дисциплины «Генетические алгоритмы» студенты используют знания, умения, навыки, сформированные в процессе изучения смежных дисциплин: «Основы компьютерного моделирования», «Численные методы в научных расчетах». Также изучение данного курса является необходимой основой для последующего изучения смежных дисциплин: «Введение в технологии высокопроизводительных вычислений», «Основы распознавания образов».
Предисловие В ходе изучения дисциплины у студентов должны быть сформированы следующие компетенции: ОПК-1 - владеть широкой общей подготовкой (базовыми знаниями) для решения практических задач в области информационных систем и технологий. ПК-12 - способность разрабатывать средства реализации информационных технологий (методические, информационные, математические, алгоритмические, технические и программные). Этапы формирования компетенции ОПК-1 имеют вид: • знать основы алгоритмизации; • уметь программировать на языке высокого уровня для решения задач в области информационных систем и технологий; • владеть численными методами и реализацией различных структур данных. Этапы формирования компетенции ПК-12 имеют вид: • знать математические, алгоритмические особенности генетических алгоритмов и генетического программирования; • уметь применять информационные технологии (любую среду программирования) для реализации процесса применения и построения генетических алгоритмов; • владеть навыками создания генетических алгоритмов, программных средств для применения в практической сфере. Пособие представляет собой лабораторный практикум, составлено в соответствии с рабочей программой дисциплины и предназначено для студентов бакалавриата. В работе рассматривается практика программирования генетических алгоритмов на примерах шахматных задач, где необходимо в результате глобального поиска отыскать необходимую расстановку фигур. Для программирования генетического алгоритма студент должен разобраться в таких этапах, как создание популяции, её оценка, ранжирование особей и получение новых особей путём скрещивания старых, и мутации. Рассматривается также использование генетических алгоритмов в среде Matlab.
1. ЗНАКОМСТВО С МАСТЕРОМ GATOOL В MATLAB
Цель и содержание работы: познакомить студента с быстрым созданием генетического алгоритма в среде Matlab.
Знания, умения и владения, приобретаемые обучающимися в результате освоения темы, в рамках формируемых компетенций: ОПК-1, ПК-12.
Теоретическая часть
Для того чтобы вызвать мастера по работе с ГА, в среде Matlab необходимо ввести gatool. Данная команда для современных версий Matlab уже устаревшая, поэтому лучше использовать optimtool. По этой команде вызывается универсальный мастер численной оптимизации, который в том числе содержит и метод ГА.
Выбор метода ГА в мастере Optimization Tool показан на рисунке 1.1.
Рис. 1.1. Выбор метода ГА для задач численной оптимизации
Рассмотрим поиск минимумов у следующих функций: Ackley function (1.1), Rastrigin’s function (1.2), функция суммы квадратов (1.3) и Easom function (1.4).
f(x₁,x₂,...,xₙ) =
-е*
1
20
^*(cos(c*x₁) + cos(c*x₂) + ... + cos(c*x„)) +
+20+€ + 5.7
где глобальный минимумах*) = 0 достигается прих*=(0,0,..0).
Ras(x) = 20 + xf + х₂ -10*(соз2л-х₁ +cos2?rx₂), (1-2)
где глобальный минимумах*) = 0 достигается при х*=(0, 0).
f(x) = tx', (1-3)
/=1
где глобальный минимумах*) = 0 достигается прих*=(0,0,..0).
/(х) = - cos х, cosx₂ ехр(-(х, - л-)² - (х₂ - л)²), (1-4)
где глобальный минимумах*) = -1 достигается при х*=(л, л).
Если функция от двух или от одной переменной, то хорошо построить её график либо в пространстве, либо на плоскости. Пусть функция (1.1) от двух переменных, а не от п, тогда следующий код позволяет получить её трехмерный график (рис. 1.2). Конкретные значения переменных приведены в коде.
% получаем матрицы X, Y для трехмерного рисунка, они содержат различные
% комбинации координат (xi, yj).
[X, Y] = meshg rid (-100:02:100, -100:0.2:100);
% высчитываем саму функцию на X и Y
Z=(1 /0.8)*(-20*exp(-0.2*sqrt(( 1 /2)*(X(:,:).A2+Y(:,:) .л2)))-ехр(( 1 /2)*(cos(2*pi* X(:,:))+cos(2*pi*Y(:,:))))+20+exp( 1 )+5.7);
% рисуем трехмерный график
plot3(X,Y,Z)
Рис. 1.2. График функции Акли от двух перменных Более подробную справку по той или иной команде можно получить через команду help «имя_функции». Для функции (1.2) график приведён на рисунке 1.3, для функции (1.3) - на рисунке 1.4, для функции (1.4) - на рисунке 1.5. Рис. 1.3. График Rastrigin’s function
Рис. 1.4. График квадратичной формы Рис. 1.5. График Easom function Наша задача - воспользоваться мастером ГА для быстрого нахождения глобального или локального минимума. Но, прежде всего, необходимо создать в Matlab 4 функции по формулам (1.1) - (1-4). Именно эти функции будут передаваться к мастеру ГА. Создание функции в Matlab осуществляется через New —*■ Function, в появившемся файле с расширением «.т» вводится код функции. Потом функцию необходимо сохранить и связать её с текущей директорией Matlab. По простому это можно сделать, нажав кнопку Run и согласившись с предложенным каталогом.
Коды четырёх функций приведены ниже.
function z = ft_ackley(input)
а = 20;
b = 0.2;
с = 2*pi;
d = 5.7;
f=0.8;
n = 2;
x = input(:, 1);
у = inputf:, 2);
z= (1/f)*(-a*exp(-b*sqrt((1/n)*(x.A2+y.A2)))-exp((1/n)*(cos(c*x)+cos(c*y)))+ a+exp(1)+d);
end
function у = rastrfx)
n = 2;
s = 0;
forj = 1:n
s = s + (x(j)A2-10*cos(2*pi*x(j)));
end
у = 10 * n + s;
end
function у = sum2(x)
n = 15;
s = 0;
forj = 1:n
s = s+j*x(j)A2;
end
y = s;
end
function у = easomfx)
у = -cos(x(1)) * cos(x(2)) * exp(-(x(1 )-pi)A2-(x(2)-pi) A2);
end
Функция получает входное значение в виде массива.
- 10