Генетски алгоритам

Из Википедије, слободне енциклопедије

Генетски алгоритам[1][2][3] или генетички алгоритам[4] (ГА) је стохастични метод претраживања, који опонаша биолошки процес еволуције.[5] Карактеристично за њега је да одржава већу групу могућих решења проблема, која се назива популацијом. Одабрана решења из популације се међусобно комбинују како би формирала нову генерацију решења која би потенцијално садржала боље потомке. Главна одлика ГА у односу на друге стохастичне методе је постојање операција укрштања и мутације. Симболично, податак о стању неке променљиве се назива геном, а скуп стања променљивих које дефинишу једно решење се назива хромозомом.

ГА се примарно деле на бинарне и континуалне[6]. Есенцијална разлика између ова два типа ГА је то што хромозом бинарног ГА чини низ битова, док је он код континуалног низ реалних вредности.

Принцип рада[уреди]

Рад ГА се може описати у осам односно седам корака[7]:

  1. Дефинисање свих потребних параметара проблема и ГА
  2. Формирање почетне популације
  3. Декодирање хромозома — овај корак се јавља само код бинарних ГА
  4. Одређивање цена хромозомима (фитнес функцијом)
  5. Одабир селекције хромозома који ће опстати за парење
  6. Парење — обично се из бољег дела популације одабиру родитељи који ће на неки начин укрстити свој генетски материјал и дати једног или више потомака који обично замене неког од лошијих хромозома
  7. Мутције, при којима се мења генетски садржај хромозома
  8. Испитивање конвергенције, да би се утврдило да ли има основа да се ток алгоритма прекине. Уколико није испуњен услов конвергенције, вратити се на корак 3 односно 4.

Хибридни ГА[уреди]

Због својства ГА да спорије конвергира неком решењу од класичних метода оптимизације, препоручује се употреба ГА који у одређеним моментима над својом популацијом покрећу локални оптимизатор, и његове резултате опет уврштавају у нову генерацију популације.[8]

У пракси, хибридни ГА брже конвергирају ка решењу од класичних. Као локални оптимизатор може да се употреби не само неки од класичних метода (нпр. симплекс), већ и микро ГА — ГА са јако малом популацијом.

Види још[уреди]


Референце[уреди]

Литература[уреди]

  • 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