Бібліотека для реалізації генетичних алгоритмів в. NET Framework 2.0 (вихідні коди), Різне, Програмування, статті

Теорія


Для початку треба сказати, що з себе представляють ці самі генетичні алгоритми. Детально описувати їх не буду, тому що ви можете знайти багато хороших статей по ним та інтернеті. А якщо в двох словах, то генетичний алгоритм – це такий алгоритм за допомогою якого можна шукати мінімум (або максимум) цільової функції, яка залежить від багатьох змінних. Такий алгоритм застосовують, коли цільова функція складна і не зрозуміло як ще можна знайти її екстремум. Для прикладу, цільовою функцією може бути помилка між отриманими даними і розрахунковими з параметрами, які треба встановити. Наприклад, в исходниках, які ви можете скачати за посиланням у кінці статті, алгоритм обчислює коефіцієнти перед змінними.


Ідея генетичних алгоритмів взята з теорії Дарвіна про еволюцію. Ми створюємо види (рішення), які схрещуються між собою, мутують, самий невдалі вмирають. Суть алгоритму в тому, що спочатку ми маємо набір довільних видів. Кожен вид містить в собі набір хромосом (змінних, значення яких треба знайти), які й треба розрахувати. Спочатку ми маємо в популяції види, у яких всі хромосоми випадкові. Після цього відбувається схрещування видів і, можливо, мутирование. Після цього відбираються найкращі види (у яких мінімальна цільова функція), а найгірші (з максимальними цільовими функціями і з хромосомами, які не потрапляють в заданий інтервал) видаляються з популяції. На наступній ітерації схрещування, мутирование і відбір повторюється. Завдяки цьому у нас поступово залишаються тільки ті, у яких цільова функція близька до мінімуму. І так повторюється до тих пір поки не буде знайдено рішення, яке задовольняє нас з точки зору похибки. Також часто алгоритм зупиняють, якщо протягом заданого числа поколінь (ітерацій) не вдається знайти ще кращий вигляд, ніж той, що у нас є.


Реалізація


Реалізація алгоритму була зроблена на мові C # для. NET Framework 2.0.


Базовий клас для видів


Всі види повинні бути похідними від базового класу BaseSpecies , де TSpecies – конкретний тип для виду. TSpecies повинен бути похідним від класу BaseSpecies .






/// <summary> / / / Базовий клас для виду
     /// </summary>
     abstract public class BaseSpecies<TSpecies>: IComparable
        where TSpecies: BaseSpecies<TSpecies>
     { # Region Статичні функції для схрещування хромосом базових типів
             /// <summary> / / / Схрестити дві хромосоми типу double
             /// </summary> / / / 1-а хромосома / / / 2-а хромосома / / / Нова хромосома
             static protected double Cross (double x, double y)
             {
                 …
             }
                static protected Int32 Cross (Int32 x, Int32 y)
             {
                 …
             }
               static protected Int64 Cross (Int64 x, Int64 y)
             {
                 …
             }
             #endregion # Region Методи для мутацій в базових типах
             /// <summary> / / / Мутація для типу double
             /// </summary> / / / Мутіруемое значення / / / Промутірующее значення
             static protected double Mutation (double val)
             {
                 …
             }
              static protected Int32 Mutation (Int32 val)
             {
                 …
             }
             static protected Int64 Mutation (Int64 val)
             {
                 …
             }
             #endregion
             /// <summary> / / / Мертвий чи вид.
             /// </summary> / / / Наприклад, коли хромосови не потрапляють в задані інтервал
             protected Boolean m_Dead = false;
             /// <summary> / / / Мертвий чи вид?
             /// </summary>
             public bool Dead
             {
                     get        { return m_Dead; }
             }
             /// <summary> / / / Перевіряє, щоб всі хромосоми потрапили б в задані інтервали. / / / В іншому випадку позначає вид як “мертвий”.
             /// </summary>
             abstract public void TestChromosomes();
             /// <summary> / / / Метод для схрещування себе з іншим видом
             /// </summary> / / / Інший вид / / / Отриманий вид
             abstract public TSpecies Cross (TSpecies Species);
             /// <summary> / / / Провести мутацію
             /// </summary>
             abstract public void Mutation();
             /// <summary> / / / Цільова функція. Повинна в разі вдалого набору хромосом прагнути до свого мінімуму
             /// </summary> / / / Значення цільової функції
             abstract public double FinalFunc
             {
                     get;
             }
             #region IComparable Members
             /// <summary> / / / Вид вважається більше, якщо він мертвий або у нього більше цільова функція
             /// </summary>
             /// <param name=”obj”></param>
             /// <returns></returns>
             public Int32 CompareTo(object obj)
             {
                 …
             }
             #endregion
        }

