Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,791

АДАПТИРУЮЩИЙСЯ МЕМЕТИЧЕСКИЙ АЛГОРИТМ ОПТИМИЗАЦИИ КОНФИГУРАЦИИ УЛИЧНО-ДОРОЖНОЙ СЕТИ

Сапрыкина О.В. 1 Сапрыкин О.Н. 1
1 ФГАОУ ВО «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)»
Разработан адаптирующийся меметический алгоритм, направленный на повышение эффективности при многокритериальной оптимизации. Алгоритм применяется для решения задачи поиска рациональной конфигурации улично-дорожной сети и отличается от существующих наличием генотипа, состоящего из нескольких видов хромосом и модификацией операторов скрещивания и мутации. В качестве критериев при оптимизации конфигурации улично-дорожной сети использованы: критерий надежности, критерий напряженности, критерий связности, критерий транспортной доступности. Особенностью разработанного адаптирующегося меметического алгоритма является высокая скорость поиска решения, которая достигается за счет введения в генотип хромосом-мем, сохраняющих информацию о примененных операторах скрещивания и мутации, в случае достижения положительного результата. Адаптирующийся меметический алгоритм может быть применим для многокритериальной оптимизации конфигурации любой улично-дорожной сети урбанизированной территории.
конфигурация улично-дорожной сети
функция приспособленности
оператор мутации
оператор скрещивания
хромосома
генотип
1. Егунов М.М. Анализ структурной надёжности транспортной сети / М.М. Егунов, В.П. Шувалов // Вестник СибГУТИ. – 2012. – № 1. – С. 54-60.
2. Карпенко А.П. Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов / А.П. Карпенко // Приложение к журналу «Информационные технологии». – 2012. – № 7. – 32 с.
3. Михайлов А.Ю. Научные основы проектирования улично-дорожных сетей: дис. ... д-ра тех. наук. – Иркутск, 2004. – 378 с.
4. Сапрыкин О.Н. Построение архитектуры аналитического инструментария интеллектуальной транспортной системы на основе паттернов проектирования [текст] / О.Н. Сапрыкин, О.В. Сапрыкина, Т.И. Михеева // Вестник Самарского гос. техн. ун-та. Серия «Технические науки». – 2010. – № 4 (27). – С. 27-35.
5. Сапрыкина О.В. Модель эволюции транспортной сети урбанизированной территории [текст] / О.В. Сапрыкина, Т.И. Михеева // Вестник Самарского гос. техн. ун-та. Серия «Технические науки». – 2012. – № 4(36). – С. 58-65.
6. BackT. Evolutionary Computation 1: basicalgorithmsandoperators / T. Back, D. Fogel, Z. Michalewicz Institute of Physics. – 2000. – 378 p.

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

Меметические алгоритмы входят в класс гибридных популяционных алгоритмов поисковой оптимизации, основанных на метаэвристиках [2]. Понятие мема определил C.R. Dawkins в 1979 г. Применение меметического алгоритма направлено на повышение эффективности многокритериальной оптимизации.

Решение задачи поиска рациональной конфигурации улично-дорожной сети

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

Пусть генотип каждой особи состоит из трех хромосом. Хромосома имеет смысл определенной топологии УДС и кодируется бинарной строкой фиксированной длины , где – количество участков УДС, представленной графом . Назовем её хромосомой-решением. Локус гена трактуется как идентификационный номер участка УДС . Гены отсортированы согласно идентификационным номерам участков сети по возрастанию. Аллель каждого гена хромосомы определяется следующим образом: если участок УДС существует, то и , в противном случае.

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

, (1)

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

Шаг 1 инициализация популяции ;

Шаг 2 проверка условия остановки алгоритма;

Шаг 3 селекция хромосом-решений;

Шаг 4 применение генетических операторов для хромосом-решений;

Шаг 5 применение генетических операторов для хромосом-мем;

Шаг 6 вычисление функций приспособленности хромосом-решений;

Шаг 7 селекция;

Шаг 8 выбор «наилучшей» хромосомы-решения.

Рис. 1. Блок-схема адаптирующегося меметического алгоритма оптимизации

На этапе первоначальной инициализации алгоритма формируется начальная популяция особей . Выберем размер популяции равным десяти особям. Хромосома-решение особи представляется набором из двоичных цифр и формируется случайным образом. Затем хромосома проверяется по формуле связности Эйлера. Сеть называется связной, если для любых двух её вершин и существует путь из вершины в вершину . Условие связности Эйлера имеет вид:, (2)

где – количество вершинам сети; – количество ребер; – компонент связности, равный двум для связного графа.

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

Для каждой особи инициализация заключается в следующих шагах:

Шаг 1 Генерация хромосомы решений случайным образом;

Шаг 2 Проверка на отсутствие в пуле «использованных»;

Шаг 3 Проверка на отсутствие в пуле «несвязных»;

Шаг 4 Проверка по условию связности Эйлера, если условие не выполняется, то хромосома сохранения в пул «несвязных» и осуществляется возврат к шагу 1.

