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

Как нам говорит википедия, генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации.

Автор . Дата: 01.11.2014

Введение

Как нам говорит википедия, генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Т.е. правильность этого алгоритма не доказана, но он чаше работает, чем обратное, чем и заслужил право на существование.

Применяется для:

- оптимизации функций;

- решения задач на графах (задача коммивояжёра, задача о рюкзаке);

- обучения нейронных сетей;

- и др.

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

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

Берётся некоторая функция f(x1, x2, …, xn), где x1, x2, …, xn – параметры.

От этих параметров зависит количество генов в хромосоме, т.е создаются одномерные массивы(хромосома), содержащие значения этих параметров(гены).

Пусть f(x) – это уравнение:

5a + b^(2/3) + 1/c + d = 17.

Выделим следующие шаги:

  1. Создание первого поколения;
  2. Вычисление коэффициентов выживаемости;
  3. Вычисление «подходящести»;
  4. Выбор родителей;
  5. Размножение;
  6. Мутации;
  7. Формирование нового поколения;
  8. Возврат на шаг 2;

 

1) Создание первого поколения.

Создается некоторое количество особей(хромосом). Каждая содержит n параметров, которые задаются случайно, но лучше, чтобы диапазон значений входил в область допустимых значений(ОДЗ).

Предположим, что корни уравнения лежать на отрезке от 0 до 17.

Пусть количество особей – 4.

Выберем случайные значения параметров a, b, c, d для каждой:

  1. 1, 7, 9, 12;
  2. 2, 8, 10, 11;
  3. 0, 15, 4, 6;
  4. 14, 2, 8, 3.

Это и будет первое поколение.

2) Вычисление коэффициентов выживаемости(fitness).

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

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

Подставляем параметры в уравнение 5a + b^(2/3) + 1/c + d – 17 = 0.

1) |5 + 3,65 + 0,11 + 12 – 17| = 3,76;

2) |10 + 4 + 0,1 + 11 – 17| = 8,1;

3) |0 + 6,08 + 0,25 + 6 – 17| = 4,67;

4) |85 + 1,58 + 0,125 +3 - 17| = 72.

Самое близкое к нулю первое значение, поэтому параметры первой хромосомы наиболее близки к искомым.

3) Вычисление «подходящести».

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

И поделить каждое обратное значение fitness на S:

Approach[k] = Fk/S, где Fk ­=

Расcчитаем S:

S = 1/3.76 + 1/8.1 + 1/4.67 + 1/72 = 0.26 + 0.12 + 0.21 + 0.01 = 0.6.

Значения подходящести:

1) 0.26/06 = 0.43 = 43%;

2) 0.12/0.6 = 0.2 = 20%;

3) 0.21/0.6 = 0.35 = 35%;

4) 0.01/0.6 = 0.01 = 1%.

4) Выбор родителей.

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

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

Пары пусть будут следующие:

1) 1 – 3;

2) 3 – 1;

5) Размножение.

Выбраны пары. Каждая особь содержит свой вариант генов:

x1, x2, …, xn – первая особь;

y1, y2, …, yn – вторая особь.

Существует несколько способов поместить информацию о родителях в потомков. Здесь будет использоваться "кроссовер" (cross-over).

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

Хромосома-отец

Хромосома-мать

Хромосома-потомок

1 | 7, 9, 12

0 | 15, 4, 6

1, 15, 4, 6

0, 15 | 4, 6

1, 7 | 9, 12

0, 15, 9, 12

 

6) Мутации.

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

Мутирует 2-я и 4-я особь.

2) 2, 8, 10, 11 -> 2, 7, 5, 11;

4) 14, 2, 8, 3 -> 1, 2, 8, 3;

7) Формирование нового поколения.

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

В наше новое поколение войдут особи:

  1. 1, 15, 4, 6;
  2. 0, 15, 9, 12;
  3. 2, 7, 5, 11;
  4. 1, 2, 8, 3.

8) Переходим на шаг 2.
И вновь находим fitness.

Продолжаем до тех пор, пока fitness не будет меньше или равно установленной погрешности.

Программная реализация

В качестве языка выбран C#.

Программа реализует решение уравнения, представленного выше.

Приведём список соответствия этапов алгоритма и методов:

Этап Метод Входящие параметры
Создание первого поколения double[,]  CreateFirstGeneration(int Nparams, int count_chromos, double strt, double fnsh) Кол-во генов, кол-во хромосом, диапазон выбора параметров
Вычисление коэффициентов выживаемости double[]  CalcFitness(double[,] generation, int count_chromos, double[] abcd) Предыдущее поколение, кол-во хромосом, гены
Вычисление «подходящести» int[] CalcApproach(double[] fits, int count_chromos) Коэф-ты выживаемости, кол-во хромосом
Выбор родителей

