Найти

Результаты поиска

• АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОЙ ГИБРИДИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

  Е. Е. Полупанова, А.А. Рыбалко

  2023-08-14

  Аннотация ▼

  Задача коммивояжера является задачей комбинаторной оптимизации. В статье при-
  водится постановка данной задачи и предлагается графовая математическая модель, в ко-
  торой вершины соответствуют городам, а рёбра – это пути между городами, причем пред-
  полагается, что граф взвешен. Решение задачи коммивояжёра состоит в нахождении га-
  мильтонова цикла минимального веса в полном взвешенном графе. Задача является NP-
  трудной, поэтому для решения данной задачи используется эвристический подход для полу-
  чения решения задачи на больших объёмах входных данных. Эвристика заключается в приме-
  нении для решения задачи коммивояжера гибридизации двух алгоритмов: алгоритма имита-
  ции отжига и алгоритма ближайшего соседа. Для решения задачи коммивояжера использу-
  ется последовательная схема гибридизации. Основная идея заключается в том, что на
  стартовом наборе решений запускается метод ближайшего соседа, а затем лучшее реше-
  ние, полученное на первом этапе, подается на вход алгоритму имитации отжига. В статье
  подробно освещены построение, блок-схемы гибридного алгоритма, алгоритма имитации
  отжига и метода ближайшего соседа. Далее в статье приводится описание пользователь-
  ского интерфейса приложения, написанного на Typescript. Приложение использует реальную
  карту местности для решения задачи коммивояжера. В последней части статьи освещает-
  ся сравнительный анализ эффективности работы алгоритмов: сравнение точности и време-
  ни работы разработанного гибридного алгоритма, алгоритма имитации отжига и метода
  ближайшего соседа на различных входных наборах данных. Удалось установить, что разра-
  ботанный гибридный алгоритм находится на втором месте по скорости работы и на пер-
  вом по качеству решения среди реализованных алгоритмов. Кроме того, разработанное ре-
  шение имеет высокую экономическую и практическую ценность ввиду того, что приложение
  для решения задачи коммивояжера, а следовательно, приложение для навигации по маршру-
  ту может заменить существующие аналоги или же оно может быть использовано в каких-
  либо узконаправленных областях, а также в логистике.

• СОСТАВЛЕНИЕ РАЦИОНА ПИТАНИЯ НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

  Е.Е. Полупанова , А. С. Олейник

  2023-08-14

  Аннотация ▼

  Данная работа посвящена решению задачи составления рациона питания с помощью
  генетического алгоритма. Задача составления рациона питания является задачей комби-
  наторной оптимизации. Основная цель решения задачи составления рациона питания за-
  ключается в нахождении оптимального плана питания в соответствии с особыми по-
  требностями человека. В статье приводится постановка задачи составления рациона
  питания и её математическая модель. Так как задача составления рациона питания явля-
  ется NP-трудной и входные данные могут потребовать больших вычислительных затрат
  для точного алгоритма, разумно применить эвристический подход в решении данной про-
  блемы. В статье подробно освещены основные используемые понятия теории генетиче-
  ских алгоритмов, последовательность шагов разработанного генетического алгоритма
  составления рациона питания, блок-схема генетического алгоритма. Для исследования
  генетического алгоритма составления рациона питания, было разработано клиент-
  серверное приложение под управлением операционной системы Android. Результатом ра-
  боты генетического алгоритма составления рациона питания является найденное меню на
  семь дней, которое выводится и хранится в приложении. Клиент-серверная архитектура
  приложения была выбрана с целью экономии ресурсов телефона пользователя. В статье
  приводятся описание пользовательского интерфейса приложения на платформе Android с
  возможностью регулировки различных параметров алгоритма. Также в статье проведен
  анализ эффективности работы полученного алгоритма: оценка точности и времени ра-
  боты разработанного генетического алгоритма при различных конфигурациях. По резуль-
  татам экспериментов удалось определить оптимальные значения настраиваемых пара-
  метров генетического алгоритма (число хромосом, количество итераций, вероятность
  мутации), позволяющих получать достаточно хорошие результаты за приемлемое время.
  Характерными чертами реализованного генетического алгоритма составления рациона
  питания является относительно небольшое время работы, даже при больших входных
  данных. Кроме того, разработанное решение имеет высокую экономическую ценность
  ввиду применения алгоритма на практике, например, в работе врачей-диетологов, фитнес-
  тренеров, а также для простых пользователей с избыточным весом.

• ЭВРИСТИЧЕСКИЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ДИОФАНТОВЫХ УРАВНЕНИЙ

  Е.Е. Полупанова , П.Е. Усов

  115-123

  2022-01-31

  Аннотация ▼

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