Генетический алгоритм для задачи максимизации заданной целочисленной функции

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

 

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

В курсовой работе исследуется следующая оптимизационная задача:

Пусть задана целочисленная функция от четырёх переменных.

f(x1, x2, x3, x4) = |x1 - x2| + |x3 - x4| + |x1 * Sin(x2)|,

где x1, x2, x3, x4 – целые числа из отрезка [0, 1024]

Требуется найти максимум данной функции.

 

 

2.3 Описание  алгоритма

ГА будет состоять из следующих шагов:

1. Генерация начальной популяции. В качестве хромосомы используется битовая строка из 40 элементов. Строка логически разбивается на 4 равные части по 10 бит, каждая из которых отвечает за свою переменную. Т.о. кодируются значения переменных от 0 до 1023. Начальная популяция состоит из n (рассмотрим варианты 100 и 200) особей, генотипы которых генерируются случайным образом.
2. Вычисляется значение фитнес-функции каждой особи, по которому производится сортировка. В качестве фитнес-функции можно взять значение максимизируемой функции, так как она удовлетворяет требованиям, предъявляемым к фитнес-функции (неотрицательна, значение фитнес функции лучших особей больше).
3. Выбор пары особей для размножения. Выбор происходит посредством метода рулетки. Для каждой особи вычисляется отношение её значения функции приспособленности к суммарному значению функции приспособленности популяции. В зависимости от этого значения особи выделяется некоторое количество ячеек в массиве рулетки. Выбор особей для составления пары происходит независимо в результате двух последовательных запусков рулетки.
4. К выбранной на предыдущем шаге паре особей применяется оператор одноточечного кроссинговера. Точка кроссинговера выбирается равновероятно, случайным образом. Из полученных потомков случайным образом выбирается один, который добавляется в новую популяцию.
5. Повторение пп.2-3 n раз. В результате на этом этапе получаем новую популяцию из n особей. Т.к. выбор родителей производится по числу особей в популяции (n раз), велика вероятность того, что в новую популяцию попадёт большое количество потомков скрещивания наиболее удачных особей. С другой стороны, у более слабых особей остаётся шанс попасть в новую популяцию, а значит меньше шанс «потерять» хорошие признаки, присущие в целом не самым удачным особям.
6. Этап мутации. Каждая особь из новой популяции мутирует с вероятностью 1%. То есть оператор мутации применяется к 1% особей. Оператор мутации заключается в инвертировании случайно выбранного гена в генотипе особи.
7. В соответствии с логикой элитного отбора добавим в новую популяцию 10% лучших особей прошлого поколения. Для этого отсортируем новую популяцию по значению фитнес-функции и будем последовательно просматривать 10% слабейших особей. Особь заменяется на элитную из прошлого поколения только в случае выигрыша в значении фитнес-функции. Т.е. замена происходит, если текущая особь не превосходит по значению фитнес-функции той, на которую её предполагается заменить.
8. пп.2-6 выполняются некоторое заранее определённое число раз (m).

2.4 Результаты  работы и выводы

Тип	Число особей в популяции (n)	Число поколений (m)	Время работы	Результат
I	100	100	36 мс	3025,76
			34 мс	2976,76
			32 мс	3034,19
II	100	200	62 мс	3041,41
			74 мс	3045,39
			69 мс	3035,91
III	200	100	68 мс	3044,39
			53 мс	3041,41
			65 мс	3047,98
IV	200	200	139 мс	3057,99
			128 мс	3035,90
			138 мс	3057,99

 

Принципиальное отличие настроек II и III (n = 100, m = 200 и n = 200, m = 100) состоит в том, что в первом случае стартовое разнообразие меньше, меньше вероятность получить хорошие решения ещё на этапе генерации популяции, но развитие идёт дольше. То есть с одной стороны, есть опасность «пропустить» правильное решение, попав изначально в локальный максимум. Но в случае удачной стартовой популяции большее число шагов позволит лучше приблизиться к ответу. Соответственно вариант III менее подвержен опасности попадания в локальный максимум, но имеет меньше возможностей для улучшения найденных решений. IV вариант даёт наилучшие результаты как комбинация достоинств II и III вариантов.