Як видно з коду, BaseSpecies – це абстрактний клас, який містить статичні protected-методи для схрещування і мутації. Розберемо деякі методи детальніше. Почнемо з методів, які необхідно реалізувати в похідних класах.





abstract public void TestChromosomes();

Цей методи повинен встановлювати внутрішню захищену Булеву змінну m_Dead, яка показує, чи підходять хромосоми з обмежень, які на них накладають (наприклад, в нашому прикладі, потрапляють Чи значення хромосом у відрізок [-5.0; 5.0]). Якщо значення хромосом нас влаштовують, то m_Dead треба встановити в false, інакше в true. З цієї змінної (отримується через властивість Dead) популяція відкидає свідомо невдалі види.


Наступний метод, який необхідно реалізувати в похідному класі, це






abstract public TSpecies Cross (TSpecies Species);

Цей метод створює новий вид, схрещуючи себе і інший вид, який передається як аргумент. Тут треба зробити деякі пояснення. Зазвичай, якщо вид містить кілька хромосом, схрещують хромосоми “одного виду “, тобто в нашому випадку схрещуємо a0 себе (тобто this) і a0 іншого виду, анологично схрещуємо a1 і a1, тобто немає сенсу схрещувати a0 себе і a1 іншого класу. Можливо, у вас буде задача, де це знадобиться, але я так сходу її придумати не зможу.


Сенс схрещування полягає в тому, що беремо одну частину хромосоми себе і другу частину іншого виду і створюємо з них нову хромосому, яка і буде міститися в новому вигляді. Часто хромосоми схрещують побайтово. Суть його полягає в тому, що спочатку випадково вибираємо точку розриву (схрещування) хромосоми, потім створюємо нову хромосому, яка складається з лівої частини першої хромосоми і правої другий. Нехай наприклад у нас є дві хромосоми (8-бітові для простоти): 10110111 і 01110010. Випадково вибираємо точку розриву (відзначена символом “/”):


101 / 10111
011 / 10010
Звідси ми може зробити дві різні хромосоми це 101 10010 і 011 10111. Яку з них вибрати – це також можна вирішити генератором випадкових чисел. Також можна шукати дві і більше точок перетину. Таким чином, ми повинні мати конструктор, який створює вигляд з хромосом.


Для того, щоб не треба було винаходити велосипед, в класі BaseSpecies є публічні статичні методи для схрещування хромосом деяких типів (Double, Int64 і Int32). Розберемо детальніше перші два методу. В даному випадку по суті є дві точки перечеченія – в середині слова та знак числа, тобто спочатку схрещуються хромосоми побитово без урахування знака, а потім також випадково беремо знак від однієї з хромосоми.


Розглянемо код.






/// <summary> / / / Схрестити дві хромосоми типу double
 /// </summary> / / / 1-а хромосома / / / 2-а хромосома / / / Нова хромосома
 static protected double Cross (double x, double y)
 {
         Int64 ix = BitConverter.DoubleToInt64Bits(x);
         Int64 iy = BitConverter.DoubleToInt64Bits(y);
         double res = BitConverter.Int64BitsToDouble(BitCross(ix, iy));
         if (m_Rnd.Next() % 2 == 0)
         {
                 if (x * res < 0)
                 {
                         res = -res;
                 }
         }
         else
         {
                 if (y * res < 0)
                 {
                         res = -res;
                 }
         }
         return res;
 }

Працює цей метод таким чином: спочатку перетворимо хромосоми з типу Double в Int64. Це зроблено для того, щоб можна було б без проблем схрещувати побитово. (Дякуємо henson-у з форуму RSDN за те, що підказав, Що є метод DoubleToInt64Bits. Власне все ця гілка форуму знаходиться тут.) Після схрещування вже типів Int64 без урахування знака (про це трохи пізніше), переводимо число назад до Double, а потім беремо знак однієї з двох хромосом. Також я бачив реалізацію генетичного алгоритму, де для схрещування дрібних хромосом просто брали їх середнє арифметичне, проте в тих, прикладах, які я пробував, такий метод працює краще.


