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

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ


ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «СЕВЕРО-КАВКАЗСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»






Р. М. Немков




    ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ




УЧЕБНОЕ ПОСОБИЕ (ЛАБОРАТОРНЫЙ ПРАКТИКУМ)




Направление подготовки
           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.
   Для успешного освоения дисциплины «Генетические алгоритмы» студенты используют знания, умения, навыки, сформированные в процессе изучения смежных дисциплин: «Основы компьютерного моделирования», «Численные методы в научных расчетах». Также изучение данного курса является необходимой основой для последующего изучения смежных дисциплин: «Введение в технологии высокопроизводительных вычислений», «Основы распознавания образов».


-4-

Предисловие

   В ходе изучения дисциплины у студентов должны быть сформированы следующие компетенции:
   ОПК-1 - владеть широкой общей подготовкой (базовыми знаниями) для решения практических задач в области информационных систем и технологий.
   ПК-12 - способность разрабатывать средства реализации информационных технологий (методические, информационные, математические, алгоритмические, технические и программные).
   Этапы формирования компетенции ОПК-1 имеют вид:
   •  знать основы алгоритмизации;
   •  уметь программировать на языке высокого уровня для решения задач в области информационных систем и технологий;
   •  владеть численными методами и реализацией различных структур данных.
   Этапы формирования компетенции ПК-12 имеют вид:
   •  знать математические, алгоритмические особенности генетических алгоритмов и генетического программирования;
   •  уметь применять информационные технологии (любую среду программирования) для реализации процесса применения и построения генетических алгоритмов;
   •  владеть навыками создания генетических алгоритмов, программных средств для применения в практической сфере.
   Пособие представляет собой лабораторный практикум, составлено в соответствии с рабочей программой дисциплины и предназначено для студентов бакалавриата. В работе рассматривается практика программирования генетических алгоритмов на примерах шахматных задач, где необходимо в результате глобального поиска отыскать необходимую расстановку фигур. Для программирования генетического алгоритма студент должен разобраться в таких этапах, как создание популяции, её оценка, ранжирование особей и получение новых особей путём скрещивания старых, и мутации. Рассматривается также использование генетических алгоритмов в среде Matlab.

-5-

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





                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).


-6-

Лабораторная работа 1

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)

-7-

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

Рис. 1.2. График функции Акли от двух перменных

   Более подробную справку по той или иной команде можно получить через команду help «имя_функции».
   Для функции (1.2) график приведён на рисунке 1.3, для функции (1.3) - на рисунке 1.4, для функции (1.4) - на рисунке 1.5.


Рис. 1.3. График Rastrigin’s function

-8-

Лабораторная работа 1

Рис. 1.4. График квадратичной формы

Рис. 1.5. График Easom function

   Наша задача - воспользоваться мастером ГА для быстрого нахождения глобального или локального минимума.
   Но, прежде всего, необходимо создать в Matlab 4 функции по формулам (1.1) - (1-4). Именно эти функции будут передаваться к мастеру ГА. Создание функции в Matlab осуществляется через New —*■ Function, в появившемся файле с расширением «.т» вводится код функции. Потом функцию необходимо сохранить и связать её с текущей директорией Matlab. По простому это можно сделать, нажав кнопку Run и согласившись с предложенным каталогом.


-9-

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

    Коды четырёх функций приведены ниже.

    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-