Вычисление ответа методом полного перебора займёт порядка 3-4 часов (алгоритмическая сложность О(n4), где n=1024. Если считать, что за 1 сек выполняется порядка 108 операций, время работы составит 10244/108/60/60 ≈ 3,3 часа). Если же зафиксировать значение первой переменной равным 1023 (сделать вывод об этом можно на основе работы алгоритма при больших ограничениях на значения переменных и по результатам работы генетического алгоритма), перебор сократится до O(n3), что позволит получить точное решение: F(1023, 11, 0, 1023) = 3057,99. То есть генетический алгоритм с параметрами n = 200, m = 200 нашёл точное решение за время порядка секунды, тогда как результатов перебора нужно ждать несколько часов.

 

Заключение

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

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

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

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

 

Список использованных источников

 

1. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Основы логического проектирования дискретных устройств. - М.: Физматлит, 2007.
2. Сперанский Д.В., Самойлов В.Г., Емельянова О.В. Введение в генетические алгоритмы. - Саратов: Изд-во Сар. гос. ун-та, 2006.
3. Рутковская Д., Пилиньский М., Рутковский Я. Нейронные сети, генетические алгоритмы как нечёткие системы. - М.: Горячая линия – Телеком, 2004.
4. Гладков Л.А., Курейчик В.В, Курейчик В.М. Генетические алгоритмы. - М.: Физматлит, 2007.
5. Дарвин Ч. Происхождение видов путём естественного отбора / Пер. и вводная ст. К.А. Тимирязева. М., 1952.
6. Холланд Дж. Генетические алгоритмы // В мире науки. 1992 № 9-10.

 

Приложение

 

class Program

{

static void Main(string[] args)

{

// Число особей  в популяции

int initNum = 200;

// Число поколений

int numGen = 200;

 

Development dev = new Development(initNum);

Genotype g = dev.StartDevelopment(numGen);

 

Console.WriteLine(g.ToString() + "\nF = {0}\n", g.FitFunction);

 

Console.ReadLine();

}

}

 

/// <summary>

/// Класс для описания эволюции

/// </summary>

class Development

{

/// <summary>

/// Метод, реализующий подсчёт фитнес-функции

/// </summary>

/// <returns>Значение фитнес-функции</returns>

public static double GetFitFunction(int x1, int x2, int x3, int x4)

{

return Math.Abs(x1 - x2) + Math.Abs(x3 - x4) +

Math.Abs(x1 * Math.Sin(x2));

}

public static double GetFitFunction(Genotype g)

{

return GetFitFunction(g[0], g[1], g[2], g[3]);

}

 

Population _p;

/// <summary>

/// Популяция

/// </summary>

public Population Members

{

get{ return _p; }

}

 

/// <summary>

/// Конструктор с заданным числом особей

/// </summary>

/// <param name="num">Число особей в популяции</param>

public Development(int num)

{

Population.Init();

_p = new Population(num);

Genotype.Init();

}

 

/// <summary>

/// Метод запуска эволюции

/// </summary>

/// <param name="maxNum">Максимальное число поколений</param>

/// <returns>Особь с наибольшим значением фитнес-функции</returns>

public Genotype StartDevelopment(int maxNum)

{

_p.GenerateRandPopulation();

for (int i = 0; i < maxNum; i++)

{

_p.ChangeGeneration();

}

return _p[_p.Num - 1];

}

}

 

/// <summary>

/// Класс, описывающий популяцию

/// </summary>

class Population

