Генетски алгоритам
Генетски алгоритам[1][2][3] или генетички алгоритам[4] (ГА) је стохастични метод претраживања, који опонаша биолошки процес еволуције.[5] Карактеристично за њега је да одржава већу групу могућих решења проблема, која се назива популацијом. Одабрана решења из популације се међусобно комбинују како би формирала нову генерацију решења која би потенцијално садржала боље потомке. Главна одлика ГА у односу на друге стохастичне методе је постојање операција укрштања и мутације. Симболично, податак о стању неке променљиве се назива геном, а скуп стања променљивих које дефинишу једно решење се назива хромозомом.
ГА се примарно деле на бинарне и континуалне[6]. Есенцијална разлика између ова два типа ГА је то што хромозом бинарног ГА чини низ битова, док је он код континуалног низ реалних вредности.
Садржај |
Принцип рада [уреди]
Рад ГА се може описати у осам односно седам корака[7]:
- Дефинисање свих потребних параметара проблема и ГА
- Формирање почетне популације
- Декодирање хромозома — овај корак се јавља само код бинарних ГА
- Одређивање цена хромозомима (фитнес функцијом)
- Одабир селекције хромозома који ће опстати за парење
- Парење — обично се из бољег дела популације одабиру родитељи који ће на неки начин укрстити свој генетски материјал и дати једног или више потомака који обично замене неког од лошијих хромозома
- Мутције, при којима се мења генетски садржај хромозома
- Испитивање конвергенције, да би се утврдило да ли има основа да се ток алгоритма прекине. Уколико није испуњен услов конвергенције, вратити се на корак 3 односно 4.
Хибридни ГА [уреди]
Због својства ГА да спорије конвергира неком решењу од класичних метода оптимизације, препоручује се употреба ГА који у одређеним моментима над својом популацијом покрећу локални оптимизатор, и његове резултате опет уврштавају у нову генерацију популације.[8]
У пракси, хибридни ГА брже конвергирају ка решењу од класичних. Као локални оптимизатор може да се употреби не само неки од класичних метода (нпр. симплекс), већ и микро ГА — ГА са јако малом популацијом.
Референце [уреди]
- ^ Програм изборног предмета „генетски алгоритми“ на докторским студијама, Математички факултет, приступљено 12.12.2010.
- ^ Књига предмета, Рачунарски факултет — Мастер студије, стр. 28, приступљено 12.12.2010.
- ^ Преглед неких радова који користе термин генетски алгоритам
- ^ Преглед неких радова који користе термин генетички алгоритам
- ^ Ген, Чен, Лин, стр. 1
- ^ Хаупт и Хаупт, увод, стр. XIII
- ^ Хаупт и Хаупт, стр. 29 и 52
- ^ Хаупт и Хаупт, стр. 101-104
Литература [уреди]
- Mitsuo Gen, Runwei Cheng, Lin Lin (2008), Network models and optimization: multiobjective genetic algorithm approach, ISBN 978-1-84800-181-7
- Randy L. Haupt, Sue Ellen Haupt (2004), Practical Genetic Algorithms, Second Edition, ISBN 0-471-45565-2
Види још [уреди]
- Генетско програмирање
- Културални алгоритми
- Симулирано каљење
- Оптимизација ројењем честица
- Оптимизација симулирањем колоније мрава
 |
Овај незавршени чланак Генетски алгоритам везан је за рачунарство. Користећи правила Википедије, можете га проширити. |
