Генетические алгоритмы используют прямую аналогию с таким механизмом. Они работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. Например, мерой приспособленности могло бы быть отношение силы/веса для данного проекта моста. (В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы.) Наиболее приспособленные особи получают возможность "воспроизводит" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.
Так и воспроизводится вся новая популяция допустимых решений, выбирая лучших представителей предыдущего поколения, скрещивая их и получая множество новых особей. Это новое поколение содержит более высокое соотношение характеристик, которыми обладают хорошие члены предыдущего поколения. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге, популяция будет сходиться к оптимальному решению задачи.
Имеются много способов реализации идеи биологической эволюции в рамках генетического алгоритма. Традиционным считается генетический алгоритм, представленный на схеме 1:
НАЧАЛО /генетический алгоритм/
Создать начальную популяцию
Оценить приспособленность каждой особи
останов := FALSE
ПОКА НЕ останов ВЫПОЛНЯТЬ
НАЧАЛО /создать популяцию нового поколения/
ПОВТОРИТЬ (размер_популяции/2) РАЗ
НАЧАЛО /* цикл воспроизводства */
Выбрать две особи с высокой приспособленностью из предыдущего поколения для скрещивания.
Скрестить выбранные особи и получить двухпотомков
Оценить приспособленности потомков
Поместить потомков в новое поколение
КОНЕЦ
ЕСЛИ популяция сошлась ТО останов := TRUE
Схема 1. Реализация генетического алгоритма
В последние годы, реализовано много генетических алгоритмов и в большинстве случаев они мало похожи на этот генетический алгоритм. По этой причине в настоящее время под термином "генетические алгоритмы" скрывается не одна модель, а достаточно широкий класс алгоритмов, подчас мало похожих друг от друга. Исследователи экспериментировали с различными типами представлений, операторов кроссовера и мутации, специальных операторов, и различных подходов к воспроизводству и отбору.
Хотя модель эволюционного развития, применяемая в генетическом алгоритме, сильно упрощена по сравнению со своим природным аналогом, тем не менее генетический алгоритм является достаточно мощным средством и может с успехом применяться для широкого класса прикладных задач, включая те, которые трудно, а иногда и вовсе невозможно, решить другими методам. Однако, генетические алгоритмы, как и другие методы эволюционных вычислений, не гарантирует обнаружения глобального решения за полиномиальное время. Генетические алгоритмы не гарантируют и того, что глобальное решение будет найдено, но они хороши для поиска "достаточно хорошего" решения задачи "достаточно быстро". Там, где задача может быть решена специальными методам, почти всегда такие методы будут эффективнее генетических алгоритмов и в быстродействии и в точность найденных решений. Главным же преимуществом генетических алгоритмов является то, что они могут применяться даже на сложных задачах, там, где не существует никаких специальных методов. Даже там, где хорошо работаю существующие методики, можно достигнуть улучшения сочетанием их с генетическими алгоритмами.
Генетические алгоритмы в различных формах применились ко многим научным и техническим проблемам. Генетические алгоритмы использовались при создании других вычислительных структур, например, автоматов или сетей сортировки. В машинном обучении они использовались при проектировании нейронных сетей или управлении роботами. Они также применялись при моделировании развития в различных предметных областях, включая биологические (экология, иммунология и популяционная генетика), социальный (такие как экономика и политические системы) и когнитивные системы.
Тем не менее, возможно наиболее популярное приложение генетических алгоритмов - оптимизация многопараметрических функций. Многие реальные задачи могут быть сформулированы как поиск оптимального значения, где значение - сложная функция, зависящая от некоторых входных параметров. В некоторых случаях, представляет интерес найти те значения параметров, при которых достигается наилучшее точное значение функции. В других случаях, точный оптимум не требуется - решением может считаться любое значение, которое лучше некоторой заданное величины. В этом случае, генетические алгоритмы - часто наиболее приемлемый метод для поиска "хороших" значений. Сила генетического алгоритма заключена в его способности манипулировать одновременно многими параметрами, эта особенность генетического алгоритма использовалось в сотнях прикладных программ, включая проектирование самолетов, настройку параметров алгоритмов и поиску устойчивых состояний систем нелинейных дифференциальных уравнений.
Однако нередки случаи, когда генетический алгоритм работает не так эффективно, как ожидалось. Предположим, есть реальная задача, сопряженная с поиском оптимального решения, как узнать, является ли генетический алгоритм хорошим методом для ее решения? До настоящего времени не существует строгого ответа, однако многие исследователи разделяют предположения, что если пространство поиска, которое предстоит исследовать, - большое, и предполагается, что оно не совершенно гладкое и унимодальное (т.е. содержит один гладкий экстремум) или не очень понятно, или если функция приспособленности с шумами, или если задача не требует строго нахождения глобального оптимума - т.е. если достаточно быстро просто найти приемлемое "хорошее" решения (что довольно часто имеет место в реальных задачах) - генетический алгоритм будет иметь хорошие шансы стать эффективной процедурой поиска, конкурируя и превосходя другие методы, которые не используют знания о пространстве поиска.
Если же пространство поиска небольшое, то решение может быть найдено методом полного перебора, и можно быть уверенным, что наилучшее возможное решение найдено, тогда как генетический алгоритм мог с большей вероятностью сойтись к локальному оптимуму, а не к глобально лучшему решению. Если пространство гладкое и унимодальное любой градиентный алгоритм, такой как, метод скорейшего спуска будет более эффективен, чем генетический алгоритм. Если о пространстве поиска есть некоторая дополнительная информация (как, например, пространство для хорошо известной задачи о коммивояжере), методы поиска, использующие эвристики, определяемые пространством, часто превосходят любой универсальный метод, каким является генетический алгоритм. При достаточно сложном рельефе функции приспособленности методы поиска с единственным решением в каждый момент времени, такой как простой метод спуска, могли "затыкаться" в локальном решении, однако считается, что генетический алгоритм, так как они работают с целой "популяцией" решений, имеют меньше шансов сойтись к локальному оптимуму и робастно функционируют на многоэкстремальном ландшафте.
Конечно, такие предположения не предсказывают строго, когда генетический алгоритм будет эффективной процедурой поиска, конкурирующей с другими процедурами. Эффективность генетического алгоритма сильно зависит от таких деталей, как метод кодировки решений, операторы, настройки параметров, частный критерий успеха. Теоретическая работа, отраженная в литературе, посвященной генетическим алгоритмам, не дает оснований говорить о выработки каких-либо строгих механизмов для четких предсказаний.
Цель в оптимизации с помощью генетического алгоритма состоит в том, чтобы найти лучшее возможное решение или решения задачи по одному или нескольким критериям. Чтобы реализовать генетический алгоритм нужно сначала выбрать подходящую структуру для представления этих решений. В постановке задачи поиска, экземпляр этой структуры данных представляет точку в пространстве поиска всех возможных решений.
Структура данных генетического алгоритма состоит из одной или большее количество хромосом (обычно из одной). Как правило, хромосома - это битовая строка, так что термин строка часто заменяет понятие "хромосома". В принципе, генетические алгоритмы не ограничены бинарным представлением. Известны другие реализации, построенные исключительно на векторах вещественных чисел . Несмотря на то, что для многих реальных задач, видимо, больше подходят строки переменной длины, в настоящее время структуры фиксированной длины наиболее распространены и изучены. Пока и мы ограничимся только структурам, которые являются одиночными строками по l бит.
Каждая хромосома (строка) представляет собой конкатенацию ряда подкомпонентов называемых генами. Гены располагаются в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген - бит, локус - его позиция в строке, и аллель - его значение (0 или 1). Биологический термин "генотип" относится к полной генетической модели особи и соответствует структуре в генетическом алгоритме. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров. Чрезвычайно простой, но иллюстративный пример - задача максимизации следующей функции двух переменных: (1)
f (x1, x2) = exp(x1x2), где 0 < x1< 1 и 0 < x2 < 1. (1)
Обычно, методика кодирования реальных переменных x1 и x2 состоит в их преобразовании в двоичные целочисленные строки достаточной длины - достаточной для того, чтобы обеспечить желаемую точность. Предположим, что 10-разрядное кодирование достаточно и для x1, и x2. Установить соответствие между генотипом и фенотипом закодированных особей можно, разделив соответствующее двоичное целое число - на 210-1. Например, 0000000000 соответствует 0/1023 или 0, тогда как 1111111111 соответствует 1023/1023 или 1. Оптимизируемая структура данных - 20-битная строка, представляющая конкатенацию кодировок x1 и x2. Переменная x1 размещается в крайних левых 10-разрядах, тогда как x2 размещается в правой части генотипа особи (20-битовой строке). Генотип - точка в 20-мерном хеммининговом пространстве, исследуемом генетическим алгоритмом. Фенотип - точка в двумерном пространстве параметров.
Страницы: 1, 2, 3, 4, 5