int[,] SelectParents(int[] best)

int[] SelectBest(int[] approach)

int[] SelectMutants(int[] best)

Список лучших хромосом

Список подходящести

Список лучших хромосом

Размножение

Мутации

Формирование нового поколения

double[,] CreateNewgeneration(int[,] parents, int[] n_mutants, double[,] generation, double[] abcd, double strt, double fnsh) Матрица родителей, список мутантов, предыдушее поколение, гены, диапазон выбора параметров

Листинг

Текст программы
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace GeneticAlgorithm
{
    public partial class Form1 : Form
    {   
        const int y_val = 17;
        /*
        int count_chromos = 100;
        int Nparams = 4;
        double strt = 1;
        double fnsh = 17;*/
        public Form1()
        {
            InitializeComponent();
        }
        //y = 5 * abcd[0] + Math.Pow(abcd[1], 2 / 3) + 1 / abcd[2] + abcd[3];
        private void button1_Click(object sender, EventArgs e)
        {
            textBox1.Clear();
            string best_fits;
            string best_res;
            int count_chromos = (int)numericUpDown1.Value;
            double strt = Convert.ToDouble(textBox2.Text);
            double fnsh = Convert.ToDouble(textBox3.Text);
            double eps = Convert.ToDouble(textBox4.Text);
            int over = (int)numericUpDown2.Value;
            double[] result = Solver(4, count_chromos, strt, fnsh, eps, out best_fits, out best_res, over);
            richTextBox1.Text = best_fits;
            richTextBox2.Text = best_res;
             for (int j = 0; j < result.Length; j++)
                 {
                   textBox1.Text += Convert.ToString(result[j]) + "   "; 
                 }            
        }

        double[] Solver(int Nparams, int count_chromos, double strt, double fnsh, double eps, out string lst_bst_fits, out string lst_bst_res, int over)
        {
            double[] result = new double[Nparams];
            double[] abcd = new double[4]; 
            double[,] generation;
            double[] fits;
            int[] approach;
            int[] best;
            int[,] parents;
            int[] mutants;
            double[,] new_generation;
            double fits_min = 35;
            lst_bst_fits = "";
            lst_bst_res = "";
            int k = 1; //step
            generation = CreateFirstGeneration(Nparams, count_chromos, strt, fnsh);
            while(k < over)
            {
                fits = CalcFitness(generation, count_chromos, abcd);
                 fits_min = fits.Min();
                 //outer
                 lst_bst_fits += Convert.ToString(fits_min) + " Шаг" + Convert.ToString(k) + "\n"; k++;
                 for (int i = 0; i < fits.Length; i++)
                {
                    if(fits[i] == fits_min)
                    {
                        for (int j = 0; j < abcd.Length; j++)
                        {
                            lst_bst_res += Convert.ToString(generation[i, j]) + "   "; 
                        }
                        lst_bst_res += "\n";
                        break;
                    }
                }               
                 //----
                 if (Math.Abs(fits_min) < eps)
                 {
                     for (int i = 0; i < fits.Length; i++)
                     {
                         if (fits[i] == fits_min)
                         {
                             for (int j = 0; j < abcd.Length; j++)
                             {
                                 result[j] = generation[i, j];
                             }
                             lst_bst_res += "\n";
                             break;
                         }
                     }           
                     break;
                 }
                 approach = CalcApproach(fits, count_chromos);
                 best = SelectBest(approach);
                 parents = SelectParents(best);
                 mutants = SelectMutants(best);
                 new_generation = CreateNewgeneration(parents, mutants, generation, abcd, strt, fnsh);
                 generation = new_generation;               
            }
            if (k >= over) 
            { 
                lst_bst_res += "\n" + "Не сходится! =(";
                lst_bst_fits += "\n" + "Не сходится! =(";
            }
            return result;
        }

        double[,] CreateNewgeneration(int[,] parents, int[] n_mutants, double[,] generation, double[] abcd, double strt, double fnsh)
        {
            double[,] new_generation = new double[generation.Length / abcd.Length, abcd.Length];
            double[,] childs = new double[parents.Length / 2, abcd.Length];
            double[,] mutants = new double[n_mutants.Length, abcd.Length];
            //cross-over
            Random rnd = new Random();
            int l = 1;
            for (int i = 0; i < childs.Length/abcd.Length; i++)
            {
                l = rnd.Next(1, abcd.Length);
                for(int j = 0; j < abcd.Length; j++)
                {
                    if(j < l)
                    {
                        childs[i, j] = generation[parents[i, 0], j];
                    }
                    else
                    {
                        childs[i, j] = generation[parents[i, 1], j];
                    }                  
                }
            }
            //mutation          
            int str_n = (int)(strt * 100);
            int fnsh_n = (int)(fnsh * 100);
            for (int i = 0; i < n_mutants.Length; i++)
            {
                l = rnd.Next(1, abcd.Length);
                for (int j = 0; j < abcd.Length; j++)
                {
                    if (j < l)
                    {
                        mutants[i, j] = generation[n_mutants[i], j];
                    }
                    else
                    {
                        mutants[i, j] = ((double)rnd.Next(str_n, fnsh_n)) / 100;
                    }
                }
            }
            //appending childs & mutants
            for (int i = 0; i < new_generation.Length / abcd.Length; i++)
            {
                for (int j = 0; j < abcd.Length; j++)
                {
                    if (i < new_generation.Length / abcd.Length / 2)
                    {
                        new_generation[i, j] = childs[i, j];
                    }
                    else
                    {
                        new_generation[i, j] = mutants[i - new_generation.Length / abcd.Length / 2, j];
                    }                   
                }
            }
                return new_generation;
        }
        int[] SelectMutants(int[] best)
        {
            int[] mutants = new int[best.Length];
            int k = 0;
            for (int i = 0; i < best.Length * 2; i++)
            {
                bool flag = true;
                for (int j = 0; j < best.Length; j++)
                {
                    if (i == best[j])
                    {
                        flag = false;
                    }
                }
                if(flag)
                {
                    mutants[k] = i; k++;
                }
            }
            return mutants;
        }
        int[] SelectBest(int[] approach) //половина лучших
        {
            int[] best = new int[approach.Length/2];
            int k = 0;
            for (int i = 10000; i > 0; i--)
           {
                for(int j = 0; j < approach.Length; j++)
                {
                    if(approach[j] == i)
                    {
                        best[k] = j; k++;
                    }
                    if (k >= best.Length) break;
                }
                if (k >= best.Length) break;
           }
            return best;
        }
        int[,] SelectParents(int[] best)
       {
           Random rnd = new Random();
           int[,] parents = new int[best.Length, 2];
           for (int i = 0; i < best.Length; i++)
           {
               int x = best[rnd.Next(best.Length)];

               parents[i, 0] = x;
               int y = best[rnd.Next(best.Length)];
               while (y == parents[i, 0])
               {
                   y = best[rnd.Next(best.Length)];
               }
               parents[i, 1] = y;
           }
           return parents;
       }
        int[] CalcApproach(double[] fits, int count_chromos)
        {
            int[] approach = new int[count_chromos];
            double[] inv_cf = new double[count_chromos];
            double summ_inv_cf = 0;
            for (int i = 0; i < count_chromos; i++)
            {
                inv_cf[i] = 1 / fits[i];
                summ_inv_cf += inv_cf[i];
            }
            for (int i = 0; i < count_chromos; i++)
            {
                approach[i] = Convert.ToInt32(Math.Round(inv_cf[i] / summ_inv_cf * 100, 3) * 100);
            }
            return approach;
        }

        double[] CalcFitness(double[,] generation, int count_chromos, double[] abcd)
        {
            double[] fit = new double[count_chromos];
            for (int i = 0; i < count_chromos; i++)
            {
                for(int j = 0; j < generation.Length/count_chromos; j++)
                {
                    abcd[j] = generation[i, j];
                }
                fit[i] = Math.Abs(5 * abcd[0] + Math.Pow(abcd[1], (0.666)) + (1 / abcd[2]) + abcd[3] - y_val);
            }

            return fit;
        }

        double[,] CreateFirstGeneration(int Nparams, int count_chromos, double strt, double fnsh)
        {
            double[,] res = new double[count_chromos, Nparams];
            Random rnd = new Random();
            int str_n = (int)(strt * 100);
            int fnsh_n = (int)(fnsh * 100);
            for(int i = 0; i < count_chromos; i++)
            {
                for(int j = 0; j < Nparams; j++)
                {
                    res[i, j] = ((double)rnd.Next(str_n, fnsh_n)) / 100;         
                }
            }

            return res;
        }
    }
}

 

Пример работы

Здесь количество итераций – количество проходов до того, как алгоритм завершит работу, так и не достигнув идеала; чем больше особей, тем большая вероятность найти искомые значения.

A = 2.95; B =2.1; C = 8.96; D = 2.25.

Подставим в уравнение:

5 * 2.95+ 2.1^(2/3) + 1/8.96 + 2.25 = 17;

12.95 + 1.64 + 0.11 + 2.25 = 17;

16.95 = 17.

Учитывая точность и погрешность округления, делаем вывод, что программа работает верно.

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

Использованные источники информации:

- Википедия;

- algolist.manual.ru