Работа генетического алгоритма

ГА предназначены для оптимизации задач. Традиционные методы поиска имеют ряд недостатков и обычно предполагают дифференцируемость исследуемой функции от ее параметров и обычно используют градиентные процедуры. ГА принципиально отличаются от традиционных. Они основаны на использовании сразу нескольких точек поиска. Используемые при этом механизмы позволяют отсеять наименее подходящие варианты и усилить нужные.

Основные понятия ГА:

- индивидуум - потенциальное решение определенной проблемы;

- популяция - множество родственных индивидуумов;

- хромосомы – закодированный ряд, составленный в соответствии с некоторым алфавитом;

- ген – элемент хромосомы;

- генотип – значение хромосомы.

Наиболее часто используется двоичный алфавит {0,1 }. Например, х1 = 0011010011, х2 = 0101110100101.

Если раскодировать хромосому в область реальных переменных, то можно оценить насколько хорошо подходит каждый член популяции для решения поставленной задачи. Такая оценка проводится с помощью заранее заданной целевой функции – функции пригодности. Эта функция оценивает способность индивидуума выживать в окружающей среде. Наиболее «породистые» индивидуумы скрещивают между собой. Основные операции скрещивания – кроссинговер – межхромосомная мутация, обмен участков между хромосомами. Другой оператор – мутация – случайный процесс, когда одна часть хромосом заменяется др., что приводит к появлению новой генетической структуры. После этих операторов необходим оператор отбора, т.е. после скрещивания снова отбираются индивидуумы с большей функцией пригодности. Такой процесс продолжается на протяжении выбранного количества поколений. ГА заканчивает работу при выполнении определенного критерия.