{

static Random _rg;

 

/// <summary>

/// Инициализация статического рандомизатора класса

/// </summary>

public static void Init()

{

_rg = new Random();

}

 

Genotype[] _gen;

/// <summary>

/// Генотипы популяции

/// </summary>

public Genotype[] Members

{

get { return _gen; }

}

 

int _num;

/// <summary>

/// Число особей в популяции

/// </summary>

public int Num

{

get { return _num; }

}

 

Genotype[] _ngen;

int[] Arr4Roulett;

 

/// <summary>

/// Конструктор с заданным числом особей

/// </summary>

/// <param name="num">Число особей в популяции</param>

public Population(int num)

{

_gen = new Genotype[num];

_num = num;

}

 

/// <summary>

/// Генерация исходной популяции

/// </summary>

public void GenerateRandPopulation()

{

for (int i = 0; i < Num; i++)

{

_gen[i] = new Genotype();

_gen[i].GenerateRandGenotype();

}

}

 

/// <summary>

/// Доступ к генотипу из популяции

/// </summary>

/// <param name="idx">Порядковый номер</param>

/// <returns>Генотип</returns>

public Genotype this[int idx]

{

get { return _gen[idx]; }

}

 

/// <summary>

/// Метод, реализующий одноточечный кроссинговер

/// </summary>

/// <param name="m">1 родитель</param>

/// <param name="f">2 родитель</param>

/// <param name="s">1 потомок</param>

/// <param name="d">2 потомок</param>

public static void MakeCrossingover(Genotype m, Genotype f,

out Genotype s, out Genotype d)

{

int place = _rg.Next(1, Genotype.Length);

s = new Genotype();

d = new Genotype();

s.MakeCross(place, m, f);

d.MakeCross(place, f, m);

}

 

/// <summary>

/// Метод смены поколения

/// </summary>

public void ChangeGeneration()

{

Array.Sort(_gen);

Arr4Roulett = new int[1000];

GenerateArr4Roulette();

 

_ngen = new Genotype[Num];

for (int i = 0; i < _gen.Length; i++)

{

AddScion(i);

}

_gen = _ngen;

 

Array.Sort(_gen);

MakeMutation();  

AddSomeParents();

Array.Sort(_gen);

}

 

/// <summary>

/// Мутация (вероятность мутации 1% для каждой особи)

/// </summary>

public void MakeMutation()

{

for (int i = 0; i < Num; i++)

{

if (_rg.Next(100) == 4)

{

_gen[i].MakeMutation();

}

}

}

 

/// <summary>

/// Добавляем в популяцию "лучших" из предыдущего поколения (1%)

/// </summary>

public void AddSomeParents()

{

int num = _gen.Length / 100 * 10; //10%

int i = num - 1;

int j = _gen.Length - 1;

while (i >= 0)

{

if (_ngen[i].FitFunction < _gen[j].FitFunction)

{

_ngen[i] = _gen[j].Clone();

j--;

}

i--;

}

}

 

/// <summary>

/// Создание массива для запуска рулетки

/// </summary>

public void GenerateArr4Roulette()

{

double sumVal = 0;

for (int i = 0; i < _gen.Length; i++)

{

sumVal += _gen[i].FitFunction;

}

 

int idx = 0;

for (int i = 0; i < _gen.Length; i++)

{

int temp = (int)(Math.Floor(_gen[i].FitFunction * 1.0 /

sumVal * 1000));

for (int j = 0; j < temp; j++)

{

Arr4Roulett[idx] = i;

idx++;

}

}

while (idx < 1000)

{

Arr4Roulett[idx] = _rg.Next(_gen.Length);

idx++;

}

}

 

/// <summary>

/// Добавление потомка

/// </summary>

public void AddScion(int idx)

{

Genotype m = _gen[Arr4Roulett[_rg.Next(1000)]];

Genotype f = _gen[Arr4Roulett[_rg.Next(1000)]];

Genotype s, d;

MakeCrossingover(m, f, out s, out d);

if (_rg.Next(2) == 1)

{

_ngen[idx] = s;

}

else

{

_ngen[idx] = d;

}

}

}

 

/// <summary>

/// Класс, описывающий генотип

/// </summary>

class Genotype : IComparable<Genotype>

{

public static readonly int NMAX = 1024;

 

/// <summary>

/// Длина битовой строки

/// </summary>

public static int Length

{

get { return 4 * 10; }

}

 

static BitVector32.Section[] _s;

static Random _rg;

 

/// <summary>

/// Инициализация рандомизатора и задание секций битовой строки

/// </summary>

public static void Init()

{

_s = new BitVector32.Section[4];

_s[0] = BitVector32.CreateSection((1 << 10) - 1);

_s[1] = BitVector32.CreateSection((1 << 10) - 1, _s[0]);

_s[2] = BitVector32.CreateSection((1 << 10) - 1, _s[1]);

_s[3] = BitVector32.CreateSection((1 << 10) - 1, _s[2]);

_rg = new Random();

}

 

BitVector32 _gen;

 

/// <summary>

/// Значение фитнес-функции особи с данным генотипом

/// </summary>

public double FitFunction

{

get { return Development.GetFitFunction(this[0], this[1],

 this[2], this[3]); }

}

 

/// <summary>

/// Конструктор по умолчанию

/// </summary>

public Genotype()

{

_gen = new BitVector32();

}

 

/// <summary>

/// Конструктор копирования

/// </summary>

/// <param name="g">Копируемый генотип</param>

public Genotype(Genotype g)

{

_gen = g.ByteGens;

}

 

/// <summary>

/// Конструктор генотипа по значениям переменных

/// </summary>

public Genotype(int x1, int x2, int x3, int x4)

{

_gen[_s[0]] = x1;

_gen[_s[1]] = x2;

_gen[_s[2]] = x3;

_gen[_s[3]] = x4;

}

 

/// <summary>

/// Метод создания копии

/// </summary>