А тепер давайте подивимося як відбувається схрещування типів Int64:






/// <summary> / / / Схрестити побитово без урахування знака дві хромосоми типу Int64
 /// </summary> / / / 1-а хромосома / / / 2-а хромосома / / / Нова хромосома
 static protected Int64 BitCross (Int64 x, Int64 y)
 { / / Число біт, що залишилися зліва від точки перетину хромосом
         int Count = m_Rnd.Next(62) + 1;
         Int64 mask = ~0;
         mask = mask << (64 – Count);
 return (x & mask) / (y & ~mask);
 }
 /// <summary> / / / Схрестити побитово з урахуванням знака дві хромосоми типу Int64
 /// </summary> / / / 1-а хромосома / / / 2-а хромосома / / / Нова хромосома
 static protected Int64 Cross (Int64 x, Int64 y)
 {
         Int64 res = BitCross(x, y);
         if (m_Rnd.Next() % 2 == 0)
         {
                 if (x * res < 0)
                 {
                         res = -res;
                 }
         }
         else
         {
                 if (y * res < 0)
                 {
                         res = -res;
                 }
         }
         return res;
 }

Як видно з коду, спочатку схрещуються хромосоми без урахування знака, а потім (як і з типом Double) вибирається знак однієї з хромосом. Точніше, це працює так, що порівнюють знак обраної хромосоми з результатом, і, якщо знаки не співпали (твір менше нуля), то знак результату змінюється на протилежний. Схрещування без урахування знаків – це просто гра з битами.


Якщо вас з якихось причин не влаштовують ці методи для схрещування, то ви можете зробити свої і використовувати їх, а ми переходимо до наступного абстрактного методу, який треба реалізувати.


public void Mutation (); Тут все дуже схоже на схрещування. Мутація діє на одну хромосому. У теорії при мутації можуть відбуватися будь-які зміни. Але в даній реалізації мутація змінює один біт в слові. Ось приклад коду:






/// <summary> / / / Мутація для типу double
 /// </summary> / / / Мутіруемое значення / / / Промутірующее значення
 static protected double Mutation (double val)
 {
     UInt64 x = BitConverter.ToUInt64(BitConverter.GetBytes(val), 0);
     UInt64 mask = 1;
     mask <<= m_Rnd.Next(63);
     x ^= mask;
     double res = BitConverter.ToDouble(BitConverter.GetBytes(x), 0);
     return res;
 }
 /// <summary> / / / Мутація для типу Int64
 /// </summary> / / / Мутіруемое значення / / / Промутірующее значення
 static protected Int64 Mutation (Int64 val)
 {
     Int64 mask = 1;
     mask <<= m_Rnd.Next(63);
     return val ^ mask;
 }

Мутації відбуваються порівняно рідко. Наприклад, часто ймовірність мутації роблять 5-10%, але іноді варто спробувати зробити її побільше (приблизно 30%). Також досить часто в якості мутації для дробових чисел краще застосовувати не написану вище функцію, а просто генератор випадкових чисел, який видає випадкове число в потрібному нам інтервалі. У доданому прикладі для дрібних чисел так і зроблено, а для цілих хромосом використовується мутація, описана тут.


Реалізація популяції (клас Population)


А тепер розглянемо клас популяції, де живуть, розмножуються і помирають види. Ви будете додавати свої види в цей клас (точніше в масив видів, що знаходиться в цьому класі). Клас Population оголошений як






public class Population<TSpecies> where TSpecies:BaseSpecies<TSpecies>

Як видно, він має generic-параметр, який представляє собою вид, який має бути похідним від BaseSpecies


Почнемо з властивостей, які треба налаштувати перед початком роботи алгоритму.
MaxSize (Int32) – Максимальне число видів, яке може містити популяція. Це той розмір, до якого “урізається” популяція після схрещування. За замовчуванням 500.
CrossPossibility (Double) – Ймовірність схрещування. Вона повинна бути в інтервалі (0.0; 1.0]. Якщо ця умова не виконується, то впадає виняток ArgumentOutOfRangeException. За замовчуванням це значення встановлено в 0.95.
MutationPossibility (Double) – Ймовірність мутації. Вона повинна бути в інтервалі [0.0; 1.0). Якщо ця умова не виконується, то впадає виняток ArgumentOutOfRangeException.
Впринципі, можна було б ввести ще ймовірність відбору, але в даному випадку вона вважається рівною 1.0. В іншому випадку треба було б видаляти види з популяції не всі підряд найгірші, а з деякою вірогідністю. Але мертві види (нагадаю, що це види, у яких хромосоми не потрапляють в заданий інтервал або не задовольняє іншим умовам) треба видаляти в будь-якому випадку.


