от Даниел Шифман

  • Добре дошли
  • Благодарности
  • всеотдайност
  • Предговор
  • Въведение
  • 1. Вектори
  • 2. Сили
  • 3. Трептене
  • 4. Системи за частици
  • 5. Библиотеки по физика
  • 6. Автономни агенти
  • 7. Клетъчни автомати
  • 8. Фрактали
  • 9. Еволюцията на кода
  • 10. Невронни мрежи
  • Допълнителна информация
  • Индекс

Даниел Шифман

Глава 9. Еволюция на кода

„Фактът, че животът се е развил от почти нищо, около 10 милиарда години след като Вселената се е развила буквално от нищо, е факт, толкова зашеметяващ, че аз ще се побъркам да опитам думи, за да го оправдая.“ - Ричард Докинс

Нека отделим малко време, за да се върнем към по-просто време, когато сте написали първите си скици за обработка и животът е бил безплатен и лесен. Коя е една от основните концепции за програмиране, която вероятно сте използвали в тези първи скици и продължавате да използвате отново и отново? Променливи. Променливите ви позволяват да запазвате данни и да ги използвате повторно, докато се изпълнява програма. Това, разбира се, не е нищо ново за нас. Всъщност ние сме преминали далеч отвъд скицата само с една или две променливи и към по-сложни структури от данни - променливи, направени от персонализирани типове (обекти), които включват както данни, така и функционалност. Създали сме свои малки светове на хамали и частици и превозни средства и клетки и дървета.

Във всеки пример в тази книга променливите на тези обекти трябва да бъдат инициализирани. Може би сте направили цял куп частици с произволни цветове и размери или списък с превозни средства, които започват от едно и също място x, y на екрана. Но вместо да действаме като „интелигентни дизайнери“ и да присвояваме свойствата на нашите обекти чрез случайност или внимателно обмисляне, ние можем да оставим процес, открит в природата - еволюция - да реши вместо нас.

Можем ли да мислим за променливите на даден обект като негова ДНК? Могат ли обектите да правят други обекти и да предават своята ДНК на ново поколение? Може ли нашата симулация да се развие?

Отговорът на всички тези въпроси е да. В крайна сметка не бихме могли да се изправим пред огледалото като естествени кодери, без да се заемем със симулация на един от най-мощните алгоритмични процеси, открити в самата природа. Тази глава е посветена на изследването на принципите, стоящи зад биологичната еволюция и намирането на начини за прилагане на тези принципи в кода.

9.1 Генетични алгоритми: вдъхновени от действителни събития

За нас е важно да изясним целите на тази глава. Няма да навлизаме задълбочено в науката за генетиката и еволюцията, както се случва в реалния свят. Няма да правим квадратчета на Punnett (съжалявам, че ще разочаровам) и няма да има дискусия за нуклеотиди, синтез на протеини, РНК и други теми, свързани с действителните биологични процеси на еволюция. Вместо това ще разгледаме основните принципи на Дарвиновата еволюционна теория и ще разработим набор от алгоритми, вдъхновени от тези принципи. Ние не се интересуваме толкова от точна симулация на еволюцията; по-скоро ни интересуват методи за прилагане на еволюционни стратегии в софтуера.

Това не означава, че проект с по-голяма научна дълбочина не би имал стойност и аз насърчавам читателите с особен интерес към тази тема да проучат възможностите за разширяване на примерите, предоставени с допълнителни еволюционни характеристики. Въпреки това, за да поддържаме нещата управляеми, ще се придържаме към основите, които ще бъдат много сложни и вълнуващи.

Терминът „генетичен алгоритъм“ се отнася до специфичен алгоритъм, реализиран по специфичен начин за решаване на специфични видове проблеми. Въпреки че самият формален генетичен алгоритъм ще служи като основа за примерите, които създаваме в тази глава, не е нужно да се притесняваме за прилагането на алгоритъма с перфектна точност, като се има предвид, че търсим творчески приложения на еволюционните теории в нашия код. Тази глава ще бъде разделена на следните три части (с по-голямата част от времето, прекарано в първата).

