Найти точку - сумма расстояний до которой от заданного набора точек минимальна
Условный магазин стоит размещать поближе к центру города и складу, но подальше, например от свалки и тюрьмы...
Хочу написать функцию решающую так называемую "Задачу Вебера с притяжением и отталкиванием", суть которой состоит в том что есть набор n-мерных точек, и набор их привлекательности(в том числе и отрицательной) и нужно найти такую точку(не обязательно из набора), сумма расстояний от которой до привлекательных объектов минимальна, а до отвратительных максимальна.
Расстояние между точками определяется по Евклидову расстоянию
Для начала написал Алгоритм Вайсфельда . :
import numpy as np
import matplotlib.pyplot as plt
def weisfeld(vec, v_res):
def dist(v1, v2): #расстояние между точками
v1=np.array(v1)
v2=np.array(v2)
return np.linalg.norm(v1-v2)
sumZnam=0.0
dist1=0.0
nev_V_res=[0]* len(v_res)
for i in range(len(vec)): #перебираем точки
dist1 = dist(vec[i], v_res)
sumZnam += 1./dist1 #знаменатель формулы Веисфельда
for n in range(len(vec)):
dist2 = dist(vec[n], v_res)
for t in range(len(vec[n])):
nev_V_res[t] = nev_V_res[t] + (( vec[n][t] / dist2 ) / sumZnam)
return nev_V_res
v1=[10, 1] # одна точка
v2=[0, 0]# вторая точка
v3=[10, -1]
v_res=[8, 1] #Точка из которой начинаем искать оптимальную точку
weis=weisfeld([v1, v2, v3], v_res)
plt.plot(v1[0], v1[1], 'ro')
plt.plot(v2[0], v2[1], 'ro')
plt.plot(v3[0], v3[1], 'ro')
plt.plot(weis[0], weis[1], 'bo')
plt.show()
Он решает проблему, но только если нету отталкивания- все точки только привлекательные. А при попытке добавить отталкивание функция становится не выпуклой и нет гарантии, что не попадем в локальный минимум.
Да и как корректно добавить отталкивание не понятно. Пробовал симметрично отражать точку, которая отталкивает таким образом чтобы она как бы притягивала, но с другой стороны.
#заменим точку на симметричную относительно приближаемой для отталкивающих точек
def symmetry(vec, vec_symmetry):
nev_vec=[0]* len(vec)
for i in range(len(vec)):
nev_vec[i] = vec_symmetry[i]*2 - vec[i]
#nev_vec[i] = 1/nev_vec[i]
return nev_vec
Нагуглить по теме ничего стоящего так и не удалось.
Каков алгоритм решения "Задачи Вебера с притяжением- отталкиванием"? В идеале с весами(мерами значимости) точек и запрещенными зонами. Может кто-то писал код(не важно на каком языке)- задача, на мой взгляд должна встречаться во многих сферах, поделитесь пожалуйста.
Иллюстрации (Зеленые это притягивающие точки. Красные отталкивающие. Синие -итеративное приближение искомой точки алгоритмом.):
Начинаем с точки [2, 2].
То же самое только точка [0, 0] отталкивающая.
Как и предыдущее но стартуем с [-1, -1]
Стартуем с [-1, 0] попадаем в локальный минимум
Ответы (2 шт):
Мне кажется, у вас где-то потерялся физический смысл задачи. Насколько я понимаю, в экономической географии силы притягивания и отталкивания не сводятся к евклидовому расстоянию на плоскости.
Давайте для определённости возьмём задачу где выбрать съемную квартиру. В точке 0.0 есть супермаркет, где всё есть (сильная притягивающая точка), но постоянно толкутся люди (слабое отталкивание). В точке (10,1) есть магазин, где продается еда на каждый день (слабое притяжение) но он не вызывает никакого негатива. И в координатах (10,-1) есть завод, где шум, гам, и работяги (сильная отталкивающая точка).
То, насколько сильно отталкивают и притягивают объекты, должны нам сказать социологи. Для вычисления потенциала притягивания и отталкивания я от балды взял механизм штрафов: чем дальше вы от притягивающей точки, тем жальче вам от неё удаляться, чем ближе вы к отталкивающей точке, тем больнее вам к ней приближаться.
Для притягивающей точки я заложил убывание штрафа к бесконечности - иначе нас бы давно всех порвало от тоски по какому-нибудь гипотетическому Уолл-Марту в гипотетическом Канзас-Сити.
# Штраф для функции притяжения - сначала нарастает, потом убывает. На большом расстоянии уже пофиг, что там притягивает.
def attract(power, distance):
# притягивающая часть - квадратичная сигмоидная функция
p1 = power*distance/np.sqrt(distance+1)
# забывание - степенная функция
p2 = p1*(1/(distance+1))
return p2
# Штраф для отталкивания - постепенно убывает.
def repell(power, distance):
return power*(1/(distance+1))
Конкретный вид потенциалов для притяжения отталкивания я просто выдумал. По-хорошему, нужно проводить исследования среди реальных людей, насколько меняются их отношения к притягательным и отталкивающим местам с расстоянием.
Дальше понятно. Задать потенциал по сумме точек и найти локальный минимум. Глобальный минимум с такими потенциалами искать бесполезно, он находится на бесконечности.
class Point:
def __init__(self, coords, attracting, repelling):
self.coords = np.atleast_2d(coords)
self.attracting_power = attracting
self.repelling_power = repelling
def potential(self, point):
point = np.atleast_2d(point)
distance = np.linalg.norm(point-self.coords)
attracting_penalty = attract(self.attracting_power, distance) if self.attracting_power > 0 else 0
repelling_penalty = repell(self.repelling_power, distance)
return attracting_penalty + repelling_penalty
class Potential:
def __init__(self, points):
self.points = points
def potential(self, v):
resPot = 0.0
for p in self.points:
potential = p.potential(v)
resPot += potential
return resPot
def __call__(self, v):
return self.potential(v)
Вернёмся к примеру.
supermarket = Point((0.0), attracting=10, repelling=0.5)
factory = Point((10, -1), attracting=0, repelling=5)
minishop = Point((10,1), attracting=3, repelling=0)
fn = Potential((supermarket, minishop, factory))
Супермаркет и магазин создают локальные минимумы, фабрика создаёт локальный максимум.
Далее ищем ограниченный локальный максимум и вуа-ля! Жить надо возле супермаркета ))
spo.minimize(fn, x0=(1,0), bounds=((-5, 15), (-10, 10)))
Результат
fun: 1.7733099211366816
hess_inv: <2x2 LbfgsInvHessProduct with dtype=float64>
jac: array([1.54659745, 0.5809764 ])
message: b'CONVERGENCE: REL_REDUCTION_OF_F_<=_FACTR*EPSMCH'
nfev: 210
nit: 20
status: 0
success: True
x: array([-3.93721209e-09, -4.60977379e-09])
Jupyter Notebook c функциями и графиками
UPDATE
Отвечаю на вопросы, заданные в исходном посте и в комментариях.
Насколько я понял, вы настроились решать именно задачу Вебера, в которой стоимость расположения определяется взвешенной суммой расстояний до фиксированных точек и спрашиваете об универсальном решателе.
В
scipy.optimizeесть функцияminimizeкоторая реализует несколько общих методов поиска минимума многомерной функции. В силу своей универсальности функцияminimizeне гарантирует нахождение глобального минимума даже без отталкивающих точек. Например, в конфигурации "кластер близких слабо притягивающих точек и удалённая супер-притягивающая точка" общий метод вполне может "застрять" в локальном минимуме в центре кластера, а не в глобальном возле супер-притягивающей точки.С отталкивающими точками в задаче Вебера глобальный минимум может существовать только в том случае, если сумма позитивных весов по модулю больше суммы отрицательных. В противном случае отрицательные веса "перевесят" и глобальный минимум будет
-infна бесконечности. Это как бы намекает, что даже специализированный метод поиска минимумов в задаче Вебера может "сломаться". Добавление отталкивающих точек полностью меняет задачу.Ну и в общем. Я категорически не согласен с применением простейшей линейной функции оценивания для реальных задач "пространственной" экономики. Функции оценивания, ИМХО, должны стремиться к константе на бесконечности - нам совершенно не важно, что там есть вдали. Есть и есть, как фон. Поэтому я за то, чтобы использовать сигмоидные функции, а это совсем другие методы поиска минимумов. Но и в этом случае универсальные минимизаторы из
scipy.optimize.minimizeсмогут застрять в локальных минимумах.Не существуют универсальные методы, которые гарантированно находят глобальный минимум. Глобальные минимумы могут находить только специализированные методы, заточенные под конкретную задачу. Но эти методы сразу перестают работать, как только меняется форма функции оценивания. Тот же метод Вайсфельда работает с притягивающими точками, но ломается при отталкивающих. С сигмоидными функциями оценивания он, возможно, справится, но для более конкретного ответа нужно смотреть доказательство сходимости этого метода, какие требования он предъявляет к норме.
Соответственно, я предлагаю вам попробовать использовать общие методы из
scipy.optimize, и переходить к специализированным только тогда, когда вы наткнётесь на явные промахи.
Рассмотрим вариант с трассировкой лучей:
Все объекты изображаем на карте с учетом их реальных размеров. Из каждой точки карты выпускаем N=60 (например) лучей по всем направлениям.
Для каждого луча смотрим на список объектов, куда этот луч попал суммируем очки. В конце, суммируем очки по всем лучам для этой точки.
В этом примере все объекты на карте кроме веса получают реальные физические размеры, таким образом маленький сортир и огромный завод будут создавать вокруг себя более реалтстичный потенциал вони (а далеко стоящий сортир алгоритм вообще не заметит)
Дальше, можно усложнить алгоритм, добавив на карту дороги, и тогда вместо лучей нужно будет трассировать уже вдоль дорог, составляя список посещенных объектов ("Куда из этой точки можно приехать?").
![Начинаем с точки [2, 2].](https://i.stack.imgur.com/hDkcN.png)

![Как и предыдущее но стартуем с [-1, -1]](https://i.stack.imgur.com/3SXuj.png)
![Стартуем с [-1, 0] попадаем в локальный минимум](https://i.stack.imgur.com/wyyW0.png)

