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


Алгоритм решения задачи о рюкзаке ( версия 2, исправленная) / Хабр

Ниже приведен алгоритм точного решения целочисленной задачи о рюкзаке. Предлагаемый алгоритм требует меньше вычислительных ресурсов и возможно несколько проще алгоритма динамического программирования (ДП). Первая версия описания алгоритма было послана мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую: Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.Тем не менее я решил ознакомить сообщество с алгоритмом, т.к. в известных мне учебниках по дискретной математике я его не обнаружил (возможно плохо искал). В первой версии алгоритма была ошибка, указанная мне пользователем wataru. За это ему большое спасибо. Я постарался эту ошибку устранить. До алгоритма я дошел самостоятельно, так что надеюсь ничьих прав не нарушаю. Возможно кому нибудь описание будет интересно и пригодится.

Введение

Задача о одномерном рюкзаке (0-1 knapsack) является классической задачей дискретной оптимизации [1],[2]. Данная задача и ее варианты широко используются для моделирования большого числа практических задач. В общем виде задачу можно сформулировать так: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес. Более точно, пусть P(i) > 0 и W(i) > 0 – соответственно стоимость и вес i-го предмета, где i = 1,2,3,…,N , а N– число предметов. Требуется найти такой булев вектор X размерностью N, гдеX(i) = 1, если предмет с номером i положен в рюкзак; X(i) = 0, если предмет с номером i не положен в рюкзак; чтобы была максимальной сумма Σ P(i) X(i) и выполнялось неравенство Σ W(i) X(i) ≤ C, где C > 0 – вместимость рюкзака. Существуют различные точные и приближенные алгоритмы решения задачи о рюкзаке. К точным алгоритмам относятся:
  • полный перебор
  • метод ветвей и границ
  • динамического программирования (ДП)
. Приближенными алгоритмами являются жадный (ЖА) и генетический (ГА). Сравнение различных методов решения задачи о рюкзаке широко представлено в литературе и интернете, поэтому не будем на нем останавливаться и сразу перейдем к делу.Предлагаемый ниже алгоритм можно условно рассматривать как усложнение ЖА и как упрощение алгоритма ДП. Рассмотрим вариант алгоритма решения задачи о рюкзаке при условии, что веса предметов являются натуральными числами, а стоимости предметов являются вещественными числами.

Описание алгоритма решения задачи о рюкзаке с элементами псевдокода

INPUT: // Входные данные Массивы исходных данных (ИД) содержат целые веса W и вещественные стоимости P предметов W(1...N) > 0 и P(1...N) > 0 где N число предметов и C > 0 – вместимость рюкзака.OUTPUT: // Выходные данные Булев массив X(1...N), где X(i) = 1, если предмет с номером i входит в решение, и X(i) = 0, если предмет с номером i не входит в решение.

START // начало алгоритма

Этап 1 // сортировка ИД Сортируем ИД в порядке уменьшения удельной стоимости предметов:P(1) / W(1) >= P(2) / W(2) >= ...>= P(i) / W(i)>=… >= P( N) / W(N) где P(i) > 0 стоимость предмета i , W(i) >0 вес предмета i. В массиве X(1...N) все элементы первоначально = 0. Для снижения потребности в памяти для алгоритма определяем минимальный вес в наборе ИД W_min = min( W )

Этап 2 // инициализация рабочих массивов Создаем массив вещественных чисел LP размерностью (W_min… С) и массив целых чисел LCr размерностью (W_min… С) . Заносим в массив LP и LCr данные первого элемента из отсортированного списка ИД

LP( W(1) ) = P(1) LCr( W(1) ) = 1 где P(1) стоимость и W(1) вес первого предмета в отсортированном списке ИД.

Этап 3 // заполнение рабочих массивов