Традиционен генетичен алгоритъм. Ще започнем с традиционния генетичен алгоритъм на компютърните науки. Този алгоритъм е разработен за решаване на проблеми, при които пространството за решения е толкова обширно, че алгоритъмът „груба сила“ просто ще отнеме твърде много време. Ето пример: мисля за число. Число между един и един милиард. Колко време ще ви отнеме да го познаете? Решаването на проблем с „груба сила“ се отнася до процеса на проверка на всяко възможно решение. Един ли е? Две ли са? Три ли е? Четири ли е? И така и така нататък. Въпреки че късметът играе фактор тук, с груба сила често бихме се оказали търпеливо да чакаме години, докато броите до един милиард. Какво обаче, ако мога да ви кажа дали отговорът, който сте дали, е добър или лош? Топло или студено? Много топло? Горещо? Супер, супер студено? Ако можете да прецените доколко е подходящо едно предположение, можете да изберете други числа по-близо до това предположение и да стигнете до отговора по-бързо. Вашият отговор може да се развие.

Интерактивен избор. След като установим традиционния алгоритъм за компютърни науки, ще разгледаме други приложения на генетичните алгоритми във визуалните изкуства. Интерактивният подбор се отнася до процеса на развитие на нещо (често компютърно генерирано изображение) чрез взаимодействие с потребителя. Да кажем, че влизате в музейна галерия и виждате десет картини. С интерактивния подбор бихте избрали своите фаворити и бихте позволили на алгоритмичен процес да генерира (или „еволюира“) нови картини въз основа на вашите предпочитания.

Екосистемна симулация. Традиционният информатичен генетичен алгоритъм и интерактивната техника за подбор са това, което най-вероятно ще намерите, ако търсите онлайн или четете учебник за изкуствения интелект. Но както скоро ще видим, те всъщност не симулират процеса на еволюция, както се случва в реалния свят. В тази глава искам също да изследвам техники за симулиране на процеса на еволюция в екосистема от псевдоживи същества. Как могат нашите обекти, които се движат по екрана, да се срещат помежду си, да се чифтосват и да предават гените си на ново поколение? Това би се отнасяло пряко за екосистемния проект, посочен в края на всяка глава.

9.2 Защо да използваме генетични алгоритми?

Докато компютърните симулации на еволюционни процеси датират от 50-те години на миналия век, голяма част от това, което ние смятаме за генетични алгоритми (известни още като „GAs“), днес е разработено от Джон Холанд, професор от Университета в Мичиган, чиято книга „Адаптация в естествените и Изкуствените системи са пионери в изследванията на GA. Днес повече генетични алгоритми са част от по-широка област на изследване, често наричана „еволюционни изчисления“.

За да илюстрираме традиционния генетичен алгоритъм, ще започнем с маймуните. Не, не нашите еволюционни предци. Ще започнем с някои измислени маймуни, които се блъскат по клавиатури с цел да напишат пълните произведения на Шекспир.

бъдеш бъдеш това

„Теоремата за безкрайните маймуни“ е формулирана по следния начин: Маймуна, удряща произволно клавиши на пишеща машина, в крайна сметка ще напише пълните произведения на Шекспир (дадено безкрайно време). Проблемът с тази теория е, че вероятността споменатата маймуна всъщност да напише Шекспир е толкова ниска, че дори тази маймуна да е започнала в Големия взрив, е невероятно вероятно дори да имаме Хамлет в този момент.

Нека разгледаме маймуна на име Джордж. Джордж пише на намалена пишеща машина, съдържаща само двадесет и седем знака: двадесет и шест букви и една интервал. Така че вероятността Джордж да удари който и да е ключ е една на всеки двадесет и седем.

Нека разгледаме фразата „да бъдеш или да не бъдеш, това е въпросът“ (ние го опростяваме от оригинала „Да бъдеш или да не бъдеш: това е въпросът“). Фразата е с дължина 39 знака. Ако Джордж започне да пише, шансът да получи правилния първи знак е 1 към 27. Тъй като вероятността да получи правилния втори символ също е 1 към 27, той има шанс 1 към 27 * 27 да кацне първия два знака в правилен ред - което следва директно от нашата дискусия за „вероятността от събитие“ във Въведението. Следователно вероятността Джордж да напише пълната фраза е:

(1/27), умножено по себе си 39 пъти, т.е. (1/27) 39

което се равнява на 1 на 66,555,937,033,867,822,607,895,549,241,096,482,953,017,615,834,735,226,163 шанс да се оправи!