А тепер розглянемо публічні методи, які необхідно викликати.


public void Add (TSpecies species) – Додати новий вид в популяцію. Зауважте, що ви повинні вручну додавати необхідну кількість видів. Перед початком роботи алгоритму треба, щоб в популяції було хоча б два види. Число видів в популяції може бути менше, ніж встановлене значення MaxSize. Якщо після схрещування розмір популяції менше MaxSize, то просто не видаляються найгірші види (навіть мертві).


Щоб отримати наступну популяцію, необхідно викликати метод void NextGeneration(). Робота цього методу може займати досить багато часу, тому краще всього його викликати з окремого потоку. Давайте подивимося що він робить.






/// <summary> / / / Оновити популяцію (отримати слудующие покоління)
/// </summary>
public void NextGeneration()
{
    if (m_Generation == 0 && m_Species.Count == 0)
    {
        throw new ZeroSizePopulationException();
    } / / Спочатку схрестімо
    Cross(); / / Промутіруем і заодно перевіримо всі хромосоми
    foreach (BaseSpecies<TSpecies> species in m_Species)
    { / / Якщо треба мутувати з урахуванням ймовірності.
        if (m_Rnd.NextDouble() <= m_MutationPossibility)
        {
            species.Mutation();
        }
        species.TestChromosomes();
    } / / Відберемо самі живучі види
    m_Species.Sort();
    Selection();
    m_Generation++;
}

Спочатку метод перевіряє, щоб при першому виклику методу (при нульовому поколінні, про покоління трохи пізніше) розмір популяції був би більше 2 (інакше нема кого схрещувати). Якщо це не так, то впадає виняток SmallSizePopulationException. Після цього відбувається схрещування видів:






/// <summary> / / / Отримати нові види схрещуванням
/// </summary>
protected void Cross()
{ / / Розмір до початку поповнення популяції (щоб не схрещувати нові види, / / Які додаються в кінець списку)
    Int32 OldSize = m_Species.Count; / / Номер пари для схрещується виду
    Int32 Count = m_Species.Count;
    for (int i = 0; i < Count; ++i)
    { / / Якщо треба схрещувати з урахуванням ймовірності.
        if (m_Rnd.NextDouble() <= m_CrossPossibility)
        { / / Додаємо в список вид, отриманий схрещуванням чергового виду та / / Виду з випадковим номером.
            m_Species.Add (m_Species[i].Cross (m_Species[m_Rnd.Next (OldSize)] ) );
        }
    }
}

При схрещуванні перебираємо всі види і схрещуємо їх до встановленої ймовірністю схрещування з іншими видами, які вибираються випадково.


Після схрещування відбувається мутація видів також із заданою вірогідністю, а після схрещування йде тест хромосом. Потім сортуємо види за значенням їх цільової функції. Метод Sort визначено в класі BaseSpecies, тут я його наводити не буду, але скажу, що вид вважається більше той, який мертвий, а, якщо всі види живі, то з максимальною цільової функцією. Відбір видів також відбувається просто:






/// <summary> / / / Провести відбір найбільш “живучих” видів
 /// </summary>
 protected void Selection()
 { / / Скільки видів треба видалити
     Int32 Count = m_Species.Count – m_MaxSize;
     for (Int32 i = 0; i < Count; ++i)
     {
         m_Species.RemoveAt (m_Species.Count – 1);
     }
 }

Приклад використання


Розглянемо задачу, що вирішується в прикладах, які додаються в исходниках.


Є функція f = a5 * X05 + a4 * X14 + a3 * X23 + a2 * X32 + a1 * X4 + a0. Тут X0…X4 – Змінні функції, а a0…a5 – Це коефіцієнти, які в принципі не міняються, але нам не відомі і які ми хочемо знайти. У проекті знаходяться два приклади. Перший, коли значення коефіцієнтів a0 … a5 є дробовими, а другий, коли вони є цілими значеннями. Т.к. по суті ці приклади мало відрізняються, то далі більш детально я буду розглядати саме види з дробовими значеннями хромосом.


