Комбинаторная оптимизация с взаимозависимыми переменными

Это мой первый пост на этих форумах, спасибо за все ответы.Комбинаторная оптимизация с взаимозависимыми переменными

Я разрабатываю приложение Java, в котором я столкнулся с тем, что, как мне кажется, называется «проблемой комбинаторной оптимизации». У меня есть только базовые математические навыки, поэтому попытка исследовать настройку такой проблемы пока не принесла больших результатов.

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

Я заинтересован в выборе подмножества, которое дает максимальную общую стоимость/оценку.

Так, например, полный набор N состоит из следующих переменных и имеют следующие определенные значения, а также отношения к другим переменным:

v1 8 { v2 ; v8 } 
v2 6 { v1 ; v4 } 
v3 9 { } 
v4 7 { v2 ; v5 ; v8 } 
v5 6 { v4 ; v10 } 
v6 8 { v7 } 
v7 5 { v6 } 
v8 9 { v1 ; v4 } 
v9 6 { } 
v10 7 { v5 }

Имея отношение к одному или нескольким другим выбранной переменной означает, что общее значение будет иметь определенный «взлет» - ради этого примера допустим один для каждого отношения. Так выбирая первые пять переменных, как подмножество даст общее значение 30:

v1 8 { v2 ; v8 }  = 8 - 1 = 7 
v2 6 { v1 ; v4 }  = 6 - 2 = 4 
v3 9 { }    = 9 - 0 = 9 
v4 7 { v2 ; v5 ; v8 } = 7 - 2 = 5 
v5 6 { v4 ; v10 }  = 6 - 1 = 5

Это, конечно, не проблема для таких небольших наборов, но я в настоящее время сталкиваются наборы 100К и подмножества 10K - с текущим алгоритмом мой компьютер вычислил решение через 3 дня!

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

Снова благодарим за все ответы!

источник

2016-12-20 Einar Jakob Hovland

К сожалению, эта проблема является NP-трудной для нахождения оптимального решения.

Если бы вы могли решить эту проблему эффективно, вы могли бы решить NP-hard maximum independent set problem, установив для каждой вершины значение 1 и очень большой штраф за каждое ребро.

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

источник

2016-12-20 13:26:43

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

Вы можете видеть, как ваш график представлен в виде графика. Каждый vX является узлом/вершиной с соответствующим значением. Пример v1 - это узел/вершина со значением 8, v2 - узел/вершина со значением 6 и т. Д. Затем между ними есть ребра. Пример v1 имеет 2 ребра: один для v2 и другой для v8. Каждое ребро также может иметь значение (в вашем случае -1).

Итак, если вы используете графики и выбираете v1 - v5: у вас есть 8 + 6 + 9 + 7 + 6 (значение вершины) -1 -1 -1 -1 -1 -1 (значение ребра).

Постарайтесь это увидеть http://jgrapht.org/, чтобы узнать, если это поможет вам.

Также см. Некоторые диаграммы: http://www.people.vcu.edu/~gasmerom/MAT131/graphs.html. Соблюдать самые длинные/кратчайшие алгоритмы (пример: http://www.maxburstein.com/blog/introduction-to-graph-theory-finding-shortest-path/)

источник

2016-12-20 12:17:43 pringi

Для линейной программы решателя, принимать входной сигнал как

v1 8 { v2 ; v8 } 
v2 6 { v1 ; v4 } 
v3 9 { } 
v4 7 { v2 ; v5 ; v8 } 
v5 6 { v4 ; v10 } 
v6 8 { v7 } 
v7 5 { v6 } 
v8 9 { v1 ; v4 } 
v9 6 { } 
v10 7 { v5 }

и преобразовать его в целочисленной программу как

maximize 8*v1 - v1v2 - v1v8 
     + 6*v2 - v2v1 - v2v4 
     + 9*v3 
     + 7*v4 - v4v2 - v4v5 - v4v8 
     + 6*v5 - v5v4 - v5v10 
     + 8*v6 - v6v7 
     + 5*v7 - v7v6 
     + 9*v8 - v8v1 - v8v4 
     + 6*v9 
     + 7*v10 - v10v5 

subject to 
v1 + v2 - v1v2 <= 1 
v1 + v8 - v1v8 <= 1 
v2 + v1 - v2v1 <= 1 
v2 + v4 - v2v4 <= 1 
v4 + v2 - v4v2 <= 1 
v4 + v5 - v4v5 <= 1 
v4 + v8 - v4v8 <= 1 
v5 + v4 - v5v4 <= 1 
v5 + v10 - v5v10 <= 1 
v6 + v7 - v6v7 <= 1 
v7 + v6 - v7v6 <= 1 
v8 + v1 - v8v1 <= 1 
v8 + v4 - v8v4 <= 1 
v10 + v5 - v10v5 <= 1 

binary v1, v1v2, v1v8, 
     v2, v2v1, v2v4, 
     v3, 
     v4, v4v2, v4v5, v4v8, 
     v5, v5v4, v5v10, 
     v6, v6v7, 
     v7, v7v6, 
     v8, v8v1, v8v4, 
     v9, 
     v10, v10v5

Вашего размер экземпляр, скорее всего, слишком много для оптимального решения, но никогда не знает ...

источник

2016-12-20 17:35:33

Комбинаторная оптимизация с взаимозависимыми переменными

ответ

Смежные вопросы