Излишно е да казвам, че дори да ударите само тази една фраза, да не говорим за цяла пиеса, е много малко вероятно. Дори ако Джордж е компютърна симулация и може да пише един милион случайни фрази в секунда, за да има 99% вероятност Джордж да е в крайна сметка да се оправи, той ще трябва да пише в продължение на 9 719 096 182 0810 563 073 125 255 311 903 305 625 605 077 години. (Обърнете внимание, че възрастта на Вселената се оценява на само 13 750 000 000 години.)

Смисълът на всички тези необозримо големи числа не е да ви боли глава, а да демонстрира, че алгоритъмът за груба сила (въвеждане на всяка възможна произволна фраза) не е разумна стратегия за случайно достигане до „да бъдеш или да не бъдеш това е въпрос ”. Въведете генетични алгоритми, които ще покажат, че все пак можем да започнем с произволни фрази и да намерим решението чрез симулирана еволюция.

Сега си струва да се отбележи, че този проблем (стигнете до фразата „да бъдеш или да не бъдеш това е въпросът“) е абсурден. Тъй като знаем отговора, всичко, което трябва да направим, е да го напишем. Ето скица за обработка, която решава проблема.

Независимо от това, въпросът тук е, че решаването на проблем с известен отговор ни позволява лесно да тестваме кода си. След като успешно решим проблема, можем да се чувстваме по-уверени в използването на генетични алгоритми за извършване на действителна полезна работа: решаване на проблеми с неизвестни отговори. Така че този първи пример няма друга реална цел освен да демонстрира как работят генетичните алгоритми. Ако тестваме резултатите от GA спрямо известния отговор и получим „да бъдеш или да не бъдеш“, тогава сме успели да напишем нашия генетичен алгоритъм.

Упражнение 9.1

Създайте скица, която генерира произволни низове. Ще трябва да знаем как да направим това, за да приложим примера на генетичния алгоритъм, който скоро ще последва. Колко време отнема на Обработката, за да генерира произволно низа „котка“? Как бихте могли да адаптирате това, за да генерирате произволен дизайн, използвайки функциите за изчертаване на фигури на Processing?

9.3 Дарвинов естествен подбор

Преди да започнем да се разхождаме през генетичния алгоритъм, нека отделим малко време, за да опишем три основни принципа на дарвиновата еволюция, които ще са необходими, докато прилагаме нашата симулация. За да се случи естественият подбор, както се случва в природата, трябва да присъстват и трите тези елемента.

Наследственост. Трябва да има процес, чрез който децата да получават свойствата на своите родители. Ако съществата живеят достатъчно дълго, за да се размножават, тогава техните черти се предават на децата им в следващото поколение същества.

Вариация. Трябва да има разнообразие от черти в популацията или средство, с което да се въведат вариации. Например, да кажем, че има популация от бръмбари, при които всички бръмбари са абсолютно еднакви: един и същи цвят, еднакъв размер, еднакъв размах на крилата, същото всичко. Без никакво разнообразие в популацията децата винаги ще бъдат идентични с родителите и помежду си. Нови комбинации от черти никога не могат да възникнат и нищо не може да се развие.

Избор. Трябва да има механизъм, чрез който някои членове на една популация да имат възможност да бъдат родители и да предават генетичната си информация, а някои не. Това обикновено се нарича „оцеляване на най-силните.“ Например, да кажем, че популация газели е преследвана от лъвове всеки ден. По-бързите газели са по-склонни да избягат от лъвовете и следователно е по-вероятно да живеят по-дълго и да имат шанс да се възпроизвеждат и предават гените си на децата си. Терминът най-подходящ обаче може да бъде малко подвеждащ. Като цяло, ние смятаме, че това означава по-голямо, по-бързо или по-силно. Въпреки че в някои случаи това може да се случи, естественият подбор действа на принципа, че някои черти са по-добре адаптирани към околната среда на съществото и следователно създават по-голяма вероятност да оцелеят и да се размножат. Това няма нищо общо с дадено създание, което е „по-добро“ (в края на краищата това е субективен термин) или по-„физически годно“. В случая с нашите пишещи маймуни, например, по-„годна“ маймуна е тази, която е въвела фраза по-близо до „да бъде или да не бъде“.

След това бих искал да разгледам разказа за генетичния алгоритъм. Ще направим това в контекста на пишещата маймуна. Самият алгоритъм ще бъде разделен на две части: набор от условия за инициализация (т.е. Processing’s setup ()) и стъпките, които се повтарят отново и отново (т.е. Processing draw ()), докато стигнем до верния отговор.