Хромосомы мемы на данном этапе остаются незаполненными.

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

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

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

, (3)

где , – гены родительских хромосом решений, находящиеся на локусе .

Иллюстрация работы такого кроссинговера для хромосом фиксированной длиной равной 5 локусов показана на рисунке 2. Физическая интерпретация скрещивания хромосом-решений имеет смысл скрещивания некоторых двух топологий сети и представлена на рисунке 3.

Рис. 2. Кроссинговер для хромосом фиксированной длиной равной пяти

Рис. 3. Смысловая интерпретация скрещивания хромосом решений

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

Полученное значение сохраняется в мем-хромосоме мутации . При дальнейших мутациях хромосомы решения используется вероятность из хромосомы-мем мутации.

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

, (4)

где , – функции приспособленности первого и второго родителя соответственно.

Мутация мем происходит по некоторой стратегии, которая называется гиперэвристикой. Гиперэвристики существуют случайные, жадные и с использованием функции выбора [2]. Используем гиперэвристику простого случайного выбора (simplerandomchoice), которая заключается в случайной замене мем-хромосомы , другой мем-хромосомой из роя мем , где . Вероятность мутации мем-хромосом остаётся постоянной для каждого поколения и принята равной 0.01.

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

Алгоритм парного турнирного отбора заключается в следующих шагах:

Шаг 1 осуществляется случайный выбор из популяции двух особей (выбирается количество особей равное численности турнира, так как используем парный турнир, выбираем две особи);

Шаг 2 выбирается лучшая особь из выбранной пары особей;

Шаг 3 если не достигли требуемой численности популяции , то возвращаемся к шагу 1.

Определение функции приспособленности

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

, (5)

где ‑ весовые коэффициенты. Весовые коэффициенты принимаем равными , , , .

Критерий надежности, является показателем устойчивости функционирования транспортной сети [3]:, (6)

где – число элементов УДС, то есть ; – коэффициент готовности элемента сети, определяемый по формуле [1]:

, (7)

где – длина элемента сети; – единичная длина линии связи, принимаем равной 100 км; – коэффициент готовности линии связи единичной длины, это случайная величина в диапазоне [0,0.999].

Критерий напряженности является составным и представляет собой минимизацию значений напряженности во всех найденных акупунктурных точках УДС. Значения напряженности для каждой акупунктурной точки множества рассчитывается по заданным временным и пространственным характеристикам.

, (8)

где – количество акупунктурных точек множества , – количество участков УДС в некотором радиусе акупунктурной точки , – напряженность акупунктурной точки .

Критерий, основанный на вычислении ранга связности сети, при низких значениях которого увеличивается вероятность заторов:

(9)

где – количество ребер графа УДС; – количество вершинграфа УДС; – компонент связности.

Критерий транспортной доступности, определяющий плотность транспортных потоков вдоль связей в сети:

(10)

где – общее количество условных транспортных районов;

– количество связей -го планировочного района, . Связи отсортированы в порядке возрастания согласно количеству поездок транспортных средств или пассажирских поездок , полученных для этой связи;

– количество поездок или -го планировочного района, ;

– штрафная функция, , если в сети нет модификаций, то есть нет присоединения нового участка УДС.

Условием остановки алгоритма является отсутствие улучшения усредненного для особей значения функции приспособленности на протяжении трех поколений.

Лучшей хромосомой признаётся хромосома-решение с наибольшим значением функции приспособленности.

Заключение

Разработанный адаптирующийся меметический алгоритм используется для поиска оптимальной конфигурации УДС в аналитическом инструментарии интеллектуальной транспортной системы [4],[5] и позволяет снизить скорость поиска решения, направляя поиск в область оптимальных решений, за счет введения мем-хромосом, содержащих информацию о предпринятых действиях при достижении положительных результатов.

Рецензенты:

Титов Б.А., д.т.н., профессор, заведующий кафедрой организации и управления перевозками на транспорте, ФГАОУ ВО «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)», г. Самара;

Кораблин М.А., д.т.н., профессор, декан факультета информационных систем и технологий, заведующий кафедрой вычислительная техника ФГОБУ ВПО «Поволжский государственный университет телекоммуникаций и информатики», г. Самара;

Пачурин Г.В., д.т.н., профессор, зав. кафедрой «Производственная безопасность и экология» (ПБиЭ) Нижегородский государственный технический университет им. Р.Е. Алексеева, г. Нижний Новгород.


Библиографическая ссылка

Сапрыкина О.В., Сапрыкин О.Н. АДАПТИРУЮЩИЙСЯ МЕМЕТИЧЕСКИЙ АЛГОРИТМ ОПТИМИЗАЦИИ КОНФИГУРАЦИИ УЛИЧНО-ДОРОЖНОЙ СЕТИ // Современные проблемы науки и образования. – 2014. – № 5.;
URL: http://science-education.ru/ru/article/view?id=15256 (дата обращения: 17.10.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074