FOR i = 2 TO N // цикл по оставшимся элементам ИД Пусть W(i) и P(i) вес и стоимость текущего элемента ИД. Создаем пустой массив вещественных чисел Clone размерностью (W_min… С). Вносим в массив Clone стоимость текущего элемента ИД Clone( W(i) ) = P(i). Копируем в массив Clone ненулевые данные из массива LP добавляя стоимость P(i) текущего элемента и увеличивая его индекс на его вес W(i), при условии что индекс в Clone не превзойдет вместимости рюкзака C.FOR j = W_min TO ( C - W(i) ) IF LP(j) >0 THEN Clone( j + W(i) ) = LP(j) + P(i) END IF NEXT // конец цикла копирования Проводим модификацию массивов LP, LCr на основе данных массива Clone. Обновляем в массивах LP,LCr только те элементы стоимость которых в Clone больше чем в LP. FOR j = W_min TO C IF Clone( j ) >0 AND Clone( j ) > LP( j ) THEN LP( j ) = Clone( j ) LCr( j ) = i END IF NEXT // конец цикла модификации LP, LCr NEXT // конец цикла по оставшимся элементам Этап 4 // формирование результата, обратный спуск В массиве LP находим максимальное значение стоимости Pmax = MAX( LP ), это стоимость найденного оптимального решения. Индекс найденного в массиве элемента равен весу решения, обозначим его Wr, т.е. LP( Wr) = Pmax. Внесем первый найденный элемент в X: X( LCr( Wr ) ) = 1 далее// цикл формирование результата UNTIL Wr > 0 // если Wr = 0, результат сформирован // уменьшаем вес решения на вес добавленного в результат предмета Wr = Wr - W( LCr( Wr ) ) // Проверяем, не внесен ли уже следующий элемент в X IF X(LCr( Wr ) = 0 then // не внесен X( LCr( Wr ) ) = 1 // вносим ELSE // внесен Выходим из цикла UNTIL и повторяем этапы 2, 3, 4 ( только на этапе 2 массивы LP, LCr не создаем, a заполняем нулями ). Повторять этап 1 (сортировка ИД) не нужно. Это по существу рекурсия, но из за предварительной сортировки ИД, она будет не глубокой. На некоторых наборах ИД рекурсии вообще может не быть. При повторе расчетов рассматриваем только те ИД, индекс которых меньше LCr( Wr ) и снижаем требуемый размер рюкзака до достигнутого веса Wr. N_NEW = LCr( Wr ) -1 C_NEW = Wr GOTO этап 2 END IF NEXT // конец цикла формирование результата FINISH // конец алгоритма Стоимость найденного решения Σ P(i) X(i), вес Σ W(i) X(i). Правильность расчета итоговой стоимости рюкзака легко доказывается по индукции. Восстановление оптимального набора предметов, тоже не вызывает затруднений. Представленный алгоритм позволяет получить точное решение целочисленной задачи о рюкзаке.

Итоговые замечания

  1. Общая сложность представленного алгоритма складывается из сложности сортировки ИД и сложности выполнения этапа 3 алгоритма (с учетом числа итераций). Время работы этапа 3 пропорционально числу предметов на вместимость рюкзака (N * C). Заранее определить число итераций достаточно сложно. Число итераций может варьироваться от 0 до числа предметов в решении Σ X(i). При каждой итерации возникающей на этапе 4 объем вычислений на этапах 2, 3 уменьшается. Верхняя оценка временной сложности всего алгоритма не превышает N * C * ( число итераций + 1)
  2. Потребность алгоритма в памяти пропорциональна вместимости рюкзака C и не зависит от числа предметов во входном наборе данных N, что выгодно отличает его от метода ДП.
  3. Внутренние циклы этапа 3 легко выполняются параллельно.
  4. При большом разбросе удельной стоимости предметов, если на этапе 3 алгоритма в верхней части массива LP перестают происходить изменения, можно прерывать этап 3 и не рассматривать оставшиеся предметы с низкой удельной стоимостью.
  5. Если вместимость рюкзака С, достаточно велика, так что массивы размерности С не могут быть созданы по техническим причинам или веса предметов являются вещественными числами, то предложенный алгоритм может быть легко модифицирован заменой массивов связанными списками.
  6. Является ли данный алгоритм полиномиальным или нет, я не берусь судить.
Литература
  1. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985.
  2. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ. М.: Издательский дом «Вильямc», 2005.

habr.com

Лекция №7 Алгоритмы с открытыми ключами

Концепция криптографии с открытыми ключами была выдвинута Диффе и Хэлменом и независимо от них Мерклом в 1976 году. Их вкладом в криптографию было убеждение, что ключи можно использовать парами(ключ зашифрования и ключ расшифрования), и что может быть не возможно получить один ключ из другого.

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

Алгоритм открытых рюкзаков(укладки ранца)

Первым алгоритмом для обобщенного шифрования с открытым ключом стал “алгоритм рюкзака”, разработанный Мерклом и Хелменом. Проблемы рюкзака состоит в следующем:

Дано n предметов различной массы, можно ли взять только часть предметов из них, таким образом, чтобы суммарная масса была равно некоторому числу S.

Mi – масса предметов, i=1,n

S = b1M1+b2M2+…+bnMn=Summ(от 1 до n)biMi

Bi = 0 или 1

1 : предмет кладут в рюкзак.

0: предмет не кладут в рюкзак.

Например, массы предметов могут иметь значения: 1, 5, 6, 11, 14, 20(2^6).

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

В основе алгоритма рюкзака лежит идея шифровать сообщения, как решение проблем набора рюкзака.

M : 111001 010110 011000

K: 156111420 156111420 56111420

C: 32 30 11(делим по 6 числе в блоке верхней строки, затем внизу выбираем из тех, чьими числами является единица и высчитываем число)

Главная идея состоит в том, что существуют 2 различные проблемы рюкзака с одни и тем же решением:

  1. Решается за экспоненциальное время.

  2. Решается за линейное время.

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

Сверх возрастающие рюкзаки

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

Пример:

Последовательность : 2, 3, 6, 13, 27, 52

S= 70

70>52 =>(берем 52)

70-52=18

