Алгоритм автоматической ширины ленты

Question

Буду очень признателен за некоторые комментарии по поводу этой практической проблемы.

Краткое описание. У меня есть переменное количество ссылок, которые могут быть использованы для создания данной ширины ремня. Вопрос в том, сколько у каждой ссылки. Критерии выбора: лучше использовать более длинные предметы.

Пример. Допустим, мы хотим создать ширину ремня, W = 1024,0 Одна из моделей имеет следующие длины ссылок: L = [34,0, 65,0, 96,0, 126,0]

Вопрос в том, сколько из каждой ссылки сделать шириной.

Вот несколько подходов, которые я попробовал.

1. Жадный (выберите самый длинный 1-й для соответствия критериям) с = [0,0,0,8] где с - количество каждого предмета. Это оставляет разрыв 16,0, и я не могу соответствовать даже 1 из самых маленьких предметов. Жадный это легко, но не хорошо.

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

3. Метод ранцев Не совсем подходит, потому что это основано на заданном количестве предметов.

4. Задача подмножества сумм Это подкласс рюкзака, но я не смог заставить его работать.

5. Проблема с бункером Звучит похоже, но я не смог применить это к моей проблеме.

6. Грубая сила (случайный выбор) Странно, этот находит много точных совпадений. Я использую простой полином от подсчета в качестве рейтинга. рейтинг = n [0] + n [1] * 2 + n [2] * 3 + n [4] ** 4 + ... Одним из решений от грубой силы является [4, 0, 4, 4] дает ровно 1024. Проблема в том, что этот метод часто предлагает другой выбор, поэтому он не идеален.

7. Исчерпывающий поиск Непрактично, потому что есть слишком много вариантов.

8. Имитация отжига От успеха грубой силы это выглядит как хорошая альтернатива. Может кто-нибудь указать мне простой пример (пожалуйста, не другой коммивояжер).

9. Генетический и рой частиц Не уверен в этом.

Теперь я застрял и разочарован. Есть ли прямой алгоритм, который можно использовать для этой проблемы?

Answer 1

Хорошо, если я правильно понимаю проблему, вам нужно выбрать x1 объекты длиной 34, x2 объекты длины 65 и т. Д., И т. Д., Так, чтобы сумма всех этих объектов была равна W, но естьуклон в сторону более длинных объектов (в данном случае 126,0 будет наиболее предпочтительным объектом).

Я полагаю, вы могли бы создать целевую функцию, подобную этой:

f (x1, x2), .., xn) = b1 * x1 * L1 + b2 * x2 * L2 + ... + bn * xn * Ln - p * (W - x1 * L1 + x2 * L2 + ... + xn * Ln)^ 2

Где b1 - bn - смещения этих объектов (положительные числа благоприятны, отрицательные числа означают, что объект обесценен), L1 - Ln - длины этих объектов, а p - штраф за отсутствиеточно W (если это должно быть точно W, p - это inf.)

(Мы могли бы также поместить его в матричную форму как f (X) = b ^ T * X * L - p * (W - I^ T * X * L) ^ 2, где b и L - векторы, X - квадратно-диагональная разреженная матрица из x1, x2, ..., xn I - вектор из 1, а T - транспонирование.)

Так что цель то максимаИзмените f, выполнив поиск по n-кортежному набору целых чисел x1, x2, ..., xn.

whew Хорошо, теперь я думаю, что понимаю проблему.:)

Это какая-то целочисленная задача программирования, но я не думаю, что она точно квалифицируется как квадратично-целочисленная задача программирования.Возможно, кто-то еще знает, что это такое.

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

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

Я недостаточно знаю одругие методы решения для предоставления комментариев.