Генетические алгоритмы: суть, описание, примеры, применение.

Генетические алгоритмы: суть, описание, примеры, применение

Идея генетических алгоритмов (ГА) появилась достаточно давно (1950-1975 гг.), но по-настоящему объектом изучения они стали только в последние десятилетия. Первооткрывателем в этой области признано считать Д. Холланда, который позаимствовал многое из генетики и адаптировал под вычислительные машины. ГА широко используются в системах искусственного интеллекта, нейронных сетях и задачах оптимизации.

Эволюционный поиск

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

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

Зачем нужны генетические алгоритмы

ГА преследуют следующие цели:

• объяснить адаптационные механизмы как в естественной среде, так и в интеллектуально-исследовательской (искусственной) системе;
• моделирование эволюционных функций и их применение для эффективного поиска решений различных задач, главным образом оптимизационных.

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

Особенности ГА

Перечислим главные отличия ГА от большинства других методов поиска оптимального решения.

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

Критерии работы

Генетические алгоритмы производят расчеты исходя из двух условий:

1. Выполнение заданного числа итераций.
2. Качество найденного решения соответствует требованиям.

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

Базовая терминология

Ввиду того, что ГА основаны на генетике, то и большая часть терминологии соответствует ей. Любой генетический алгоритм работает исходя из начальной информации. Множество начальных значений есть популяция П t = <п₁, п₂, . п_n>, где п_i = <г₁, . г_v>. Разберем подробнее:

• t – это номер итерации. t₁, . t_k – означает итерации алгоритма с номера 1 по k, и на каждой итерации создается новая популяция решений.
• n – размер популяции П t .
• п ₁, . п_i – хромосома, особь, или организм. Хромосома или цепочка – это закодированная последовательность генов, каждый из которых имеет порядковый номер. При этом следует иметь в виду, что хромосома может быть частным случаем особи (организма).
• г_v – это гены, являющиеся частью закодированного решения.
• Локус – это порядковый номер гена в хромосоме. Аллель – значение гена, которое может быть как числовым, так и функциональным.

Что значит “закодированный” в контексте ГА? Обычно любое значение кодируется на основе какого-либо алфавита. Простейшим примером является перевод чисел из десятеричной системы счисления в двоичное представление. Таким образом алфавит представляется как множество <0, 1>, а число 157₁₀ будет кодироваться хромосомой 10011101₂ , состоящей из восьми генов.

Родители и потомки

Родителями называются элементы, выбираемые в соответствии с заданным условием. Например, часто таким условием является случайность. Выбранные элементы за счет операций скрещивания и мутации порождают новые, которые называются потомками. Таким образом, родители в течение реализации одной итерации генетического алгоритма создают новое поколение.

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

Функция приспособленности

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

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

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

Отклонения в ту или иную сторону отдельных элементов в общем случае находятся в соответствии с нормальным законом распределения величин. При этом ГА обеспечивает наследственность признаков, наиболее приспособленные из которых закрепляются, обеспечивая тем самым лучшую популяцию.

Базовый генетический алгоритм

Разложим по шагам наиболее простой (классический) ГА.

1. Инициализация начальных значений, то есть определение первичной популяции, того множества особей, с которыми будет происходить эволюция.
2. Установление первичной приспособленности каждой особи в популяции.
3. Проверка условий прекращения итераций алгоритма.
4. Использование функции селекции.
5. Применение генетических операторов.
6. Создание новой популяции.
7. Шаги 2-6 повторяются в цикле до выполнения необходимого условия, после чего происходит выбор наиболее приспособленной особи.

Пройдемся вкратце по мало очевидным частям алгоритма. Условий прекращения работы может быть два:

1. Количество итераций.
2. Качество решения.

Генетическими операторами является оператор мутаций и оператор скрещивания. Мутация изменяет случайные гены с определенной вероятностью. Как правило, вероятность мутации имеет низкое числовое значение. Поговорим подробнее о процедуре генетического алгоритма “скрещивание”. Он происходит по следующему принципу:

1. Для каждой пары родителей, содержащих L генов, случайным образом выбирается точка скрещивания Тск_i.
2. Первый потомок составляется путем присоединения к [1; Тск_i] генам первого родителя [Тск_i+1; L] генов второго родителя.
3. Второй потомок составляется обратным путем. Теперь к генам второго родителя [1; Тск_i] добавляется гены первого родителя на позициях [Тск_i+1; L].

