Природний відбір і генетичне спадкування

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

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

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

Ген - це відрізок ланцюга ДНК, відповідальний за визначену властивість особини, наприклад за колір очей, тип волосся, колір шкіри і т.д. Вся сукупність генетичних ознак людини кодується за допомогою приблизно 60 тис. генів, довжина яких складає більш 90 млн. нуклеотидів.

Розрізняють два види клітин: статеві (такі, як сперматозоїд і яйцеклітина) і соматичні. В кожній соматичній клітині людини міститься 46 хромосом. Ці 46 хромосом - насправді 23 пари, причому в кожній парі одна з хромосом отримана від батька, а друга - від матері. Парні хромосоми відповідають за однакові ознаки - наприклад, батьківська хромосома може містити ген чорного кольору око, а парна їй материнська - ген голубого кольору. Існують визначені закони, що керують участю тих чи інших генів у розвитку особини. Зокрема, у нашому прикладі нащадок буде чорнооким, оскільки ген блакитних очей є "слабким" (рецесивним) і подавляється геном будь-якого іншого кольору.

В статевих клітинах хромосом тільки 23, і вони непарні. При заплідненні відбувається злиття чоловічої і жіночої статевих клітин і утворюється клітина зародка, що містить саме 46 хромосом. Які властивості нащадок одержить від батька, а які - від матері? Це залежить від того, які саме статеві клітини брали участь у заплідненні. Справа в тім, що процес вироблення статевих клітин (так званий мейоз) в організмі піддається випадкам, завдяки яким нащадки все-таки багато в чому відрізняються від своїх батьків. При мейозі, зокрема, відбуваються наступне: парні хромосоми соматичної клітини зближаються впритул, потім їхні нитки ДНК розриваються в декількох випадкових місцях і хромосоми обмінюються своїми частинами (рис. 1).

Рис.1. Умовна схема кросінговеру

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

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

Задачі оптимізації

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

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

Уведемо позначення і приведемо кілька класичних прикладів. Як правило, у задачі оптимізації ми можемо керувати декількома параметрами (позначимо їх значення через x1, x2,..., xn, а нашою метою є максимізація (чи мінімізація) деякої функції, f(x1, x2,..., xn), що залежить від цих параметрів. Функція f називається цільовою функцією. Наприклад, якщо потрібно максимізувати цільову функцію "дохід компанії", тоді керованими параметрами будуть число співробітників компанії, обсяг виробництва, витрати на рекламу, ціни на кінцеві продукти і т.д. Важливо відзначити, що ці параметри зв'язані між собою - зокрема, при зменшенні числа співробітників швидше за все впаде й обсяг виробництва.

Генетичний алгоритм - новітній, але не єдино можливий спосіб рішення задач оптимізації.

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

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

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

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