Анкета

Знаете ли какво е генетичен алгоритъм?

Да знам, и съм ползвал такъв.
2 (6.1%)
Да знам, но не съм ползвал такъв.
5 (15.2%)
Чувал съм за такова нещо , но не знам точно какво е.
7 (21.2%)
Не, не знам и не съм чувал за такова нещо.
19 (57.6%)

Общ брой гласове: 27

Гласуването приключено: Февруари 01, 2011, 10:05:39 pm

Автор Тема: Генетичен алгоритъм  (Прочетена 9477 пъти)

cech

  • Новодошъл
  • *****
  • Публикации: 8
    • Профил
Генетичен алгоритъм
« -: Февруари 01, 2011, 10:05:39 pm »
Здравейте на всички,

новобранец съм във форума, но имам значително количество теоретични знания по роботика. За съжаление нямам време и ресурси все още за да практикувам това занимание. Началото на това лято ми дойде идея да си направя самообучаващ се робот. В началото си мислих да е на принципа "brute force" - с проба и грешка просто да запомни всяка отделна ситуация в която попадне и най-доброто действие в тази ситуация. Този метод е много добър за прости роботи с малко сензори и мотори,  но за по сложен робот е безсмислено да се използва поради факта че ще отнеме прекалено много време за обучаването му. Също така при този метод роботът не може да взима правилни решения при ситуации, в които не е попадал, независимо дали те са много близки до други ситуации в които е попадал. По-късно, във форума намерих тема относно невронни мрежи. Не ги разбрах напълно но ми харесаха като решение за самообучаващ се робот. Невронните мрежи могат да приемат информация от множество сензори и могат да контролират множество мотори при неограничен брой ситуации. Един от недостатъците на невронните мрежи обаче, е трудното им програмиране. За мен лично, а предполагам и за останалите от вас е трудно и неестествено да се мъчим да разберем точно какви тежести трябва да се дадат на всеки неврон за да сработи всичко както трябва. И в този момент на помощ идват генетичните алгоритми за които ще говоря от сега нататък.

Генетичния алгоритъм се използва за оптимизация. За какво? За всичко което може да бъде обективно изчислено колко е "добро". Говорим всичко от рода на дизайна на кола (аеродинамика, окачване и т.н.), дизайна на антена, програмиране на невронна мрежа за ходещ робот, разпознаване на изображения и всичко друго което можете да измислите. Същността на този алгоритъм се базира на теорията за биологична еволюция на Дарвин. Нашата програма ще се развива и размножава виртуално във нашият компютър. Преди за започнем да програмираме трябва първо да разясня няколко термина:

1. Организъм

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

2.Популация

Популацията е просто един сбор от организми. Колкото по-голяма е популацията толкова по-добър резултат ще имаме, но и също така всичко ще става по-бавно. Горна граница на популацията няма но засега не съм виждал някой да ползва повече от 10 000 организма в популация. Най-малко трябва да имаме два организма в популация, като единия може да бъде родител а другия дете (единия е от едно поколение а другия от следващото)

3.Мутация

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

4.Размножаване или кръстосване

Размножаването или кръстосването е една много важна. Ако се сбърка начина на кръстоска между организмите, могат да се получат "изроди"- несъвместими променливи в генома. Има няколко начина по които можем да размножаваме организмите, като всеки си има своите силни и слаби страни. Разделят се на два основни дяла- сексуално и асексуално. При асексуалното размножаване няма полове, организмите се размножават като бактерии- създава се абсолютно копие на майчиния организъм, след което се прави малка промяна в генома (мутация). Асексуалният начин за размножаване е най-лесният и сигурен , но също така най-бавният. Сега ще дам пример за асексуално размножаване: имаме следния геном в който има няколко променливи-тежести в невронна мрежа (00110110). За да се размножи този организъм правим негово копие, след което добавяме случайна мутация (0011110). При сексуалното размножаване ни трябват два организма. Има няколко начина да кръстосаме геномите на два организма: да вземем минимална , максимална или средно аритметична стойност от променливите в двата майчини организма и да ги пренесем в дъщерния. Пример за максимално кръстосване: имаме следните два генома (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
михаил, пловдив, 18 години
http://www.erepublik.com/en/referrer/petr_cech (Който иска да влиза)

sv_shady

  • Administrator
  • *****
  • Публикации: 636
    • Профил
Генетичен алгоритъм
« Отговор #1 -: Февруари 01, 2011, 11:17:14 pm »
Здравей, Михаиле, радвам се, че вече лека по лека тези идеи за изкуствен живот започват да навилизат и в България, и че има хора, които ги намират за интересни. Ако се поразровиш из форума има тема, която съм пускал за самообучаващ се робот като ползва вероятностно обучение. Роботът разполага с 7 сензора, които описват 128 ситуации и така роботът не може да попадне в ситуация, която не е "виждал" преди.
Много добре си се справил с описването на генетичните алгоритми.
Въпреки това искам да внеса още малко светлина по въпроса. Обучението на невронните мрежи е математически доказан метод, който минимизира грешката на мрежата, като намира минимума на хиперравнината в пространството на тежестите. За това не е разумно да се ползват генетични алгоритми за обучение на невронна мрежа. Подбирането на подходящата структура на невронната мрежа, обаче, е нещо,за което все още не е намерен алгоритъм. Знае се, че 3 слоя могат да апроксимират всяка една функция. Именно тук идват генетичните алгоритми, за намиране на подходящия брой неврони във всеки слой. Всяка мрежа се кръстосва с друга мрежа от популацията, като вероятността една мрежа да се кръстоса с друга е толкова по-голяма, колкото по-добре решава проблема.
За симулация на ходещ робот, може да разгледаш Microsoft Robotics Studio или Robot Operating System (ROS). Двете платформи са сходни, едната за линукс, другата уиндоус, но и двете имат симулатор на роботи. Ако изяваваш интерес, мога да кача няколко прости класа на С++, които ползвам за работа с невронни мрежи.
Imagination is the only limit.......

Светлин Пенков
София / Рединг, Великобритания

viko

  • Бил знаел какво е Мехатроника!
  • *****
  • Публикации: 113
    • Профил
Генетичен алгоритъм
« Отговор #2 -: Февруари 09, 2011, 09:20:24 pm »
Добра статия  ;) Прочетох с интерес, макар и вече да съм чел на тази тема. Мисля, че (ако имаш възможност) трябва да довършиш темата.