Тривиальный пример

Решим задачу генетическим алгоритмом на примере поиска особи с максимальным числом единиц. Пусть особь состоит из 10 генов. Зададим первичную популяцию в количестве восьми особей. Очевидно, наилучшей особью должна быть 1111111111. Составим для решения ГА.

• Инициализация. Выберем 8 случайных особей:

• Оценка приспособленности. Очевидно, в нашем генетическом алгоритме функция пригодности F будет подсчитывать количество единиц в каждой особи. Таким образом, имеем:

Из таблицы видно, что особи 3 и 7 имеют наибольшее число единиц, а значит являются наиболее подходящими членами популяции для решения задачи. Так как на данный момент решения требуемого качества нет, алгоритм продолжает работу. Необходимо провести селекцию особей. Для простоты объяснения пусть селекция происходит случайным образом, и мы получаем выборку особей <п₇, п₃, п₁, п₇, п₃, п₇, п₄, п₂> – это родители для новой популяции.

• Использование генетических операторов. Снова для простоты положим, что вероятность мутаций равна 0. Иными словами все 8 особей передают свои гены такими, какие есть. Для проведения скрещивания, составим пары особей случайным образом: (п₂, п₇), (п₁, п₇), (п₃, п₄) и (п₃, п₇). Так же случайным способом выбираются точки скрещивания для каждой пары:

• Составление новой популяции, состоящей из потомков:

• Оцениваем приспособленность каждой особи новой популяции:

Дальнейшие действия очевидны. Самое интересное в ГА открывается в случае, если оценить среднее количество единиц в каждой популяции. В первой популяции в среднем на каждую особь приходилось 5,375 единиц, в популяции потомков – 6,25 единиц на особь. И такая особенность будет наблюдаться даже в случае, если в ходе мутаций и скрещивания особь с наибольшим числом единиц в первой популяции потеряется.

План реализации

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

1. Определение представления (алфавита).
2. Определение операторов случайных изменений.
3. Определение выживания особей.
4. Генерация первичной популяции.

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

Не менее сложным является определение операторов изменения и создания потомков. Существует множество операторов, которые способны выполнять требуемые действия. Например, из биологии известно, что каждый вид может размножаться двумя способами: половым (скрещиванием) и бесполым (мутациями). В первом случае родители обмениваются генетическим материалом, во втором – происходят мутации, определенные внутренними механизмами организма и внешним воздействием. Помимо этого, можно применять несуществующие в живой природе модели размножения. Например, использовать гены трех и более родителей. Аналогично скрещиванию в генетическом алгоритме мутации может быть заложен разнообразный механизм.

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

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

Эффективность

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

1. Создание полной популяции, что будет включать всевозможные варианты особей в некоторой заданной области.
2. Случайное создание особей на основе всех допустимых значений.
3. Точечное случайное создание особей, когда среди допустимых значений выбирается диапазон для генерации.
4. Комбинирование первых трех способов создания популяции.

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

ПРИМЕРЫ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ;

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

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

Рассмотрим пример использования генетического алгоритма. Для оптимизации экспертных правил в сфере страхования.

Допустим, что компания, занимающаяся страхованием автомобилей, использует базу данных, которая помимо прочих включает следующие факторы: максимальную скорость автомобиля (км/час), возраст автомобиля (лет), возраст водителя (лет) и риск, определенный экспертно по некоторой шкале на основе анализа обращений клиентов о выплате компенсации по страховым случаям. Правила, задающие оценку страхового риска, сконструированы в виде:

ЕСЛИ максимальная скорость автомобиля лежит в диапазоне [A_i] И возрастной диапазон автомобиля [B_i] И возраст водителя находится в диапазоне [С_i], ТО страховой риск имеет значение [D_i].

Для конкретной выборки из БД это правило может иметь следующий вид:

ЕСЛИ максимальная скорость [91 − 100 км/час] И возраст автомобиля [11 − 15 лет] И возраст водителя [31 − 40 лет], ТО риск [3]. Здесь уровень риска отображается на интервал [1, 5], при этом высокие значения соответствуют большим страховым рискам.

