Доброго времени суток, коллеги.
Этой статьей я продолжаю цикл посвященный EvoJ — Java фреймворку для решения задач генетическим алгоритмом.
В своей предыдущей заметке я познакомил читателей Хабра с основными принципами работы с EvoJ.
Сегодня мы рассмотрим, как при помощи EvoJ можно решить задачу упаковки в контейнеры.
Постановка задачи
Если в двух словах, то задача упаковки в контейнеры ставится следущим образом: имеется набор контейнеров определенного объема, и набор предметов, которые в эти контейнеры требуется уложить (в простейшем случае пространственной ориентацией пренебрегают). Цель — уложить все предметы, использовав при этом как можно меньше контейнеров.
Выбор способа описания решения
Чтобы воспользоваться EvoJ мы должны неким образом описать переменные составляющие решение задачи в виде Java-интерфейса.
Первый вариант, это описать каждый контейнер, как список предметов в него попавших:
public interface Solution { List<List<Integer>> getContainers(); } По сути это список контейнеров, каждый из которых описан списком деталей, которые в него попали.
Не смотря на то, что EvoJ позволяет описать решение таким образом, такой подход заставит принимать дополнительные усилия по отсеву противоречивых решений, когда один и тот же предмет попадает в несколько контейнеров.
Более простым подходом будем описать в какой контейнер попал каждый конкретный предмет:
public interface Solution { @ListParams(length = "itemsCount", elementRange = @Range(strict = "true", min = "0", max = "lastBinIndex"), elementMutationRange = @MutationRange(value = "100%")) List<Integer> getBinIndices(); } Здесь решение представлено, как список, каждый элемент которого указывает в какой контейнер попал соответствующий предмет.
Этот интерфейс так же демонстрирует некоторые приемы EvoJ. Во-первых, длина списка, и максимальное значение его элементов задано не конкретными числами, а именами переменных. Это позволяет не завязываться на конкретные значения в compile-time.
Во-вторых, в данной задаче важным элементом является указание MutationRange=100%. Вспомним, что в списке лежат номера контейнеров, и если оставить радиус мутации по умолчанию, то в ходе мутации предмет сможет перемещаться только между близко расположенными контейнерами, что резко снизит эффективность эволюции.
Выбор фитнесс-функции
Натуральной фитнесс-функцией будет количество занятых контейнеров, однако такой подход не очень эффективен. Проиллюстрируем почему.
Решение 1
Решение 2
В обоих решениях занято три контейнера. Но, очевидно, что второе решение предпочтительнее, так как ему остается всего одна мутация до того, чтобы стало занято два контейнера. Конечно, и из первого решения в результате мутации может получиться решение, где заняты всего два контейнера, однако вероятность этого гораздо ниже.
Таким образом, количества занятых контейнеров недостаточно для полноценной оценки «приспособленности» решения. Чтобы исправить ситуацию введем дополнительный показатель — сумму квадратов свободного места в контейнерах (простая сумма свободного места в обоих случаях окажется одинаковой).
Может случиться так, что какие-нибудь из контейнеров окажутся перегруженными. С нашей точки зрения такое решение не валидно и можно было бы избавляться от подобных членов генофонда выставляя им рейтинг null. С другой стороны перегруженность может быть небольшой, в то время как решение занимает не так много контейнеров и есть шанс, что в результате мутации или удачного скрещивания перегузка исчезнет.
Введем третий показатель для оценки решения — сумму квадратов перегрузок.
Таким образом, чтобы адекватно оценить решение, требуется три числа. Можно было бы свести их в некий интегральный показатель, однако EvoJ позволяет возвращать из fitness-функции любое Comparable значение. Заведем свой класс для этого.
public class PackRating implements Comparable { private int binsUsed; private int score; private int overflow; public PackRating(int binsUsed, int score, int overflow) { this.binsUsed = binsUsed; this.score = score; this.overflow = overflow; } public int compareTo(Object o) { PackRating other = (PackRating) o; if (this.overflow != other.overflow) { return other.overflow - this.overflow; } if (this.binsUsed != other.binsUsed) { return other.binsUsed - this.binsUsed; } return this.score - other.score; } public int getBinsUsed() { return binsUsed; } public int getOverflow() { return overflow; } public int getScore() { return score; } } Здесь поле binsUsed — количество занятых контейнеров. Поле score — сумма квадратов свободного места в контейнерах. И, наконец, поле overflow — сумма квадратов перегрузок контейнеров.
Процедура сравнения, считает любое решение без перегрузки лучше любого решения с перегрузкой, при равенстве перегрузок начинают приниматься во внимание занятые контейнеры (меньше — лучше), и, наконец, если занято одинаковое число контейнеров, начинает приниматься во внимание поле score (больше — лучше).
Осталось имплементировать fitness-функцию. Сделам это, как и в примерах из предыдущей статьи, расширив класс AbstractSimpleRating.
public class BinPackRatingCalculator extends AbstractSimpleRating<Solution> { private int[] items; private int[] bins; public BinPackRatingCalculator(int[] items, int[] bins) { this.items = items; this.bins = bins; } @Override protected Comparable doCalcRating(Solution solution) { int[] tmpBins = new int[bins.length]; int score = 0; int overflow = 0; int binsUsed = 0; final List<Integer> indicex = solution.getBinIndices(); for (int item = 0; item < indicex.size(); item++) { Integer binIndex = indicex.get(item); tmpBins[binIndex] += items[item]; } for (int bin = 0; bin < tmpBins.length; bin++) { int dl = bins[bin] - tmpBins[bin]; final int dl2 = dl * dl; if (dl < 0) { overflow += dl2; } else { score += dl2; } if (tmpBins[bin] > 0) { binsUsed++; } } return new PackRating(binsUsed, score, overflow); } } Не будем подробно разбирать этот код, он просто вычисляет наши fitness-показатели и возвращает их в виде экземпляра класса PackRating.
Заставляем все работать
Создадим новый класс с main-методом:
public static void main(String[] args) { int[] items = {3, 2, 4, 4, 5, 3, 4, 5, 6}; int[] bins = {8, 8, 8, 8, 8, 4, 12, 12, 8, 6}; Map<String, String> context = new HashMap<String, String>(); context.put("itemsCount", Integer.toString(items.length)); context.put("lastBinIndex", Integer.toString(bins.length - 1)); DefaultPoolFactory factory = new DefaultPoolFactory(); GenePool<Solution> pool = factory.createPool(200, Solution.class, context); DefaultHandler handler = new DefaultHandler(new BinPackRatingCalculator(items, bins), null, null, null); handler.iterate(pool, 40); Solution bestSolution = pool.getBestSolution(); showSolution(bestSolution, bins, items); } Здесь массив items содержит условные размеры предметов. Массив bins — условную вместимость имеющихся контейнеров. Особенностью приведенного кода является использование контекста с переменными для указания длины списка из интерфейса Solution и ограничения возможных значений. В остальном, код повторяет то, что было показано в предыдущей статье: создание фабрики популяций, создание популяции из 200 особей, создание хэндлера и осуществление 40 итерации.
Размер популяции и количество итерации подобраны экспериментальным путем.
Приведенный код выполняется довольно быстро, и даже 1000 итераций над популяцией в 200 решений на моем четырехлетнем ноутбуке выполняется около двух секунд.
Послесловие
Мы рассмотрели, как можно применить генетический алгоритм к решнию одной из классических NP-сложных задач. Следует сделать замечание, что генетический алгоритм не гарантирует нахождения самого лучшего решения, но позволяет очень неплохо к нему приблизиться, что в большинстве случаев является достаточным.
Для заинтересовавшихся здесь выложены исходники рассмотренного примера в виде Maven-проекта.
Спасибо за внимание.
Автор: tsvetkovpa
