Здравейте на всички,
новобранец съм във форума, но имам значително количество теоретични знания по роботика. За съжаление нямам време и ресурси все още за да практикувам това занимание. Началото на това лято ми дойде идея да си направя самообучаващ се робот. В началото си мислих да е на принципа "brute force" - с проба и грешка просто да запомни всяка отделна ситуация в която попадне и най-доброто действие в тази ситуация. Този метод е много добър за прости роботи с малко сензори и мотори, но за по сложен робот е безсмислено да се използва поради факта че ще отнеме прекалено много време за обучаването му. Също така при този метод роботът не може да взима правилни решения при ситуации, в които не е попадал, независимо дали те са много близки до други ситуации в които е попадал. По-късно, във форума намерих тема относно невронни мрежи. Не ги разбрах напълно но ми харесаха като решение за самообучаващ се робот. Невронните мрежи могат да приемат информация от множество сензори и могат да контролират множество мотори при неограничен брой ситуации. Един от недостатъците на невронните мрежи обаче, е трудното им програмиране. За мен лично, а предполагам и за останалите от вас е трудно и неестествено да се мъчим да разберем точно какви тежести трябва да се дадат на всеки неврон за да сработи всичко както трябва. И в този момент на помощ идват генетичните алгоритми за които ще говоря от сега нататък.
Генетичния алгоритъм се използва за оптимизация. За какво? За всичко което може да бъде обективно изчислено колко е "добро". Говорим всичко от рода на дизайна на кола (аеродинамика, окачване и т.н.), дизайна на антена, програмиране на невронна мрежа за ходещ робот, разпознаване на изображения и всичко друго което можете да измислите. Същността на този алгоритъм се базира на теорията за биологична еволюция на Дарвин. Нашата програма ще се развива и размножава виртуално във нашият компютър. Преди за започнем да програмираме трябва първо да разясня няколко термина:
1. Организъм
Организъм ще наричаме набор от променливи, които ние искаме да подобрим. Това също може да се нарече геном, защото носи информацията на организма. Тези променливи могат да бъдат различни неща - тежести в невронна мрежа (за оптимизация на поведението на робот) или някакви размери или ъгли във дизайна на този робот (големина на гуми, твърдост на амортисьори и т.н.). Тези променливи се задават на случаен принцип в началото на изпълнението на алгоритъма или могат да бъдат въведени ръчно ( например сте се спрели на общ дизайн и само искате да го подобрите).
Тези и променливи като истински жив организъм са подложени на мутации ,размножаване и кръстосване,за които ще говоря по нататък.
2.Популация
Популацията е просто един сбор от организми. Колкото по-голяма е популацията толкова по-добър резултат ще имаме, но и също така всичко ще става по-бавно. Горна граница на популацията няма но засега не съм виждал някой да ползва повече от 10 000 организма в популация. Най-малко трябва да имаме два организма в популация, като единия може да бъде родител а другия дете (единия е от едно поколение а другия от следващото)
3.Мутация
Мутацията е случайна промяна в някоя от променливите в генома на организма. Мутацията не бива да бъде твърде голяма, защото може да навреди на организма и драстично да влоши неговото качество. Колкото е по- малък размерът на мутацията толкова по-съвършен и оптимизиран ще бъде той. При липса на мутации ще се постигне едно равновесно положение в популацията като всички организми ще бъдат абсолютно еднакви и в доста от случаите далеч от състоянието в което искаме да бъдат. Няма строго определена формула по-която да определим колко големи по размер трябва да бъдат мутациите. По принцип е добре да се започне с малко по-голяма стойност на мутациите за да се пести време и с наближаване на желания от нас резултат размерът на мутациите да се намали.
4.Размножаване или кръстосване
Размножаването или кръстосването е една много важна. Ако се сбърка начина на кръстоска между организмите, могат да се получат "изроди"- несъвместими променливи в генома. Има няколко начина по които можем да размножаваме организмите, като всеки си има своите силни и слаби страни. Разделят се на два основни дяла- сексуално и асексуално. При асексуалното размножаване няма полове, организмите се размножават като бактерии- създава се абсолютно копие на майчиния организъм, след което се прави малка промяна в генома (мутация). Асексуалният начин за размножаване е най-лесният и сигурен , но също така най-бавният. Сега ще дам пример за асексуално размножаване: имаме следния геном в който има няколко променливи-тежести в невронна мрежа (00110110). За да се размножи този организъм правим негово копие, след което добавяме случайна мутация (001
1110). При сексуалното размножаване ни трябват два организма. Има няколко начина да кръстосаме геномите на два организма: да вземем минимална , максимална или средно аритметична стойност от променливите в двата майчини организма и да ги пренесем в дъщерния. Пример за максимално кръстосване: имаме следните два генома
(21, 2, 15,77) и
(18, 44, 6, 56) и получаваме следния дъщерен организъм (
21,
44,
15, 77). Друг метод за кръстоска е да вземем началото на първият организъм и края на втория и да ги свържем. Можем да вземем по 50% от всеки от двата майчини оргаизма но може да бъде и в друго отношение. В следващия пример ще демонстрирам този вид кръстосване с отношение 30/70. Имаме следните два майчини организма
(00110111011) и
(1110001011), получаваме следните два дъщерни организма: (
0010001011) и (
11110111011). Сексуалното размножаване е много по-бързо и ефективно от асексуалното , но ако не го използваме по правилният начин има значителен шанс да се получат неблагоприятни грешки. Сексуално размножаване на максимален, минимален или средно аритметичен принцип не е желателно когато работим с двоичен геном. По-добър вариант е взимането на една част от всеки родител (последният пример) или асексуално размножаване. При асексуалното размножаване е необходимо при всяко размножаване да има мутация (няма смисъл иначе, просто създаваме клонинг- нито по-добър, нито по-лош), а при сексуалното размножаване може да внасяме мутации по- нарядко, например на всеки десети организъм.
При сексуалното размножаване е добра идея , не задължително да подберем два организма които си приличат, за да се намали риска от грешка при размножаването.
5.Фитнес
Фитнесът е също много важна част от генетичния алгоритъм. Фитнесът определя колко добре даден организъм върши своята задача. Той се определя от нас и чрез него задаваме какъв точно искаме да е крайния резултат. Фитнесът трябва да е измерима величина, тоест не можем да зададем параметри като красота или др. Например за един крачещ робот можем да зададем фитнес като: колко време стои прав преди да падне, колко разстояние изминава, колко бързо го изминава, колко високо скача, колко ефективно ходи и др. Фитнесът може да се изчислява и като сбор от изброените досега. За да може да се определи фитнесът трябва да направим симулация на организмът в работа. За това ни трябва симулатор за роботи или подобен софтуер. Възможно е и да проведем тестовете в реалният свят но там ни трябва повече време и усилие, свързано с наблюдаването на робота докато изпълнява алгоритъма (ако имаме крачещ робот ще е нужно да го изправяме след всеки опит).
Та какво точно става за да проработи генетичния алгоритъм.Първо задаваме какви ще са променливите на генома (организма). След това определяме фитнес формулата. Задаваме случайни начални стойности на генома. Минаваме всеки организъм през фитнес теста и отделяме най-добрите. Кръстосваме и размножаваме най добрите. Добавяме мутации. Повтаряме процеса (без случайните начални стойности на геномите) докато получим желаният резултат.
Това е основата на генетичния алгоритъм. Призовавам всички които имат въпроси да ме питат, а ако някои види ,че съм пропуснал нещо да го отбележи.Също така ще помоля да ми препоръчате някаква среда за симулация (искам да си направя ходещ робот) защото до сега не съм имал удоволствието да изпробвам някой от тези алгоритми.
Сега ще представя и няколко примерни клипа от YouTube за генетични алгоритми:
Симулация на ходещ робот, която е ползвана в новата GTA 4:
http://www.youtube.com/watch?v=lSG--GY2p2oЕволюция на часовник:
http://www.youtube.com/watch?v=mcAq9bmCeR0
Анкета
