Направления развития генетических алгоритмов

Практическая деятельность человека ставит перед наукой все новые исследовательские задачи. Область применения генетических алгоритмов постоянно расширяется, что требует их совершенствования и исследова­ния. Перечислим несколько новых задач, которые могут решаться с ис­пользованием генетических алгоритмов, и связанные с ними направления исследование в этой области:

· разработка новых методов тестирования генетических алгоритмов;

· разработка адаптивных генетических алгоритмов;

· расширение круга решаемых с использованием генетических алго­ритмов задач;

· максимальное приближение генетических алгоритмов к естествен­ному эволюционному процессу.

До недавнего времени в качестве критерия качества большинства кон­кретных генетических алгоритмов использовалась эффективность решения задачи получения битового вектора с максимальным числом единичных разрядов. Чем быстрее алгоритм находил наилучшее решение, тем он счи­тался эффективнее. Сейчас эта задача уже не является объективным сред­ством тестирования алгоритмов, что свидетельствует об их бурном разви­тии не только с точки зрения применимости к тем или иным классам задач, но и с точки зрения их внутреннего построения и принципов работы.

В области «исследований, направленных на повышение эффективности генетических алгоритмов, большое значение приобрели идеи создания адап­тивных генетических алгоритмов, которые могут изменять свои парамет­ры в процессе работы. Они стали продолжением развития идеи поколенческих алгоритмов, которые в процессе работы изменяют размер популя­ции. Адаптивные алгоритмы способны изменять не только этот параметр, но и суть генетических операторов, вероятность мутации и даже генотип алгоритма. Как правило, данные изменения происходят путем выбора па­раметров из нескольких вариантов, определенных перед началом работы алгоритма.

Идея адаптивных генетических алгоритмов получила свое воплощение в концепции NGA, представляющей многоуровневые генетические ал­горитмы. Нижний уровень такого алгоритма непосредственно выполняет задачу улучшения популяции решений. Верхние уровни представляют со­бой генетические алгоритмы, решающие оптимизационную задачу по улуч­шению параметров алгоритма нижнего уровня. При этом в качестве целе­вой функции используется обычно скорость работы алгоритма нижнего уровня и скорость улучшения им популяции от поколения к поколению.

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

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

Перспективным направлением развития является добавление к генети­ческим операторам ламарковских операторов, которые позволяют вводить в рассмотрение признаки, приобретенные особью не в результате наследо­вания, а в течение своего жизненного цикла. Это еще более приближает модель генетических алгоритмов к природным процессам и, по мнению ученых, способно повысить их эффективность.

Идея приближения генетических алгоритмов к реальному эволюцион­ному процессу нашла свое отражение и в предложениях ввести в рассмот­рение такие понятия, как вид и пол, учитывать взаимодействие особей в популяции в процессе "жизни", причем особей как одного вида, так и раз­личных. Это позволит моделировать процессы сотрудничества, отноше­ний хозяев и паразитов и т. д.

Помимо этих новых течений в области исследования генетических ал­горитмов ведутся работы и в традиционных направлениях. Создаются все новые разновидности операторов отбора, скрещивания и мутации. Конст­руируются адаптивные алгоритмы, совершенствуются методы распарал­леливания вычислений и структурирования популяций. Одновременно разрабатываются методики оценки эффективности и тестирования гене­тических алгоритмов.

Таким образом, генетические алгоритмы представляют собой одну из важных и активно развивающихся парадигм обширной области алгорит­мов поиска оптимальных решений. И в последнее время, с развитием ме­тодов компьютерной поддержки принятия решений, они приобретают все большее значение.