Въведение в генетичните алгоритми
автор: TheCеll (TheCell61 at hotmail dot com)
Превод от английски: Мордет
Материалът е публикуван с разрешението на DevMaster
Генетични алгоритми... За какво могат да бъдат полeзни? За хората интересуващи се от разработка на игри генетичните алгоритми могат да им помогнат за създаването на по-добър изкуствен интелект. Могат да бъдат от полза в реалновремевите стратегии, където компютърният опонент трябва да еволюира, избира действията си по-добре, да се учи и т.н.
Това е първата ми статия, така че, ако нещо липсва или е неясно, свържете се с мен за да обновя текста и, надявам се, да го направя по-добър.
Тази статия е предназначена за хора, които нямат или почти нямат, познания по генетични алгоритми и генетично програмиране. Какво точно представляват генетичните алгоритми? Това е начин да правим нещата подобно на Майката Природа – само най-силните оцеляват. Но как можем да преведем това на компютърен език? По-добре първо да видим как приподата се справя с това. Нека ви разкажа една история.
Имало едно време идна малка земя наречена Езрас. В тази земя имало два вида същества – растения и тревопасни. Тревопасните обикаляли и изяждали храната, която откривали. Един ден растенията се свършили и тревопасните трябвали да пътуват надалеч за да открият храна. Тези, които останали на старото място, умряли от глад. Тревопасните, предприели пътуването, имали шанс да оцелеят и възпроизведат. Някои пътували повече от другите и развили силни мускули на краката си. Когато храната отново свършила и се наложило да пътуват, тревопасните с по-добре развити мускули се движили по-бързо и първи стигали до новата храна и следователно се хранели и оцелявали по-добре от другите. Твърде бавните недостигали до храната и умирали...
По този прост начин Майката Природа отсява най-добрите екземпляри и им позволява да оцелеят и възпроизведат. Но как това може да бъде пресъздадено с компютър? Това е относително просто.
Човешкото дете наследява хромозомите на родителите си – 23 от майката и 23 от бащата. Хромозомите са множества от гени, които определят цвета на очите, цвета на косата и т.н. Генът също представлява множество от данни. Ето как изглежда един ген:
(11100010)
а хромозомите изглеждат така (в бинарно представяне):
Ген1 Ген2 Ген3 Ген4
(11000010, 00001110, 001111010, 10100011)
Всеки ген представлява някакви данни (цвят на косата, зрение, цвят но очите и т.н.). Така бебето представлява размяна на информация между бащата и майката.
Понякога се получават мутации. Мутацията представлява променен бит в някой ген. По този начин се осигурява богатството на генния фонд.
Нека ви покажа пример приложим при компютрите.
Имаме фонд от същества, които искаме да еволюират. Имаме и гени представляващи зрение, скорост и енергиа. Когато хромозомите се декодират може да бъде видяно това:
1ви хромозом | 2ри хромозом
Зрение Скорост | Енергия
(0110 0110) | (1100)
Сега имаме същество с дефинирани характеристики под формата на хромозоми. Но как ще го накараме да еволюира за да стане по-добро? Тук вече идва трудната част. Трябва да се дефинират правила, които определят кое животно е най-силно. Обикновено при изкуствения живот най-силното е това, което е още живо, но понякога нещата могат да станат наистина сложни. Ето едно примерно правило: ако една версия на поведението отнема повече време да бъде победена от друга то тази версия има по-голямо право да еволюира.
Но нека оставим нещата прости и се средоточим само върху оцеляването. Ако форма на живот оцелее значи тя е силна. Но ако само разрушаваме слабите ще унищожим целия изкуствен живот. Тук идва нуждата от репродукция. Както в историята по-горе ние трябва да направим някаква размяна за да сме сигурни, че получаваме най-доброто от всяка изкуствена форма на живот. Това става чрез размяна на информацията на гените.
1ви хромозом | 2ри хромозом
(Зрение Скорост)| (Енергия)
(0110 0110)| (1100)
Когато две изкуствени същества се въпроизведат ние разменяме хромозомите.
Хромозоми на първия подител:
1ви | 2ри
(01100110) | (1100)
Хромозоми на втория родител:
1ви | 2ри
(00101111) | (0110)
Създаваме две деца с разбъркани хромозоми:
Първо дете:
1ви родител | 2ри родител
1ви хромозом | 2ри хромозом
(01100110) | (0110)
Второ дете:
2ри родител | 1ви подител
1ви хромозом | 2ри хромозом
(00101111) | (1100)
Мутацията се получава, когато даден ген претърпява малка модификация. Едното дете може да получи или не получи мутация. Примерно хромозомите на второто дете след мутацията могат да изглеждат така:
Хромозоми на второто дете:
1ви | 2ри
(00101111) | (1101)
^
|
Така като комбинираме хромозомите на двамата родители осигуряваме богатството и разнообразието на генния фонд. Забележете, че първите хромозоми са съставени от два гена, а вторите от един.
Сега да приложим наученото към изкуствения живот. Имаме фонд от изкуствени същества. Поставяме ги в среда, чийто правила дефинираме: всяко същество се нуждае от храна, зрението определя намираната храна, скоростта определя колко бързо съществото достига до храната, максималната енергия определя колко енергия може да получи едно същество, когато енергията на някое същество стане равна на нула то умира, ако две същеста се срещнат и енергията им е над 50% те се въпроизведждат. Определяме ген за всяка характеристика (зрение, скорост, енергия). Групираме първите два гена в един хромозом, а третият сам представлява хромозом.
Съществата ще се възпроизвеждат и умират поради липса на храна. Най-силните ще оцелеят, защото запазват по-дълго енергията си, набавят си по-бързо храна или я забелязват първи. Така те имат по-добър шанс да се въпроизведат и да се подобрят. Понякога същества ще оцеляват заради късмет. Генетичните алгоритми се поддават на подобреня, но е трудно да се получи максимума.
Това е края на тази статия. Надявам се че ви помогнах да разбирате по-добре основите на генетичните алгоритми.