Одним суботнім грудневим вечором сидів я над книгою The Blind Watchmaker (сліпий каплиець), як на очі мені попався неймовірно цікавий експеримент: візьмемо будь-яку пропозицію, наприклад Шекспірівський рядок: Methinks it is like a weasel і випадковий рядок такої ж довжини: wdltmnlt dtjbkwirzrezlmqco p і почнемо вносити в неї випадкові зміни. Через скільки поколінь цей випадковий рядок перетвориться на Шекспірівський рядок, якщо виживати будуть лише нащадки більш схожі на Шекспірівську?
Сьогодні ми повторимо цей експеримент, але в уже зовсім іншому масштабі.
Структура статті:
- Що таке генетичний алгоритм
- Чому це працює
- Формалізуйте завдання з випадковим рядком
- Приклад роботи алгоритму
- Експерименти з класикою
- Код і дані
- Висновки
Обережно трафік!
Що таке генетичний алгоритм
У галузі штучного інтелекту під генетичним алгоритмом мається на увазі евристика пошуку рішень, заснована на природному відборі. Як правило застосовується для завдань, де простір пошуку наскільки величезний, що точне рішення знайти неможливо і евристичне рішення задовольняє вимогам. Саме завдання має деяку функцію якості рішення, яку необхідно максимізувати.
У найпростішому вигляді генетичний алгоритм має таку структуру (див. схему): починаємо з деяким рішенням, у нашому випадку, це випадковий рядок; вносимо мутації, наприклад, змінюємо випадково вибрану букву в рядку на випадково вибрану букву і отримуємо новий набір рядків (k мутацій на рядок); з них відбираємо тільки ті, які ближче до шекспірівської (за кількістю збігаються символом), наприклад 10 таких рядків, якщо шекспірівської серед них немає, то запускаємо процес заново.
Чому це працює
Багато в чому генетичні алгоритми схожі на класичні методи оптимізації, популяція - це набір поточних точок, мутації - це дослідження сусідніх точок, відбір - це вибір нових точок для пошуку рішення в умовах обмежених обчислювальних ресурсів.
Популяція завжди прагне до найближчого максимуму, оскільки ми відбираємо поточні точки пошуку, як такі, що мають максимальне значення (всі інші точки «помруть», не витримають конкуренції з найближчим максимумом). Оскільки розмір популяції значний, а значить ймовірність зробити хоча б один крок у напрямку максимуму не зневажливо мала, то через деяку кількість кроків популяція зміститься в бік локального максимуму. А нащадки точки, зміщеної ближче до максимуму, мають велику «виживаність». Значить через достатню кількість кроків, нащадки цієї точки почнуть домінувати в популяції і вся вона зміститься до максимуму.
Візуалізація популяції, яка прагне локального максимуму:
(due to Randy Olson)
Формалізуйте завдання з випадковим рядком
Вхідні дані: рядок S
Вихідні дані: натуральне число N, рівне кількості поколінь необхідних для перетворення випадкового рядка довжини len (S) на рядок S
Що в нашому випадку мутація? Під мутацією рядка S ми розуміємо заміну одного випадково обраного символу з рядка S на інший довільний символ алфавіту. У даному завданні ми використовуємо тільки символи нижнього регістру латиниці і пробіл.
Що таке початкова популяція (initial population у схемі)? Це випадковий рядок рівний за довжиною вхідного рядка S.
Що таке нащадки (offsprings)? Нехай ми зафіксували кількість мутацій одного рядка на константу k, тоді нащадки - це k мутацій кожного рядка поточного покоління.
Що таке ті, хто вижив (survivors)? Нехай ми зафіксували розмір популяції на константу h, тоді ті, хто вижив, - це h рядків максимально схожих на вхідний рядок S.
У псевдокоді (підозріло схожому на python) це виглядає наступним чином:
Приклад роботи алгоритму
Розгляньмо такий рядок: The quick brown fox jumps over the lazy dog і відтворюємо для неї висновок нашої програми:
Розглянемо ланцюжок змін (зліва номер покоління):
1 rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk
2 rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk
3 rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk
4 rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmodyk
5 rbb mffwfhbtxnjjiozz ujhhlxeoyhezarquzmodyk
6 rbb mffcfhbtxnjjiozz ujhhlxeoyhezarquzmodyk
7 rbb mffcf btxnjjiozz ujhhlxeoyhezarquzmodyk
8 rbb mffcf btxnjjiozz ujhhlxeoyheza quzmodyk
9 rbb mffcf brxnjjiozz ujhhlxeoyheza quzmodyk
10 rbb mffcf brxnjjiozz ujphlxeoyheza quzmodyk
20 rbb mffcf bronj fox jujpslxveyheza luzmodyk
30 rbb mficf bronj fox jumps overhehe luzy dyg
40 he m ick bronn fox jumps over the lazy dog
41 he q ick bronn fox jumps over the lazy dog
42 he q ick bronn fox jumps over the lazy dog
43 he q ick brown fox jumps over the lazy dog
44 he quick brown fox jumps over the lazy dog
45 ahe quick brown fox jumps over the lazy dog
46 the quick brown fox jumps over the lazy dog
Повний вивід
print_genes(""The quick brown fox jumps over the lazy dog"")
1 rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk
2 rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk
3 rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk
4 rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmodyk
5 rbb mffwfhbtxnjjiozz ujhhlxeoyhezarquzmodyk
6 rbb mffcfhbtxnjjiozz ujhhlxeoyhezarquzmodyk
7 rbb mffcf btxnjjiozz ujhhlxeoyhezarquzmodyk
8 rbb mffcf btxnjjiozz ujhhlxeoyheza quzmodyk
9 rbb mffcf brxnjjiozz ujhhlxeoyheza quzmodyk
10 rbb mffcf brxnjjiozz ujphlxeoyheza quzmodyk
11 rbb mffcf brxnj iozz ujphlxeoyheza quzmodyk
12 rbb mffcf brxnj ioz ujphlxeoyheza quzmodyk
13 rbb mffcf bronj ioz ujphlxeoyheza quzmodyk
14 rbb mffcf bronj ioz ujphlxeeyheza quzmodyk
15 rbb mffcf bronj ioz ujphlxeeyheza luzmodyk
16 rbb mffcf bronj ioz ujphlxveyheza luzmodyk
17 rbb mffcf bronj foz ujphlxveyheza luzmodyk
18 rbb mffcf bronj foz jujphlxveyheza luzmodyk
19 rbb mffcf bronj foz jujpslxveyheza luzmodyk
20 rbb mffcf bronj fox jujpslxveyheza luzmodyk
21 rbb mffcf bronj fox jujpslxveyheza luzm dyk
22 rbb mffcf bronj fox jujpslxverheza luzm dyk
23 rbb mffcf bronj fox jumpslxverheza luzm dyk
24 rbb mffcf bronj fox jumpslxverheha luzm dyk
25 rbb mffcf bronj fox jumpslxverhehe luzm dyk
26 rbb mffcf bronj fox jumps xverhehe luzm dyk
27 rbb mffcf bronj fox jumps xverhehe luzm dyg
28 rbb mffcf bronj fox jumps xverhehe luzy dyg
29 rbb mffcf bronj fox jumps overhehe luzy dyg
30 rbb mficf bronj fox jumps overhehe luzy dyg
31 rbb mficf bronj fox jumps overhehe lazy dyg
32 rbb mficf bronn fox jumps overhehe lazy dyg
33 rbb mficf bronn fox jumps over ehe lazy dyg
34 rhb mficf bronn fox jumps over ehe lazy dyg
35 hb mficf bronn fox jumps over ehe lazy dyg
36 hb mfick bronn fox jumps over ehe lazy dyg
37 hb m ick bronn fox jumps over ehe lazy dyg
38 hb m ick bronn fox jumps over ehe lazy dog
39 he m ick bronn fox jumps over ehe lazy dog
40 he m ick bronn fox jumps over the lazy dog
41 he q ick bronn fox jumps over the lazy dog
42 he q ick bronn fox jumps over the lazy dog
43 he q ick brown fox jumps over the lazy dog
44 he quick brown fox jumps over the lazy dog
45 ahe quick brown fox jumps over the lazy dog
46 the quick brown fox jumps over the lazy dog
Як ми бачимо кожне покоління відрізняється не більше, ніж на один символ один від одного. Всього знадобилося 46 поколінь, щоб дістатися від rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk до the quick brown fox jumps over the lazy dog за допомогою мутацій і відбору.
Експерименти з класикою
Окремі приклади, шекспірівський рядок або англійська панграма про лисицю, цікаві, але не надто переконливі. Тому і вирішив розглянути більш цікаве питання: що буде якщо взяти пару класичних творів, розбити їх на пропозиції і порахувати число поколінь для кожного з них? Який буде характер залежності кількості поколінь від рядка (наприклад, від його довжини)?
Як класичні твори вибрав To Kill a Mocking Bird by Harper Lee (Вбити Пересмішника, Харпер Лі) і Catcher in the Rye by J.D. Salinger (Над Прірвою у Житі, Джей Ді Селінджер). Ми будемо вимірювати два параметри - розподіл кількості поколінь за пропозиціями і залежність кількості поколінь від довжини рядка (чи є кореляція?).
Параметри були такі: кількість нащадків у рядку: 100; кількість вцілілих у поколінні: 10.
Результати
Як ми бачимо, для більшості пропозицій вийшло досягти рядка досить швидко, потрібні менше 100 ітерацій, практично для всіх пропозицій достатньо 200 ітерацій (серед всіх пропозицій було тільки одне, якому було потрібно 1135 ітерацій, судячи з пропозиції алгоритм розбивки помилився і склеїв кілька пропозицій в одне):
Кореляція між довжиною рядка і кількістю поколінь ідеальна. Це означає, що практично в кожному поколінні вдавалося просунутися на крок ближче до цільового рядка.
R 2 дорівнює 0.996 і 0.997 відповідно.
Таким чином експериментально встановили, що в умовах нашого завдання для будь-якого вхідного рядка S, кількість поколінь лінійно залежить від довжини рядка, що узгоджується з вихідними припущеннями.
Код і дані
Весь код, python - генетичний алгоритм\обробка тексту і R - візуалізація, доступний в github:
github.com/SergeyParamonov/genetics-experiments
Висновки
Ми розібралися з базовою структурою генетичних алгоритмів і застосували для вирішення завдання про мутацію рядка. У результаті експериментів з класичними текстами ми виявили, що в наших умовах існують лінійна залежність між довжиною рядка і кількістю поколінь необхідних для досягнення вхідного рядка.
Так само ми зазначили, що базова структура пошуку може бути модифікована (наприклад, за допомогою crossover - використання кількох членів покоління для створення нащадків) для вирішення широкого класу завдань оптимізації, де занадто складно шукати точне рішення.