Федеральное Агентство по Образованию
Государственного Образовательного Учреждения
Высшего Профессионального Образования
Сибирский Федеральный Университет
Институт Космических и Информационных Технологий
Лабораторная работа
«Эволюционные алгоритмы»
Выполнили:
Группа КИ08-19
Орлов М.В.
Савран Е.И.
Булыно Е.С.
Лазарева О.П.
Красноярск 2011
Содержание:
Цели и задачи выполнения лабораторной работы …………………………………………………………………………….………………..3
Вариант и ход выполнения лабораторной работы……………………………………………………………………………………..…………4
Приложение 1: Основной код программы на языке C #............................................................................................6
Приложение 2: Таблицы ……………………………………………………………………………………………………………………………………….38
Цели и задачи выполнения лабораторной работы:
1. Приобретение студентами знаний, умений и навыков по разработке интеллектуальной информационной системы, реализующей эволюционный алгоритм.
2. Выполнение лабораторной работы требует выбора варианта целевой функции для эволюционного алгоритма и, как результат создание программы на любом из языков программирования, реализующей поиск глобального экстремума выбранной функции. Созданная программа должна быть протестирована с различными параметрами работы алгоритма. Выполненная работа оценивается по пятибалльной системе.
Вариант и ход выполнения лабораторной работы:
Вариантами тем являются различные целевые функции для проверки работы эволюционного алгоритма.
Наша функция:
Функция |
Область поиска |
Координаты глобального минимума |
|
|
|
Ход работы:
Изучить теоретический материал учебного пособия, представленный в главе 4.
Определить способы кодирования и декодирования индивидов, так как алгоритм будет работать с вещественным и бинарным представлением. При вещественном кодировании (Real – coded EA) преобразования индивида в генотип не требуется, так как генотип и фенотип тождественны. При бинарном представлении следует решить каким образом преобразовывать индивид из набора вещественных чисел в бинарную строку. При кодировании бинарной строкой важно отсутствие недопустимых индивидов.
Задать возможность изменения индивидов в популяции (например, 100, 200, 500).
Решить каким образом оценивать индивидов, для того, чтобы узнать какой индивид лучше решает задачу. На этом этапе необходимо вводить функцию пригодности, так как сама целевая функция не может ей быть.
Реализовать механизмы отбора индивидов в промежуточную популяцию родителей. Необходимо использовать пропорциональную, ранговую и турнирную селекцию в программной реализации.
Для каждого из способов представления реализовать несколько способов рекомбинации. Например, для бинарного представления рекомбинацию с помощью масок и двухточечное скрещивание, для вещественного представления арифметическое и плоское скрещивание. Также следует решить, каким будет число родителей. Выбор механизмов рекомбинации осуществляется студентом, но для каждого из представлений их должно быть не менее двух.
Выбрать способы мутации для каждого типа представления.
Определить условия останова.
Решить проблему недопустимых индивидов.
Реализовать программу на одном из выбранных языков программирования.
Протестировать программу с различными параметрами. Результаты тестирования должны быть приведены в таблице (см. приложение 6). По результатам тестирования следует сделать выводы о наиболее подходящих параметрах алгоритма для решения данной задачи и объяснить результат.
Оформить отчет по результатам тестирования.
Приложение 1: Основной код программы на языке c# :
namespace IIS_lab6
{ class Program
{ static void Main(string[] args)
{ //Начало программы
// будем использовать вещественное представление
Random func = new Random(); //функция рандома для представления
int count = 0;//количество индивидов в популяции
double[] population;//текущая популяция
double[] old_population;
double max_x = max_fx();
double[] suitability;// пригодность каждого элемента популяции
int i;// для счетчиков
int tests;//для тестирования проги - 20 прогонов
int steps = 10;//шаги в формуле i=1..20
int group = 2;//количество индивидов в группе турнирной селекции
int triple = 0;//переменная отвечающая за отсчет
Stopwatch time = new Stopwatch();//секундомер
StreamWriter stream;//для работы с файлом
do
{
Console.WriteLine("Введите размер популяции популяции, Не более 600");
count = Convert.ToInt32(Console.ReadLine());
if (count > 600)
{
count = 0;
Console.WriteLine("ВВедите меньшее значение");
}
if (count < 10) { count = 0; Console.WriteLine("Введите значение больше 9"); }
} while (count == 0);
int old_count = count;//сохраняем начальное количество популяции
population = new double[count];//текущая популяция
suitability = new double[count];//пригодность текущей популяции
old_population = new double[count];
FileInfo fi = new FileInfo(count + " results.txt");//привязка к файлу по размеру популяции
stream = fi.AppendText();
stream.WriteLine();
stream.WriteLine("Селекция пропорциональная, скрещивание линейное, мутация случайная");
for (tests = 0; tests < 20; tests++)//тестирования программы, вывод данных в файл
{
time.Start();
for (i = 0; i < count; i++)
{
population[i] = func.Next(-5000000, 5000000);
population[i] = Math.Round(population[i] / 10000, 4);//приводим к норм виду популяцию четыре знака после запятой
suitability[i] = FuncX(population[i], steps);//высчитываем пригодность с точностью 4 знака после запятой
}
old_population = population;//записываем старую популяцию
selection select = new selection(count);
select = selection.selection_proporcional(population, count);//селекция из популяции, отбор к новой популяции
crossover cross = new crossover(select.new_number);//элемент класса скрещивания, создается на основе количества элементов после селекц.
cross = crossover.linear(select.new_population, select.new_number);
mutation mut = new mutation(cross.new_number);
mut = mutation.operation_random(cross.new_population, cross.new_number);
population = mut.new_population;
count = mut.new_number;
double change = 0;
double purpose;
for (i = 0; i < old_count; i++)//сортировка старой популяции, чтобы сначала шли самые не пригодные
{
for (int j = 0; j < old_count - 1; j++)
{
if (prigodnost_x(old_population[j], max_x) > (prigodnost_x(old_population[j + 1], max_x)))
{
change = old_population[j];
old_population[j] = old_population[j + 1];
old_population[j + 1] = change;
}
}
}
purpose = old_population[0];
for (i = 0; i < count; i++)//формирование новой популяции
{
old_population[i] = population[i];
if (prigodnost_x(old_population[i], max_x) > prigodnost_x(purpose, max_x)) purpose = old_population[i];
}
population = old_population;
count = old_count;
double old_purpose = purpose;//минимум предыдущего поколения
triple = 0;
int t = 2;//для отсчета прошедших эпох
do//начало ЭА
{
select = selection.selection_proporcional(population, count);//этап селекции
cross = crossover.linear(select.new_population, select.new_number);//этап скрещивания
mut = mutation.operation_random(cross.new_population, cross.new_number);//этап мутации
population = mut.new_population;//замена текущей популяции на новую
count = mut.new_number;//замена количества элементов
for (i = 0; i < old_count; i++)//сортировка старой популяции, чтобы сначала шли самые не пригодные
{
for (int j = 0; j < old_count - 1; j++)
{
if (prigodnost_x(old_population[j], max_x) > (prigodnost_x(old_population[j + 1], max_x)))
{
change = old_population[j];
old_population[j] = old_population[j + 1];
old_population[j + 1] = change;
}
}
}//конец сортировки старой популяции
for (i = 0; i < count; i++)//формирование новой популяции
{
old_population[i] = population[i];
if (prigodnost_x(old_population[i], max_x) > prigodnost_x(purpose, max_x)) purpose = old_population[i];//поиск минимального элемента в новой популяции
}
if (old_purpose == purpose) triple++;//если минимум предыдущего поколения равен минимуму текущего, +1 к условию останова
else triple = 0;//иначе, сбрасывается
//замена популяции
population = old_population;//замена популяции
count = old_count;//замена количества эл-ов
old_purpose = purpose;//после того как новая популяция становистся старой, старый минимум = новому.
t++;//увеличиваем эпоху на 1
} while (triple < 5);//конец алгоритма, условие останова
int epoh = t;
time.Stop();
stream.WriteLine("Размер популяции: " + count + "| Полученный минимум: " + purpose + "| Значение этого минимума : " + FuncX(purpose, steps) + "| Количество прошедших эпох" + " = " + epoh + "| Прошедшее время " + time.Elapsed);
Console.WriteLine("Полученный минимум:" + purpose + " = " + FuncX(purpose, steps));
time.Reset();
}
Console.ReadLine();
}//конец программы
//целевая функция для тестирования номер 6
public static double FuncX(double xi, int i)
{
Math.Round(xi, 4);
double f = 0;
for (int j = 0; j < i; j++)
{
f += -xi * Math.Sin(Math.Sqrt(Math.Abs(xi)));
}
Math.Round(f, 4);
return f;
}
public static double max_fx()
{
double max;
max = 0;
for (int x = -500; x < 500; x++)
{
if (FuncX(x, 10) > max) max = FuncX(x, 10);
}
return max;
}
public static double prigodnost_x(double x, double max_x)
{
double pr = 0;
double MaxSuit = Math.Abs(FuncX(420.9687, 10)) + Math.Abs(max_x);
pr = MaxSuit - (FuncX(x, 10) + Math.Abs(FuncX(420.9687, 10)));
return pr;
}
public class selection//виды селекции
{
public double[] new_population;
public int new_number;
public selection(int kol)//конструктор селекции , 1 параметр - количество элементов в новой популяции
{
new_population = new double[kol];
new_number = kol;
}
public static selection selection_proporcional(double[] pop, int kol)//пропорциональная селекция
{
//считаем пригодность элементов. Пригодность будем считать так - т.к. число с минимальной ф(х) является наиболее пригодным, то будем считать пригодность по след формуле : ко всем элементам прибавляем |minF(x)| в массиве индивидов, потом суммируем |MinF(x)|+|MaxF(x)|=макс пригодность. пригодность эл-та = макс.пригодность-пригодность элемента+|MinF(x)|
double summ = 0;// сумма значений, для вычисления вероятности выбора
Random choose = new Random();
double minFx;
double maxFx;
double MaxSuit;
int elements = 0;
double[] new_population = new double[kol];//массив новой популяции, для записи в класс селекции
double[] suitability = new double[kol];//массив пригодностей элементов
double[] value = new double[kol];//массив значений
double[] probability = new double[kol];//массив вероятностей выбора
int i;
for (i = 0; i < kol; i++)//заполняем массив значений индивидов
{
value[i] = FuncX(pop[i], 10);
}
minFx = value[0];
maxFx = value[0];
for (i = 0; i < kol; i++)
{
if (value[i] < minFx) minFx = value[i];
if (value[i] > maxFx) maxFx = value[i];
}
MaxSuit = Math.Abs(minFx) + Math.Abs(maxFx);//максимальная пригодность.
for (i = 0; i < kol; i++)
{
suitability[i] = MaxSuit - (value[i] + Math.Abs(minFx));//пригодность каждого элемента
summ += suitability[i];//общая пригодность
}
double OK_prob = -1;
for (i = 0; i < kol; i++)
{
probability[i] = (suitability[i] / summ) * 100;//вероятность выбора в процентах
if (probability[i] > OK_prob) OK_prob = probability[i];
}
for (i = 0; i < kol; i++)//выборка индивидов по вероятности выбора
{
if (probability[i] >= choose.Next(0, Convert.ToInt32(Math.Round(OK_prob))))
{
new_population[elements] = pop[i];
elements++;
}
}
selection select = new selection(elements);
for (i = 0; i < elements; i++)
{
select.new_population[i] = Math.Round(new_population[i], 4);
}
return select;
}//конец пропорциональной селекции
public static selection selection_range(double[] pop, int kol)//ранговая селекция
{
double[] probability = new double[kol];//создаем массив рангов. чем больше ранг, тем ближе к концу должен стоять элемент
double[] new_population = new double[kol];//массив для новой популяции
int elements = 0;
double a = 0;
double prob_z = 0;
double max_prob = 0;
Random rand = new Random();
int summ = 0;
for (int i = 0; i < kol; i++)
{
probability[i] = i + 1;//сюда заносится ранг
summ += i + 1;
for (int j = 0; j < kol - 1; j++)
{
if (FuncX(pop[j], 10) < FuncX(pop[j + 1], 10))//все элементы сортируются по рангу - чем меньше ф(х), тем больше ранг
{
a = pop[j];
pop[j] = pop[j + 1];
pop[j + 1] = a;
}
}
}
for (int z = 0; z < kol; z++)
{
prob_z = (z + 1) / summ;//вероятность ранга пройти в след популяцию
probability[z] = prob_z * 100;//перевод вероятности в 100%
if (max_prob < prob_z) max_prob = prob_z;//поиск максимальной вероятности
}
for (int i = 0; i < kol; i++)
{
if (Math.Round(probability[i]) >= rand.Next(0, Convert.ToInt32(Math.Round(max_prob * 100))))//выборка элемента
{
new_population[elements] = Math.Round(pop[i], 4);
elements++;
}
}
selection select = new selection(elements);//перенос элементов прошедших выборку, в элемент класса селекции
for (int i = 0; i < elements; i++)
{
select.new_population[i] = Math.Round(new_population[i], 4);
}
return select;
}//конец ранговой селекции
public static selection selection_tour(double[] pop, int kol, int group)//турнирная селекция
{
double[] gr_pop = new double[group];
double[] tour_win = new double[kol / group];
int j;
int z;
int for_group;
double change = 0;
for_group = kol / group;
for (int i = 0; i < for_group; i++)//проходим по всем индивидам, которые попадают в группу. если какие то индивиды не попали в группу, они считаются некомпетентными
{
for (j = 0; j < group; j++)//записываем из массива популяции в турнирную группу
{
gr_pop[j] = pop[j + i * group];
}
for (j = 0; j < group; j++)//сортируем элементы в группе, чтобы элемент, максимально подходящий был на 1м месте
{
for (z = 0; z < (group - 2); z++)
{
if (FuncX(gr_pop[z], 10) > FuncX(gr_pop[z + 1], 10))
{
change = gr_pop[z];
gr_pop[z] = gr_pop[z + 1];
gr_pop[z + 1] = change;
}
}
}
tour_win[i] = Math.Round(gr_pop[0], 4);//в этом массиве будут находится победители всех турнирных групп;
}
selection select = new selection(for_group);
select.new_population = tour_win;
return select;
}
}
//виды скрещивания
public class crossover
{
public double[] new_population;
public int new_number;
public crossover(int kol)//конструктор скрещивания , 1 параметр - количество элементов в новой популяции
{
new_population = new double[kol];
new_number = kol;
}
public static crossover flat(double[] pop, int kol)//плоское скрещивание
{
int i;
int h = 0;
double[] new_population = new double[kol];//массив новой популяции
Random rand = new Random();//нужен для скрещивания
int[] gen1 = new int[8];//массив генома 1го родителя
int[] gen2 = new int[8];//массив генома 2го родителя
int[] gen_new = new int[8];//массив генома ребенка
for (i = 0; i < kol - 1; i++)//скрещиваются 1 и 2, 2 и 3, 3 и 4
{
gen1 = mutation.hromosom_to_gen(pop[i]);//геном 1го родителя
gen2 = mutation.hromosom_to_gen(pop[i + 1]);//геном 2го родителя
for (h = 0; h < 8; h++)
{
if (gen1[h] < gen2[h])//чтобы правильно вызвать функцию рандома
gen_new[h] = rand.Next(gen1[h], gen2[h]);//скрещивание
else
gen_new[h] = rand.Next(gen2[h], gen1[h]);
}
new_population[i] = mutation.gens_to_hromosom(gen_new);//собираем гены ребенка в новый хромосом
if ((new_population[i] < 500) & (new_population[i] > -500)) new_population[i] = new_population[i];
else if (new_population[i] < 0) new_population[i] = -499.9999;
else new_population[i] = 499.999;
if (i == kol - 2)//если последний шаг в массиве, для последнего гена, скрещиваем последний и первый ген
{
gen1 = mutation.hromosom_to_gen(pop[kol - 1]);
gen2 = mutation.hromosom_to_gen(pop[0]);
for (h = 0; h < 8; h++)
{
if (gen1[h] < gen2[h])
gen_new[h] = rand.Next(gen1[h], gen2[h]);
else
gen_new[h] = rand.Next(gen2[h], gen1[h]);
}
new_population[i + 1] = mutation.gens_to_hromosom(gen_new);//собираем последний хромосом
if ((new_population[i + 1] < 500) & (new_population[i + 1] > -500)) new_population[i + 1] = new_population[i + 1];
else if (new_population[i + 1] < 0) new_population[i + 1] = -499.9999;
else new_population[i + 1] = 499.999;
}
}
crossover cross = new crossover(kol);//создаем новый элемент класса скрещивание
cross.new_population = new_population;//заносим в него новую популяцию
cross.new_number = kol;
return cross;
}
public static crossover arithmetical(double[] pop, int kol, double n) // арифм.скрещ.
{
int i;
int h = 0;
int old_count = kol;
double[] new_population = new double[kol];//массив новой популяции
Random rand = new Random();//нужен для скрещивания
int[] gen1 = new int[8];//массив генома 1го родителя
int[] gen2 = new int[8];//массив генома 2го родителя
int[] gen_new1 = new int[8];//массив генома ребенка 1
int[] gen_new2 = new int[8];//массив генома ребенка 2
if (kol / 2 == 1)//если количество хромосом нечетное, то скрещиваем последний и первый хромосомы, чтобы создать последний хромосом в массиве
{
kol -= 1;
gen1 = mutation.hromosom_to_gen(pop[kol]);//геном 1го родителя
gen2 = mutation.hromosom_to_gen(pop[0]);//геном 2го родителя
for (h = 0; h < 8; h++)
{
gen_new1[h] = Convert.ToInt32(n * gen1[h] + (1 - n) * gen2[h]);
}
new_population[kol] = mutation.gens_to_hromosom(gen_new1);
}
for (i = 0; i < kol - 1; i++)//скрещиваются 1 и 2, 2 и 3, 3 и 4
{
gen1 = mutation.hromosom_to_gen(pop[i]);//геном 1го родителя
gen2 = mutation.hromosom_to_gen(pop[i + 1]);//геном 2го родителя
for (h = 0; h < 8; h++)
{
gen_new1[h] = Convert.ToInt32(n * gen1[h] + (1 - n) * gen2[h]);//формулы в методе
gen_new2[h] = Convert.ToInt32(n * gen2[h] + (1 - n) * gen1[h]);//см методу
}
new_population[i] = mutation.gens_to_hromosom(gen_new1);//записываем i хромосом
if ((new_population[i] < 500) & (new_population[i] > -500)) new_population[i] = new_population[i];
else if (new_population[i] < 0) new_population[i] = -499.9999;
else new_population[i] = 499.999;
new_population[i + 1] = mutation.gens_to_hromosom(gen_new2);
if ((new_population[i + 1] < 500) & (new_population[i + 1] > -500)) new_population[i + 1] = new_population[i + 1];
else if (new_population[i + 1] < 0) new_population[i + 1] = -499.9999;
else new_population[i + 1] = 499.999;
i++;
}
crossover cross = new crossover(old_count);//создаем новый элемент класса скрещивание
cross.new_number = old_count;
cross.new_population = new_population;//заносим в него новую популяцию
return cross;
}
public static crossover BLXa(double[] pop, int kol, double alpha)\\ BLXa скре.
{
int i;
int h = 0;
double delta;
double[] new_population = new double[kol];//массив новой популяции
Random rand = new Random();//нужен для скрещивания
int[] gen1 = new int[8];//массив генома 1го родителя
int[] gen2 = new int[8];//массив генома 2го родителя
int[] gen_new = new int[8];//массив генома ребенка
for (i = 0; i < kol - 1; i++)//скрещиваются 1 и 2, 2 и 3, 3 и 4
{
gen1 = mutation.hromosom_to_gen(pop[i]);//геном 1го родителя
gen2 = mutation.hromosom_to_gen(pop[i + 1]);//геном 2го родителя
for (h = 0; h < 8; h++)
{
delta = Math.Max(gen1[h], gen2[h]) - Math.Min(gen1[h], gen2[h]);
gen_new[h] = rand.Next(Convert.ToInt32(Math.Min(gen1[h], gen2[h]) - delta * alpha), Convert.ToInt32(Math.Max(gen1[h], gen2[h]) + delta * alpha));
}
new_population[i] = mutation.gens_to_hromosom(gen_new);//собираем гены ребенка в новый хромосом
if ((new_population[i] < 500) & (new_population[i] > -500)) new_population[i] = new_population[i];
else if (new_population[i] < 0) new_population[i] = -499.9999;
else new_population[i] = 499.999;
if (i == kol - 2)//если последний шаг в массиве, для последнего гена, скрещиваем последний и первый ген
{
gen1 = mutation.hromosom_to_gen(pop[kol - 1]);
gen2 = mutation.hromosom_to_gen(pop[0]);
for (h = 0; h < 8; h++)
{
delta = Math.Max(gen1[h], gen2[h]) - Math.Min(gen1[h], gen2[h]);
gen_new[h] = rand.Next(Convert.ToInt32(Math.Min(gen1[h], gen2[h]) - delta * alpha), Convert.ToInt32(Math.Max(gen1[h], gen2[h]) + delta * alpha));
}
new_population[i + 1] = mutation.gens_to_hromosom(gen_new);//собираем последний хромосом
if ((new_population[i + 1] < 500) & (new_population[i + 1] > -500)) new_population[i + 1] = new_population[i + 1];
else if (new_population[i + 1] < 0) new_population[i + 1] = -499.9999;
else new_population[i + 1] = 499.999;
}
}
crossover cross = new crossover(kol);//создаем новый элемент класса скрещивание
cross.new_population = new_population;//заносим в него новую популяцию
cross.new_number = kol;
return cross;
}
public static crossover linear(double[] pop, int kol ) \\скрещ
{
int i;
int h = 0;
double change1 = 0;
double change2 = 0;
double[] new_population = new double[kol];//массив новой популяции
Random rand = new Random();//нужен для скрещивания
int[] gen1 = new int[8];//массив генома 1го родителя
int[] gen2 = new int[8];//массив генома 2го родителя
int[] gen_new1 = new int[8];//массив генома ребенка 1
int[] gen_new2 = new int[8];//массив генома ребенка 2
int[] gen_new3 = new int[8];//массив генома ребенка 2
double[] select = new double[3];//массив для селекции 2х более подходящих детей детей
double[] prob = new double[3];
int old_count = kol;
if (kol / 2 == 1)//если количество хромосом нечетное, то скрещиваем последний и первый хромосомы, чтобы создать последний хромосом в массиве
{
kol -= 1;
gen1 = mutation.hromosom_to_gen(pop[kol]);//геном 1го родителя
gen2 = mutation.hromosom_to_gen(pop[0]);//геном 2го родителя
for (h = 0; h < 8; h++)
{
gen_new1[h] = (gen1[h] + gen2[h]) / 2;//первый ребенок по ф-ле из методы
gen_new2[h] = (3 * gen1[h] - gen2[h]) / 2;//второй -\\-\\-
gen_new3[h] = ((-1) * gen1[h] + 3 * gen2[h]) / 2;//третий -\\-\\-
}
select[0] = mutation.gens_to_hromosom(gen_new1);
select[1] = mutation.gens_to_hromosom(gen_new2);
select[2] = mutation.gens_to_hromosom(gen_new3);
for (int j = 0; j < 3; j++)//считаем функцию ф(х) для кажого индивида, чтобы определить 2х наиболее пригодных
{
prob[j] = FuncX(select[j], 10);//10 - количество шагов для формулы. в мейне = steps
}
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
if (prob[k] > prob[k + 1])//сортируем детей, чтобы в конце массива был детей с минимальной пригодностью (максимальной ф(х))
{
change1 = prob[k + 1];
change2 = select[k + 1];
prob[k + 1] = prob[k];
select[k + 1] = select[k];
prob[k] = change1;
select[k] = change2;
}
}
}
if ((select[0] < 500) & (select[0] > -500)) new_population[kol] = select[0];
else if (select[0] < 0) new_population[kol] = -499.9999;
else new_population[kol] = 499.999;
new_population[kol] = select[0];
}
for (i = 0; i < kol - 1; i++)//скрещиваются 1 и 2, 2 и 3, 3 и 4
{
gen1 = mutation.hromosom_to_gen(pop[i]);//геном 1го родителя
gen2 = mutation.hromosom_to_gen(pop[i + 1]);//геном 2го родителя
for (h = 0; h < 8; h++)
{
gen_new1[h] = (gen1[h] + gen2[h]) / 2;//первый ребенок по ф-ле из методы
gen_new2[h] = (3 * gen1[h] - gen2[h]) / 2;//второй -\\-\\-
gen_new3[h] = ((-1) * gen1[h] + 3 * gen2[h]) / 2;//третий -\\-\\-
}
select[0] = mutation.gens_to_hromosom(gen_new1);
select[1] = mutation.gens_to_hromosom(gen_new2);
select[2] = mutation.gens_to_hromosom(gen_new3);
for (int j = 0; j < 3; j++)//считаем функцию ф(х) для кажого индивида, чтобы определить 2х наиболее пригодных
{
prob[j] = FuncX(select[j], 10);//10 - количество шагов для формулы. в мейне = steps
}
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
if (prob[k] > prob[k + 1])//сортируем детей, чтобы в конце массива был детей с минимальной пригодностью (максимальной ф(х))
{
change1 = prob[k + 1];
change2 = select[k + 1];
prob[k + 1] = prob[k];
select[k + 1] = select[k];
prob[k] = change1;
select[k] = change2;
}
}
}
if ((select[0] < 500) & (select[0] > -500)) new_population[i] = select[0];
else if (select[0] < 0) new_population[i] = -499.9999;
else new_population[i] = 499.999;
if ((select[1] < 500) & (select[1] > -500)) new_population[i + 1] = select[1];
else if (select[1] < 0) new_population[i + 1] = -499.9999;
else new_population[i + 1] = 499.999;
i++;
}
crossover cross = new crossover(old_count);//создаем новый элемент класса скрещивание
cross.new_number = old_count;
cross.new_population = new_population;//заносим в него новую популяцию
return cross;
}
public static crossover fordouble(double[] population, int count) \\скрещ.
{
double_gen pred1 = new double_gen();
double_gen pred2 = new double_gen();
double_gen child1 = new double_gen();
double_gen child2 = new double_gen();
int cross_chance = 80;
int old_count = count;
Random rand = new Random();
int cross = 0;
if (count / 2 != 0)
{
if (cross_chance >= rand.Next(0, 100)) //шанс скрещивания
{
pred1 = double_gen.gens_to_double(mutation.hromosom_to_gen(population[count - 1]));
pred2 = double_gen.gens_to_double(mutation.hromosom_to_gen(population[0]));
cross = rand.Next(1, 6);
for (int i = 0; i < cross; i++)
{
child1.mass[i] = pred1.mass[i];
child2.mass[i] = pred2.mass[i];
}
for (int j = cross; j < 7; j++)
{
child1.mass[j] = pred2.mass[j];
child2.mass[j] = pred1.mass[j];
}
}
population[count - 1] = mutation.gens_to_hromosom(double_gen.double_gen_to_real_gen(child1));
count--;
}
for (int t = 0; t < count - 1; t++)//проходим по всему массиву популяции, старо
{
if (cross_chance >= rand.Next(0, 100))//если вдруг скрещивание случилось
{
pred1 = double_gen.gens_to_double(mutation.hromosom_to_gen(population[t]));
pred2 = double_gen.gens_to_double(mutation.hromosom_to_gen(population[t + 1]));
cross = rand.Next(1, 6);
for (int i = 0; i < cross; i++)
{
child1.mass[i] = pred1.mass[i];
child2.mass[i] = pred2.mass[i];
}
for (int j = cross; j < 7; j++)
{
child1.mass[j] = pred2.mass[j];
child2.mass[j] = pred1.mass[j];
}
}
population[t] = mutation.gens_to_hromosom(double_gen.double_gen_to_real_gen(child1));
population[t + 1] = mutation.gens_to_hromosom(double_gen.double_gen_to_real_gen(child2));
t++;
}//конец скрещивания
crossover fordouble = new crossover(old_count);
fordouble.new_population = population;
return fordouble;
}
public static crossover fordouble_mask(double[] population, int count) \\скрещ.
{
double_gen pred1 = new double_gen();
double_gen pred2 = new double_gen();
double_gen child1 = new double_gen();
double_gen mask = new double_gen();
int cross_chance = 80;
int old_count = count;
Random rand = new Random();
int cross = 0;
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 4; j++)
{
mask.mass[i][j] = rand.Next(0, 1);
}
}
mask.znak = rand.Next(0, 1);
if (count / 2 != 0)
{
if (cross_chance >= rand.Next(0, 100)) //вероятность скрещивания
{
pred1 = double_gen.gens_to_double(mutation.hromosom_to_gen(population[count - 1]));
pred2 = double_gen.gens_to_double(mutation.hromosom_to_gen(population[count - 1]));
cross = rand.Next(1, 6);
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 4; j++)
{
if (mask.mass[i][j] == 1) child1.mass[i][j] = pred1.mass[i][j];
else child1.mass[i][j] = pred2.mass[i][j];
}
}
if (mask.znak == 1) child1.znak = pred1.znak;
else child1.znak = pred2.znak;
population[count - 1] = mutation.gens_to_hromosom(double_gen.double_gen_to_real_gen(child1));
}
count--;
}
for (int t = 0; t < count - 1; t++)//проходим по всему массиву популяции, старо
{
if (cross_chance >= rand.Next(0, 100))//если вдруг скрещивание случилось
{
pred1 = double_gen.gens_to_double(mutation.hromosom_to_gen(population[t]));
pred2 = double_gen.gens_to_double(mutation.hromosom_to_gen(population[t + 1]));
cross = rand.Next(1, 6);
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 4; j++)
{
if (mask.mass[i][j] == 1) child1.mass[i][j] = pred1.mass[i][j];
else child1.mass[i][j] = pred2.mass[i][j];
}
}
if (mask.znak == 1) child1.znak = pred1.znak;
else child1.znak = pred2.znak;
population[t] = mutation.gens_to_hromosom(double_gen.double_gen_to_real_gen(child1));
}
}//конец скрещивания
crossover fordouble = new crossover(old_count);
fordouble.new_population = population;
return fordouble;
}
}
//мутaция
public class mutation
{
public double[] new_population;
public int new_number;
public mutation(int kol)//конструктор скрещивания , 1 параметр - количество элементов в новой популяции
{
new_population = new double[kol];
new_number = kol;
}
public static mutation operation_random(double[] population, int kol) \\мутация случайная
{
Random rand = new Random();
double[] pop = new double[kol];
pop = population;
int[] gens = new int[8];
int chance = 0;
double hromosom = 0;
int p = 0;
if (kol != 0) chance = 100 / kol;//вероятность мутации в процентах 1/N
else if (chance == 0) chance = 100 / 8;//если мутация 1/N близка к 0% (а округленная равна 0) то используем вероятность мутации 1/L
else if (kol == 0) chance = 100 / 8;
for (int i = 0; i < kol; i++)
{
if (chance >= rand.Next(0, 100))//если произошла мутация для текущего индивида
{
gens = hromosom_to_gen(pop[i]);//разбираем хромосом на гены
p = rand.Next(0, 7);//какой ген мутирует
if (p == 0)//если должен мутировать 1ый знаковый ген
{
if ((gens[p + 1] != 0) && (gens[p + 1] != -1))//если действительно знаковый ген,т.е след ген число, то мутирует.
{
//ген мутировал
if (gens[p] == 0) gens[p] = (-1);
else gens[p] = 0;
}
else //если след ген не число, т.е. является знаковым, то проверка дальше
{
if ((gens[p + 2] == 0) & (gens[p + 2] == -1))//если перед геном стоит знаковый ген, то мутирует он
{ //ген мутировал
if (gens[p + 2] == 0) gens[p + 2] = -1;
if (gens[p + 2] == -1) gens[p + 2] = 0;
}
else//если 3ий ген не знаковый, то мутирует 2ой. 4ый ген знаковым быть не может
{
//ген мутировал
if (gens[p + 1] == 0) gens[p + 1] = -1;
if (gens[p + 1] == -1) gens[p + 1] = 0;
}
}
}
else if ((p == 1) & (((gens[p] == 0))) & (gens[0] == 0))//если мутирует 2ой ген, и он является знаковым (при положительном значении числа)
{
if ((gens[p + 1] == 0) || (gens[p + 1] == -1))//если перед геном стоит знаковый ген, то мутирует он
{ //ген мутировал
if (gens[p + 1] == 0) gens[p + 1] = -1;
if (gens[p + 1] == -1) gens[p + 1] = 0;
}
else//если 3ий ген не знаковый, то мутирует 2ой. 4ый ген знаковым быть не может
{
//ген мутировал
if (gens[p] == 0) gens[p] = -1;
if (gens[p] == -1) gens[p] = 0;
}
}
else if ((p == 1) & (((gens[p] == -1))) & (gens[0] == 0))//если мутирует 2ой ген, и он является знаковым (-)
{
gens[p] = 0;//ген мутирует
}
else if ((p == 1) & (((gens[p] != 0))) & (gens[p] != -1))//если ген не знаковый, т.е. ни 0, ни -1, то он мутирует в любое доступное для него значение, от 0 до 4...т.к. ограничение до 500
{
gens[p] = rand.Next(0, 4);
}
else if ((p == 2) & (gens[0] == 0) & (gens[1] == 0) & ((gens[p] == 0) || (gens[p] == -1)))//если должен мутировать ген №2, и он знаковый, то меняется знак
{
if (gens[p] == 0) gens[p] = -1;
else gens[p] = 0;
}
else//если же ген не подходит для всех предыдущих правил исключений, то ген мутирует по общему правилу
{
gens[p] = rand.Next(0, 9);
}
hromosom = gens_to_hromosom(gens);//если мутация прошла, то собираем ген обратно, из новых хромосом
if (hromosom > 500) hromosom = 500;//исключения
if (hromosom < -500) hromosom = -500;//исключения
pop[i] = hromosom;//заменяем в популяции мутировавший ген
}//конец мутации
}
mutation mut = new mutation(kol);
mut.new_population = pop;
mut.new_number = kol;
return mut;
}
public static double sigma(double t, double y, double b, int Emax)
{
Random r = new Random();
double sigma = 0;
sigma = y * (1 - Math.Pow(r.NextDouble(), Math.Pow(1 - (t / Emax), b)));
return sigma;
}
public static mutation operation_ambiguous(double[] population, int kol, double b, double t) \\мутация
{
int eMax = 20;
Random rand = new Random();
double[] pop = new double[kol];
pop = population;
int[] gens = new int[8];
int chance = 0;
double hromosom = 0;
int p = 0;
double a = Math.Abs(10 - b);
int x = 0;
double Ci = 0; //ген для мутации
chance = 100 / kol;//вероятность мутации в процентах 1/N
if (chance == 0) chance = 100 / 8;//если мутация 1/N близка к 0% (а округленная равна 0) то используем вероятность мутации 1/L
for (int i = 0; i < kol; i++)
{
if (chance >= rand.Next(0, 100))//если произошла мутация для текущего индивида
{
gens = hromosom_to_gen(pop[i]);//разбираем хромосом на гены
p = rand.Next(0, 7);//какой ген мутирует
if (p == 0)//если должен мутировать 1ый знаковый ген
{
if ((gens[p + 1] != 0) && (gens[p + 1] != -1))//если действительно знаковый ген,т.е след ген число, то мутирует.
{
//ген мутировал
if (gens[p] == 0) gens[p] = (-1);
else gens[p] = 0;
}
else //если след ген не число, т.е. является знаковым, то проверка дальше
{
if ((gens[p + 2] == 0) & (gens[p + 2] == -1))//если перед геном стоит знаковый ген, то мутирует он
{ //ген мутировал
if (gens[p + 2] == 0) gens[p + 2] = -1;
if (gens[p + 2] == -1) gens[p + 2] = 0;
}
else//если 3ий ген не знаковый, то мутирует 2ой. 4ый ген знаковым быть не может
{
//ген мутировал
if (gens[p + 1] == 0) gens[p + 1] = -1;
if (gens[p + 1] == -1) gens[p + 1] = 0;
}
}
}
else if ((p == 1) & (((gens[p] == 0))) & (gens[0] == 0))//если мутирует 2ой ген, и он является знаковым (при положительном значении числа)
{
if ((gens[p + 1] == 0) || (gens[p + 1] == -1))//если перед геном стоит знаковый ген, то мутирует он
{ //ген мутировал
if (gens[p + 1] == 0) gens[p + 1] = -1;
if (gens[p + 1] == -1) gens[p + 1] = 0;
}
else//если 3ий ген не знаковый, то мутирует 2ой. 4ый ген знаковым быть не может
{
//ген мутировал
if (gens[p] == 0) gens[p] = -1;
if (gens[p] == -1) gens[p] = 0;
}
}
else if ((p == 1) & (((gens[p] == -1))) & (gens[0] == 0))//если мутирует 2ой ген, и он является знаковым (-)
{
gens[p] = 0;//ген мутирует
}
else if ((p == 1) & (((gens[p] != 0))) & (gens[p] != -1))//если ген не знаковый, т.е. ни 0, ни -1, то он мутирует в любое доступное для него значение, от 0 до 4...т.к. ограничение до 500
{
x = rand.Next(0, 1);
if (x == 0)
{
Ci = gens[p];
gens[p] = Convert.ToInt32(Ci + mutation.sigma(t, b - Ci, b, eMax));
Ci = 0;
}
else
{
Ci = gens[p];
gens[p] = Convert.ToInt32(Ci + mutation.sigma(t, Ci - a, b, eMax));
Ci = 0;
}
if (gens[p] > 4) gens[p] = gens[p] / 2;
}
else if ((p == 2) & (gens[0] == 0) & (gens[1] == 0) & ((gens[p] == 0) || (gens[p] == -1)))//если должен мутировать ген №2, и он знаковый, то меняется знак
{
if (gens[p] == 0) gens[p] = -1;
else gens[p] = 0;
}
else//если же ген не подходит для всех предыдущих правил исключений, то ген мутирует по общему правилу
{
x = rand.Next(0, 1);
if (x == 0)
{
Ci = gens[p];
gens[p] = Convert.ToInt32(Math.Round(Ci + mutation.sigma(t, b - Ci, b, eMax)));
Ci = 0;
}
else
{
Ci = gens[p];
gens[p] = Convert.ToInt32(Ci + mutation.sigma(t, Ci - a, b, eMax));
Ci = 0;
}
}
hromosom = gens_to_hromosom(gens);//если мутация прошла, то собираем ген обратно, из новых хромосом
pop[i] = hromosom;//заменяем в популяции мутировавший ген
}//конец мутации
}
mutation mut = new mutation(kol);
mut.new_population = pop;
mut.new_number = kol;
return mut;
}
public static int[] hromosom_to_gen(double hrom)//разбор
{
string hr = Convert.ToString(Math.Round(hrom, 4));
if (hr == "0") hr = "0,0";
int z = 7;
int check = 0;
int[] gens = new int[8];
for (int j = 0; j < 8; j++) gens[j] = 0;
for (int j = 0; j < hr.Length; j++)
{ if (hr[j] == ',')check = 1; }
if (check == 0) { gens[7] = 0; z--; gens[6] = 0; z--; gens[5] = 0; z--; gens[4] = 0; z--; }
else if (hr[hr.Length - 2] == ',') { gens[7] = 0; z--; gens[6] = 0; z--; gens[5] = 0; z--; }
else if (hr[hr.Length - 3] == ',') { gens[7] = 0; z--; gens[6] = 0; z--; }
else if (hr[hr.Length - 4] == ',')//если вдруг в хромосоме 3 значимых цифры после запятой, а не 4, обработка этой ошибки.
{ gens[7] = 0; z--; }//последний элемент сразу 0
for (int i = hr.Length - 1; i >= 0; i--)
{
if (hr[i] == '0' || hr[i] == '1' || hr[i] == '2' || hr[i] == '3' || hr[i] == '4' || hr[i] == '5' || hr[i] == '6' || hr[i] == '7' || hr[i] == '8' || hr[i] == '9')
{
gens[z] = (Convert.ToInt32(hr[i]) - 48);
z--;
}
if (hr[i] == '-')
{
gens[z] = -1;
z--;
}
}
return gens;
}
public static double gens_to_hromosom(int[] gens)//перевод генома индивида в хромосом (массив ген)
{
double hrom;
hrom = 0;
for (int j = 0; j <= 7; j++)
{
if (gens[j] != -1) hrom += gens[j] * Math.Pow(10, (3 - j));
}
for (int i = 0; i < 7; i++) { if (gens[i] == -1) hrom = 0 - hrom; }
if (hrom > 500) hrom = 500;//исключения
if (hrom < -500) hrom = -500;
return hrom;
}
public static mutation fordouble(double[] population, int kol)//мутация для двоичного представления
{
mutation fordouble = new mutation(kol);
Random rand = new Random();
double[] pop = new double[kol];
pop = population;
double_gen dg = new double_gen();
int chance = 0;
int p = 0;
if (kol != 0) chance = 100 / kol;//вероятность мутации в процентах 1/N
else if (chance == 0) chance = 100 / 8;//если мутация 1/N близка к 0% (а округленная равна 0) то используем вероятность мутации 1/L
else if (kol == 0) chance = 100 / 8;
int gen;
for (int i = 0; i < kol; i++)
{
dg = double_gen.gens_to_double(mutation.hromosom_to_gen(pop[i]));
if (chance >= rand.Next(0, 100))//если произошла мутация для текущего индивида
{
p = rand.Next(0, 7);//какой из 8 ген мутирует, 0 - знак , 1-7 числа
if (p == 0) { if (dg.znak == 1)dg.znak = 0; else dg.znak = 1; }//если мутировал знаковый ген, то меняется знак
else if (p == 1)//если ген №1 - он не может быть больше 5, поэтому в геноме 0000, первый ген не мутирует
{
gen = rand.Next(1, 3);
if (dg.mass[p][gen] == 0) dg.mass[p][gen] = 1; else dg.mass[p][gen] = 0;
}
else//если ген другой, не 1ый, мутирует любой из 4х генов
{
gen = rand.Next(0, 3);
if (dg.mass[p][gen] == 0) dg.mass[p][gen] = 1; else dg.mass[p][gen] = 0;
}
}
pop[i] = mutation.gens_to_hromosom(double_gen.double_gen_to_real_gen(dg));
}
fordouble.new_population = pop;
return fordouble;
}
}
public class double_gen//для представления в бинарной системе
{
public int[][] mass;//первый массив - номер гена, второй массив - ген в бинарном представлении
public string str;//строка, представляющая хромосом
public int znak;//знак начального хромосома
public double_gen()
{
mass = new int[7][];
for (int i = 0; i < 7; i++)
{
mass[i] = new int[4];
for (int j = 0; j < 4; j++) mass[i][j] = 0;
}
str = "";
znak = 0;
}
public static double_gen gens_to_double(int[] gen)
{
double_gen dd_gen = new double_gen();
int check = 0;
for (int i = 0; i < 8; i++)
{
if (gen[i] == -1) check = 1;//определение знака числа
}
if (check == 1) dd_gen.znak = 1;
else dd_gen.znak = 0;
int j = 0;
for (int i = 1; i < 8; i++)//перевод в двоичное число
{
if ((gen[i] == 0) || (gen[i] == -1)) { dd_gen.mass[i - 1][0] = 0; dd_gen.mass[i - 1][1] = 0; dd_gen.mass[i - 1][2] = 0; dd_gen.mass[i - 1][3] = 0; }
if (gen[i] == 1) { dd_gen.mass[i - 1][0] = 0; dd_gen.mass[i - 1][1] = 0; dd_gen.mass[i - 1][2] = 0; dd_gen.mass[i - 1][3] = 1; }
if (gen[i] == 2) { dd_gen.mass[i - 1][0] = 0; dd_gen.mass[i - 1][1] = 0; dd_gen.mass[i - 1][2] = 1; dd_gen.mass[i - 1][3] = 0; }
if (gen[i] == 3) { dd_gen.mass[i - 1][0] = 0; dd_gen.mass[i - 1][1] = 0; dd_gen.mass[i - 1][2] = 1; dd_gen.mass[i - 1][3] = 1; }
if (gen[i] == 4) { dd_gen.mass[i - 1][0] = 0; dd_gen.mass[i - 1][1] = 1; dd_gen.mass[i - 1][2] = 0; dd_gen.mass[i - 1][3] = 0; }
if (gen[i] == 5) { dd_gen.mass[i - 1][0] = 0; dd_gen.mass[i - 1][1] = 1; dd_gen.mass[i - 1][2] = 0; dd_gen.mass[i - 1][3] = 1; }
if (gen[i] == 6) { dd_gen.mass[i - 1][0] = 0; dd_gen.mass[i - 1][1] = 1; dd_gen.mass[i - 1][2] = 1; dd_gen.mass[i - 1][3] = 0; }
if (gen[i] == 7) { dd_gen.mass[i - 1][0] = 0; dd_gen.mass[i - 1][1] = 1; dd_gen.mass[i - 1][2] = 1; dd_gen.mass[i - 1][3] = 1; }
if (gen[i] == 8) { dd_gen.mass[i - 1][0] = 1; dd_gen.mass[i - 1][1] = 0; dd_gen.mass[i - 1][2] = 0; dd_gen.mass[i - 1][3] = 0; }
if (gen[i] == 9) { dd_gen.mass[i - 1][0] = 1; dd_gen.mass[i - 1][1] = 0; dd_gen.mass[i - 1][2] = 0; dd_gen.mass[i - 1][3] = 1; }
}
string s = "";
for (int i = 0; i < 7; i++)
{
for (j = 0; j < 4; j++)
{
s += dd_gen.mass[i][j];
}
}
dd_gen.str = s;
return dd_gen;
}
public static int[] double_gen_to_real_gen(double_gen dd_gen)
{
int[] gen = new int[8];
if (dd_gen.znak == 1) gen[0] = -1;
else gen[0] = 0;
for (int i = 0; i < 7; i++)
{
gen[i + 1] = 0;
for (int j = 0; j < 4; j++)
{
gen[i + 1] += dd_gen.mass[i][j] * Convert.ToInt32(Math.Pow(2, 3 - j));
}
}
return gen;
}
}
}
}