Генетические алгоритмы для задач комбинаторной оптимизации. Задача укладки рюкзака


НОУ ИНТУИТ | Лекция | Генетические алгоритмы для задач комбинаторной оптимизации

Аннотация: До сих пор рассматривалось применение ГА, в основном, при решении задачи численной оптимизации при поиске экстремумов функции. Но в настоящее время ГА используются больше для решения задач комбинаторной оптимизации, которым посвящена подавляющая часть публикаций. Базовой задачей комбинаторной оптимизации является задача коммивояжера, для которой отрабатываются новые методы решения задач данного типа. Поэтому большая часть лекции посвящена решению задачи коммивояжера с помощью ГА на основе различных способов кодирования потенциальных решений и проблемно-ориентированных генетических операторов кроссинговера. Однако сначала рассматриваются задачи об укладке рюкзака и покрытии множества, которые допускают использование простого (классического) ГА.

2.1. Задача об укладке рюкзака

Эта задача имеет следующую неформальную простую постановку [4,5]. Имеется рюкзак объемом и различных предметов. Каждый предмет имеет известный объем и стоимость . В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем . Форма предметов здесь не учиты.

Формальная постановка задачи: для данного множества весов , стоимостей и объема надо найти двоичный вектор

и при этом должно выполняться условие:

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

В качестве фитнесс-функции в простейшем случае можно взять

но в этом случае, как указано выше, есть проблемы с неправильными решениями.

Данная задача относится к классу задач с ограничениями, при решении которых применяются следующие подходы [4,5]: 1) введение в фитнесс-функцию дополнительного штрафа; 2) использование алгоритмов "восстановления" некорректных решений.

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

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

    Здесь для всех трех случаев .

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

    В этом случае в качестве фитнесс-функции используется

    где вектор – восстановленная версия исходного вектора . Здесь следует отметить, по крайней мере, два аспекта. Во-первых, можно использовать различные алгоритмы восстановления. Во-вторых, восстановленные особи могут замещать только некоторую часть исходных особей в популяции. Процент замещаемых особей может варьироваться от 0% до 100% и его значение является важнейшим параметром метода восстановления. В некоторых работах отмечается, что наилучшие результаты получаются при 5%, во всяком случае, лучше, чем в двух крайних случаях – 0% (без замещения) и 100% (любая восстановленная особь заменяет исходную). Ниже приведен простой алгоритм восстановления.

    При этом используются два основных способа выбора объекта:

    • случайный выбор объекта из рюкзака;
    • "жадное восстановление", при котором вначале все предметы сортируются в порядке убывания их стоимости и на каждом шаге для удаления выбирается предмет минимальной стоимости (из имеющихся в рюкзаке).
  3. Третий подход к решению задач с ограничениями использует специальное отображение (декодирование) особей, которое гарантирует генерацию допустимого решения (с учетом ограничений), или используют проблемно-ориентированные генетические операторы, сохраняющие корректность решения.

    Рассмотрим один из возможных вариантов алгоритма декодирования, который основан на кодировании решения вектором целых чисел, так называемом "упорядоченном представлении" (ordinal representation), подробно описанном в разделе 3.3.2. Здесь каждая хромосома кодируется вектором целых чисел, где -я компонента вектора – есть целое число в диапазоне от 1 до . "Упорядоченное представление" использует для ссылок (базовый) список предметов . Вектор фактически содержит указатели на базовый список . Декодирование вектора осуществляется путем выбора соответствующего предмета из текущего списка и удаления его из базового списка. Например, при базовом списке предметов текущий вектор декодируется в следующую последовательность предметов: 4, 3, 6, 1,2, 5. Первым в рюкзак включается четвертый элемент списка - 4, который устраняется из . Далее в рюкзак включается третий элемент из текущего списка . Затем включается 6 - четвертый элемент текущего и т.д. Подробнее описание этого представления и выполнение кроссинговера на нем описано в разделе 2.3.2. В данном методе хромосома может интерпретироваться как стратегия (порядок) включения предметов в решение. Отметим, что основным достоинством данного кодирования хромосомы является то, что на нем работает одноточечный кроссинговер. То есть для двух допустимых решений –родителей кроссинговер порождает также допустимое решение–потомок. Оператор мутации при данном представлении выполняется путем замены -го гена (целочисленной компоненты вектора) на случайное целое число из диапазона .

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

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

www.intuit.ru

Задача о ранце Википедия

Пример задачи о ранце: необходимо уложить коробки в ранец вместимостью 15 кг так, чтобы стоимость уложенных коробок была максимальной

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

В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес» требуется отобрать подмножество с максимальной полной стоимостью, соблюдая при этом ограничение на суммарный вес.

Классическая постановка задачи

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

Математически задача формулируется следующим образом: имеется n{\displaystyle n} грузов. Для каждого i{\displaystyle i}-го груза определён его вес wi>0{\displaystyle w_{i}>0} и ценность vi>0{\displaystyle v_{i}>0}, i=1,2,...,n{\displaystyle i=1,2,...,n}. Ограничение суммарного веса предметов в рюкзаке задаётся грузоподъёмностью W{\displaystyle W}. Необходимо

максимизировать ∑i=1nvixi{\displaystyle \sum _{i=1}^{n}v_{i}x_{i}} с ограничениями ∑i=1nwixi≤W{\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W} и xi∈{0,1}{\displaystyle x_{i}\in \{0,1\}} [1].

Варианты задачи о ранце

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

  1. Рюкзак 0-1 (англ. 0-1 Knapsack Problem)[2]: не более одного экземпляра каждого предмета.
  2. Ограниченный рюкзак (англ. Bounded Knapsack Problem)[3]: не более заданного числа экземпляров каждого предмета.
  3. Неограниченный рюкзак (англ. Unbounded Knapsack Problem)[3]: произвольное количество экземпляров каждого предмета.
  4. Рюкзак с мультивыбором (англ. Multiple-choice Knapsack Problem)[4]: предметы разделены на группы, и из каждой группы требуется выбрать только один предмет.
  5. Множественный рюкзак (англ. Multiple Knapsack Problem)[5]: есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
  6. Многомерный рюкзак (англ. Multy-dimensional knapsack problem): вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна[4].
  7. Квадратичная задача о рюкзаке (англ. Quadratic knapsack problem): суммарная ценность задается неотрицательно определённой квадратичной формой[6].

Нелинейная задача о ранце

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

Пусть вектор x=(x1,..,xn)∈Rn{\displaystyle x=(x_{1},..,x_{n})\in \mathbb {R} ^{n}} определяет количество экземпляров каждого предмета в ранце. Тогда задача состоит в нахождении минимума функции

minx∈S f(x){\displaystyle \min _{x\in S}\ f(x)},

при заданном ограничении:

g(x)≤b{\displaystyle g(x)\leq b}.

Функции f(x),g(x):Rn→R{\displaystyle f(x),g(x):\mathbb {R} ^{n}\rightarrow \mathbb {R} } предполагаются непрерывными и дифференцируемыми на Rn{\displaystyle \mathbb {R} ^{n}}. b{\displaystyle b} — целочисленная константа, множество S{\displaystyle S} непусто[7].

В случае линейных функций f(x),g(x){\displaystyle f(x),g(x)}, задача сводится к одной из классических постановок, в зависимости от множества S{\displaystyle S}:

  • S={0,1}n{\displaystyle S=\{0,1\}^{n}} — рюкзак 0-1
  • S=N0n{\displaystyle S=\mathbb {N_{0}} ^{n}} — неограниченный рюкзак
  • S={(x1,..,xn)∈N0n:xi≤ci}{\displaystyle S=\{(x_{1},..,x_{n})\in \mathbb {N_{0}} ^{n}:x_{i}\leq c_{i}\}} — ограниченный рюкзак

Свобода в выборе функций f(x),g(x){\displaystyle f(x),g(x)} позволяет решать более широкий класс задач, включая организацию производственных мощностей (англ.)русск., оптимальное распределение семплов в районированной выборке или решение квадратичной задачи о ранце[7].

Точные методы решения

Как было сказано выше, задача о ранце относится к классу NP-полных, и для неё нет полиномиального алгоритма, решающего её за разумное время. Поэтому при решении задачи о ранце необходимо выбирать между точными алгоритмами, которые неприменимы для «больших» рюкзаков, и приближенными, которые работают быстро, но не гарантируют оптимального решения задачи.

Дерево полного перебора, соответствующее поиску решения для трех предметов. В каждом узле определяется, будет ли данный предмет уложен в рюкзак. Цифра в узле соответствует номеру предмета. Цифры на рёбрах: 0 означает, что предмет не был взят, 1 — что был.

Полный перебор

Как и для других дискретных задач, задачу о ранце можно решить, полностью перебрав все возможные решения. Допустим, имеется N{\displaystyle N} предметов, которые можно укладывать в рюкзак. Нужно определить максимальную стоимость груза, вес которого не превышает W{\displaystyle W}.

Для каждого предмета существует 2 варианта: предмет либо кладётся в рюкзак, либо нет. Тогда перебор всех возможных вариантов имеет временну́ю сложность O(2N){\displaystyle O(2^{N})}, что позволяет его использовать лишь для небольшого количества предметов[8]. С ростом числа предметов задача становится неразрешимой данным методом за приемлемое время.

На рисунке показано дерево перебора для трёх предметов. Каждый лист соответствует некоторому подмножеству предметов. После составления дерева необходимо найти лист с максимальной ценностью среди тех, вес которых не превышает W{\displaystyle W}[9].

Метод ветвей и границ

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

Оригинальный алгоритм, предложенный Питером Колесаром (англ. Peter Kolesar) в 1967 году, предлагает отсортировать предметы по их удельной стоимости (отношению ценности к весу) и строить дерево полного перебора. Его улучшение заключается в том, что в процессе построения дерева, для каждого узла мы оцениваем верхнюю границу ценности решения, и продолжаем строить дерево только для узла с максимальной оценкой[10]. Когда максимальная верхняя граница оказывается в листе дерева, алгоритм заканчивает свою работу.

Способность метода ветвей и границ уменьшать количество вариантов перебора сильно опирается на входные данные. Его целесообразно применять только в том случае, когда удельные ценности предметов отличаются значительно[11].

Методы динамического программирования

Задача о неограниченном рюкзаке

При дополнительном ограничении на веса предметов, задачу о ранце можно решить за псевдополиномиальное время методами динамического программирования.

Пусть вес каждого предмета wi{\displaystyle w_{i}} является целым неотрицательным числом. Тогда для решения задачи необходимо вычислить оптимальные решения для всех w∈Z:0<=w<=W{\displaystyle w\in \mathbb {Z} :0<=w<=W}, где W{\displaystyle W} — заданная грузоподъемность. Определим m[w]{\displaystyle m[w]} как максимальную ценность предметов, которые можно поместить в рюкзак грузоподъемностью w{\displaystyle w}.

Для m[w]{\displaystyle m[w]} можно записать рекуррентные формулы:

  • m[0]=0{\displaystyle m[0]=0}
  • m[w]=maxwi≤w(vi+m[w−wi]){\displaystyle m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])}[12],

где vi,wi{\displaystyle v_{i},w_{i}} — ценность и вес i{\displaystyle i}-го предмета соответственно, а максимум из пустого множества следует считать равным нулю.

Фактически последнее уравнение является функциональным уравнением Р. Беллмана или функциональным уравнением динамического программирования. В данном случае для его решения достаточно вычислить все значения m[w]{\displaystyle m[w]}, начиная с 0{\displaystyle 0} и до W{\displaystyle W}[12]. Если дополнительно хранить на каждом шаге набор предметов, который реализует максимальную ценность, то алгоритм выдаст и оптимальный набор предметов.

Так как на каждом шаге необходимо найти максимум из n{\displaystyle n} предметов, алгоритм имеет вычислительную сложность O(nW){\displaystyle O(nW)}. Поскольку W{\displaystyle W} может зависеть экспоненциально от размера входных данных, алгоритм является псевдополиномиальным. Поэтому эффективность данного алгоритма определяется значением W{\displaystyle W}. Алгоритм даёт отличные результаты при W≤1000{\displaystyle W\leq 1000}, но не очень хорошие для W≥10 000 000{\displaystyle W\geq 10\ 000\ 000}[13].

Задача о рюкзаке 0-1

Решение задачи о рюкзаке 0-1 близко к решению предыдущей задачи, но необходимо учесть тот факт, что каждый предмет имеется в единственном экземпляре. Пусть m[i,w]{\displaystyle m[i,w]} — максимальная ценность предметов, полученных из первых i{\displaystyle i} имеющихся предметов, с суммарным весом не превышающим w{\displaystyle w}.

Рекуррентные соотношения:

  • m[0,w]=0{\displaystyle m[0,w]=0}
  • m[i,w]=m[i−1,w]{\displaystyle m[i,\,w]=m[i-1,\,w]}, если wi>w{\displaystyle w_{i}>w}
  • m[i,w]=max(m[i−1,w],m[i−1,w−wi]+vi){\displaystyle m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})}, если wi≤w{\displaystyle w_{i}\leq w}