Подобные правила, основанные на фактических значениях переменных, случайным образом выбранных из БД, составляют исходную популяцию. Для каждой из переменных, входящих в популяцию, предварительно задается диапазон состояний. Например, переменная «возраст автомобиля», может иметь пять возможных состояний: 1 − 5, 6 − 10, 11 − 15, 16 − 20, 21 − 25 лет. Далее сформированная популяция обрабатывается генетическими операторами с учетом специфики рассматриваемой задачи. Целевая функция должна показывать, насколько точно сгенерированные правила описывают реальные страховые случаи, хранящиеся в БД. Например, если какое-то правило описывает 4 случая из 5, то значение целевой функции будет 4/5, или 80%.

Новые члены популяции образуются в результате скрещивания и мутации начального набора правил. В данном случае при скрещивании двух правил происходит обмен парами «атрибут − значение» на участке строки после точки кроссинговера. В результате образуются два новых правила, жизнеспособность которых оценивается по тому, насколько удачно они описывают страховые случаи, которые имели место в прошлом. Мутация правил обеспечивает необходимое разнообразие признаков и заключается в изменении значений атрибутов с заданной вероятностью. Таким образом, первоначально сформированный набор правил преобразуется случайно направленным способом в другой набор, который лучше остальных описывает накопленную статистику страховых случаев. Результирующая система правил в дальнейшем используется для прогнозирования страховых рисков.

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

Классифицирующие системы. На основе генетических алгоритмов Дж.Холланд предложил классифицирующие системы, которые можно использовать для целей управления. Классифицирующая система состоит из трех вложенных друг в друга подсистем (рис.9.3): классификатора, системы обучения и генетического алгоритма. В классификатор поступают внешние сообщения и положительные оценки (поощрения) его действий. Классификатор содержит правила вида ЕСЛИ , ТО , с помощью которых формируются выходные сообщения. Обучающая система выполняет оценку используемых правил. Генетический алгоритм предназначен для случайно направленной модификации правил. Схема обработки правил представлена на рис.9.4.

Каждому правилу приписывается численная оценка силы правила. Сообщения и условные части правил (антецеденты) формулируются в одних и тех же терминах. Список сообщений содержит все текущие сообщения − поступающие из внешней среды и те, что формируются внутри системы.

В процессе работы КС все сообщения из списка сравниваются с условиями всех правил. Классификатор выполняет следующие действия.

Рис. 9.3. Схема классифицирующей системы

Шаг 1. В список сообщений (рабочую память) добавляются, все сообщения, поступившие извне.

Шаг 2. Проводится сравнение всех сообщений из списка с антецедентами всех правил. Все правила, антецеденты которых совпадают с присутствующими в рабочей памяти сообщениями, записываются в список правил М.

Шаг 3. Выполняются правила из списка М, при этом сообщения каждого правила посылаются в список новых сообщений.

Шаг 4. Обновление списка сообщений.

Шаг 5. Сообщения из списка посылаются в выходной интерфейс. Вероятность выдачи сообщения зависит от силы правила: не каждое сообщение выдается на управляемый объект, часть их может быть связана с изменением внутренней структуры системы (правил).

Шаг 6. Возврат к шагу 1.

Рис. 9.4. Схема обработки правил в классифицирующей системе

В процессе обучения каждому правилу присваивается численное значение силы, а алгоритм обучения регулирует это значение с учетом полезности правила для системы. На шаге 3 описанного алгоритма для каждого отобранного правила С вычисляется цена по формуле В(С, t)=bR(C)s(С, t), где s(C, t) − сила правила С в момент t; R(С) − специфичность условия в правиле, равная числу символов, отличающихся от символа * в условии, деленному на длину условия; b − коэффициент, который обычно принимают равным 1/8 или 1/6.

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

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

Для правил С, пославших сообщения, которые на следующем шаге работы оказались полезными (совпали с условиями правила-победителя, имеющего высокую цену), оценка силы возрастает на долю В:

где a = 1/К, К − число правил С’, т.е. каждый поставщик получает равную долю В.

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

Классификатор и обучающая система не порождают новых правил. Эту функцию выполняет генетический алгоритм, который работает с учетом силы правил, определенной в системе обучения. Работа генетического алгоритма рассмотрена в предшествующем примере.

Комбинированные методы и интеллектуальные системы. В настоящее время активно развиваются методы, основанные на объединении технологий инженерии знаний и генетических алгоритмов. В области ГА разрабатываются операторы, ориентированные на обработку знаний.

