qweqweqe123123

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

Генетическими алгоритмами (genetic algorithms) называется группа адаптивных методов, которые могут использоваться для решения задач поиска и оптимизации. Они происходят от тех же основ, что и естественная эволюция и генетика. Популяции живых существ развиваются в течение многих поколений в соответствии с принципами естественного отбора и «выживания наиболее приспособленных». Имитируя этот процесс, генетические алгоритмы способны решать реальные задачи, при условии, что те будут правильно закодированы [13].

Сила генетических алгоритмов в их устойчивости и в способности решать задачи самых разных типов, в том числе и трудноразрешимые другими методами. Хотя генетические алгоритмы не обязательно находят глобально-оптимальное решение, они обычно «достаточно быстро» находят «достаточно хорошие» решения. Разумеется, специализированные методы, ориентированные на конкретные задачи, по сравнению с генетическими алгоритмами почти наверняка дадут лучшую скорость и точность конечного результата. Превосходство генетических алгоритмов проявляется в таких областях, где специализированных методов не существует. Однако даже имеющиеся методы можно в некоторых случаях усовершенствовать, «скрестив» их с генетическими алгоритмами [56].

Основные принципы генетических алгоритмов были заложены Холландом [71], им посвящено достаточно много трудов. Эти алгоритмы имитируют то, чем обусловливается эволюция в живых популяциях. В природе выживают те, кто лучше приспособлен к конкуренции за ограниченные ресурсы, поэтому адаптация к изменяющейся конкурентной среде принципиально важна для выживания индивидуумов любого вида. Уникальные особенности индивидуума определяют его жизнеспособность, но сами они, в свою очередь, определяются генами индивидуума. Каждой особенности сопоставляется элемент наследственной информации — ген. Наборы генов, определяющих особенности организма, объединяются в хромосомы. Процесс воспроизводства создает разнообразие в генофонде, а начинается оно с рекомбинации хромосом родительских особей в момент объединения их половых клеток. Из исходных комбинаций генов создаются новые, в результате чего получается новый генотип. Происходит обмен генами между хромосомами, что дает хромосомы с новыми свойствами. Этот процесс называется кроссовером (crossover). Таким образом осуществляется поиск наиболее правильной комбинации генов, по которой был бы построен более совершенный организм. Отбор и кроссовер обеспечивают постоянную эволюцию генотипа и приводят к рождению организмов, лучше приспособленных к выживанию.

В начале 70-х гг. Холланд предложил обозначать термином «генетические алгоритмы» программы, имитирующие природный эволюционный процесс. Генетические алгоритмы работают с популяцией потенциальных решений задачи оптимизации (или поиска). Решения представляются в закодированном виде, подобно тому как в генетическом материале кодируется информация об особенностях индивидуума. В генетических алгоритмах Холланда решения кодировались в виде последовательностей битов двоичного алфавита. Как и в природе, механизмы отбора обеспечивали выживание наиболее совершенных решений. Каждому решению сопоставляется определенное значение «приспособленности», отражающее качество данного решения по сравнению с другими решениями той же популяции. Чем больше значение приспособленности, тем больше шансы на выживание и воспроизводство, и тем больший вклад вносит данный индивидуум в последующее поколение. Рекомбинация генетического материала в генетических алгоритмах имитируется механизмом кроссовера, осуществляющим обмен участками строк. Дополнительная операция, называемая мутацией, вызывает спорадические случайные изменения битов строк. Мутация тоже существует в природе, где она обеспечивает восстановление утраченного генетического материала [56].

Смотрите также