Вычисляя m[n,W]{\displaystyle m[n,W]}, можно найти точное решение. Если массив m[i,w]{\displaystyle m[i,w]} помещается в памяти машины, то данный алгоритм, вероятно, является одним из наиболее эффективных[12].

1 // Ввод: 2 // Ценности предметов (загруженные в массив v) 3 // Веса предметов (загруженные в массив w) 4 // Количество предметов (n) 5 // Грузоподъемность (W) 6 7 for j from 0 to W do: 8 m[0, j] := 0 9 10 for i from 1 to n do: 11 for j from 0 to W do: 12 if w[i] > j then: 13 m[i, j] := m[i-1, j] 14 else: 15 m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

Проиллюстрировать решение методом динамического программирования можно следующим образом: на двумерной плоскости по оси X{\displaystyle X} откладывается количество предметов, по оси Y{\displaystyle Y} — их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось Y{\displaystyle Y} равны весу предмета. На втором шаге опять строятся 2 линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Положим длину горизонтальных дуг равной нулю, а наклонных — ценности предмета[14].

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

Таким образом, любому решению задачи соответствует некоторый путь в построенном дереве. Задача сводится к нахождению пути максимальной длины[14].

Пусть вместимость рюкзака W=14{\displaystyle W=14}.

Номер предмета Ценность Вес
1 3 5
2 5 10
3 4 6
4 2 5

Из рисунка видно, что суммарная ценность для оптимального решения равна 7, так как это максимальная ценность в построенном дереве.

Динамическое программирование над ценностями предметов

Рекуррентные соотношения можно записывать не только относительно веса предметов, но также и относительно ценности. Для этого обозначим за y[i,V]{\displaystyle y[i,V]} минимальный вес предметов, суммарной ценностью V{\displaystyle V}, который можно получить из первых i{\displaystyle i} предметов. Если необходимый вес получить невозможно, то отметим это как y[i,V]=W+1{\displaystyle y[i,V]=W+1}.

После этого решим функциональное уравнение динамического программирования:

