Що таке генетичні алгоритми
Тимофій струнці
У 13-му номері PC Week / RE за цей рік було розказано про будову біологічних нейронів і про штучні нейронних мережах. У цій статті ми продовжимо тему імітації біологічних процесів і познайомимо вас з одним гарним засобом для вирішення завдань оптимізації. Цього разу об'єктом для наслідування буде не нейрон і навіть не будь-яка частина окремого живого організму, а весь процес розвитку життя на Землі в цілому.
Звичайно, ми не будемо торкатися релігійних поглядів на зародження життя, згідно з якими всі тварини на Землі, включаючи людину, були створені протягом трьох днів. Набагато цікавішим (і зрозумілим) представляється науковий підхід, заснований на еволюційної теорії Дарвіна. Завдяки відкриттям останніх ста років сучасній науці відомі всі основні механізми еволюції, пов'язані з генетичним успадкуванням. Ці механізми досить прості за своєю ідеєю, але дотепні (якщо до природи може бути застосовано це слово) і ефективні. Дивно, але просте моделювання еволюційного процесу на комп'ютері дозволяє отримати рішення багатьох практичних завдань. Такі моделі отримали назву "генетичні алгоритми" і вже широко застосовуються в різних областях. У наступних розділах ми послідовно розповімо спочатку про біологічні механізми еволюції, а потім про способи їх моделювання за допомогою генетичних алгоритмів.
еволюційна теорія
Як відомо, еволюційна теорія стверджує, що життя на нашій планеті виникло спочатку лише в найпростіших її формах - у вигляді одноклітинних організмів. Ці форми поступово ускладнювалися, пристосовуючись до навколишнього середовища і породжуючи нові види, і тільки через багато мільйонів років з'явилися перші тварини і люди. Можна сказати, що кожен біологічний вид з плином часу покращує свої якості так, щоб найбільш ефективно справлятися з найважливішими завданнями виживання, самозахисту, розмноження і т. Д. Таким шляхом виникла захисна забарвлення у багатьох риб і комах, панцир у черепахи, отрута у скорпіона і багато інших корисних пристосування.
За допомогою еволюції природа постійно оптимізує все живе, знаходячи часом самі неординарні рішення. З першого погляду зрозуміло, за рахунок чого відбувається цей прогрес, однак йому є наукове пояснення. Дати це пояснення можна, грунтуючись лише на двох біологічних механізмах - природного відбору і генетичного успадкування.
Природний відбір і генетичне спадкування
Ключову роль в еволюційній теорії грає природний відбір. Його суть полягає в тому, що найбільш пристосовані особини краще виживають і приносять більше потомства, ніж менш пристосовані. Зауважимо, що сам по собі природний відбір ще не забезпечує розвитку біологічного виду. Дійсно, якщо припустити, що всі нащадки народжуються приблизно однаковими, то різні покоління будуть відрізнятися тільки за чисельністю, але не по пристосованості. Тому дуже важливо вивчити, яким чином відбувається спадкування, т. Е. Як властивості нащадка залежать від властивостей батьків.
Основний закон спадкування інтуїтивно зрозумілий кожному - він полягає в тому, що нащадки схожі на батьків. Зокрема, нащадки більш пристосованих батьків будуть, швидше за все, одними з найбільш пристосованих у своєму поколінні. Щоб зрозуміти, на чому заснована ця подібність, нам буде потрібно трохи заглибитися в будову тваринної клітини - в світ генів і хромосом.
Майже в кожній клітині будь-якої тварини є набір хромосом, що несуть інформацію про цю тварину. Основна частина хромосоми - нитка ДНК (молекула дезоксирибонуклеїнової кислоти), яка складається з чотирьох видів спеціальних з'єднань - нуклеотидів, що йдуть в певній послідовності. Нуклеотиди позначаються буквами A, T, C і G, і саме порядок їх слідування кодує всі генетичні властивості даного організму. Говорячи більш точно, ДНК визначає, які хімічні реакції будуть відбуватися в даній клітині, як вона буде розвиватися і які функції виконувати.
Ген - це відрізок ланцюга ДНК, що відповідає за певну властивість особини, наприклад за колір очей, тип волосся, колір шкіри і т. Д. Вся сукупність генетичних ознак людини кодується за допомогою приблизно 60 тис. Генів, сумарна довжина яких становить понад 90 млн. Нуклеотидів .
Розрізняють два види клітин: статеві (такі, як сперматозоїд і яйцеклітина) і соматичні. У кожній соматичній клітині людини міститься 46 хромосом. Ці 46 хромосом - насправді 23 пари, причому в кожній парі одна з хромосом отримана від батька, а друга - від матері. Парні хромосоми відповідають за одні й ті ж ознаки - наприклад, батьківська хромосома може містити ген чорного кольору очей, а парна їй материнська - ген блакитноокого. Існують певні закони, що керують участю тих чи інших генів у розвитку особини. Зокрема, в нашому прикладі нащадок буде чорнооким, так як ген блакитних очей є "слабким" (рецесивним) і пригнічується геном будь-якого іншого кольору.
У статевих клітинах хромосом тільки 23, і вони непарні. При заплідненні відбувається злиття чоловічої і жіночої статевих клітин і утворюється клітина зародка, що містить як раз 46 хромосом. Які властивості нащадок одержить від батька, а які - від матері? Це залежить від того, які саме статеві клітини брали участь у заплідненні. Справа в тому, що процес вироблення статевих клітин (так званий мейоз) в організмі піддається випадковостям, завдяки яким нащадки все ж багато в чому відрізняються від своїх батьків. При мейозі, зокрема, відбувається наступне: парні хромосоми соматичної клітини зближаються впритул, потім їх нитки ДНК розриваються в декількох випадкових місцях і хромосоми обмінюються своїми частинами (рис. 1). Цей процес забезпечує появу нових варіантів хромосом і зветься "кросинговер". Кожна з новопосталих хромосом виявиться потім всередині однієї з статевих клітин, і її генетична інформація може реалізуватися в нащадках даної особини.
Мал. 1. Умовна схема кросинговеру
Другий важливий фактор, що впливає на спадковість, - це мутації, які виражаються в зміні деяких ділянок ДНК. Мутації також випадкові і можуть бути викликані різними зовнішніми факторами, такими, як радіоактивне опромінення. Якщо мутація відбулася в статевій клітині, то змінений ген може передатися нащадку і проявитися у вигляді спадкової хвороби або в інших нових властивостях нащадка. Вважається, що саме мутації є причиною появи нових біологічних видів, а кросинговер визначає вже змінність всередині виду (наприклад, генетичні відмінності між людьми).
завдання оптимізації
Як уже було відзначено вище, еволюція - це процес постійної оптимізації біологічних видів. Тепер ми в стані зрозуміти, як відбувається цей процес. Природний відбір гарантує, що найбільш пристосовані особини дадуть досить велике потомство, а завдяки генетичному спадкуванню ми можемо бути впевнені, що частина цього потомства не тільки збереже високу пристосованість батьків, але буде мати і деякими новими властивостями. Якщо ці нові властивості виявляться корисними, то з великою ймовірністю вони перейдуть і в наступне покоління. Таким чином, відбувається накопичення корисних якостей і поступове підвищення пристосовності біологічного виду в цілому. Знаючи, як вирішується завдання оптимізації видів у природі, ми тепер застосуємо схожий метод для вирішення різних реальних завдань.
Завдання оптимізації - найбільш поширений і важливий для практики клас задач. Їх доводиться вирішувати кожному з нас або в побуті, розподіляючи свій час між різними справами, або на роботі, домагаючись максимальної швидкості роботи програми чи максимальної прибутковості компанії - в залежності від посади. Серед цих завдань є розв'язувані простим шляхом, але є і такі, точне рішення яких знайти практично неможливо.
Введемо позначення і приведемо кілька класичних прикладів. Як правило, в задачі оптимізації ми можемо керувати кількома параметрами (позначимо їх значення через x1, x2, ..., xn, а нашою метою є максимізація (або мінімізація) деякої функції, f (x1, x2, ..., xn) , що залежить від цих параметрів. Функція f називається цільовою функцією. Наприклад, якщо потрібно максимізувати цільову функцію "дохід компанії", то керованими параметрами будуть число співробітників компанії, обсяг виробництва, витрати на рекламу, ціни на кінцеві продукти і т. д. Важливо відзначити , що ці параметри пов'язані між собою - в приватно ти, при зменшенні числа співробітників швидше за все впаде й обсяг виробництва.
Звичайно, математики здавна займалися подібними завданнями і розробили кілька методів їх вирішення. У разі, якщо цільова функція досить гладка і має тільки один локальний максимум (унімодальне), то оптимальне рішення можна отримати методом градієнтного спуску. Ідея цього методу полягає в тому, що оптимальне рішення виходить ітераціями. Береться випадкова початкова точка, а потім в циклі відбувається зрушення цієї точки на малий крок, причому крок робиться в тому напрямку, в якому цільова функція зростає найшвидше. Недоліком градиентного алгоритму є занадто високі вимоги до функції - на практиці унімодальне зустрічається вкрай рідко, а для неправильної функції градієнтний метод часто призводить до неоптимальному відповіді. Аналогічні проблеми виникають і з застосуванням інших математичних методів. У багатьох важливих завданнях параметри можуть приймати лише певні значення, причому у всіх інших точках цільова функція не визначена. Звичайно, в цьому випадку не може бути й мови про її гладкості і потрібні принципово інші підходи.
Класичний приклад такого завдання, відомий як "завдання комівояжера" (Traveling Salesman Problem, TSP), формулюється так: комівояжеру потрібно об'їхати кілька міст, побувавши в кожному один раз, і повернутися у вихідну точку. Потрібно знайти найкоротший маршрут.
Найпростіший спосіб знайти оптимальне рішення - перебрати всі можливі значення параметрів. При цьому не потрібно робити ніяких припущень про властивості цільової функції, а задати її можна просто за допомогою таблиці. Однак, щоб вирішити таким способом завдання комівояжера хоча б для 20 міст, потрібно перебрати близько 1019 маршрутів, що абсолютно нереально ні для якого обчислювального центру. Таким чином, виникає необхідність в будь-якому новому методі оптимізації, придатному для практики. У наступному розділі ми покажемо, яким чином можна застосувати механізми еволюційного процесу до наших завдань. Фактично ми організуємо штучну еволюцію в спеціально побудованому світі.
Робота генетичного алгоритму
Уявімо собі штучний світ, населений безліччю істот (особин), причому кожна істота - це деяке рішення нашої задачі. Будемо вважати особину тим більше пристосованої, чим краще відповідне рішення (чим більше значення цільової функції воно дає). Тоді завдання максимізації цільової функції зводиться до пошуку найбільш пристосованого істоти. Звичайно, ми не можемо поселити в наш віртуальний світ все істоти відразу, так як їх дуже багато. Замість цього ми будемо розглядати багато поколінь, що змінюють один одного. Тепер, якщо ми зуміємо ввести в дію природний відбір і генетичне спадкування, то отриманий світ буде підкорятися законам еволюції. Зауважимо, що, відповідно до нашого визначенням пристосованості, метою цієї штучної еволюції буде якраз створення найкращих рішень. Очевидно, еволюція - нескінченний процес, в ході якого пристосованість особин поступово підвищується. Примусово зупинивши цей процес через досить довгий час після його початку і вибравши найбільш пристосовану особину в поточному поколінні, ми отримаємо не абсолютно точний, але близький до оптимального відповідь. Така, коротко, ідея генетичного алгоритму. Перейдемо тепер до точних визначень і опишемо роботу генетичного алгоритму більш детально.
Для того щоб говорити про генетичне спадкування, потрібно забезпечити наші істоти хромосомами. У генетичному алгоритмі хромосома - це деякий числовий вектор, відповідний підбирається параметру, а набір хромосом даної особини визначає рішення задачі. Які саме вектори варто розглядати в конкретному завданні, вирішує сам користувач. Кожна з позицій вектора хромосоми називається ген.
Визначимо тепер поняття, відповідні мутації і кросинговеру в генетичному алгоритмі.
Мутація - це перетворення хромосоми, випадково змінює одну або кілька її позицій (генів). Найбільш поширений вид мутацій - випадкова зміна тільки одного з генів хромосоми.
Кроссинговер (в літературі по генетичним алгоритмам також вживається назва кросовер або схрещування) - це операція, при якій з двох хромосом породжується одна або декілька нових хромосом. У найпростішому випадку кроссинговер в генетичному алгоритмі реалізується так само, як і в біології (див. Рис. 1). При цьому хромосоми розрізаються в випадкової точці і обмінюються частинами між собою. Наприклад, якщо хромосоми (1, 2, 3, 4, 5) і (0, 0, 0, 0, 0) розрізати між третім і четвертим генами і обміняти їх частини, то вийдуть нащадки (1, 2, 3, 0, 0) і (0, 0, 0, 4, 5).
Блок-схема генетичного алгоритму зображена на рис. 2. Спочатку генерується початкова популяція особин (індивідуумів), т. Е. Певний набір рішень задачі. Як правило, це робиться випадковим чином. Потім ми повинні змоделювати розмноження всередині цієї популяції. Для цього випадково відбираються декілька пар індивідуумів, проводиться схрещування між хромосомами в кожній парі, а отримані нові хромосоми поміщаються в популяцію нового покоління. У генетичному алгоритмі зберігається основний принцип природного відбору - чим пристосувань індивідуум (чим більше відповідне йому значення цільової функції), тим з більшою ймовірністю він братиме участь в схрещуванні. Тепер моделюються мутації - в декількох випадково обраних особинах нового покоління змінюються деякі гени. Потім стара популяція частково або повністю знищується і ми переходимо до розгляду наступного покоління. Популяція нового покоління в більшості реалізацій генетичних алгоритмів містить стільки ж особин, скільки початкова, але в силу відбору пристосованість в ній в середньому вище. Тепер описані процеси відбору, схрещування і мутації повторюються вже для цієї популяції і т. Д.
Мал. 2. Блок-схема генетичного алгоритму
В кожному наступному поколінні ми будемо спостерігати виникнення зовсім нових рішень нашої задачі. Серед них будуть як погані, так і хороші, але завдяки відбору число хороших рішень буде зростати. Зауважимо, що в природі не буває абсолютних гарантій, і навіть самий пристосований тигр може загинути від рушничного пострілу, не залишивши потомства. Імітуючи еволюцію на комп'ютері, ми можемо уникати подібних небажаних подій і завжди зберігати життя краще з індивідуумів поточного покоління - така методика називається "стратегією елітизму".
Застосування генетичних алгоритмів
Щоб використовувати генетичний алгоритм для вирішення практичних завдань, необхідно розглядати більш складні варіанти введених вище понять. Пояснимо це на прикладі завдання комівояжера для 20 міст.
Як індивідуумів будемо розглядати маршрути обходу. Інформацію про маршрут можна записати у вигляді однієї хромосоми - вектора довжини 20, де в першій позиції стоїть номер першого міста на шляху проходження, потім - номер другого міста і т. Д. Перше утруднення виникає, коли ми намагаємося визначити мутації для таких хромосом - стандартна операція, яка зраджує тільки одну позицію вектора, є неприпустимою, оскільки призводить до некоректного маршруту. Але можна визначити мутацію як перестановку значень двох випадково обраних генів. При такому перетворенні шлях прямування змінюється тільки в двох містах.
За умовою завдання в розглянутих хромосомах кожен ген (номер міста) повинен зустрічатися тільки один раз. Такий різновид хромосом називається "перелічуваних хромосоми з унікальними генами" і часто використовується в комбінаторних задачах. Стандартна операція схрещування для цього типу хромосом знову ж некоректна, тому тут використовується більш складна схема двухточечного схрещування. За браком місця ми не висловлюємо цю схему і рекомендуємо зацікавленому читачеві звернутися до спеціальної літератури.
На рис. 3 зображений результат роботи генетичного алгоритму в задачі комівояжера (ми використовували демонстраційну програму до пакету GeneHunter). Зазначені на рисунку значення параметрів досить типові - як і в природі, мутації відбуваються набагато рідше, ніж схрещування. У правому нижньому вікні можна спостерігати, як змінювалася довжина найкоротшого в популяції маршруту в процесі еволюції. Ця довжина монотонно убуває до певного моменту, а потім стабілізується. Знайдений маршрут, ймовірно, не є найоптимальнішим, але близький до нього по довжині - як правило, генетичні алгоритми "помиляються" не більше ніж на 5 - 10%. Цей недолік компенсується для комбінаторних завдань відносно високою швидкістю роботи - в нашому прикладі відповідь була отримана за 25 секунд. На практиці генетичні алгоритми нерідко використовують спільно з іншими методами, які дозволяють підвищити їх точність.
Мал. 3. Найкоротший маршрут, знайдений генетичним алгоритмом
Генетичні алгоритми використовуються не тільки в задачах комбінаторного типу (як TSP), але і в тих випадках, коли підбираються параметри можуть бути будь-якими дійсними числами. Така, наприклад, завдання оптимального розподілу інвестицій; один з варіантів її буде стисло описано.
Нехай є деякий капітал R, який потрібно розподілити між кількома проектами з метою отримання максимального доходу через певний термін. Для кожного проекту задана функція доходу, принесеного проектом за цей термін, в залежності від вкладеної суми. Використовується також диверсифікація, т. Е. Заборонено вкладати в будь-який проект занадто велику суму. У цьому завданню цільовою функцією є сумарний прибуток від інвестицій, а керованими параметрами - обсяги вкладень в кожен з проектів.
Подібні моделі є стандартними для економістів, але в них розглядаються тільки лінійні функції прибутковості. В цьому випадку точне рішення можна отримати за допомогою лінійного програмування (симплекс-метод). Однак в реальних задачах немає підстав вважати всі функції лінійними - більш того, вони можуть бути навіть розривними. При цьому цільова функція має складний вигляд і не є унімодальної. У такій нелінійної ситуації стандартні методики працюють погано - зокрема, симплекс-метод непридатний принципово, а градієнтний метод найчастіше призводить до неоптимальному рішенням.
Розглянемо, яким чином вирішується це завдання для 10 проектів за допомогою генетичного алгоритму. Нехай кожен індивідуум має 10 хромосом, де k-я хромосома - це вектор з нулів і одиниць, що містить двійкову запис обсягу вкладень в k-й проект. Якщо довжина хромосоми дорівнює 8 двійковим розрядам, то знадобиться попередня нормировка всіх чисел в діапазон від 0 до 255. Такі хромосоми називаються безперервними і дозволяють представляти значення довільних числових параметрів. Мутації безперервних хромосом випадковим чином змінюють один біт (ген) в них, впливаючи таким чином на значення параметра. Кроссинговер також можна здійснювати стандартним чином, об'єднуючи частини відповідних хромосом (з однаковими номерами) різних індивідуумів. Особливістю цього завдання є те, що сумарний капітал, що інвестується фіксований і дорівнює деякому числу R. Очевидно, при мутаціях і схрещуванні можуть виходити рішення, для реалізації яких потрібен капітал більше або менше R. У генетичному алгоритмі використовується спеціальний механізм роботи з такими рішеннями, що дозволяє враховувати обмеження типу "сумарний капітал = R" при підрахунку пристосованості індивідуума. В процесі еволюції особини з сильним порушенням зазначених обмежень вимирають. В результаті роботи алгоритму виходить рішення з сумарним капіталом, бути може, не рівним в точності, але близьким до заданого R. Як і у випадку з завданням комівояжера, цю похибку слід вважати платою за швидкість пошуку рішення. Відзначимо, що повний перебір всіх варіантів інвестування в 10 проектів (для функцій прибутковості, заданих на 256 точках) включає в себе більше 1020 рішень і не реалізуємо на практиці.
Висновок - про евристиці в цілому
У даній статті ми не наводимо жодного математичного твердження про збіжність або про якість роботи генетичних алгоритмів - ця область дуже спеціальна і відноситься в основному до теоретичних модельним постановок задач. Викладений підхід є евристичним, т. Е. Показує хороші результати на практиці, але погано піддається теоретичному дослідженню і обґрунтуванню. Природно поставити питання - чи слід користуватися такими алгоритмами, що не мають строгого математичного обгрунтування? Як і в питанні про нейронних мережах, тут не можна відповісти однозначно. З одного боку, в математиці існує досить великий клас абсолютно надійних (у сенсі гарантії отримання точного рішення) методів вирішення різних завдань. З іншого боку, мова йде про дійсно складних практичних завданнях, в яких ці надійні методи часто непридатні. Нерідко ці завдання виглядають настільки неозорими, що не робиться навіть спроб їх осмисленого рішення. Наприклад, фірма, що займається транспортними перевезеннями, в сучасних умовах російського бізнесу швидше віддасть перевагу найняти зайвих водіїв і підвищити ціни на свої послуги, ніж оптимізувати маршрути і розклади поїздок. На західному ринку, де вже давно діють закони більш-менш чесної конкуренції, оптимальність діяльності компанії значно впливає на її доходи і навіть може стати вирішальним фактором для її виживання. Тому будь-які ідеї, що дозволяють компанії стати "розумнішими" своїх конкурентів, знаходять там широке застосування. Генетичні алгоритми - реалізація однієї з найбільш популярних ідей такого роду. Ця популярність викликана, мабуть, винятковою красою підходу і його близькістю до природного механізму. Подібним чином популярність нейромережевої технології підігрівається багато в чому її схожістю з роботою мозку. По-справжньому активний розвиток евристичних підходів, як ми бачимо, безпосередньо пов'язане з розвитком вільного ринку і економіки в цілому.
З автором можна зв'язатися за адресою: [email protected].
Версія для друку
Які властивості нащадок одержить від батька, а які - від матері?Природно поставити питання - чи слід користуватися такими алгоритмами, що не мають строгого математичного обгрунтування?