Математика. Генетические алгоритмы

Секция: математика. Генетические алгоритмы.

Кутуков Никита

Школа № 83, 11 «В» класс

Научный руководитель к. т.н., доцент

Зарождение генетики, как науки о механизмах наследственности и изменчивости живых организмов в процессе их эволюционного развития обязано учителю математики и биологии Грегори Менделю. Более чем столетие спустя идеи генетики  стимулировали зарождение нового направления в математике – генетические алгоритмы.

В основе этих алгоритмов используется идея постепенного улучшения состава популяции на основе дарвинского принципа естественного отбора, на каждом шаге которого образуется новое множество приближений, создаваемое посредством процесса отбора индивидуумов согласно их уровню пригодности. Операндом генетического алгоритма являются гены @G – закодированные оценки переменных, объединенных в «хромосому» (chromosome, string) - n-мерный вектор &S.

Обычно используются четыре генетических оператора:

репродукция (reproduction) кроссинговер (crossingover); мутация (mutation); селекция (selection).

Кроссинговер и мутация играют разную роль. Кроссинговер, как правило, наиболее эффективен в начале поиска, в то время как мутация позволяет найти более точное решение в конце его. Совместное использование операторов отбора и кроссинговера приводит к тому, что области пространства, обладающие лучшей в среднем оптимальностью, содержат больше членов популяции, чем другие. Таким образом, эволюция популяции направляется к областям, содержащим оптимум с большей вероятностью, чем другие.

       Основные преимущества генетических алгоритмов: параллельность процесса поиска; вовлечение в соответствующую процедуру сразу большого числа кандидатов на решение и большого числа исследуемых областей пространства поиска. Метод обеспечивает нахождение приближенного глобального решения задачи, не встречая затруднений при решении проблемы локальных экстремумов.