Лекция. Генетические алгоритмы
Генетические алгоритмы – перспективное и динамично развивающееся направление интеллектуальной обработки данных, связанное с решением задач поиска и оптимизации.
Область применения генетических алгоритмов достаточно обширна. Финансовые компании используют их для прогнозирования развития финансовых рынков при управлении пакетами ценных бумаг. Генетические алгоритмы применяются для решения комбинаторных задач, для оценки значений непрерывных параметров моделей большой размерности, для оптимизации моделей, включающих одновременно непрерывные и дискретные параметры. Другая область применения – использование в системах извлечения новых знаний из больших баз данных, обучение нейронных сетей, оценка параметров в задачах многомерного статистического анализа.
Сейчас при решении очень сложных задач основной целью является поиск уже не оптимального, а более «хорошего» решения по сравнению с решением, полученным ранее или заданным в качестве начального. Именно для этих целей и применяются генетические алгоритмы. Они не гарантируют обнаружения глобального экстремума целевой функции (или оптимального решения) за определенное время. Основное их преимущество в том, что они позволяют найти более “хорошие” решения очень трудных задач за меньшее время, чем другие методы. Генетические алгоритмы оказались достаточно эффективными для решения ряда реальных задач инженерного проектирования, планирования, маршрутизации и размещения, управления портфелями ценных бумаг, прогнозирования, а также во многих других областях.
Отрицательной чертой генетических алгоритмов является то, что они представляют собой скорее подход к решению задач оптимизации, чем алгоритм. И вследствие этого требуют адаптации к каждому конкретному классу задач путем выбора определенных характеристик и параметров.
Основные определения и свойства
Генетические алгоритмы имеют целью нахождение не оптимального, а лучшего решения по сравнению с имеющимся решением задачи. Это связано с тем, что для сложной задачи часто требуется найти хоть какое-нибудь удовлетворительное решение, а проблема достижения оптимума отходит на второй план. При этом другие методы, ориентированные на поиск именно оптимального решения, вследствие чрезвычайной сложности задачи становятся вообще неприменимыми.
Основные отличия генетических алгоритмов от традиционных методов:
1. Генетические алгоритмы работают с кодами, в которых представлен набор параметров, напрямую зависящих от аргументов целевой функции. Причем интерпретация этих кодов происходит только перед началом работы алгоритма и после завершения его работы для получения результата. Впроцессе работы манипуляции с кодами происходят независимо от их интерпретации, код рассматривается просто как битовая строка.
2. Для поиска генетический алгоритм использует несколько точек поискового пространства одновременно, а не переходит от точки к точке, как это делается в традиционных методах. Это позволяет преодолеть один из их недостатков – опасность попадания в локальный экстремум целевой функции, если она не является унимодальной, т. е. имеет несколько таких экстремумов.
3. Генетические алгоритмы в процессе работы не используют никакой дополнительной информации, что повышает скорость работы. Единственной используемой информацией может быть область допустимых значений параметров и целевой функции в произвольной точке.
4. Генетический алгоритм использует как вероятностные правила для порождения новых точек, так и детерминированные правила для перехода от одних точек к другим. Одновременное использование элементов случайности и детерминированности дает значительно больший эффект, чем раздельное.
Прежде чем рассматривать непосредственно работу генетического алгоритма, введем ряд терминов, которые широко используются в данной области.
Выше было показано, что генетический алгоритм работает с кодами безотносительно их смысловой интерпретации. Поэтому сам код и его структура описываются понятием генотип, а его интерпретация, с точки зрения решаемой задачи, – понятием фенотип. Каждый код представляет, по сути, точку пространства поиска. С целью максимально приблизиться к биологическим терминам, экземпляр кода называют хромосомой, особью или индивидуумом.
На каждом шаге работы генетический алгоритм использует несколько точек поиска одновременно. Совокупность этих точек является набором особей, который называется популяцией. Количество особей в популяции называют размером популяции. Размер популяции является фиксированным и представляет одну из характеристик генетического алгоритма. На каждом шаге работы генетический алгоритм обновляет популяцию путем создания новых особей и уничтожения ненужных. Чтобы отличать популяции на каждом из шагов и сами эти шаги, их называют поколениями и обычно идентифицируют по номеру. Например, популяция, полученная из исходной популяции после первого шага работы алгоритма, является первым поколением, после следующего шага – вторым и т. д.
В процессе работы алгоритма генерация новых особей происходит на основе моделирования процесса размножения. При этом, естественно, порождающие особи называются родителями, а порожденные – потомками. Родительская пара порождает пару потомков. Непосредственная генерация новых кодовых строк из двух выбранных происходит за счет работы оператора скрещивания. При порождении новой популяции оператор скрещивания может применяться не ко всем парам родителей. Часть этих пар может переходить в популяцию следующего поколения непосредственно. Насколько часто будет возникать такая ситуация, зависит от значения вероятности применения оператора скрещивания, которая является одним из параметров генетического алгоритма.
Моделирование процесса мутации новых особей осуществляется за счет работы оператора мутации. Основным параметром оператора мутации также является вероятность мутации.
Поскольку размер популяции фиксирован, то порождение потомков должно сопровождаться уничтожением других особей. Выбор пар родителей из популяции для порождения потомков производит оператор отбора, а выбор особей для уничтожения – оператор редукции. Основным параметром их работы является качество особи, которое определяется значением целевой функции в точке пространства поиска, описываемой этой особью.
Таким образом, можно перечислить основные понятия и термины, используемые в области генетических алгоритмов:
• генотип и фенотип;
• особь и качество особи;
• популяция и размер популяции;
• поколение;
• родители и потомки.
К характеристикам генетического алгоритма относятся:
• размер популяции;
• оператор скрещивания и вероятность его использования;
• оператор мутации и вероятность мутации;
• оператор отбора;
• оператор редукции;
• критерий останова.
Операторы отбора, скрещивания, мутации и редукции называют еще генетическими операторами.
Критерием останова работы генетического алгоритма может быть одно из трех событий:
1. Сформировано заданное пользователем число поколений.
2. Популяция достигла заданного пользователем качества (например, значение качества всех особей превысило заданный порог).
3. Достигнут некоторый уровень сходимости, т. е. особи в популяции стали настолько подобными, что дальнейшее их улучшение происходит чрезвычайно медленно.
Характеристики генетического алгоритма выбираются таким образом, чтобы обеспечить малое время работы, с одной стороны, и поиск как можно лучшего решения, с другой.
Дата добавления: 2016-04-22; просмотров: 2015;