X Международная студенческая научная конференция Студенческий научный форум - 2018

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

Генетические алгоритмы впервые были опубликованы в 1975 году[1]. С этого времени они являются перспективным способом разрешения научных и технических проблем.

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

Принцип работы генетического алгоритма

Рассмотрим основные этапы алгоритма[2]:

Начальная популяция

На начальной стадии выполнения генетического алгоритма случайным образом инициализируется определённая популяция хромосом. Каждая хромосома это случайная L-битная строка, где L — длина кодировки хромосомы. Каждая хромосома является одним из решений поставленной задачи.

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

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

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

Критерий окончания процесса

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

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

Рассмотрим задачу, идея которой была рассмотрена на одном из форумов[4]. Возьмём любое предложение, например шекспировскую строку: Methinks it is like a weasel и случайную строку такой же длины: wdltmnlt dtjbkwirzrezlmqco p.Начнем вносить в неё случайные изменения с применением генетических операторов. Сколько потребуется поколений (итераций) для того, чтобы эта случайная строка превратилась в шекспировскую строку, если выживать будут лишь потомки более схожие с шекспировской строкой? В виду отсутствия реализация данная задача была рассмотрена и реализована.

Для решения данной задачи нам необходимо формализовать работу со случайной строкой. Блок-схема алгоритма представлена на рис. 1.

Входные данные:

строка S – осмысленное предложение, к получению которого стремимся;

строка C– строка из случайных символов, начальная популяция для работы программы. Длина данной строки берётся равной длине строки S.

Выходные данные:

натуральное число N, равное количеству поколений (итераций), необходимых для преобразования строки С в строку S.

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

Сформировав программу на языке Python, мы можем подать на вход следующую строку S: The quick brown fox jumps over the lazy dog. При запуске программы создаётся строка С, заполняющаяся случайными символами алфавита или пробелом. В нашем случае строка С получилась: rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk. Как можно заметить каждое поколение отличается не более чем на один символ друг от друга. Всего потребовалось 46 поколений (итераций), чтобы добраться от ‘rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk’ до ‘the quick brown fox jumps over the lazy dog’ с помощью мутаций и отбора (рис. 2). На каждой итерации подчёркнут символ, который изменился по отношению к предыдущей итерации.

Рис. 1 Блок-схема работы алгоритма

Рис. 2 Вывод результатов

Далее, с помощью улучшения программы производим анализ двух произведений: To Kill a Mocking Bird by Harper Lee и Catcher in the Rye by J.D. Salinger. Для измерения выбраны два параметра — распределение количества поколений по предложениям и зависимость количества поколений от длины строки. Второй параметр выбираем, чтобы проверить наличие или отсутствие корреляции. Параметры для алгоритма были следующие: количество потомков у строки: 100; количество выживших в поколении: 10.

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

Для большинства предложений получилось достичь строки достаточно быстро, потребовалось менее 100 итераций, практически для всех предложений достаточно 200 итераций (рис. 3).

Рис. 3 Зависимость количества предложений от количества итераций

Корреляция между длиной строки и количеством поколений идеальная. Это означает, что практически в каждом поколении удавалось продвинуться на шаг ближе к целевой строке (рис. 4).

Рис. 4 Зависимость длины предложений от количества итераций

Заключение

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

Список источников и литературы

Холланд Дж. Х., Адаптация в естественных и искусственных сетях, Издательство Мичиганского Университета, 1975.

Генетические алгоритмы, Гладков Л.А., Курейчик В.В., Курейчик В.М.,М.: ФИЗМАТЛИТ, 2006.

http://algolist.manual.ru/ai/ga/ga1.php

https://habrahabr.ru/

Код для цитирования: Скопировать