Компютърната наука за еволюцията: въведение в генетичните алгоритми

Снимка на Hal Gatewood на Unsplash

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

Така че в опит да изпробвам някои от моите знания досега и да споделя своите открития с останалия свят, реших да събера поредица от статии по тази тема.

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

Животът на Земята

През последните 3,5 милиарда години майката природа, времето на бащата, еволюцията и естественият подбор си сътрудничат за създаването на всички специализирани форми на живот, които днес виждаме на земята: подобно на месоядния растение на Венерия Flytrap; атлантическата летяща риба в океана; прилепи, използващи ехолокация; жирафи с дълги врати; супер бързи гепарди, танцуващи медени пчели; и разбира се, наистина твоят, уличният умен Homo sapiens.

Мухоловката на Венера е месоядно растение, което се храни главно с насекоми и паякообразни.Някои прилепи използват ехолокация за навигация и лов на плячка и противно на общоприетото схващане, прилепите всъщност не са слепи; вид прилепи, известен като Летящите лисици, всъщност имат по-добро зрение от хората.Летящите риби не могат да летят по същия начин, както птиците, но тези риби могат да правят мощни, самоходни скокове от водата, където дългите им перки, подобни на крило, им позволяват да се плъзгат на значителни разстояния над повърхността на водата.

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

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

Слепият часовникар

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

Прогресивната еволюция на човешкото око. Това, което започна като прости фоточувствителни клетки, се превърна в сложен инструмент, който често приемаме напълно за даденост. Първите животни с нещо, наподобяващо око, са живели преди около 550 милиона години. И според изчисленията на един учен, ще са необходими само 364 000 години, за да може да се развие подобно на камерата око от светлочувствителен пластир.

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

Какво представляват генетичните алгоритми и защо имаме нужда от тях?

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

Проблемът с пътуващия продавач задава следния въпрос: „Като се има предвид списък с градове и разстоянията между всяка двойка градове, какъв е най-краткият възможен маршрут, който посещава всеки град и се връща в града на произход?“ Това е проблем с NP комбинаторно оптимизиране.

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

Как работят генетичните алгоритми?

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

Стъпките са следните:

1. Създайте първоначална съвкупност от N възможни решения (първоначалната супа)

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

2. Класирайте решенията на населението по фитнес (оцеляване на най-силните, част 1).

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

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

3. Откажете по-слабите разтвори (оцеляване на най-добрите, част 2)

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

Стъпки 3 и 4 са общо известни като подбор.

4. Развъждайте по-силните решения (оцеляване на най-добрите, част 3)

След това останалите разтвори се сдвояват помежду си, за да се чифтосват и възпроизвеждат потомство. По време на този процес, в най-основната си форма, всеки родител ще допринесе% от своите гени (в природата това е разделяне 50/50) на всяко потомство, където P1 (G)% + P2 (G)% = 100 %. Процесът на определяне кой от родителите на гените ще бъде наследен от потомството е известен като кросоувър.

5. Мутирайте гените на потомството (мутация)

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

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

В генетичните алгоритми селекцията, кросоувърът и мутацията са известни като генетични оператори.

6. Прекратяване

Стъпки 2 до 5 ще се повтарят до предварително определена точка на прекратяване. Тази точка на прекратяване може да бъде едно от следните:

  1. Максимално достигнато разпределение на време / ресурси
  2. Фиксиран брой поколения са преминали.
  3. Пригодността на доминиращото решение не може да бъде надминат от бъдещите поколения.

Конвергенция на решения

1. Глобален оптимум

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

2. Локален оптимум

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

Глобален оптимум срещу локален оптимум

Какво би станало, ако няма мутации?

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

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

Без мутации не бихме имали мутанти и без мутанти нямаше да имаме франчайзинг на X-men.

Какво би се случило, ако размерът на населението не е достатъчно голям?

Наскоро бях в светилището на дивата природа Jukani в Плеттенберг, където имах привилегията да срещна бял тигър. Той беше наистина величествено животно. Той беше голям, изглеждаше свиреп и също беше 80% сляп и прогресивно се влошаваше с напредването на годините.

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

Но един от негативните ефекти на кръвоспирането е, че силно ограничавате генетичните вариации в рамките на вида, което прогресивно увеличава шансовете, че вредните рецесивни черти ще бъдат предадени на потомството.

Белият тигър, когото срещнах в светилището на дивата природа Jukani през април 2019 г. Изглежда величествено, но страда.

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

Снимка от redcharlie на Unsplash.

Разбира се, хората не са непознати за инбридинга. Един известен резултат от непрекъснатото инбридинг в рамките на нашия собствен вид е Чарлз (Карлос) II на Испания.

„Испанският крал Хабсбург Карлос II беше тъжно изроден с огромна грешна глава. Челюстта му в Хабсбург стоеше толкова силно, че двата му реда зъби не можеха да се срещнат; той не успя да дъвче. Езикът му беше толкова голям, че едва успя да говори. Неговият интелект също беше деактивиран. "

Испанският крал Хабсбург Карл II. Баща му беше чичо на майка му, правейки Чарлз съответно техен син, правнук и първи братовчед.

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

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

Обобщавайки

Добре, това трябва да покрива основите. Ако имате някакви въпроси, искания или генетични мутации, за да допринесете, моля, оставете коментар по-долу.

В следващата публикация ще се задълбочим в някакъв код, докато разглеждаме как всеки от описаните по-горе генетични оператори играе в света на програмирането. Използвах програмния език Ruby за софтуерната симулация, върху която работех, и в него показвам как само за няколко поколения генетичен алгоритъм може да генерира предварително определена дума или фраза от първоначална колекция от пълни и пълни глупости. Целият код ще бъде хостван на Github.