Генетические алгоритмы используют в теории нечетких систем для настройки параметров функций принадлежности. Интеграция четких и нечетких нейронных сетей и генетических алгоритмов обеспечивает реализацию оптимизационной задачи. Средства fuzzy-neuro-genetic используются в интеллектуальных системах и содержат следующие процедуры:

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

• извлечение знаний, представленных в виде продукций ЕСЛИ-ТО, из нечеткой обучающей выборки с помощью нейронной сети;

• оптимизацию структуры продукционных правил с помощью генетического алгоритма.

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

• HLN − количество скрытых слоев;

• N_k − число нейронов в каждом слое;

• w_ij − весовые коэффициенты межнейронных связей;

• F_j(X, W) − передаточные функции нейронов скрытых слоев, а также нейронов выходного слоя.

Сформулируем общую задачу оптимизации сети: при заданных количествах входных и выходных нейронов на основе заданного множества обучающих примеров определить оптимальное значение HLN, N_k, k = I. HLN, значения всех весовых коэффициентов межнейронных связей w_ij, где j − индекс нейрона; i − индекс межнейронной связи (синапса), F_j(X, W) − передаточные функции всех нейронов, за исключением нейронов входного слоя. Критерием оптимизации является максимальное отклонение выходного вектора сети Y’ от эталонного значения выхода, полученное в результате обработки всех примеров, т.е. необходимо найти

(9.4)

где δ = Y’ − Y; Q − множество обучающих примеров, содержащих значения X, Y; Y’ = F(HLN, N_k, X, W); F(HLN, N_k, X,W) − передаточная функция ИНС, которая строится на основе частных функций отдельных нейронов F_j(X, W).

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

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

Генетические алгоритмы или как учебник по биологии может помочь в функциональной оптимизации

Одной из задач интеллектуальных систем является поиск оптимального решения: когда на систему влияет множество внешних и внутренних факторов, интеллектуальное устройство должно учесть их все и выбрать оптимальное поведение с точки зрения своей выгоды. Допустим, если Вы — хозяин склада, Вам необходимо учитывать много факторов (стоимость единиц товаров, спрос, издержки на хранение различных товаров на складе и т.д.) для минимизации издержек и получение наибольшей прибыли.

Другой пример: вы едете по скользкой дороге, и вдруг ваш автомобиль начинает заносить, справа в нескольких метрах от вас столб, а по встречной полосе едет грузовик. Внимание вопрос: как выйти из ситуации с наименьшими потерями, а лучше вообще без них. Факторов, которые нужно учитывать много: ваша скорость и скорость встречного автомобиля, расстояние до столба, «крутость» заноса и т.д. Что нужно делать? Давать газу, пытаясь выйти из заноса, или тормозить, или, может, попытаться аккуратно съехать в кювет, так чтобы не попасть в столб. Вариантов много, и для того чтобы определить оптимальный — нужно попробовать их все. Будь это компьютерной игрой – вы могли бы сохраниться и переигрывать до тех пор, пака результат вас не удовлетворит. Это и есть поиск оптимального решения.

В системах искусственного интеллекта для решения подобных задач применяются генетические алгоритмы.

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

Скажем проще: по сути, генетический алгоритм — это метод перебора решений для тех задач, в которых невозможно найти решение с помощью математических формул. Однако простой перебор решений в сложной многомерной задаче – это бесконечно долго. Поэтому генетический алгоритм перебирает не все решения, а только лучшие. Алгоритм берёт группу решений и ищет среди них наиболее подходящие. Затем немного изменяет их – получает новые решения, среди которых снова отбирает лучшие, а худшие отбрасывает. Таким образом, на каждом шаге работы алгоритм отбирает наиболее подходящие решения (проводит селекцию), считая, что они на следующем шаге дадут ещё более лучшие решения (эволюционируют).

Причём тут биология?

Как вы уже поняли, в теории генетических алгоритмов проводится аналогия между задачей и биологическим процессом. Отсюда и терминология…

Особь – одно решение задачи.

Популяция — набор решений задачи. В начале алгоритма случайным образом генерируется набор решений (начальная популяция). Эти решения будут становиться лучше (эволюционировать) в процессе работы алгоритма до тех пор, пока не удовлетворят условиям задачи.

И сразу самый простой классический пример. Допустим, роботу необходимо объехать шесть контрольных точек за наименьшее время. Расстояние от каждой точки до каждой задано в виде матрицы расстояний.

