Оптимизационное решение / алгоритм размещения жильцов в домах (комбинации)

Question

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

Вот входные данные:

n домов: h1, h2, ..., hn, м арендаторов: т1, т2, ..., тм

выбор: Каждый арендатор должен выбрать до 3 мест в соответствии с приоритетом 1-первый приоритет, 2-секундный приоритет, 3-й приоритет. Каждый арендатор должен выбрать до 3 соседей в соответствии с приоритетом 1-первый приоритет, 2-секундный приоритет, 3-й приоритет (может быть также, кто НЕ должен жить рядом с ...)

Например: t1 хочет жить в домах: самый высокий приоритет (1): h12 средний приоритет (2): h5 самый низкий приоритет (3): h3

t1 хочет, чтобы следующие были его соседями: самый высокий приоритет (1): t5 средний приоритет (2): t15 самый низкий приоритет (3): t6

• весовой коэффициент может рассматриваться (не обязательно) как баланс между требуемым местоположением и соседями, например, 0 местоположений и 1 соседей для арендатора, который хочет, чтобы его друзья были закрыты для него, но не заботится о том, где будет находиться его дом быть локализованным, или 1 местоположение и 0 соседей для арендатора, который хочет иметь приоритетное местоположение и не заботится о том, кто его соседи (0,5 местоположения и 0,5 соседа для арендатора, который хочет, чтобы алгоритм равным образом уравновешивал свои выборы)

Я ищу алгоритм оптимизации, чтобы обеспечить оптимальное решение (если оно существует) для размещения арендаторов в необходимых домах в соответствии с входными данными. Что это за проблема? Оптимизация? Как лучше всего решить эту проблему? линейное программирование? Примечание: входные данные могут быть изменениями для упрощения решения или для того, чтобы позволить алгоритму сходиться более надежно.

Как мне математически сформулировать: (1) Близость расположения домов для представления домов (остовное дерево?), Как я могу представить дома, которые находятся близко или далеко? (2) Соседние отношения (арендатор хочет жить рядом с Х, но не рядом с Y) с приоритетами? Как мне записать эти условия / ограничения в виде уравнений?

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

Помощь очень ценится!

Я могу использовать Matlab, Python или любой другой язык программирования / платформу для проверки идей.

Answer 1

Одним из вариантов будет использование программирования ограничений для решения этой проблемы. Вот простая модель MiniZinc (https://www.minizinc.org) для случая, когда имеется одинаковое количество (= 5) домов и арендаторов:

% data
int: n = 5;
set of int: HOUSE = 1..n;
set of int: PEOPLE = 1..n;

array[PEOPLE, HOUSE] of 0..3: houseValue = array2d(PEOPLE, HOUSE, [
    0, 2, 3, 1, 0,
    0, 2, 3, 1, 0,
    0, 2, 3, 0, 1,
    0, 3, 2, 1, 0,
    0, 2, 1, 3, 0]);
array[PEOPLE, PEOPLE] of 0..3: neighbourValue = array2d(PEOPLE, PEOPLE, [
    0, 2, 3, 1, 0,
    0, 0, 3, 1, 2,
    2, 0, 0, 1, 3,
    0, 3, 2, 0, 1,
    1, 2, 3, 0, 0]);

% model
include "globals.mzn";

% decision variables - who lives in each house?
array[HOUSE] of var PEOPLE: tenant;

% constraint - exactly one person lives in each house
constraint alldifferent(tenant);

var int: objHouse = 
    sum(h in HOUSE where tenant[h] > 0)(houseValue[tenant[h], h]);
var int: objNeighbours = 
    sum(h in HOUSE where h > 1)(neighbourValue[tenant[h], tenant[h-1]]) + % left neighbour
    sum(h in HOUSE where h < n)(neighbourValue[tenant[h], tenant[h+1]]); % right neighbour

solve 
maximize objHouse + objNeighbours;

output ["obj = \(objHouse + objNeighbours)\n"] ++ ["objHouse = \(objHouse)\n"] ++ ["objNeighbours = \(objNeighbours)\n"] ++ ["tenant = \(tenant)"];

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

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

Answer 2

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

Если у вашей проблемы были только приоритеты типа "Я хочу этот дом". Это было бы проблемой назначения. Вы можете решить это с помощью венгерского (также называемого Kuhn-Munkres) алгоритма.

Идея состоит в том, чтобы построить двойной граф с домами с одной стороны и арендаторами с другой. Вы ставите грани между каждой парой дом / арендатор с весами в соответствии с приоритетами (то есть 1, если хотите этот дом, иначе 0). Вы также должны создать узлы приемника на стороне с узлом less, потому что этот алгоритм выделит ровно один дом каждому выбранному весу максимизатора. Например, если n> m, создайте n-m призрачных арендаторов (со всеми ребрами с весом 0), чтобы соответствовать левым пустым домам. Этот алгоритм имеет сложность O (N ^ 3) с N = max (n, m).

Приоритеты типа "мне нравится этот сосед" довольно сложны для обработки. Ограничение, которое они приносят, похоже на проблему продавца. Каждый арендатор хочет иметь лучшего соседа (с весом A / B = A хочет, B + B хочет A). К сожалению, эта проблема является NP-полной, то есть вам нужно протестировать большую часть комбинаторики, чтобы найти оптимальное решение (O (! N)).

Если N очень большое, можно использовать эвристическое решение. Вы соглашаетесь с хорошим решением, которое может быть не лучшим. Например, используя жадный алгоритм: сначала вы собрали пару соседей с лучшим весом и т. Д.

РЕДАКТИРОВАТЬ: Если вы действительно хотите оптимальное решение. Это та, которая максимизирует фитнес-функцию F (исходя из приоритета весов).

Сначала вычислите для каждого арендатора i потенциальное "счастье" Pi , которое он может иметь, что составляет сумму

• лучший вес дома,
• два лучших веса соседа.

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

Теперь вы хотите изучить дерево возможностей для улучшения Fmax, которое на данный момент является F0. Но вы не можете исследовать полное дерево (! N возможностей). Таким образом, вы должны "обрезать" какую-то ветку. Это означает, что каждый раз, когда вы размещаете арендатора в доме, вы рассчитываете потенциал этой ветви. Для каждого арендатора вы проверяете, какое желание больше не может быть выполнено, и суммируете лучшие оставшиеся варианты. если F <= Fmax, эта ветвь не представляет интереса, поэтому не исследуйте ее. Если вы наконец достигли конца ветви и F> Fmax, вы нашли лучшее решение, обновите Fmax.

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