Головна

Основи теорії генетичних алгоритмів

  1. I. РОЗРОБКА АЛГОРИТМІВ. ГРАФІЧНЕ ЗОБРАЖЕННЯ (БЛОК-СХЕМИ) І СЛОВЕСНА ЗАПИС АЛГОРИТМІВ
  2. I. Теоретичні основи формування артикуляційної моторики у дітей.
  3. II.1. основи державності
  4. IV. 14.2. Фізіологічні основи емоційних станів
  5. V. 16.2. Фізіологічні основи темпераменту
  6. V. 17.2. Фізіологічні основи характеру
  7. VI. 1. ОСНОВИ РОСІЙСЬКОЇ орфоепія

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

Будучи різновидом методів пошуку з елементами випадковості, генетичні алгоритми мають на меті знаходження кращого, а неоптимального рішення задачі. Це пов'язано з тим, що для складної системи часто потрібно знайти хоч якесь задовільний рішення, а проблема досягнення оптимуму відходить на другий план. При цьому інші методи, орієнтовані на пошук саме оптимального рішення, внаслідок складності завдання стають взагалі не відповідати дійсності. У цьому криється причина появи, розвитку і зростання популярності генетичних алгоритмів. Хоча, як і будь-який інший метод пошуку, цей підхід не є оптимальним методом вирішення будь-яких завдань.

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

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

Друге. Для пошуку генетичний алгоритм використовує кілька точок пошукового простору одночасно, а не переходить від точки до точки, як це робиться в традиційних методах. Це дозволяє подолати один з їхніх недоліків - небезпека потрапляння в локальних екстремум цільової функції, якщо вона не є унімодальної, тобто має кілька таких екстремумів. Використання декількох точок одночасно значно знижує таку можливість.

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

Четверте. Генетичний алгоритм використовує як ймовірні правила для породження нових точок аналізу, так і детерміновані правила для переходу від одних точок до інших. Вище вже говорилося, що одночасне використання елементів випадковості і детермінованості дає значно більший ефект, ніж роздільне.

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

Вище було показано, що генетичний алгоритм працює з кодами безвідносно їх смисловий інтерпретації. Тому сам код і його структура описується поняттям генотип, а його інтерпретація, з точки зору розв'язуваної задачі, поняттям фенотип. Кожен код представляє, по суті, точку простору пошуку. З метою максимально наблизитися до біологічних термінів, екземпляр коду називають хромосомою, особиною або індивідуумом. Далі для позначення рядка коду ми будемо в основному використовувати термін "особина".

На кожному кроці роботи генетичний алгоритм використовує кілька точок пошуку одночасно. Сукупність цих точок є набором особин, який називається популяцією. Кількість особин в популяції називають розміром популяції. Оскільки в даному параграфі ми розглядаємо класичні генетичні алгоритми, то можемо сказати, що розмір популяції є фіксованим і становить одну з характеристик генетичного алгоритму. На кожному кроці роботи генетичний алгоритм оновлює популяцію шляхом створення нових особин і знищення старих. Щоб відрізняти популяції на кожному з кроків і самі ці кроки, їх називають поколіннями і зазвичай ідентифікує по номеру. Наприклад, популяція, отримана з вихідної популяції після першого кроку роботи алгоритму, буде першим поколінням, після наступного кроку-другим, і т.д.

У процесі роботи алгоритму генерація нових особин відбувається на основі моделювання процесу розмноження. При цьому, природно, породжують особини називаються батьками, а породжені -потомкамі. Батьківська пара, як правило породжує пару нащадків. Безпосередня генерація нових кодових рядків з двох, обраних відбувається за рахунок роботи оператора схрещування, який називається кросинговером (від англ. Crossover.). При породженні нової популяції оператор схрещування може застосовуватися не до всіх парах батьків. Частина цих пар може переходити в популяцію наступного покоління безпосередньо. Наскільки часто виникатиме така ситуація, залежить від значення ймовірності застосування оператора схрещування, яка є одним з параметрів генетичного алгоритму.

Моделювання процесу мутації нових особин здійснюється за рахунок роботи оператора мутації .Основним параметром оператора мутації також є ймовірність мутації.