9.4 Генетичният алгоритъм, част I: Създаване на популация

В контекста на примера за пишеща маймуна ще създадем популация от фрази. (Обърнете внимание, че използваме термина „фраза“ доста свободно, което означава низ от символи.) Това поражда въпроса: Как да създадем тази популация? Ето къде е дарвиновият принцип на вариация се прилага. Да кажем, за простота, че се опитваме да развием фразата „котка“ и че имаме популация от три фрази.

Разбира се, има разнообразие в трите фрази по-горе, но се опитайте да смесите и съчетаете символите по всякакъв начин и никога няма да получите котка. Тук няма достатъчно разнообразие, за да се развие оптималното решение. Ако обаче имахме популация от хиляди фрази, всички генерирани на случаен принцип, има шанс поне един член от популацията да има c като първи символ, един да има a като втори и един a t като трети. Голяма популация най-вероятно ще ни даде достатъчно разнообразие, за да генерираме желаната фраза (а в част 2 от алгоритъма ще имаме още една възможност да въведем още повече вариации, в случай че на първо място няма достатъчно). Така че можем да бъдем по-конкретни в описанието на стъпка 1 и да кажем:

Създайте популация от произволно генерирани елементи.

Това повдига още един важен въпрос. Какъв е самият елемент? Докато се придвижваме през примерите в тази глава, ще видим няколко различни сценария; може да имаме популация от изображения или популация от превозни средства ала Глава 6. Ключът и частта, която е нова за нас в тази глава, е, че всеки член на популацията има виртуална „ДНК“, набор от свойства (можем да ги наречем „гени“), които описват как изглежда или се държи даден елемент. В случай на маймуната, която пише, например, ДНК е просто низ от символи.

В областта на генетиката има важно разграничение между понятията генотип и фенотип. Действителният генетичен код - в нашия случай самата цифрова информация - е елемент генотип. Това е, което се предава от поколение на поколение. The фенотип, обаче е изразът на тези данни. Това разграничение е ключово за това как ще използвате генетични алгоритми в собствената си работа. Какви са обектите във вашия свят? Как ще проектирате генотипа за вашите обекти (структурата на данните за съхраняване на свойствата на всеки обект), както и фенотипа (какво използвате тези променливи за изразяване?) Ние правим това през цялото време в графично програмиране. Най-простият пример е може би цветът.

Както виждаме, генотипът е цифровата информация. Всеки цвят е променлива, която съхранява цяло число и ние избираме да изразим това число като цвят. Но това как избираме да изразяваме данните е произволно. При различен подход бихме могли да използваме цялото число, за да опишем дължината на линията, тежестта на сила и т.н.

Хубавото на нашия пример за типизиране на маймуни е, че няма разлика между генотип и фенотип. Данните за ДНК са низ от символи и изразът на тези данни е точно този низ.

И така, най-накрая можем да приключим обсъждането на тази първа стъпка и да бъдем по-конкретни с нейното описание, като кажем:

Създайте популация от N елемента, всеки с произволно генерирана ДНК.

9.5 Генетичният алгоритъм, част II: Избор

Тук прилагаме дарвиновския принцип на подбор. Трябва да направим оценка на популацията и да определим кои членове са годни да бъдат избрани за родители за следващото поколение. Процесът на подбор може да бъде разделен на две стъпки.

1) Оценете фитнес.

За да функционира правилно генетичният ни алгоритъм, ще трябва да проектираме това, което се нарича a фитнес функция. Функцията ще изведе числова оценка, за да опише годността на даден член от популацията. Това, разбира се, изобщо не е как работи реалният свят. Съществата не получават оценка; те просто оцеляват или не. Но в случая с традиционния генетичен алгоритъм, където се опитваме да развием оптимално решение на даден проблем, трябва да можем да оценим числено всяко дадено възможно решение.

Нека разгледаме нашия текущ пример, пишещата маймуна. Отново, нека опростим сценария и да кажем, че се опитваме да развием думата „котка“. Имаме трима представители на населението: хижа, кола и кутия. Автомобилът очевидно е най-подходящ, като се има предвид, че има два правилни знака, хижата има само един, а кутията има нула. И ето го, нашата фитнес функция: