Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

Перекомпоновка пути Перекомпоновка пути (Path relinking, PR), как стратегия прохода поиска по траектории, проложенной через высококачественные решения, была впервые предложена в связи с TS в [14]. Позже метод был проработан в деталях как средство интеграции стратегий интенсификации и диверсификации TS. PR в основном действует, начиная с некоторого решения, выбранного из под­ множества качественных решений, и генерируя в пространстве решений путь через соседей к другим решениям из этого подмножества. PR была предложена как расширение Combination method o f Scatter Search [15]. Вместо прямой генерации нового решения через комбинацию двух или более оригинальных решений, PR, генерирует путь между выбранными решениями. Характер подобных путей легко специфицируем ссылкой на атрибуты решений, которые добавляются, удаляются или модифицируются иным образом, когда выполняются ходы. Примеры подобных атрибутов включают ребра и узлы графов, последовательные позиции в расписании, векторы, содержащиеся в решениях базисов задач линейного программирования и значения переменных и функции от переменных. Использование матрицеподобных структур при моделировании качественных зависимостей Алгебра кортежей В работе [16] описана математическая система для моделирования многоместных отношений. В её основе лежат известные свойства декартова произведения, которые соответствуют основополагающим законам матема­ тической логики. Основные понятия Атрибут - имя некоторого свойства системы или её части, предо­ ставленное множеством заданных или вычисляемых значений (доменом) Схема отношения - последовательность атрибутов, описывающая некоторое отношение. Объекты, заданные в одной схеме отношений, назы ­ ваются однотипными. Большая часть базовых операций доступна, прежде всего, для однотипных объектов. Элементарный кортеж соответствует обычному кортежу элементов в многоместных отношениях. С-кортеж - кортеж, заданный в некоторой схеме отношения. Компо­ нентами этого кортежа являются подмножества соответствующих доменов атрибутов этой схемы. С-кортеж интерпретируется как множество элемен­ тарных кортежей, содержащихся в декартовом произведении его компонент. Записывается как строка компонент в квадратных скобках: [Аи . . . , А п]. (4) С-система - объединение однотипных С-кортежей. С-система записы­ вается как: Л 1 ••• А\ ( 5 ) 71