Это вариация задачи о коммивояжёре (путешественнике) – относится к классу NP-полных, проще говоря, не может быть решена с помощью математических формул.

Решение задачи – это последовательность прохождения контрольных точек. Возьмём несколько возможных решений (особей)– это и есть начальная популяция.

Определения качества решений

Функция пригодности – функция определяющая качество особей популяции. В нашем примере это будет сумма расстояний от точки до точки в выбранном маршруте.

где Р(1) … Р(6) – расстояние между точками в соответствующем переходе из матрицы расстояний

Нам необходимо найти минимальное расстояние, поэтому, чем меньше значение ФП для особи, тем лучше.

Давайте посчитаем функции пригодности. Для первой особи:

Для остальных особей таким же образом получаем:

Тут всё очевидно: особь №3 – лучшая, а №4 – самая плохая.

Генетические операторы

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

Генетические операторы – определённые правила, по которым изменяются особи в следующей популяции. Среди них выделяют операторы скрещивания и мутации. Подробнее об этих операторах речь пойдёт в одной из следующих статей. Сейчас главное запомнить, что после их применения мы получим еще несколько особей – потомков. Допустим таких:

Для потомков тоже посчитаны функции пригодности.

Оператор селекции

Настало время искусственного отбора. На этом шаге алгоритм выберет лучших особей и отбросит худших (наименее приспособленных), подобно тому, как делает селекционер, создавая новый вид растений.

Алгоритмы селекции тоже могут быть различны, не будем пока заострять на этом внимание. Просто возьмем и отбросим из первой популяции (родители + потомки) четыре худших особи. Останутся родитель 1 и 3, и потомки 1 и 2. Эти особи сформируют новую популяцию. Далее алгоритм будет повторяться. Для наглядности посмотрим на блок-схему классического генетического алгоритма:

Критерий останова генетического алгоритма

Вспомним, что мы искали кратчайший путь прохождения робота через все контрольные точки. Абсолютно правильный ответ будет получен, только если перебрать все варианты, а их очень много даже для шести точек (а если точек будет больше?). Поэтому генетический алгоритм ищет не правильное решение, а оптимальное, исходя из условий, которые задаёт пользователь.

Критерий останова – условие, по которому генетический алгоритм останавливает свою работу.

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

В нашем случае мы можем указать, например, один из следующих критериев останова:

• Суммарный путь меньше 50
• Время работы алгоритма 1 час
• Число циклов алгоритма 10
• В течение 3 поколений не появляются особи лучше тех, которые были
• и т.д.

Ещё немного о функции пригодности

На практике далеко не всегда получается составить функцию пригодности так же просто, как в нашем примере. Например, вы — хозяин завода. Ваша цель увеличение прибыли. Для достижения этой цели вы можете варьировать много различных параметров: количество закупаемого сырья, план выпуска, зарплата рабочих, количество денег, выделяемых на модернизацию производства, повышение квалификации персонала, на рекламу и т.д. Набор конкретных значений этих параметров и будет стратегией, скажем, на месяц. Однако нет точной математической формулы, связывающей эти параметры между собой. Поэтому в данном случае для подсчёта функции пригодности необходима имитационная модель завода. Как видно из названия, это модель, имитирующая работу заводу, все его бизнес-процессы. Подробную информацию об имитационном моделировании вы также сможете найти на страницах LAZY SMART . А пока для краткости изложения скажем, что если на вход имитационной модели задать входные значения искомых параметров, то на выходе получим итоговую прибыль. Компьютер как бы проиграет всю деятельность завода, допустим, за месяц в убыстренной перемотке. Эта итоговая прибыль и будет значением функции пригодности для генетического алгоритма. Представим работу связки «Генетический алгоритм – Модель» на схеме.

Применение генетических алгоритмов

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

Такие алгоритмы могут стать хорошим помощником в бизнесе, сократить убытки и увеличить прибыль за счёт выбора оптимальных стратегий.

Источники:

http://www.syl.ru/article/393626/geneticheskie-algoritmyi-sut-opisanie-primeryi-primenenie

http://studopedia.su/6_6805_primeri-prakticheskogo-primeneniya-geneticheskih-algoritmov.html

Генетические алгоритмы или как учебник по биологии может помочь в функциональной оптимизации