Спочатку a0 = 2.2, a1 = 1.32, a2 = -4.06, a3 = -3.1, a4 = 4.7, a5 = 0.2. Для розрахунків ми знаємо значення функції в деяких точках (30 точок). Для збільшення точності й швидкості обмежимо інтервал, в якому знаходяться коефіцієнти, відрізком [-5.0; 5.0].


Реалізація видів


Я не буду приводити тут повністю код, т.к. він досить великий, а тільки його частини. Коротенько опишу його роботу, тому що базовий клас залишає досить велику свободу вибору способу подання хромосом і даних.


Для початку оголошено клас для представлення точок функції:






public class DoubleFuncPoint
 {
     public const int FuncSize = 5;
     /// <summary>
     /// X1, X2, …, X5
     /// </summary>
     private double[] m_X = new double[FuncSize];
     public double[] X
     {
         get
         {
             return m_X;
         }
     }
     /// <summary> / / / Значення функції
     /// </summary>
     private double m_Y;
     public double Y
     {
         get
         {
             return m_Y;
         }
     }
     public DoubleFuncPoint(double[] x, double y)
     {
          m_X = (double[])x.Clone();
         m_Y = y;
     }
 }

Тут я думаю все зрозуміло. Потім створимо клас види:






public class DoubleSpecies: BaseSpecies<DoubleSpecies>
{…}

У самому класі виду DoubleSpecies (причому як статичний член, щоб у всіх видів були однакові дані і не треба було б їх зайвий раз передавати) зберігається List , в який заносяться екземпляри класу DoubleFuncPoint. Значення цільової функції (що вона з себе представляє розповім трохи пізніше) обчислюється тільки в двох випадках для кожного виду, коли він створюється і коли мутує, а потім зберігається в приватному поле і витягується звідти, коли це необхідно.


А цільова функція представляє з себе суму квадратів різниці значення функції, у якій відомий її вид і значенням такої ж функції, де замість коефіцієнтів підставлені хромосоми виду:






private void GetFunc()
 {
     m_FuncVal = 0.0;
     foreach (DoubleFuncPoint point in m_FuncPoints)
     {
         double f = Func(point.X) – point.Y;
         m_FuncVal += f * f;
     }
 }

Також ще без коментарів приведу методи для схрещування і тесту хромосом:






public override DoubleSpecies Cross (DoubleSpecies Species)
{
    if (this == Species)
    {
        return new DoubleSpecies ((double[])m_Chromosomes.Clone());
    }
    DoubleSpecies Other = (DoubleSpecies)Species; / / В даному конкретному випадку краще працює схрещування відразу всіх хромосом
    double[] chromosomes = new double[m_Chromosomes.Length];
    for (int i = 0; i < chromosomes.Length; ++i)
    {
        chromosomes[i] = Cross(m_Chromosomes[i], Other.Cromosomes[i]);
    }
    return new DoubleSpecies(chromosomes);
}
 public override void TestChromosomes()
 {
     Boolean res = false;
     foreach (double chromosome in m_Chromosomes)
     {
         if (Double.IsNaN(chromosome) // chromosome < m_MinVal // chromosome > m_MaxVal)
         {
             res = true;
             break;
         }
     }
     m_Dead = res;
 }

При схрещуванні в нашому випадку є два варіанти: схрещувати відразу всі хромосоми або схрещувати по одній хромосомі за один раз. У даному прикладі краще (швидше знаходиться мінімум), якщо схрещувати відразу всі хромосоми, а в іншому випадку, наприклад, як у прикладі з цілими хромосомами краще працює схрещування по одній хромосомі. Тут вже треба експериментувати.


Робота прикладу


Після компіляції прикладу, його запуску і вибору типу хромосом (дробові або цілі) відкриється вікно, в якому можна встановити параметри для генетичного алгоритму і дивитися як змінюються значення хромосом кращого вигляду, а також помилка. Для простоти реалізації весь розрахунок відбувається в одному потоці. Приклад роботи генетичного алгоритму з конкретними параметрами видно на малюнку. Нагадаю правильні значення: a0 = 2.2, a1 = 1.32, a2 = -4.06, a3 = -3.1, a4 = 4.7, a5 = 0.2.


Загальний план використання бібліотеки


Щоб підвести підсумок, розглянемо загальний план того, що необхідно зробити, щоб використовувати цю бібліотеку:



Ось, мабуть, і все. Більш докладно приклади використання дивіться в исходниках.


Історія версій


2.0.0



1.0.0


Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*