Найти

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

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

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

  115-123

  2022-01-31

  Аннотация ▼

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

• НОВЫЙ АЛГОРИТМ ПОСТРОЕНИЯ КРАТЧАЙШЕГО ПУТИ ОБХОДА КОНЕЧНОГО МНОЖЕСТВА НЕПЕРЕСЕКАЮЩИХСЯ КОНТУРОВ НА ПЛОСКОСТИ

  А. А. Петунин, Е.Г. Полищук , С. С. Уколов

  2021-04-04

  Аннотация ▼

  Рассматривается проблема маршрутизации режущего инструмента машин листо-
  вой резки с ЧПУ для случая, когда точки врезки расположены на границах деталей, ограни-
  ченных отрезками прямых и дугами окружностей, при этом используется техника непрерывной резки (CCP), т.е. каждый контур вырезается целиком, но не используется предва-
  рительная дискретизация, то есть резка может начинаться с любой точки контура. Об-
  щая задача поиска оптимального маршрута в этом случае сводится к минимизации длины
  холостого хода. Показано, что она эквивалентна поиску кратчайшей ломаной с вершинами,
  расположенными на контурах. Предложен новый эвристический алгоритм построения
  такой ломаной для заранее заданного порядка обхода контуров. Показано, что получаю-
  щееся решение представляет собой локальный минимум. Описаны некоторые достаточ-
  ные условия, того, что решение является также глобальным минимумом, которые легко
  проверяются численно, а некоторые даже визуально. Описана методика автоматического
  учёта ограничений предшествования для практически важного случая наличия вложенных
  контуров, возникающих как за счёт отверстий в деталях, так и за счёт расположения
  мелких деталей в отверстиях крупных. При этом происходит также уменьшение размер-
  ности задачи, что положительно сказывается на времени оптимизации, особенно дис-
  кретной. Предложен эвристический алгоритм выбора порядка обхода контуров на основе
  метода переменных окрестностей (VNS). Описаны альтернативные подходы применения
  других методов дискретной оптимизации совместно с предложенным алгоритмом по-
  строения кратчайшей ломаной для решения полной задачи непрерывной резки и возникаю-
  щие при этом сложности как теоретического, так и практического характера. Описано
  обобщение задачи непрерывной резки до более широкого класс задач сегментной резки и
  обобщённой сегментной резки, что позволяет продвинуться в решении общей задачи пре-
  рывистой резки. Описана схема применения предложенного алгоритма для решения задач
  сегментной и обобщённой сегментной резки. Приведены некоторые результаты численных
  экспериментов в сравнении с точным решением задачи для дискретной модели GTSP.