@sv_shady Ще се радвам да качиш нещата, на мен тази тема ми е особено интересна!
Виктор.

cech

  • Новодошъл
  • *****
  • Публикации: 8
    • Профил
Генетичен алгоритъм
« Отговор #3 -: Февруари 14, 2011, 05:32:54 pm »
Ами не съм сигурен точно какво съм изпуснал за да го допълня. Ако обичаш ми кажи.

И допълнително по темата:

http://www.boxcar2d.com

Генетичен алгоритъм създаващ кола, която да се движи по даден терен. Според мен е много интересно да се наблюдава алгоритъма в действие. На страницата е подробно обяснен начина на работа за това няма да го обяснявам аз. Ще ми бъде интересно да ви чуя отзивите а също така ако някой отдели време и да пусне кода на някоя кола, която е развил.
михаил, пловдив, 18 години
http://www.erepublik.com/en/referrer/petr_cech (Който иска да влиза)

viko

  • Бил знаел какво е Мехатроника!
  • *****
  • Публикации: 113
    • Профил
Генетичен алгоритъм
« Отговор #4 -: Февруари 14, 2011, 07:32:01 pm »
Цитат на: "cech"
Ами не съм сигурен точно какво съм изпуснал за да го допълня. Ако обичаш ми кажи.


Примерче в код би било прекрасно! Иначе темата е супер!
Виктор.

sv_shady

  • Administrator
  • *****
  • Публикации: 636
    • Профил
Генетичен алгоритъм
« Отговор #5 -: Февруари 15, 2011, 12:42:58 am »
Ами само тези дни да си предам една курсова работа и ще кача код за ползване не невронни мрежи, който може лесно да се допълни за създаване на мрежи чрез генетични алгортми. Ами както вече казах невронните мрежи не се обучават чрез генетични алгоритми, а чрез оптимизиране на грешката в хиперпространството на тежеститеи и това е математически доказан процес. Приложението на генетичните алгоритми е в избирането на топология на мрежата.
Imagination is the only limit.......

Светлин Пенков
София / Рединг, Великобритания

sv_shady

  • Administrator
  • *****
  • Публикации: 636
    • Профил
Генетичен алгоритъм
« Отговор #6 -: Февруари 17, 2011, 09:32:41 pm »
Такам, говорих с лекотра ми по "Въведение в невронните мрежи", който се оказа, че пази всички лекции и библиотеката, върху която работихме миналия семестър, публично достъпни онлайн. Та ето линкове към лекциите, както и към практиките с всички необходими файлове:

Лекции - 1ва част
Лекции - 2ра част
Практика
Файлове необходими за практиката

Общо взето, ако на някой му е интересно може да мине материала за има няма 1-2 седмици плюс практиката, която представлява доразвиване на библиотека на С++ за невронни мрежи. Лекциите обхващат както основната теория зад невронните мрежи, така и имплементирането на С++. Честно казано, архитектурата на библиотеката не ми харесва, но е едно добро начало. Аз имам идеи да я пренапиша на С#, но ще видим дали ще отделя време за това. След като човек има такава библиотека съвсем лесно се създават и обучават мрежи, което е ключово за използване на генетични алгоритми. За съжаление, обаче, всичко е на английски.
Imagination is the only limit.......

Светлин Пенков
София / Рединг, Великобритания

viko

  • Бил знаел какво е Мехатроника!
  • *****
  • Публикации: 113
    • Профил
Генетичен алгоритъм
« Отговор #7 -: Февруари 21, 2011, 11:15:16 am »
Благодаря! На мен са ми доста интересни невронните мрежи и си изтеглих презентациите и файловете! :)
Виктор.

suzi4ka

  • Новодошъл
  • *****
  • Публикации: 1
    • Профил
Генетичен алгоритъм
« Отговор #8 -: Юни 06, 2013, 11:00:58 am »
Здравейте! Нова съм във форума, интересуват ме невронните мрежи. Изтеглих си лекциите, но практиката и файловете вече не са на този сайт. Възможно ли е някой от Вас, който ги има да ми ги изпрати? Предварително Ви благодаря!

emil74

  • Зомбиран Роботостроител
  • *****
  • Публикации: 227
    • Профил
    • http://www.maystorio.com
Re: Генетичен алгоритъм
« Отговор #9 -: Декември 18, 2013, 11:42:53 am »
Същата молба и от мен.

sv_shady

  • Administrator
  • *****
  • Публикации: 636
    • Профил
Re: Генетичен алгоритъм
« Отговор #10 -: Декември 30, 2013, 11:07:57 pm »
Презентациите, към които бях дал линкове вече не са свободно достъпни, но пък може да разгледате материалите от Ден 2 на миналогодишния курс по приложен изкуствен интелект, който водих - има и видео запис и презентация. Ако има въпроси ще се радвам да ги обсъждаме тук във форума :)

Imagination is the only limit.......

Светлин Пенков
София / Рединг, Великобритания