генетичен алгоритъм
Генетичният алгоритъме алгоритъм за намиране на решение на конкретен проблем въз основа на евристика. Обхватът на задачите, които трябва да бъдат решени, е малко тесен: основно това са задачи за оптимизация и моделиране. Търсенето на решение се извършва чрез случаен подбор, комбинация и вариация на желаните параметри с помощта на методи, напомнящи за биологичната еволюция.
Генетичният алгоритъм е вид еволюционно изчисление.
Задачата е кодирана по такъв начин, че нейното решение може да бъде представено като набор от коефициенти - гени. Това е може би единственото ограничение и ако е възможно, тогава проблемът ще бъде доста успешно решен от генетичен алгоритъм. Тоест, основната трудност е представянето (тълкуването) на решението на проблема в необходимата форма.
Първоначално се създава първата популация (набор от решения), чиито гени се определят на случаен принцип, след което за всяко решение се определя стойността на фитнес функцията.
Фитнес функцията е обективна функция, тоест мярка за точността на дадено решение или мярка за удовлетворение от решението на проблем. Генетичният алгоритъм се занимава с увеличаване на стойността на фитнес функцията.
След определяне на фитнес функциите и преброяването им за всяка опция се избират най-добрите гени, които да бъдат прехвърлени към следващото поколение опции за вземане на решения. Така след няколко поколения ще се намери добро решение на проблема (ако е възможно).
Типична процедура за алгоритъма е представена по-долу. Инициализация: 1. Дефинирана е фитнес функция, т.е. начин за оценка на гените за селекция. 2. Създаване на първоначалната популация. Най-често първоначалните гени са запълнени със случайни стойности. Цикъл: 1. Определяне на стойностите на фитнес функцията за всеки ген. 2. Избор на най-добрите гени. 3. Кръстосванегени и/или мутация. 4. Създаване на нова популация на базата на получените гени.
Цикълът спира, когато се достигне необходимата точност на решаване на проблема.
Като пример за работата на генетичен алгоритъм, давам графика от моята статия (Бюлетин на IzhSTU 2008):
Графиката показва максималните и средните стойности на фитнес функцията за всяка епоха от цялата популация. Коефициентите бяха избрани за невронната мрежа, задачата не беше проста - обучение на механизмите да се движат правилно. И все пак за малък брой епохи вече е намерен добър вариант.
Като допълнение давам една от моите реализации на генетичния алгоритъм или по-скоро еволюционната функция, проста и в същото време отлична опция:
Стойността на разнообразието определя броя на индивидите, чиито гени ще бъдат предадени на следващото поколение. Самите тези лица няма да бъдат променяни, за да не се загубят най-добрите решения. Така получихме отлична версия на генетичния алгоритъм.
Какво е генетичен алгоритъм?