Практическая работа №5.
«Использование метода роящихся частиц и генетического алгоритма для нахождения минимума или максимума функции»
Тема 7 «Эвристические алгоритмы»

Цель: получить общее представление об использовании метода роящихся частиц  для нахождения экстремумов функции.

Теория:

Метод роящихся частиц

Схема работы алгоритма выглядит следующим образом.

1. Создаётся исходная “случайная” популяция частиц.
2. Для каждой частицы рассчитывается целевая функция.
3. Лучшая частица с точки зрения целевой функции объявляется “центром притяжения”.
4. Векторы скоростей всех частиц устремляются к этому “центру”, при этом чем дальше частица находится от него, тем большим ускорением она обладает.
5. Осуществляется расчёт новых координат частиц в пространстве решений.
6. Шаги 2—5 повторяются заданное число раз.
7. Последний “центр тяжести” объявляется найденным оптимальным решением.

Существует несколько разновидностей метода роящихся частиц. Одной из самой простой является стандартный канонический.
Рассмотрим задачу глобальной безусловной минимизации целевой функций  в -мерном арифметическом пространстве :
.                                                          (1)
Множество частиц обозначим , где  - количество частиц в рое (размер популяции). В момент времени  координаты частицы  определяются вектором , а ее скорость - вектором . Начальные координаты и скорости частицы  равны , , соответственно.
Итерации в простейшем варианте канонического метода (без «социальной» составляющей) выполняются по следующей схеме:
    (1)
   (2),
где t – момент времени (0,1,2, …); хi – вектор координат i – ой  частицы; хb – вектор координат лучшей частицы, т.е. с наилучшим значением целевой функции Ф(Х); U[0,?] – вектор псевдослучайных чисел, равномерно распределенных в интервале [0,?]; ? – свободный параметр, определяет инерционные свойства частицы; Vi – скорость i-ой частицы.
Свободный параметр  определяет «инерционные» свойства частиц (при  движение частиц, очевидно, замедляется). Рекомендуемое значение параметра  равно 0.7298. В процессе оптимизации может быть эффективным постепенное уменьшение коэффициента  от 0.9 до 0.4. При этом большие значения параметра обеспечивают широкий обзор пространства поиска, а малые – точную локализацию минимума целевой функции. Рекомендуемые значения свободного параметра  равно 1.49618.
Также существует разновидность – модифицированный канонический метод.
В данном методе формула 2 преобразуется к следующему виду:
   (3)

 где rx обеспечивает неоднозначность положения центра притяжения; rа обеспечивает неоднозначность величины ускорения; r? обеспечивает неоднозначность величины коэффициента трения, хextr – центр роя, т.е. координаты лучшей частицы.
Рекомендуемые значения для  r? – случайное число в интервале от 0.1 до 0.6, а rx и rа случайные числа в интервале [0, ?].

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

Основные понятия, используемые в генетическом алгоритме:

Мутация — это преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций — случайное изменение только одного из генов хромосомы.

Кроссинговер (в литературе по генетическим алгоритмам также употребляется название кроссовер или скрещивание) — это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. В простейшем случае кроссинговер в генетическом алгоритме реализуется так же, как и в биологии. При этом хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы (1, 2, 3, 4, 5) и (0, 0, 0, 0, 0) разрезать между третьим и четвертым генами и обменять их части, то получатся потомки (1, 2, 3, 0, 0) и (0, 0, 0, 4, 5).

Работа генетического алгоритма:

Вначале генерируется начальная популяция особей (индивидуумов), т.е. некоторый набор решений задачи. Как правило, это делается случайным образом. Затем  моделируется размножение внутри этой популяции. Для этого случайно отбираются несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора — чем приспособленнее индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании.
Теперь моделируются мутации — в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. Затем старая популяция частично или полностью уничтожается и мы переходим к рассмотрению следующего поколения. Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но в силу отбора приспособленность в ней в среднем выше. Теперь описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т. д.
В каждом следующем поколении наблюдается возникновение совершенно новых решений задачи. Среди них будут как плохие, так и хорошие, но благодаря отбору число хороших решений будет возрастать. Замечено, что в природе не бывает абсолютных гарантий, и даже самый приспособленный тигр может погибнуть от ружейного выстрела, не оставив потомства. Имитируя эволюцию на компьютере, можно избегать подобных нежелательных событий и всегда сохранять жизнь лучшему из индивидуумов текущего поколения — такая методика называется “стратегией элитизма”.

Задание:

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

Пример: Найти точку минимума функции y(x)=x2 - 2x + 4 (известно что функция достигает минимума при х=2, y(2)=0)

Шаг 1: Построить начальный рой из 5 точек.

В нашем случае, так как функция одной переменной точка будет состоять из одной координаты – это значение Х.
Выберем центр роя (отличный от точки минимума), например х1=-3 и остальные точки разместим в окрестности центра. Например, х2 = -2, х3=-1, х4=-4, х5=0.

