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

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

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

Представленный ГА дает возможность пользователю задавать размер начальной популяции особей, вероятности генетических операторов (а именно – кроссинговера и мутации), а также предоставляет выбор типов этих операторов и дает пользователю право задавать количество генераций алгоритма.

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

Постановка задачи

Задача состояла в написании программы, реализующей различные схемы простого генетического алгоритма с возможностью задания пользователем размера популяции, числа генераций и вероятностей генетических операторов. По умолчанию, следующие параметры алгоритма: размер начальной популяции − 10, формирование начальной популяции − по выбору пользователя, вероятность кроссинговера − 70%, вероятность мутации − 20%, число генераций − не менее 50.

Построить на основе описаний генетического алгоритма Холланда, Голдберга и Девиса простой генетический алгоритм вычисления максимума функции:

max f(x) = 3х^3 − 2х + 5

на интервале [1 - 10].

Генетические операторы:

• бинарное кодирование хромосом;
• варианты стратегии создания начальной популяции на основе стратегии «одеяла» и стратегии «дробовика»;
• селекция элитная;
• операторы кроссинговера: стандартный одноточечный, стандартный двухточечный;
• операторы мутации: инверсиия;
• пропорциональный оператор отбора;
• развитие популяции на основе схемы микроэволюции.

Анализ технического задания

Техническим заданием является стандартная оптимизационная задача нахождения оптимума функции на заданном числовом интервале.

Для решения этой оптимизационной задачи было решено использовать генетический алгоритм, так как он имеет несколько преимуществ:

• Поиск промежуточных решений происходит выбором из уже имеющегося случайного набора решений, и благодаря генетическим операциям свойства промежуточных решений улучшаются при формировании новых поколений;
• Помимо непосредственного использования значения целевой функции, при отборе учитываются и другие критерии для выживания особей (например, приспособленность в популяции);
• При выполнении генетических операторов используются вероятностные и случайностные методы, т.е. ГА является алгоритмом случайно-направленного поиска.

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

В данной работе генетический алгоритм реализован на языке программирования C++ с использованием структур и классов.

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

Перечислим термины, которые будут использованы далее:

• Целевая функция (ЦФ) – это функция для оптимизации: y = f(x) = 3x^3 - 2x + 5;
• Хромосома – это точка в пространстве поиска: x из отрезка [1 - 10];
• Особь – это совокупность хромосомы, значения целевой функции и значения приспособленности;
• Популяция – это набор особей;
• Поколение – это номер итерации алгоритма.

ГА состоит из набора определенных генетических операторов. Рассмотрим каждый из них.

1. Кодирование решения.

В ГА представлено двоичное кодирование хромосом. Структура:

struct chromosome {
bool binary[4]; int fitness; double completeness; };

Данная структура содержит 3 поля:

• Массив булевского типа binary[4], представляющий собой двоичный код хромосомы. Он имеет размер 4, так как мы ищем решение на отрезке [1 – 10], а наибольшее число этого отрезка 10 в двоичной системе имеет вид: 1010;
• Целочисленная переменная fitness, хранящая значение ЦФ данной хромосомы;
• Вещественная переменная completeness, которая содержит значение приспособленности особи в популяции. Это значение меняется при каждой новой итерации.

Приведем пример для лучшего понимания. Назовем особь individual. Возьмем из отрезка число x = 5, в двоичной системе это число имеет вид 0101, значение функции f (5) = 370, и, к примеру, приспособленность этой особи в популяции будет 0,5. Тогда получим:

individual.binary[0] = 0;

individual.binary[1] = 1;

individual.binary[2] = 0;

individual.binary[3] = 1;

individual.fitness = 370;

individual.completeness = 0,5.

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

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

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

В алгоритме представлено два оператора кроссинговера: стандартный одноточечный и стандартный двухточечный. Рассмотрим каждый из них.

Стандартный одноточечный кроссинговер. Перед началом работы кроссинговера выбирается пара родителей и случайным образом определяется одна точка разрыва. Эта точка обозначает место в двух родительских хромосомах, где будет производиться «разрез» на два фрагмента, из которых потом будут составляться потомки.

