Мне пришлось столкнуться с одним из методов оптимизации — генетическим алгоритмом. Хочу рассказать вам об этом методе.
Для решения задачи генетическим алгоритмом будем использовать две хромосомы, которые генерируются случайным образом, путём последовательного заполнения разрядов (генов), сразу в бинарном виде с соблюдением ранее заданных ограничений, и всякие последующие изменения в популяции затрагивают сначала генетический уровень, а только потом анализируются последствия этих изменений, но никогда не наоборот.
Создание начальной популяции. На начальной стадии выполнения генетического алгоритма инициализируется определённая популяция хромосом, в которой элементы массива X (биты), заполнены случайным образом, хотя применяются также и самонаводящиеся способы (если их можно определить заранее). Размер популяции, как правило, пропорционален количеству оптимизируемых параметров.
Генетические алгоритмы решают задачи, работая с популяцией из некоторого числа наугад взятых решений. Здесь используется прямая аналогия с таким механизмом. Они работают с совокупностью особей — популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее приспособленности согласно тому, насколько хорошо соответствующее ей решение задачи (в природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы).
Наиболее приспособленные особи получают возможность воспроизводить потомство с помощью «перекрестного скрещивания» с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.
Стратегии отбора. Стратегии отбора являются составной частью генетического алгоритма и определяют достойных для скрещивания особей.
Рассмотрим рулеточный отбор, который применяется в данной задаче.
Рулеточный отбор. Отбор происходит по принципу рулетки, при этом площадь сегмента колеса рулетки, сопоставленного конкретной хромосоме, пропорциональна величине её относительной функции приспособленности. В данной стратегии сначала определяются приспособленности особей в популяции. Затем создается некое подобие круговой диаграммы, сектора которой раздаются особям, причем, чем больше приспособленность у особи, тем больше у нее сектор.
После этого N раз запускается рулетка и особь из сектора, где она остановится, выбирается для селекции, но с поверхности рулетки не слезает.
Выбор оператора селекции. Генетические операторы необходимы, чтобы применить принципы наследственности и изменчивости к виртуальной популяции. У этих операторов есть такое свойство как вероятность. Т.е. описываемые операторы не обязательно применяются ко всем скрещиваемым особям, что вносит дополнительный элемент неопределенности в процесс поиска решения. В данном случае, неопределенность является своеобразной степенью свободы работы генетического алгоритма.
Оператор кроссовера. Оператор кроссовер, иногда называемый кроссинговером, является основным генетическим оператором, за счет которого производится обмен генетическим материалом между особями. Он моделирует процесс скрещивания особей.
Пусть имеются две родительские особи с хромосомами. Случайным образом определяется точка внутри хромосомы, в которой обе хромосомы делятся на две части и обмениваются ими. Назовем эту точку точкой разрыва. Вообще говоря, в англоязычной литературе она называется точкой кроссовера.
Для задачи используем одноточечный тип кроссовера. При нем родительские хромосомы разрезаются только в одной случайной точке.
Оператор мутации. Оператор мутации (mutation operator) состоит в замене отдельных бит (при двоичном кодировании) на противоположные.
Данный оператор необходим для выбивания популяции из локального экстремума и способствует защите от преждевременной сходимости. Однако необходимо иметь ввиду, что случайные мутации приводят к повреждению уже частично приспособленных векторов. Обычно мутации подвергается не более 1-5% бит всей популяции хромосом.
Классическая схема предполагает ограничение численности потомков путем использования вероятности кроссовера. Такая модель придает величине, соответствующей численности потомков, вообще говоря, недетерминированный характер.
В качестве генетических операторов получения новых генотипов потомков, используя генетическую информацию хромосомных наборов родителей, применяем одноточечный тип кроссовера.
Стратегии формирования нового поколения. После скрещивания особей необходимо решить проблему о том, какие из новых особей войдут в следующее поколение, а какие — нет, и что делать с их предками.
Для этого создается промежуточная популяция, которая включает в себя как родителей, так и их потомков. Члены этой популяции оцениваются, а затем из них выбирается самый лучший, который и войдёт в следующее поколение.
Отбором в генетическом алгоритме, называется процесс формирования новой популяции из старой, после чего старая популяция погибает. После отбора к новой популяции опять применяются операции кроссовера и мутации, затем опять происходит отбор, и так далее. Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе. Можно комбинировать стратегии отбора и формирования следующего поколения как угодно — ограничений нет никаких.
Суть принципа элитизма заключается в том, что в новое поколение включаются лучшие родительские особи. Их число может быть от 1 и больше. Использование элитизма позволяет не потерять хорошее промежуточное решение, но, в то же время, из-за этого алгоритм может застрять в локальном экстремуме. Однако можно сделать вывод, что в большинстве случаев эллитизм нисколько не вредит поиску решения, и главное — это предоставить алгоритму возможность анализировать разные строки из пространства поиска.
Таким образом, модель отбора определяет, каким образом следует строить популяцию следующего поколения. Как правило, вероятность участия индивидуума в скрещивании берется пропорциональной его приспособленности. Используем стратегию эллитизма, при которой несколько лучших индивидуумов переходят в следующее поколение без изменений, не участвуя в кроссовере и отборе. Каждое следующее поколение будет в среднем лучше предыдущего. Когда приспособленность индивидуумов перестает заметно увеличиваться, процесс останавливают и в качестве решения задачи оптимизации берут наилучшего из найденных индивидуумов.
Реализация генетического алгоритма на C#:
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Windows.Forms;
namespace GA_sharp
{
class GA
{
int Real_Iter;
int Num_var; //количество переменных
int Num_Ent; //количество особей
int Num_Iter; //количество итераций
int Tour_size;
double Cross_prob; //вероятность кроссовера
double Mut_prob; //вероятность мутации
double[] Min; //нижняя граница значений переменных
double[] Max; //верхняя граница значений переменных
double[] Den; //точность переменных
double[] Ans; //массив ответов
double MinFF; //минимальная ФЦ популяции
public double[][][] log_array;
public bool loggin = false;
Motor_Sharp.CData Data;
Motor_Sharp.CCalculator Calculator;
public Motor_Sharp.CResult Result;
bool[] OptParams;
bool[] FF_kind;
double[] FF_Wanted;
public double[] GetRes(double[] x)
{
double[] pars = Data.GetData();
int j = 0;
for (int i = 0; i < OptParams.Length; i++)
if (OptParams[i])
{
pars[i] = x[j];
j++;
}
Calculator.Data.SetData(pars);
Calculator.Calculate();
return Calculator.Res.GetRes();
}
double FF(double[] x)
{
int j = 0;
double[] pars = Calculator.Data.GetOptimizationParams();
for (int i = 0; i < OptParams.Length; i++)
if (OptParams[i])
{
pars[i] = x[j]; j++;
}
Calculator.Data.SetOptimizationParams(pars);
Calculator.Calculate();
double res = 0;
double[] curr_Res = Calculator.Res.GetRes();
j = 0;
for (int i = 0; i < FF_kind.Length; i++)
if (FF_kind[i])
{
res += Math.Pow((curr_Res[i] — FF_Wanted[j]) / curr_Res[i], 2);
j++;
}
return res;
}
double DecodeSingle(String code, double Min, double Den)
{
if (code != null)
return Den * int.Parse(code) + Min;
else return 0;
}
double[] GetX(String[] DNA, int[] Var_L, double[] Min, double[] Max, double[] Den)
{
double[] x = new double[DNA.Length];
for (int i = 0; i < Var_L.Length; i++)
x[i] = DecodeSingle(DNA[i], Min[i], Den[i]);
return x;
}
double GetFF(String[] DNA, int[] Var_L, double[] Min, double[] Max, double[] Den)
{
return FF(GetX(DNA, Var_L, Min, Max, Den));
}
int FindMin(double[] Arr)
{
double minVal = Arr[0];
int num = 0;
for (int i = 1; i < Arr.Length; i++)
if (minVal > Arr[i])
{
minVal = Arr[i];
num = i;
}
return num;
}
int FindMin(double[] Comm_Arr, int[] Num_Arr)
{
double minVal = Comm_Arr[Num_Arr[0]];
int num = Num_Arr[0];
for (int i = 1; i < Num_Arr.Length; i++)
if (minVal > Comm_Arr[Num_Arr[i]])
{
minVal = Comm_Arr[i];
num = Num_Arr[i];
}
return num;
}
public void InitGA(int N_var, int N_Ent, int N_Iter)
{
Num_var = N_var;
Num_Ent = N_Ent;
Num_Iter = N_Iter;
//инициализация массивов
Array.Resize(ref Min, Num_var);
Array.Resize(ref Max, Num_var);
Array.Resize(ref Den, Num_var);
}
public void InitCalculator(Motor_Sharp.CData Data, bool[] par, bool[] ff, double[] ffw)
{
Calculator = new Motor_Sharp.CCalculator();
Calculator.Data=Data;
OptParams = par;
FF_kind = ff;
FF_Wanted = ffw;
}
public void SetGAOpt(double C_prob, double M_prob, int A_size)
{
Tour_size = A_size;
Cross_prob = C_prob;
Mut_prob = M_prob;
}
public void InitVar(double[] min, double[] max, double[] den)
{
Min = min;
Max = max;
Den = den;
}
public void Run()
{
//локальные переменные
Random rnd1 = new Random();
Random rnd_int = new Random();
int i, j, pop_num; //счетчики
int par1num, par2num; //номера особей для взаимодействия
String[] parstr1 = new String[Num_var];
String[] parstr2 = new String[Num_var]; //родительские геномы
String[] chistr1 = new String[Num_var];
String[] chistr2 = new String[Num_var]; //дочерние геномы
double[] FF = new double[Num_Ent]; //массив ФЦ популяции
double[] FF_bar = new double[Num_Ent]; //массив адаптированных ФЦ популяции
String[][] parent = new string[Num_Ent][];//[Num_Ent][Num_var]
String[][] child = new string[Num_Ent][]; //популяции
int[] Chrom_Len = new int[Num_var]; //длины кодов переменных особи
int[] Tour = new int[Tour_size]; //массив для турнирного выбора родителей
int crossover_place; //точка кроссовера/мутации
double Summ_FF; //накопление суммарной фц
double Rand_Val; //случайная величина
double Auto_End_FF = 1000;
int Auto_End_Count = 0;
Real_Iter = 0;
double roulette;
//------------------инициалзация записи в лог файл и массив-------
StreamWriter fout;
if (loggin)
{
log_array = new double[Num_Iter][][];// хранятся все ответы
for (i = 0; i < Num_Iter; i++)
{
Array.Resize(ref log_array[i], Num_Ent);
for (j = 0; j < Num_Ent; j++) Array.Resize(ref log_array[i][j], 3);
}
}
//-------------------инициализация массивов-----------------------
Array.Resize(ref Ans, Num_var);
Array.Resize(ref parent, Num_Ent); Array.Resize(ref child, Num_Ent);
for (i = 0; i < Num_Ent; i++) Array.Resize(ref parent[i], Num_var);
for (i = 0; i < Num_Ent; i++) Array.Resize(ref child[i], Num_var);
//--------------подсчитываем длины днк и отрезков для переменных--
for (i = 0; i < Num_var; i++)
Chrom_Len[i] = (int)Math.Floor(Math.Log10((int)Math.Ceiling((Max[i] — Min[i]) / Den[i]) + 1));
//--------------генерация начальной популяции---------------------
for (i = 0; i < Num_Ent; i++)
for (j = 0; j < Num_var; j++)
{
parent[i][j] = rnd_int.Next((int)Math.Ceiling((Max[j] — Min[j]) / Den[j])).ToString();// генерим случайный инт
while (parent[i][j].Length <= Chrom_Len[j])//добиваем его до максимальной длины нулями
parent[i][j] = '0' + parent[i][j];
}
if (loggin)
for (i = 0; i < Num_Ent; i++)
{
log_array[0][i][0] = GetFF(parent[i], Chrom_Len, Min, Max, Den);
log_array[0][i][1] = GetX(parent[i], Chrom_Len, Min, Max, Den)[0];
log_array[0][i][2] = GetX(parent[i], Chrom_Len, Min, Max, Den)[1];
}
//---------начало глобальной итерации------------
for (pop_num = 1; pop_num < Num_Iter; pop_num++)
{
// подсчет значений ФЦ популяции и на хождение минимальной и суммарной ФЦ
Real_Iter = pop_num;
FF[0] = GetFF(parent[0], Chrom_Len, Min, Max, Den);
MinFF = FF[0];
Summ_FF = 0;
for (i = 1; i < Num_Ent; i++)
{
FF[i] = GetFF(parent[i], Chrom_Len, Min, Max, Den);
Summ_FF += FF[i];
if (MinFF > FF[i]) MinFF = FF[i];
}
//инвертирование и нормализация ФЦ(для рулетки)
for (i = 0; i < Num_Ent; i++)
FF_bar[i] = (Summ_FF — FF[i]) / Summ_FF / (Num_Ent — 1);
for (j = 0; j < Num_Ent; j++)
{
//механизм выбора родителей — рулетка
roulette = 0;
i = 0;
Rand_Val = rnd1.NextDouble();
while (roulette <= Rand_Val && i < Num_Ent)
{
roulette += FF_bar[i];
i++;
}
par1num = i — 1;
roulette = 0;
i = 0;
Rand_Val = rnd1.NextDouble();
while (roulette <= Rand_Val && i < Num_Ent)
{
roulette += FF_bar[i];
i++;
}
par2num = i — 1;
// скрещивание
Rand_Val = rnd1.NextDouble();
if (Rand_Val <= Cross_prob)
{
parstr1 = parent[par1num];
parstr2 = parent[par2num];
for (i = 0; i < Num_var; i++)
{
crossover_place = rnd_int.Next(Chrom_Len[i]); //точка кроссовера
chistr1[i] = parstr1[i].Substring(0, crossover_place) + parstr2[i].Substring(crossover_place, Chrom_Len[i] — -crossover_place);
chistr2[i] = parstr2[i].Substring(0, crossover_place) + parstr1[i].Substring(crossover_place, Chrom_Len[i] — -crossover_place);
if (chistr1[i].Length != chistr1[i].Length)
MessageBox.Show(«error»);
} //поменяли куски хромосом в точке кроссовера
}
//мутация
Rand_Val = rnd1.NextDouble();
if (Rand_Val <= Mut_prob)
{
for (i = 0; i < Num_var; i++)
{
crossover_place = rnd_int.Next(Chrom_Len[i] — 1);
chistr1[rnd_int.Next(Num_var)].Remove(crossover_place, 1);
chistr1[rnd_int.Next(Num_var)].Insert(crossover_place, rnd_int.Next(9).ToString());
}
}
Rand_Val = rnd1.NextDouble();
if (Rand_Val <= Mut_prob)
{
for (i = 0; i < Num_var; i++)
{
crossover_place = rnd_int.Next(Chrom_Len[i] — 1);
chistr2[rnd_int.Next(Num_var)].Remove(crossover_place, 1);
chistr2[rnd_int.Next(Num_var)].Insert(crossover_place,
rnd_int.Next(9).ToString());
}
}
//сравниваем потомков и далее выбираем лучшего
if (GetFF(chistr1, Chrom_Len, Min, Max, Den) > >GetFF(chistr2, Chrom_Len, Min, Max, Den))
child[j] = chistr1;
else child[j] = chistr2;
//поменять GetFF
if (GetFF(child[j], Chrom_Len, Min, Max, Den) > FF[par2num])
child[j] = parstr2;
if (GetFF(child[j], Chrom_Len, Min, Max, Den) > FF[par1num])
child[j] = parstr1;
}
parent = child;
if (loggin)
for (i = 0; i < Num_Ent; i++)
{
log_array[pop_num][i][0] = GetFF(parent[i], Chrom_Len, Min, Max, Den);
log_array[pop_num][i][1] = GetX(parent[i], Chrom_Len, Min, Max, Den)[0];
log_array[pop_num][i][2] = GetX(parent[i], Chrom_Len, Min, Max, Den)[1];
}
}
Ans = GetX(parent[0], Chrom_Len, Min, Max, Den);
Calculator.Calculate();
Result = Calculator.Res;
if (loggin)
{
fout = new StreamWriter(«log.txt»); //лог-файл
for (i = 0; i < log_array.Length; i++)
{
fout.WriteLine("=======iteration num " + i + "==========");
for (j = 0; j < log_array[i].Length; j++)
fout.WriteLine(log_array[i][j][0].ToString() + "\t" + log_array[i][j][1].ToString() + "\t" + log_array[i][j][2].ToString());
}
fout.Close();
}
}
public double[] GetAns()
{
double[] FAns = new double[Num_var + 1];
FAns[0] = MinFF;
for (int i = 1; i <= Num_var; i++)
FAns[i] = Ans[i — 1];
return FAns;
}
}
}
Для решения задачи генетическим алгоритмом будем использовать две хромосомы, которые генерируются случайным образом, путём последовательного заполнения разрядов (генов), сразу в бинарном виде с соблюдением ранее заданных ограничений, и всякие последующие изменения в популяции затрагивают сначала генетический уровень, а только потом анализируются последствия этих изменений, но никогда не наоборот.
Создание начальной популяции. На начальной стадии выполнения генетического алгоритма инициализируется определённая популяция хромосом, в которой элементы массива X (биты), заполнены случайным образом, хотя применяются также и самонаводящиеся способы (если их можно определить заранее). Размер популяции, как правило, пропорционален количеству оптимизируемых параметров.
Генетические алгоритмы решают задачи, работая с популяцией из некоторого числа наугад взятых решений. Здесь используется прямая аналогия с таким механизмом. Они работают с совокупностью особей — популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее приспособленности согласно тому, насколько хорошо соответствующее ей решение задачи (в природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы).
Наиболее приспособленные особи получают возможность воспроизводить потомство с помощью «перекрестного скрещивания» с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.
Стратегии отбора. Стратегии отбора являются составной частью генетического алгоритма и определяют достойных для скрещивания особей.
Рассмотрим рулеточный отбор, который применяется в данной задаче.
Рулеточный отбор. Отбор происходит по принципу рулетки, при этом площадь сегмента колеса рулетки, сопоставленного конкретной хромосоме, пропорциональна величине её относительной функции приспособленности. В данной стратегии сначала определяются приспособленности особей в популяции. Затем создается некое подобие круговой диаграммы, сектора которой раздаются особям, причем, чем больше приспособленность у особи, тем больше у нее сектор.
После этого N раз запускается рулетка и особь из сектора, где она остановится, выбирается для селекции, но с поверхности рулетки не слезает.
Выбор оператора селекции. Генетические операторы необходимы, чтобы применить принципы наследственности и изменчивости к виртуальной популяции. У этих операторов есть такое свойство как вероятность. Т.е. описываемые операторы не обязательно применяются ко всем скрещиваемым особям, что вносит дополнительный элемент неопределенности в процесс поиска решения. В данном случае, неопределенность является своеобразной степенью свободы работы генетического алгоритма.
Оператор кроссовера. Оператор кроссовер, иногда называемый кроссинговером, является основным генетическим оператором, за счет которого производится обмен генетическим материалом между особями. Он моделирует процесс скрещивания особей.
Пусть имеются две родительские особи с хромосомами. Случайным образом определяется точка внутри хромосомы, в которой обе хромосомы делятся на две части и обмениваются ими. Назовем эту точку точкой разрыва. Вообще говоря, в англоязычной литературе она называется точкой кроссовера.
Для задачи используем одноточечный тип кроссовера. При нем родительские хромосомы разрезаются только в одной случайной точке.
Оператор мутации. Оператор мутации (mutation operator) состоит в замене отдельных бит (при двоичном кодировании) на противоположные.
Данный оператор необходим для выбивания популяции из локального экстремума и способствует защите от преждевременной сходимости. Однако необходимо иметь ввиду, что случайные мутации приводят к повреждению уже частично приспособленных векторов. Обычно мутации подвергается не более 1-5% бит всей популяции хромосом.
Классическая схема предполагает ограничение численности потомков путем использования вероятности кроссовера. Такая модель придает величине, соответствующей численности потомков, вообще говоря, недетерминированный характер.
В качестве генетических операторов получения новых генотипов потомков, используя генетическую информацию хромосомных наборов родителей, применяем одноточечный тип кроссовера.
Стратегии формирования нового поколения. После скрещивания особей необходимо решить проблему о том, какие из новых особей войдут в следующее поколение, а какие — нет, и что делать с их предками.
Для этого создается промежуточная популяция, которая включает в себя как родителей, так и их потомков. Члены этой популяции оцениваются, а затем из них выбирается самый лучший, который и войдёт в следующее поколение.
Отбором в генетическом алгоритме, называется процесс формирования новой популяции из старой, после чего старая популяция погибает. После отбора к новой популяции опять применяются операции кроссовера и мутации, затем опять происходит отбор, и так далее. Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе. Можно комбинировать стратегии отбора и формирования следующего поколения как угодно — ограничений нет никаких.
Суть принципа элитизма заключается в том, что в новое поколение включаются лучшие родительские особи. Их число может быть от 1 и больше. Использование элитизма позволяет не потерять хорошее промежуточное решение, но, в то же время, из-за этого алгоритм может застрять в локальном экстремуме. Однако можно сделать вывод, что в большинстве случаев эллитизм нисколько не вредит поиску решения, и главное — это предоставить алгоритму возможность анализировать разные строки из пространства поиска.
Таким образом, модель отбора определяет, каким образом следует строить популяцию следующего поколения. Как правило, вероятность участия индивидуума в скрещивании берется пропорциональной его приспособленности. Используем стратегию эллитизма, при которой несколько лучших индивидуумов переходят в следующее поколение без изменений, не участвуя в кроссовере и отборе. Каждое следующее поколение будет в среднем лучше предыдущего. Когда приспособленность индивидуумов перестает заметно увеличиваться, процесс останавливают и в качестве решения задачи оптимизации берут наилучшего из найденных индивидуумов.
Реализация генетического алгоритма на C#:
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Windows.Forms;
namespace GA_sharp
{
class GA
{
int Real_Iter;
int Num_var; //количество переменных
int Num_Ent; //количество особей
int Num_Iter; //количество итераций
int Tour_size;
double Cross_prob; //вероятность кроссовера
double Mut_prob; //вероятность мутации
double[] Min; //нижняя граница значений переменных
double[] Max; //верхняя граница значений переменных
double[] Den; //точность переменных
double[] Ans; //массив ответов
double MinFF; //минимальная ФЦ популяции
public double[][][] log_array;
public bool loggin = false;
Motor_Sharp.CData Data;
Motor_Sharp.CCalculator Calculator;
public Motor_Sharp.CResult Result;
bool[] OptParams;
bool[] FF_kind;
double[] FF_Wanted;
public double[] GetRes(double[] x)
{
double[] pars = Data.GetData();
int j = 0;
for (int i = 0; i < OptParams.Length; i++)
if (OptParams[i])
{
pars[i] = x[j];
j++;
}
Calculator.Data.SetData(pars);
Calculator.Calculate();
return Calculator.Res.GetRes();
}
double FF(double[] x)
{
int j = 0;
double[] pars = Calculator.Data.GetOptimizationParams();
for (int i = 0; i < OptParams.Length; i++)
if (OptParams[i])
{
pars[i] = x[j]; j++;
}
Calculator.Data.SetOptimizationParams(pars);
Calculator.Calculate();
double res = 0;
double[] curr_Res = Calculator.Res.GetRes();
j = 0;
for (int i = 0; i < FF_kind.Length; i++)
if (FF_kind[i])
{
res += Math.Pow((curr_Res[i] — FF_Wanted[j]) / curr_Res[i], 2);
j++;
}
return res;
}
double DecodeSingle(String code, double Min, double Den)
{
if (code != null)
return Den * int.Parse(code) + Min;
else return 0;
}
double[] GetX(String[] DNA, int[] Var_L, double[] Min, double[] Max, double[] Den)
{
double[] x = new double[DNA.Length];
for (int i = 0; i < Var_L.Length; i++)
x[i] = DecodeSingle(DNA[i], Min[i], Den[i]);
return x;
}
double GetFF(String[] DNA, int[] Var_L, double[] Min, double[] Max, double[] Den)
{
return FF(GetX(DNA, Var_L, Min, Max, Den));
}
int FindMin(double[] Arr)
{
double minVal = Arr[0];
int num = 0;
for (int i = 1; i < Arr.Length; i++)
if (minVal > Arr[i])
{
minVal = Arr[i];
num = i;
}
return num;
}
int FindMin(double[] Comm_Arr, int[] Num_Arr)
{
double minVal = Comm_Arr[Num_Arr[0]];
int num = Num_Arr[0];
for (int i = 1; i < Num_Arr.Length; i++)
if (minVal > Comm_Arr[Num_Arr[i]])
{
minVal = Comm_Arr[i];
num = Num_Arr[i];
}
return num;
}
public void InitGA(int N_var, int N_Ent, int N_Iter)
{
Num_var = N_var;
Num_Ent = N_Ent;
Num_Iter = N_Iter;
//инициализация массивов
Array.Resize(ref Min, Num_var);
Array.Resize(ref Max, Num_var);
Array.Resize(ref Den, Num_var);
}
public void InitCalculator(Motor_Sharp.CData Data, bool[] par, bool[] ff, double[] ffw)
{
Calculator = new Motor_Sharp.CCalculator();
Calculator.Data=Data;
OptParams = par;
FF_kind = ff;
FF_Wanted = ffw;
}
public void SetGAOpt(double C_prob, double M_prob, int A_size)
{
Tour_size = A_size;
Cross_prob = C_prob;
Mut_prob = M_prob;
}
public void InitVar(double[] min, double[] max, double[] den)
{
Min = min;
Max = max;
Den = den;
}
public void Run()
{
//локальные переменные
Random rnd1 = new Random();
Random rnd_int = new Random();
int i, j, pop_num; //счетчики
int par1num, par2num; //номера особей для взаимодействия
String[] parstr1 = new String[Num_var];
String[] parstr2 = new String[Num_var]; //родительские геномы
String[] chistr1 = new String[Num_var];
String[] chistr2 = new String[Num_var]; //дочерние геномы
double[] FF = new double[Num_Ent]; //массив ФЦ популяции
double[] FF_bar = new double[Num_Ent]; //массив адаптированных ФЦ популяции
String[][] parent = new string[Num_Ent][];//[Num_Ent][Num_var]
String[][] child = new string[Num_Ent][]; //популяции
int[] Chrom_Len = new int[Num_var]; //длины кодов переменных особи
int[] Tour = new int[Tour_size]; //массив для турнирного выбора родителей
int crossover_place; //точка кроссовера/мутации
double Summ_FF; //накопление суммарной фц
double Rand_Val; //случайная величина
double Auto_End_FF = 1000;
int Auto_End_Count = 0;
Real_Iter = 0;
double roulette;
//------------------инициалзация записи в лог файл и массив-------
StreamWriter fout;
if (loggin)
{
log_array = new double[Num_Iter][][];// хранятся все ответы
for (i = 0; i < Num_Iter; i++)
{
Array.Resize(ref log_array[i], Num_Ent);
for (j = 0; j < Num_Ent; j++) Array.Resize(ref log_array[i][j], 3);
}
}
//-------------------инициализация массивов-----------------------
Array.Resize(ref Ans, Num_var);
Array.Resize(ref parent, Num_Ent); Array.Resize(ref child, Num_Ent);
for (i = 0; i < Num_Ent; i++) Array.Resize(ref parent[i], Num_var);
for (i = 0; i < Num_Ent; i++) Array.Resize(ref child[i], Num_var);
//--------------подсчитываем длины днк и отрезков для переменных--
for (i = 0; i < Num_var; i++)
Chrom_Len[i] = (int)Math.Floor(Math.Log10((int)Math.Ceiling((Max[i] — Min[i]) / Den[i]) + 1));
//--------------генерация начальной популяции---------------------
for (i = 0; i < Num_Ent; i++)
for (j = 0; j < Num_var; j++)
{
parent[i][j] = rnd_int.Next((int)Math.Ceiling((Max[j] — Min[j]) / Den[j])).ToString();// генерим случайный инт
while (parent[i][j].Length <= Chrom_Len[j])//добиваем его до максимальной длины нулями
parent[i][j] = '0' + parent[i][j];
}
if (loggin)
for (i = 0; i < Num_Ent; i++)
{
log_array[0][i][0] = GetFF(parent[i], Chrom_Len, Min, Max, Den);
log_array[0][i][1] = GetX(parent[i], Chrom_Len, Min, Max, Den)[0];
log_array[0][i][2] = GetX(parent[i], Chrom_Len, Min, Max, Den)[1];
}
//---------начало глобальной итерации------------
for (pop_num = 1; pop_num < Num_Iter; pop_num++)
{
// подсчет значений ФЦ популяции и на хождение минимальной и суммарной ФЦ
Real_Iter = pop_num;
FF[0] = GetFF(parent[0], Chrom_Len, Min, Max, Den);
MinFF = FF[0];
Summ_FF = 0;
for (i = 1; i < Num_Ent; i++)
{
FF[i] = GetFF(parent[i], Chrom_Len, Min, Max, Den);
Summ_FF += FF[i];
if (MinFF > FF[i]) MinFF = FF[i];
}
//инвертирование и нормализация ФЦ(для рулетки)
for (i = 0; i < Num_Ent; i++)
FF_bar[i] = (Summ_FF — FF[i]) / Summ_FF / (Num_Ent — 1);
for (j = 0; j < Num_Ent; j++)
{
//механизм выбора родителей — рулетка
roulette = 0;
i = 0;
Rand_Val = rnd1.NextDouble();
while (roulette <= Rand_Val && i < Num_Ent)
{
roulette += FF_bar[i];
i++;
}
par1num = i — 1;
roulette = 0;
i = 0;
Rand_Val = rnd1.NextDouble();
while (roulette <= Rand_Val && i < Num_Ent)
{
roulette += FF_bar[i];
i++;
}
par2num = i — 1;
// скрещивание
Rand_Val = rnd1.NextDouble();
if (Rand_Val <= Cross_prob)
{
parstr1 = parent[par1num];
parstr2 = parent[par2num];
for (i = 0; i < Num_var; i++)
{
crossover_place = rnd_int.Next(Chrom_Len[i]); //точка кроссовера
chistr1[i] = parstr1[i].Substring(0, crossover_place) + parstr2[i].Substring(crossover_place, Chrom_Len[i] — -crossover_place);
chistr2[i] = parstr2[i].Substring(0, crossover_place) + parstr1[i].Substring(crossover_place, Chrom_Len[i] — -crossover_place);
if (chistr1[i].Length != chistr1[i].Length)
MessageBox.Show(«error»);
} //поменяли куски хромосом в точке кроссовера
}
//мутация
Rand_Val = rnd1.NextDouble();
if (Rand_Val <= Mut_prob)
{
for (i = 0; i < Num_var; i++)
{
crossover_place = rnd_int.Next(Chrom_Len[i] — 1);
chistr1[rnd_int.Next(Num_var)].Remove(crossover_place, 1);
chistr1[rnd_int.Next(Num_var)].Insert(crossover_place, rnd_int.Next(9).ToString());
}
}
Rand_Val = rnd1.NextDouble();
if (Rand_Val <= Mut_prob)
{
for (i = 0; i < Num_var; i++)
{
crossover_place = rnd_int.Next(Chrom_Len[i] — 1);
chistr2[rnd_int.Next(Num_var)].Remove(crossover_place, 1);
chistr2[rnd_int.Next(Num_var)].Insert(crossover_place,
rnd_int.Next(9).ToString());
}
}
//сравниваем потомков и далее выбираем лучшего
if (GetFF(chistr1, Chrom_Len, Min, Max, Den) > >GetFF(chistr2, Chrom_Len, Min, Max, Den))
child[j] = chistr1;
else child[j] = chistr2;
//поменять GetFF
if (GetFF(child[j], Chrom_Len, Min, Max, Den) > FF[par2num])
child[j] = parstr2;
if (GetFF(child[j], Chrom_Len, Min, Max, Den) > FF[par1num])
child[j] = parstr1;
}
parent = child;
if (loggin)
for (i = 0; i < Num_Ent; i++)
{
log_array[pop_num][i][0] = GetFF(parent[i], Chrom_Len, Min, Max, Den);
log_array[pop_num][i][1] = GetX(parent[i], Chrom_Len, Min, Max, Den)[0];
log_array[pop_num][i][2] = GetX(parent[i], Chrom_Len, Min, Max, Den)[1];
}
}
Ans = GetX(parent[0], Chrom_Len, Min, Max, Den);
Calculator.Calculate();
Result = Calculator.Res;
if (loggin)
{
fout = new StreamWriter(«log.txt»); //лог-файл
for (i = 0; i < log_array.Length; i++)
{
fout.WriteLine("=======iteration num " + i + "==========");
for (j = 0; j < log_array[i].Length; j++)
fout.WriteLine(log_array[i][j][0].ToString() + "\t" + log_array[i][j][1].ToString() + "\t" + log_array[i][j][2].ToString());
}
fout.Close();
}
}
public double[] GetAns()
{
double[] FAns = new double[Num_var + 1];
FAns[0] = MinFF;
for (int i = 1; i <= Num_var; i++)
FAns[i] = Ans[i — 1];
return FAns;
}
}
}