18<27=>(НЕ БЕРЕМ 27)

18>13=>(берем 13)

18-13=5

5<6=>(не берем 6)

И т.д. получаем: 2, 3, 6, 13, 27, 52= 1, 1, 0, 1, 0, 1

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

Пример: Зашифрование и Расшифрование.

Этап 1. Создание открытого ключа из закрытого.

Чтобы получить нормальную последовательность рюкзака необходимо взять сверх возрастающую последовательность(например: 2, 3, 6, 13, 27, 52) и умножить по модулю m все значения на число n. Значения модуля должно быть больше суммы всех численных последовательностей(например m=105). Множитель n должен быть взаимно простым числом с модулем(например n=31).

2*31mod105=62

3*31mod105=93

6*31mod105=81

13*31mod105=88

27*31mod105=102

52*31mod105=37

K1: {62, 93, 81, 88, 102, 37}

Этап 2 Шифрование.

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

M=011000 110101 101110

C=174 280 333

Этап 3 Расшифрование.

Законный получатель сообщения C знает закрытый ключ K2, а так же значением m(105) и n(31), использованные для превращения ее в нормальную последовательность рюкзака. Для расшифрования сообщения получатель вначале должен определить значение (n^-1) такое, что (n*n^-1=1(mod105)).

31*n^-1=1(mod105)

31*n^-1=105*k+1(диафантовое уравнение, решаемое в целых числах)

Решается такое уравнение расширенным уравнением Эвклида:

31*n^-1=105*k+1

Прямой ход:

105=31*3+12

31=12*2+7

12=7*1+5

7=5*1+2

5=2*2+1

2=1*2+0

Обратный ход:

1=5-2*2=5-2*(7-5*1)= 5*3-7*2=(12-7*1)*3-7*2=12*3-7*5=12*3-(31-12*3)*5=12*13-31*5=(105-31*3)*13-31*5=105*13-31*44

N^-1=-44=61(mod105)

Значения шифр текста должны быть умножены на n^-1mod105

174*61(mod105)=9 в соответствии с закрытым ключом: 011000

280*61(mod105)=70 в соответствии с закрытым ключом: 110101

333*61(mod105)=48 в соответствии с закрытым ключом: 101110

Для последовательности из 6 элементов не трудно решить задачу рюкзака, даже если она не является сверх возрастающей. Реальные последовательности должны содержать не менее 250 элементов. Длина каждого элемента последовательности должна быть 200 и 400 битами, а длина модуля от 100 до 200 бит. Для получения значений практические реализации используют генератор случайных последовательностей.

studfiles.net

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

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

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

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

Эта задача имеет следующую неформальную простую постановку [4,5]. Имеется рюкзак объемом C и n различных предметов. Каждый предмет i имеет известный объем W_i и стоимость P_i(i=1,\dots,n). В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем C. Форма предметов здесь не учиты.

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

X=(x_1,\dots,x_n)\mbox{, где}\ x_i=\begin{cases}1,\mbox{если предмет помещается в рюкзак,}\\0,\mbox{в противном случаи.}\end{cases}

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

V=\sum_{i=1}^n W_i\le C\mbox{ и }\sum_{i=1}^n P_i=\max

Так как решение задачи можно представить двоичным вектором X= (x_1,\dots, x_n), то очевидно при его поиске можно применить простой ГА со стандартными операторами скрещивания и мутации. Но при этом на каждом шаге итерации надо следить за тем, чтобы новые решения, полученные в результате скрещивания или мутации, удовлетворяли требуемому ограничению V\le C. В случае невыполнения ограничения "неправильное" потенциальное решение должно быть уничтожено, что ведет к сокращению популяции.

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

P(X)=\sum_{i=1}^n x_i\cdot P_i, но в этом случае, как указано выше, есть проблемы с неправильными решениями.

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

  1. В первом случае в фитнесс-функцию вводится дополнительная штрафная функция, которая для неправильных решений дает большие отрицательные значения ЦФ. При этом задача с ограничениями трансформируется в задачу без ограничений путем назначения штрафа для некорректных решений. Фитнесс-функция для каждой особи может быть определена следующим образом f(X)=\sum_{i=1}^n x_i\cdot P_i-Pen(X)

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

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

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

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

    f(X')=\sum_{i=1}^n x_i'P_i, где вектор X'– восстановленная версия исходного вектора X. Здесь следует отметить, по крайней мере, два аспекта. Во-первых, можно использовать различные алгоритмы восстановления. Во-вторых, восстановленные особи могут замещать только некоторую часть исходных особей в популяции. Процент замещаемых особей может варьироваться от 0% до 100% и его значение является важнейшим параметром метода восстановления. В некоторых работах отмечается, что наилучшие результаты получаются при 5%, во всяком случае, лучше, чем в двух крайних случаях – 0% (без замещения) и 100% (любая восстановленная особь заменяет исходную). Ниже приведен простой алгоритм восстановления.

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

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

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

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

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

www.intuit.ru


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