Рассмотрим пример. Пусть родительские хромосомы имеют вид: Р1 = (1010), Р2 = (0101). Точкой разреза, допустим, будет точка между вторым и третьим генами. Тогда дочерние особи П1 и П2 будут иметь вид:

Р1 = 1 0 | 1 0,

Р2 = 0 1 | 0 1,

П1 = 1 0 | 0 1,

П2 = 0 1 | 1 0.

После этого определяем легальность каждого потомка (т.е. принадлежность отрезку [1 - 10]), оставляем только одного более приспособленного и записываем его в новую популяцию.

Таким образом, одноточечный кроссинговер выполняется в 4 этапа:

1. Первый родитель выбирается случайно, а второй выбирается такой, который наиболее похож на первого родителя (инбридинг – близкородственное скрещивание);
2. Случайным образом выбирается точка разрыва k из {0, …, d - 1}, где d – длина хромосомы (в нашем случае: d = 4);
3. Две новые хромосомы формируются путем перестановки фрагментов выбранных родительских хромосом;
4. Из двух потомков выбирается лучший и добавляется в новую популяцию.

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

Приведем пример. Родительские хромосомы: Р1 = (1001), Р2 = (0110), первая точка разреза между первым и вторым геном, вторая точка – между третьим и четвертым. Потомки П1 и П2 будут иметь вид:

Р1 = 1 | 0 0 | 1,

Р2 = 0 | 1 1 | 0,

П1 = 1 | 1 1 | 1,

П2 = 0 | 0 0 | 0.

Аналогично предыдущему виду кроссинговера, этот тоже выполняется в 4 этапа:

1. Первый родитель выбирается случайно, а второй выбирается такой, который наиболее похож на первого;
2. Случайным образом выбираются две точки разрыва k1 и k2 из {0, …, d - 1}, где d – длина хромосомы (в нашем случае: d = 4);
3. Две новые хромосомы формируются из родительских путем перестановки частей родительских хромосом;
4. Из двух потомков выбирается лучший и добавляется в новую популяцию.

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

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

Покажем на примере. Пусть есть хромосома Р = (0011), будем инвертировать ее часть между первым и последним генами:

Р = 0 | 0 1 | 1,

П = 0 | 1 0 | 1.

4. Оператор селекции.

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

5. Оператор отбора.

В ГА реализован пропорциональный оператор отбора. Он выполняется в конце каждой итерации основного цикла. Его задача состоит в отборе лучших хромосом из полученного поколения в количестве, равном исходной популяции.

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

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

Структурная схема алгоритма

Начало алгоритма

1. Задание целевой функции;
2. Задание всех параметров алгоритма (пользователю предоставляется выбор этих параметров);
3. Формирование исходного семейства (начальной популяции) согласно стратегии, выбранной пользователем;

Начало основного цикла

4. Селекция (вид селекции выбран пользователем) – это отбор родительских особей для последующего скрещивания;
5. Оператор кроссинговера (его вид и вероятность выполнения задаются пользователем) – это оператор скрещивания родительских хромосом, в результате которого образуются дочерние особи (потомки);
6. Оператор мутации (вероятность выполнения задается пользователем) – это оператор, реализующий некое случайное изменение отдельной хромосомы;
7. Вычисление средней приспособленности популяции и приспособленностей каждой особи с использованием ЦФ;
8. Оператор отбора – формирование нового поколения путем удаления наименее приспособленных хромосом;
9. Если выполняются условия остановки, то работа цикла завершается, иначе – переход к пункту 4;

Конец цикла

10. Вывод ответа.

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

Эксперименты

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

Заключение

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

Результатом практической работы является разработанный генетический алгоритм с возможностью задания пользователем некоторых параметров этого алгоритма. ГА написал на языке программирования C++. Разработка алгоритма прошла успешно, и он в подавляющем большинстве случаев находит верное решение поставленной задачи.

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

Эффективнее всего ГА работает при больших начальных популяциях (10 и более особей) и достаточно высоких вероятностях генетических операторов (55 и более процентов). При небольших и малых популяциях (менее 8 особей) ГА находит решение, близкое к максимальному, однако если одновременно задать высокие вероятности генетических операций, алгоритм найдет верное решение задачи.