Генетические алгоритмы
Введение
| На главную |
| Генетические алгоритмы |
| Группа исследований эволюционных алгоритмов (ТПУ) |
| Дискуссионная группа по эволюционным вычислениям |
| Написать письмо |
Генетические алгоритмы - это очень популярные в настоящее время способы решения задач оптимизации. В их основе лежит использование эволюционных принципов для поиска оптимального решения. Уже сама идея выглядит довольно интригующей и любопытной, чтобы претворить её в жизнь, а многочисленные положительные результаты только разжигают интерес со стороны исследователей.
Я не буду рассматривать историю становления и признания эволюционных вычислений вообще и генетических алгоритмов в частности. Вместо этого я сразу перейду к рассмотрению самих алгоритмов. Когда-нибудь я разрожусь статьей типа "Как это было...", но сейчас более важным, на мой взгляд, является изложение сути метода. И ещё, по ходу повествования могут встретиться мои комментарии и мнения. Так вот, если вы их заметите, то знайте, что все это частная точка зрения, охраняемая законом о свободе слова, при этом не лишенная субъективности, и если у вас есть возражения, то пишите.
Итак, генетические алгоритмы в основном применяются для решения задач оптимизации, т.е. задач, в которых есть некоторая функция нескольких переменных F(x1, x2, ... ,xn) и необходимо найти либо её максимум, либо её минимум. Функция F называется целевой функцией, а переменные - параметрами функции. Генетические алгоритмы "пришиваются" к данной задаче следующим образом.
Параметры задачи являются генетическим материалом - генами. Совокупность генов составляет хромосому. Каждая особь обладает своей хромосомой, а, следовательно, своим набором параметров. Подставив параметры в целевую функцию, можно получить какое-то значение. То, насколько это значение удовлетворяет поставленным условиям, определяет характеристику особи, которая называется приспособленностью (fitness). Функция, определяющая приспособленность должна удовлетворять следующему условию: чем "лучше" особь, тем выше приспособленность. Генетические алгоритмы работают с популяцией как правило фиксированного размера, состоящей из особей, заданных при помощи способа, описанного выше. Вот здесь начинается самое интересное. Особи "скрещиваются" между собой с помощью генетических операторов(о том как происходит этот захватывающий процесс - отдельно), естественно, получается потомство, причем часть потомков заменяют представителей более старого поколения в соответствии со стратегией формирования нового поколения. Кстати, выбор особей для скрещивания проводится согласно селективной стратегии (selection strategy). Так вот, заново сформированная популяция снова оценивается, затем выбираются наиболее достойные для скрещивания особи, которые "встречаются, влюбляются, женятся", получаются дети, занимают место престарелых индивидуумов и т.д.
Вся эта карусель продолжается до тех пор пока не найдется особь, гены которой представляют оптимальный набор параметров, при которых значение целевой функции близко к максимуму или минимуму, либо равно ему. Останов работы ГА может произойти также в случае, если популяция вырождается, т.е. если практически нет разнообразия в генах особей популяции, либо если просто вышел лимит времени. Вырождение популяции называют преждевременной сходимостью (premature convergence).
Может создаться впечатление, что ГА яыляются просто извращенным до невозможного вариантом случайного поиска. Но приспособленность была введена совсем не зря. Дело в том, что она непосредственно влияет на шанс особи принять участие в брачных играх и последующих народных забавах. Выбирая каждый раз для скрещивания наиболее приспособленных особей, можно с определенной степенью уверенности утверждать, что потомки будут либо не намного хуже, чем родители, либо лучше их. Приблизительно эту величину уверенности можно оценить с помощью теоремы шаблонов (теоремы шим). Если вас не интересуют теоретические аспекты ГА, то пожалуйте сюда:
И напоследок о том, где применяются ГА. Всего применений очень много, поэтому приведенный список не является исчерпывающим. Итак, области применения ГА:
- Экстремальные задачи (нахождение точек минимума и минимума);
- Задачи о кратчайшем пути;
- Задачи компоновки;
- Составление расписаний;
- Аппроксимация функций;
- Отбор(фильтрация) входных данных;
- Настройка искусственной нейронной сети;
Моделирование искусственной жизни (Artificial life systems) - подробнее об этом здесь;
- Биоинформатика (свертывание белков и РНК);
- Игровые стратегии;
- Нелинейная фильтрация;
- Развивающиеся агенты/машины (Evolvable agents/machines);
Некоторые разделы могут содержать подпункты. Так, например, экстремальные задачи включают в мебя целый класс задач линейного и нелинейного программирования. Как применить ГА ко многим из перечисленных пунктов я и сам не знаю. Данный список наполовину взят из "Hitch-Hiker's Guide to Evolutionary Computation" - это касается задач, начиная с "Моделирования искусственной жизни". Сам я применял ГА для аппроксимации функций, решения задач линейного и нелинейного программирования и просто для решения экстремальных задач, немного (если точнее, совсем немного) поэкспериментировал с искусственной жизнью и с моделированием распространения фотонов. В настоящее время я использую ГА для одновременной настройки весов и структуры искусственной нейронной сети. Из вопросов, которые лично меня интересуют сейчас особенно сильно, хотелось бы выделить следующие:
Я буду рад получить отзывы о содержимом страницы и надеюсь, что изложил материал достаточно интересно, чтобы ГА заинтересовали вас также, как когда-то захватили меня. И помните, "спайс должен течь", а в генетическом алгоритме преждевременная сходимость - ваш злейший враг. Избавитесь от нее - решите много проблем!
Мой e-mail: qai@mail.ru
Источники:
- Darrel Whitley "A Genetic Algorithm Tutorial", 1993.
Heitkoetter, Joerg and Beasley, David, eds. (2001) "The Hitch-Hiker's Guide to Evolutionary Computation: A list of Frequently Asked Questions (FAQ)", USENET: comp.ai.genetic. Available via anonymous FTP from rtfm.mit.edu/pub/usenet/news.answers/ai-faq/genetic/ About 110 pages.