Оскільки розмір популяції фіксований, то породження нащадків має супроводжуватися знищенням інших особин .Вибор пар батьків з популяції для нащадків виробляє оператор відбору, а вибір особин для знищення -оператор редукції. Основним параметром їх роботи є, як правило, якість особини яке визначається

§ генотип і фенотип,

§ особина і якість особини,

§ популяція і розмір популяції,

§ покоління,

§ батьки і нащадки.

До характеристик генетичного алгоритму відносяться:

§ розмір популяції,

§ оператор схрещування і ймовірність його використання,

§ оператор мутації і ймовірність мутації,

§ оператор відбору,

§ оператор редукції,

§ критерій зупинки.

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

Критерієм зупинки роботи генетичного алгоритму може бути одне з трьох подій:

§ Сформовано заданий користувачем число поколінь.

§ Популяція досягла заданого користувачем якості (наприклад, значення якості всіх особин перевищує передбачене поріг)

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

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

Розглянемо тепер безпосередньо роботу генетичного алгоритму.

Формування вихідної популяції відбувається, як правило, з використанням будь-якого випадкового закону, на основі якого вибирається потрібну кількість точок пошукового простору. Вихідна популяція може також бути результатом роботи якого-небудь іншого алгоритму оптимізації. Все тут залежить від розробника конкретного генетичного алгоритму.

Генетичні алгоритми являють собою алгоритми пошуку, побудовані на принципах, подібних до принципів природного відбору і генетики. Якщо говорити узагальнено, вони об'єднують в собі принцип виживання найбільш перспективних особин - рішень і структуризувати обмін інформацією, в якому присутній елемент випадковості, який моделює природні процеси успадкування і мутації [1,2]. Додатковим властивістю цих алгоритмів є невтручання людини в що розвивається процес пошуку.

Генетичні алгоритми мають на меті знаходження кращого, а не оптимального рішення задачі. Це пов'язано з тим, що для складної системи часто потрібно знайти задовільне рішення, а проблема досягнення оптимуму відходить на другий план. При цьому інші методи, орієнтовані на пошук саме оптимального рішення, внаслідок надзвичайної складності завдання стають взагалі не відповідати дійсності. У цьому криється причина появи, розвитку і зростання популярності генетичних алгоритмів. Хоча, як і будь-який інший метод пошуку, цей підхід не є оптимальним методом вирішення будь-яких завдань.

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

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

2. Для пошуку генетичний алгоритм використовує кілька точок пошукового простору одночасно, а не переходить від точки до точки, як це робиться в традиційних методах. Це дозволяє подолати один з їхніх недоліків - небезпека потрапляння в локальний екстремум цільової функції, якщо вона не є унімодальної, тобто має кілька таких екстремумів. Використання декількох точок одночасно значно знижує таку можливість.

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

4. Генетичний алгоритм використовує як імовірнісні правила для породження нових точок аналізу, так і детерміновані правила для переходу від одних точок до інших. Вище вже говорилося, що одночасне використання елементів випадковості і детермінованості дає значно більший ефект, ніж роздільне.

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

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

На кожному кроці роботи генетичний алгоритм використовує кілька точок пошуку одночасно. Сукупність цих точок є набором особин, який називається популяцією. Кількість особин в популяції називають розміром популяції. Оскільки в даному розділі розглядаються класичні генетичні алгоритми, то можна сказати, що розмір популяції є фіксованим і становить одну з характеристик генетичного алгоритму. На кожному кроці роботи генетичний алгоритм оновлює популяцію шляхом створення нових особин і знищення старих. Щоб відрізняти популяцію на кожному з кроків і самі ці кроки, їх називають поколіннями і зазвичай ідентифікують за номером. Наприклад, популяція, отримана з вихідної популяції після першого кроку роботи алгоритму, буде першим поколінням, після наступного кроку - другим, і т. Д.

У процесі роботи алгоритму генерація нових особин відбувається на основі моделювання процесу розмноження. При цьому, природно, породжують особини називають батьками, а породжені - нащадками. Батьківська пара, як правило, породжує пару нащадків. Безпосередня генерація нових кодових рядків з двох обраних відбувається за рахунок роботи оператора схрещування, який також називають кросинговером (від англ. Crossover). При породженні нової популяції оператор схрещування може застосовуватися і до всіх парах батьків. Частина цих пар може переходити в популяцію наступного покоління безпосередньо. Наскільки часто виникатиме така ситуація, залежить від значення ймовірності застосування оператора схрещування, який є одним з основних параметрів генетичного алгоритму.