Найдем значение функции в каждой из пяти точек (таблица 1)
Таблица 1

Шаг 2: в качестве центра следующего роя выбираем точку с наименьшим значением функции (так как ищем точку минимума) – это точка х5=0.

Шаг 3: Пересчитываем координаты остальных точек по формулам (1) и (2), если реализуется стандартный канонический метод и (1) и (3), если модифицированный канонический метод.

(В примере в дальнейшем будет рассматриваться стандартный канонический метод)

Случайные составляющие в формуле (2) или (3) для каждой частицы выбираются новые (таблица 2).
Таблица 2

Шаг 4: Находим значения функции в новых точках. Заново заполняем таблицу 1
Таблица 1

 
Далее повторяем шаги 2-4 (при ручном просчете повторить еще раз и на этом остановиться)

1. Написать программу, которая реализует алгоритм из ручного просчета (роения частиц), Повторять шаги (2-4) 50 итераций, т.е. 50 раз будет создаваться новый рой, выбираться новый центр и т.д. Программа должна выводить на экран координаты точек роя и значения функции в них после 1, 10, 30, 40, 50 итерации.

1. Выполнить ручной просчет нахождения минимума (максимума) функции генетическим методом (функция и метод роения выбирается согласно варианту).

Пример: Найти точку минимума функции y(x)=x2 - 2x + 4 на отрезке хЄ[-10, 10] (известно что функция достигает минимума при х=2, y(2)=0)

Шаг 1: Возьмем любые пять значений х, принадлежащих отрезку [0, 10]. Например: х1=3, х2 =9 , х3=7, х4=4, х5=0.
Запишем данные значения в двоичной системе.
х1 = 0011;      х2 =1001;        х3=0111;         х4=0100;         х5=0000
Каждое десятичное значение кодируется двоичным кодом длины 4, так как граничное значение диапазона 10.
Одно пробное решение, записанное в двоичной форме, называется особью или хромосомой, а набор всех пробных решений - популяцией

Шаг 2: Принцип естественного отбора заключается в том, что в конкурентной борьбе выживает наиболее приспособленный. Приспособленность особи определяется целевой функцией: чем меньше значение целевой функции (так как мы ищем минимум), тем более приспособленной является особь.  
Определим, какая особь более приспособленная (таблица 1).
Таблица 1

Более приспособленной является особь номер 1.

Шаг 3: Процесс размножения - на основе исходной популяции создается новая, так чтобы пробные решения в новой популяции были ближе к искомому минимуму целевой функции. Для этого формируются из исходной популяции брачные пары для скрещивания (кроссинговера).

Пример операции кроссинговера: скрещиваются две хромосомы 111111 и 000000. Определяем случайным образом точку разрыва хромосомы, пусть это будет 3. Теперь хромосомы обмениваются частями, стоящими после точки разрыва, и образуют двух новых потомков: 111000 и 000111.

В нашем случае операция кроссинговера дает следующие результаты:

Таблица 2

Шаг 4: мутации – случайные изменения полученных в результате скрещивания хромосом. Пусть вероятность мутации равна 0,3. Для каждого потомка берется случайное число на отрезке [0,1], и если это число меньше 0,3, то инвертируем случайно выбранный ген (заменяем 0 на 1 и наоборот)
Таблица 3

Мутации способны улучшить (второй потомок) или ухудшить (4 и 6 потомки) приспособленность особи потомка.

Шаг5: Из особей родителей (таблица 1) и особей потомков (таблица 3) необходимо сформировать новую популяцию. В новую популяцию отбираем не менее 5 наиболее приспособленных особей из числа родителей и потомков.
Строим новую таблицу 1
Таблица 1

Далее снова повторяем шаги 3-5 (для ручного просчета повторить еще раз). Таким образом, через несколько поколений получается популяция из похожих и наиболее приспособленных особей. Значение приспособленности наиболее «хорошей» особи и будет являться минимумом функции. 

1. Написать программу, которая реализует алгоритм из ручного просчета (генетический), Повторять построение новой популяции 10раз. Программа должна выводить 1, 3, 5, 7, 10 популяции (все хромосомы популяции и их приспособленность). 

Отчет:

Отчет должен включать следующие разделы:

1. Подробное описание ручного просчета для метода роящихся частиц.
2. Результаты работы программы: записать координаты всех 5 точек последнего роя и значения функции в них. Указать найденный минимум (максимум). Посчитать погрешность найденного минимума (максимума) от действительного.
3. Таблицу двоичного кода (необходимой длины) записи десятичных чисел – для генетического алгоритма.  
4. Подробное описание ручного просчета генетического алгоритма. 
5. Результаты работы программы: записать все хромосомы последней популяции и их приспособленность. Указать найденный минимум  (максимум). Посчитать погрешность найденного минимума (максимума) от действительного.

Варианты заданий:
(Вариант совпадает с номером в списке)