y[i,V]={y[i−1,V],if V<vimin{ y[i−1,V],y[i−1,V−vi]+wi},if V≥vi{\displaystyle y[i,V]={\begin{cases}y[i-1,V],&{\text{if }}V<v_{i}\\\min\{\ y[i-1,V],y[i-1,V-v_{i}]+w_{i}\},&{\text{if }}V\geq v_{i}\end{cases}}},

с начальными условиями:

y[0,0]=0{\displaystyle y[0,0]=0}

y[0,V]=W+1{\displaystyle y[0,V]=W+1}[15]

Приближенные методы решения

Как и для большинства NP-полных задач, не всегда необходимо получать точное решение, так как решения, близкие к оптимальным, могут применяться в прикладных задачах.

Жадный алгоритм

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

Время работы данного алгоритма складывается из времени сортировки и времени укладки. Сложность сортировки предметов составляет O(Nlog⁡(N)){\displaystyle O(N\log(N))}. Далее происходит вычисление того, сколько предметов поместится в рюкзак за общее время O(N){\displaystyle O(N)}[10]. Итоговая сложность O(Nlog⁡(N)){\displaystyle O(N\log(N))} при необходимости сортировки и O(N){\displaystyle O(N)} при уже отсортированных данных[10].

Пример. Пусть вместимость рюкзака W=80{\displaystyle W=80}. Предметы уже отсортированы по удельной ценности. Применим жадный алгоритм.

i вес цена цена/вес
1 15 60 4
2 30 90 3
3 50 100 2

Кладём в рюкзак первый предмет, а за ним второй. Третий предмет в рюкзак не влезет. Суммарная ценность вещей в рюкзаке равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190. Таким образом, мы получили некоторое неоптимальное решение.

Следует понимать, что жадный алгоритм может привести к ответу сколь угодно далёкому от оптимального. Например, если один предмет имеет вес 1 и стоимость 2, а другой — вес W и стоимость W, то жадный алгоритм наберёт иготовую стоимость 2 при оптимальном ответе W. При этом тот же алгоритм для неограниченной задачи о рюкзаке приведёт к ответу, составляющему не менее 50% от ценности оптимального[10]. (В приведённом примере жадный алгоритм возьмёт 5 первых предметов с общей ценностью 300, и это совпадает с оптимальным решением.)

Впервые жадный алгоритм был предложен Джорджем Данцигом[16] для решения задачи о неограниченном рюкзаке.

Приближенная схема полностью полиномиального времени

Так как точного алгоритма решения задачи за полиномиальное время не было найдено, появилась задача получить полиномиальное решение с гарантированной точностью 1−ε{\displaystyle 1-\varepsilon }. Для этого существует целый ряд приближённых схем полностью полиномиального времени, то есть со сложностью, являющейся полиномом от n{\displaystyle n} и 1ε{\displaystyle {\frac {1}{\varepsilon }}}.

Идея, стоящая за классической схемой, заключается в снижении точности, с которой заданы ценности предметов. Объединяя предметы близкой ценности в одну группу, можно снизить количество разных предметов. Алгоритм записывается следующим образом[15]:

  1. Найдём приближённое решение xl{\displaystyle x^{l}} при помощи жадного алгоритма. Пусть x∗{\displaystyle x^{*}} — точное решение. Тогда из оценки эффективности жадного алгоритма xl≤x∗≤2xl{\displaystyle x^{l}\leq x^{*}\leq 2x^{l}}.
  2. Отмасштабируем ценности следующим образом: vi′=⌊vizlεn⌋{\displaystyle v'_{i}=\left\lfloor {\frac {v_{i}}{\frac {z^{l}\varepsilon }{n}}}\right\rfloor }.
  3. Алгоритмом динамического программирования для задачи с целочисленными ценностями предметов находим решение.

Существует множество различных схем апроксимации. Тем не менее, они сильно зависят от формулировки задачи о ранце. Например, если в условии появляется второе ограничение типа неравенства (двухмерный рюкзак), то задача уже не имеет известной схемы полиномиального времени[17].

Генетические алгоритмы

Пример эволюции популяции при использовании генетического алгоритма. Объектами являются строчки, кодирующие в бинарном виде какие объекты кладутся в рюкзак. Например, строчка (0,1,0,1,0) соответствует выбору коробок весами 12 кг и 7 кг .

Как и для других NP-трудных задач оптимизации, для решения задачи о ранце применяются генетические алгоритмы. Они не гарантируют нахождения оптимального решения за полиномиальное время и не дают оценку близости решения к оптимальному, но обладают хорошими временными показателями, позволяя найти достаточно хорошее решение быстрее других известных детерминированных или эвристических методов.[18]

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

Функция приспособленности определяет близость решения к оптимальному. Например, таковой может служить суммарная ценность предметов, при условии, что суммарный вес не превосходит грузоподъемность.

После серии смен поколений, в которых скрещиваются наиболее приспособленные особи и игнорируются оставшиеся, алгоритм, по предположению, должен улучшить исходные решения[19].

Решение задачи о сумме подмножеств

Частным случаем задачи рюкзака 0-1 является задача о сумме подмножеств. Пусть W{\displaystyle W} — грузоподъёмность рюкзака, wi{\displaystyle w_{i}}— вес i{\displaystyle i}-го предмета, а его стоимость vi=wi{\displaystyle v_{i}=w_{i}}. Таким образом, задача состоит в том, чтобы нагрузить рюкзак наиболее плотно, или полностью исчерпать ресурсы:

W=∑i=1Nwixi, xi∈{0,1}{\displaystyle W=\sum _{i=1}^{N}w_{i}x_{i},\qquad \ x_{i}\in \{0,1\}}

Для решения можно воспользоваться упомянутым генетическим алгоритмом. Особью является вектор (x1,..,xn){\displaystyle (x_{1},..,x_{n})}. В качестве функции приспособленности следует использовать близость суммарного веса предметов к W{\displaystyle W}, с той лишь особенностью, что более предпочтительны наборы, помещающиеся в рюкзак (суммарный вес предметов меньше, чем W{\displaystyle W})[19].

Определим формально функцию приспособленности f(x1,..,xn):{0,1}n→R{\displaystyle f(x_{1},..,x_{n}):\{0,1\}^{n}\rightarrow \mathbb {R} }. Пусть S{\displaystyle {\mathcal {S}}} — сумма весов всех предметов. Тогда Δmax=max(W,S−W){\textstyle \Delta _{max}=max(W,{\mathcal {S}}-W)} — максимально возможное отклонение веса предметов в рюкзаке от W{\displaystyle W}.

Пусть W′=∑i=1Nwixi{\textstyle W'=\sum _{i=1}^{N}w_{i}x_{i}} — суммарный вес предметов для данного вектора. Тогда положим:

f(x1,..,xn)={1−W−W′W,W′≤W,1−W′−WΔmax,W′>W.{\displaystyle f(x_{1},..,x_{n})={\begin{cases}1-{\sqrt {\frac {W-W'}{W}}},&W'\leq W,\\1-{\sqrt {\frac {W'-W}{\Delta _{max}}}},&W'>W.\end{cases}}}[19]

Пользуясь общим алгоритмом, можно найти приближенное решение:

  1. Создать случайный набор особей — популяцию.
  2. Подсчитать функцию приспособления для каждой особи.
  3. Оставить только наиболее приспособленных особей (естественный отбор).
  4. Произвести скрещивания особей.
  5. Подвергнуть потомков мутации.
  6. Продолжить со второго шага.

Выполнение прерывается либо при нахождении решения, либо после заданного числа итераций[19].

Приложения

Доподлинно неизвестно, кто первым привел математическую формулировку задачи о ранце. Одно из первых упоминаний о ней можно найти в статье Джорджа Балларда Мэтьюса (англ.)русск.[20][21], датированной 1897 годом. Интенсивное изучение данной проблемы началось после публикации Д. Б Данцигом в 1957 году книги «англ. Discrete Variable Extremum Problem»[22], особенно в 70—90-е годы XX века, как теоретиками, так и практиками[2]. Во многом интерес был вызван достаточно простой формулировкой задачи, большим числом её разновидностей и свойств и в то же время сложностью их решения. В 1972 году данная задача вошла в список М. Карпа NP-полных задач (статья англ. «Reducibility Among Combinatorial Problems»)[23].

Наглядная интерпретация задачи о ранце привела к тому, что она нашла применение в разных областях знаний: в математике, информатике и на стыке этих наук — в криптографии. В одной из работ по вычислительной лингвистике[24] предложена формулировка задачи автоматического реферирования текстов (англ.)русск., частный случай которой соответствует постановке задачи о ранце.

На основе задачи о ранце был создан первый алгоритм асимметричного шифрования. Впервые идея криптографии с открытыми ключами была представлена Уитфилдом Диффи и Мартином Хеллманом на Национальной компьютерной конференции (англ. National Computer Conference) 1976 года[25][26].

Также задача о рюкзаке может служить моделью для большого числа промышленных задач[2][27]:

  • Размещение грузов на складе минимальной площади.
  • Раскройка ткани — из имеющегося куска материала получить максимальное число выкроек определённой формы.
  • Расчет оптимальных капиталовложений.

Задача о ранце в криптографии

В 1978 году Ральф Меркл и Мартин Хеллман разработали первый алгоритм для обобщённого шифрования с открытым ключом — криптосистему Меркла — Хеллмана, построив её на основе задачи о ранце. Они опубликовали одностадийный (англ. singly-iterated) и мультистадийный (англ. multiply-iterated) варианты, а алгоритм мог быть использован только для шифрования. Но Ади Шамир адаптировал его и для использования в цифровых подписях[28].

В дальнейшем были предложены и другие криптосистемы на основе задачи о ранце, часть из которых являются модификацией криптосистемы Меркла — Хеллмана. Известные криптосистемы[29]:

  • Рюкзак Грэма — Шамира
  • Рюкзак Гудмана — Маколи
  • Рюкзак Наккаша — Стерна
  • Рюкзак Шора — Ривеста

Шифрование с помощью задачи о ранце

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

Определение. Рюкзачным вектором A=(a1,...,an){\displaystyle A=(a_{1},...,a_{n})} назовём упорядоченный набор из n предметов, где ai{\displaystyle a_{i}} — вес i{\displaystyle i}-го предмета[30].

Рюкзачный вектор является открытым ключом. Для шифрования открытого текста его разбивают на блоки длиной n{\displaystyle n} бит, при этом каждый бит определяет наличие предмета в рюкзаке (например, открытый текст (111100){\displaystyle (111100)} соответствует наличию первых четырёх из шести возможных предметов в рюкзаке). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие[28].

После этого высчитывается суммарный вес предметов в рюкзаке для данного открытого текста, и передаётся в качестве шифротекста[28].

Пример шифрования данным алгоритмом:

Пусть задан рюкзачный вектор A=(3 4 6 7 10 11){\displaystyle A=(3\ 4\ 6\ 7\ 10\ 11)} с длиной n=6{\displaystyle n=6}.

Открытый текст 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Вещи в рюкзаке 3 4 6 7 10 6 7 11
Шифротекст 3 + 4 + 6 + 7 + 10 = 30 6 + 7 = 13 0 11

Примечания

  1. ↑ Silvano, 1990, p. 1.
  2. ↑ 1 2 3 Silvano, 1990, p. 2.
  3. ↑ 1 2 Kellerer, Pferschy, Pisinger, 2004, p. 127.
  4. ↑ 1 2 Kellerer, Pferschy, Pisinger, 2004, p. 147.
  5. ↑ Silvano, 1990, p. 157.
  6. ↑ G. Gallo, P. L. Hammer, B. Simeone Quadratic knapsack problems (англ.) // Mathematical Programming Studies. — 2009. — 24 февраль (vol. 12). — P. 132-149. — ISSN 0303-3929.
  7. ↑ 1 2 Bretthauer, Shetty, 2002.
  8. ↑ Окулов, 2007, pp. 92-93.
  9. ↑ Окулов, 2007, pp. 101-105.
  10. ↑ 1 2 3 4 5 Martello S., Toth P. Knapsack problems: algorithms and computer implementations. — John Wiley & Sons Ltd., 1990. — С. 29,50. — 296 с. — ISBN 0-471-92420-2.
  11. ↑ Бурков, Горгидзе, Ловецкий, 1974, с. 225.
  12. ↑ 1 2 3 Романовский И.В. Алгоритмы решения экстремальных задач. — Наука, 1977. — С. 252-259. — 352 с.
  13. ↑ Стивен С. Скиена. Алгоритмы. Руководство по разработке. — 2-e. — СПб: БХВ-Петербург, 2011. — С. 448-451. — 720 с. — ISBN 978-5-9775-0560-4.
  14. ↑ 1 2 Новиков, 2001, с. 12.
  15. ↑ 1 2 Kellerer, Pferschy, Pisinger, 2004.
  16. ↑ Dantzig G. B. Discrete-Variable Extremum Problems // Oper. Res. — Institute for Operations Research and the Management Sciences, 1957. — Vol. 5, Iss. 2. — P. 266–277. — ISSN 0030-364X; 1526-5463 — doi:10.1287/OPRE.5.2.266
  17. ↑ Ariel Kulik, Hadas Shachnai There is no EPTAS for two-dimensional knapsack // Information Processing Letters. — 2010-07-31. — Т. 110, вып. 16. — С. 707–710. — DOI:10.1016/j.ipl.2010.05.031.
  18. ↑ Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. Применение генетических алгоритмов к решению задач дискретной оптимизации. — 2007. — Нижний Новгород.
  19. ↑ 1 2 3 4 5 С. М. Авдошин, А. А. Савельева. Криптоанализ: современное состояние и перспективы развития (рус.). — С. 38.
  20. ↑ G. B. Mathews On the partition of numbers (англ.). — 1897. — P. 486-490.
  21. ↑ Kellerer, Pferschy, Pisinger, 2004, p. 3.
  22. ↑ Kellerer, Pferschy, Pisinger, 2004, p. 9.
  23. ↑ Р. Карп Reducibility Among Combinatorial Problems (англ.). — 1972.
  24. ↑ Riedhammer et al, 2008, pp. 2436.
  25. ↑ Шнаер, 2002, p. 19.2.
  26. ↑ Габидулин, Кшевецкий, Колыбельников, 2011.
  27. ↑ Бурков, Горгидзе, Ловецкий, 1974, p. 217.
  28. ↑ 1 2 3 4 Шнаер, 2002, p. 19.1.
  29. ↑ Kin Ming Lai. Knapsack Cryptosystems: The Past and the Future (рус.). — 2001.
  30. ↑ Саломаа, 1995, p. 103.

Литература

на русском языке
  1. Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 160–163. — 576 с. — ISBN 978-5-8459-0987-9
  2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-ое. — М.: «Вильямс», 2006. — С. 456-458. — ISBN 0-07-013151-1.
  3. Роберт Седжвик. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. — 3-е. — Россия, Санкт-Петербург: «ДиаСофт», 2002. — С. 688. — ISBN 5-93772-047-4, 0-201-35088-2.
  4. Бурков В. Н., Горгидзе И. А., Ловецкий С. Е. Прикладные задачи теории графов / под ред. А. Я. Горгидзе — Тбилиси: Вычислительный центр АН СССР, 1974. — 231 с.
  5. В. Н. Бурков, Д. А. Новиков. Элементы теории графов. — 2001. — С. 28.
  6. С. Окулов. Программирование в алгоритмах. — 1-е. — Бином. Лаборатория знаний, 2007. — С. 384. — ISBN 5-94774-010-9.
  7. Б. Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms, and Source Code in C. — 2-ое. — Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  8. А. Саломаа. Криптография с открытым ключом = Public-Key Cryptography. — М.: Мир, 1995. — С. 102-150. — ISBN 5–03–001991–X.
  9. Н. Коблиц. Курс теории чисел в криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 254. — ISBN 5-85484-014-6.
  10. Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Защита информации: учебное пособие — М.: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
  11. Осипян В. О. О системе защиты информации на основе проблемы рюкзака // Известия Томского политехнического университета [Известия ТПУ]. — 2006. — Т. 309, № 2. — С. 209-212.
на английском языке
  1. Silvano Martelo, Paolo Toth. Knapsack problems. — Great Britain: Wiley, 1990. — 306 с. — ISBN 0-471-92420-2.
  2. Kellerer H., Pferschy U., Pisinger D. Knapsack Problems — Springer Science+Business Media, 2004. — 548 p. — ISBN 978-3-642-07311-3 — doi:10.1007/978-3-540-24777-7
  3. K. Riedhammer, D. Gillick, B. Favre, and D. Hakkani-Tür Packing the Meeting Summarization Knapsack. — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.
  4. Bretthauer K. M., Shetty B. The nonlinear knapsack problem – algorithms and applications // European Journal of Operational Research — Elsevier, 2002. — Vol. 138, Iss. 3. — P. 459–472. — ISSN 0377-2217; 1872-6860 — doi:10.1016/S0377-2217(01)00179-5

Ссылки

wikiredia.ru

11.2. Система шифрования методом укладки рюкзака. (Ранцевая система шифрования).

Классическая задача о рюкзаке формулируется следующим образом. Пусть имеется множество предметов с указанием их веса, некоторые представители которого укладываются в рюкзак. Зная вес наполненного рюкзака (без учета веса самого рюкзака), необходимо определить содержимое рюкзака.

Опишем задачу о рюкзаке с использованием вектора рюкзака и вектора данных. Вектор рюкзака представляет собой набор из n различных чисел (аналогично множеству различных предметов, укладываемых в рюкзак), т.е. . Вектор данных – множество двоичных символов, т.е., где. Веснаполненного рюкзака есть сумма подмножества компонентов вектора рюкзака, определяемая как

.

Тогда задачу о рюкзаке можно сформулировать следующим образом: при заданном S и известном определить.

Пример 11.2.1. Пусть . Пусть. Требуется определить. Методом проб можно установить, что

.

Тогда .

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

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

,

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

(11.3)

где .

Пример 11.2.2. Пусть , а. Очевидно, чтоявляется быстровозрастающим. Тогда из (11.3) следует, что.

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

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

Первоначально образуем быстро возрастающий вектор и выберем простое числоP, при котором выполняется следующее неравенство

.

Затем случайным образом выберем число и вычислим, такое что

. (11.4)

Вектор и числаявляются секретными. Затем из элементовсформируем вектор, компоненты которого определяются как

.

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

,

которое и передается по открытому каналу связи.

Санкционированный пользователь получает S и, используя соотношение (11.4), превращает его в вида

.

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

Пример 11.2.3. Предположим, что абонент A хочет создать общедоступную и конфиденциальную схему шифрования. Первоначально он создает быстровозрастающий вектор , размерность которогоn определяются потребностями абонента. Затем он определяет число P из условия

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

Образовав секретный ключ, абонент A переходит к формированию общедоступного ключа, в качестве которого выступает вектор , содержащий «лазейку»:

,

так что

.

Предположим, что пользователь B собирается послать сообщение абоненту A. Если , то пользовательB создает следующее число

и передает его пользователю A. Последний преобразует его в по алгоритму

,

которое, в свою очередь, определяется как . Учитывая, что вектор является быстровозрастающим, на основании алгоритма (11.3) абонентA легко восстановит вектор .

Поскольку , то. Далее

,

следовательно, . Аналогично для:

,

то . Продолжая следовать алгоритму (11.3), получаем. Так что в итоге имеем.

Схем Меркла–Хэллмана в настоящее время считается взломанной, поэтому для реализации криптосистем с открытыми ключами используется алгоритм RSA.

studfiles.net


Смотрите также