Моделювання процесу мутації нових особин здійснюється за рахунок роботи оператора мутації. Основним параметром оператора мутації також є ймовірність мутації.

Оскільки розмір популяції фіксований, то породження нащадків має супроводжуватися знищенням інших особин. Вибір пар батьків з популяції для породження нащадків проводиться оператором відбору, а вибір особин для знищення - оператором редукції.

Таким чином, можна перерахувати основні поняття і терміни, використовувані в області генетичних алгоритмів:

· Генотип і фенотип, особина і якість особини;

· Популяція і розмір популяції;

· Покоління;

· Батьки і нащадки.

До характеристик генетичного алгоритму відносяться:

· Розмір популяції;

· Оператор схрещування і ймовірність його використання;

· Оператор мутації і ймовірність мутації;

· Оператор відбору;

· Оператор редукції;

· Критерій зупинки.

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

Критерієм зупинки роботи генетичного алгоритму може бути одне з трьох подій:

· Сформовано заданий користувачем число поколінь;

· Популяція досягла заданого користувачем якості (наприклад, значення якості всіх особин перевищує передбачене поріг);

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

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

Розглянемо тепер безпосередньо роботу генетичного алгоритму.

1. Створення вихідної популяції (задається випадковим чином).

2. Вибір батьків для процесу розмноження (працює оператор відбору).

3. Створення нащадків обраних пар батьків (працює оператор схрещування).

4. Мутація нових особин (працює оператор мутації).

5. Розширення популяції за рахунок додавання нових, щойно

породжених особин.

6. Скорочення розширеної популяції до вихідного розміру (працює оператор редукції).

7. Зупинка роботи генетичного алгоритму за заданим критерієм.

8. Пошук кращої досягнутої особини в кінцевій популяції є результатом роботи генетичного алгоритму.

 
 

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


 де n - розмір популяції; i - номер особи; Pi - ймовірність участі особини в процесі розмноження; Fi - значення цільової функції для i-ї особи. Очевидно, що одна особина може бути задіяна в кількох батьківських парах.

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

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

Наведемо найпростіший оператор схрещування. Він виконується в два етапи. Нехай особина представляє собою рядок з n елементів. На першому етапі равновероятно вибирається число k від 1 до n-1. Це число називається точкою розбиття. Відповідно до нього обидві вихідні рядки розбиваються на дві підрядка. На другому етапі рядки обмінюються своїми підрядками, що лежать після точки розбиття, тобто елементами c k + 1-го по n -й. Так виходить два нові рядки, які успадковували частково властивості обох батьків. Цей процес проілюстрований нижче.

Стоку 1 X1X2. . .XkXk + 1. . .Xn X1X2. . .XkYk + 1. . .Yn

Рядок 2 Y1Y2. . .YkYk + 1. . .Yk Y1Y2. . .YkXk + 1. . .Xn

Можливість використання оператора схрещування зазвичай вибирається досить великий, в межах від 0,9 до 1, щоб забезпечити постійну появу нових особин, які розширюють простір пошуку. При значенні ймовірності менш одиниці часто використовують елітизм. Це особлива стратегія, яка передбачає перехід в популяцію наступного покоління еліти, тобто кращих особин поточної популяції, без будь-яких змін. Застосування елітизму сприяє збереженню загальної якості популяції на високому рівні. При цьому елітні особини беруть участь ще й в процесі відбору батьків для подальшого схрещування. Кількість елітних особин визначається зазвичай за формулою

K = (1-P) IN,

де К-кількість елітних особин; Р - вірогідність застосування оператора схрещування; N- розмір популяції.

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

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

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

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

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



Попередня   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   Наступна

Нейронні мережі для нечіткого виведення. Архітектура нечіткої мережі, заснованої на нейронних мережах | Способи навчання нечіткої нейронної системи | Актуальність проблеми | Засоби створення інтелектуальних додатків | Засоби вилучення нової інформації | розділ 9 | Основні терміни та визначення | запит Відповідь | Системи обробки зв'язкових текстів | Компонент розуміння висловлювання компонент генерації висловлювання |

© um.co.ua - учбові матеріали та реферати