Найти точку - сумма расстояний до которой от заданного набора точек минимальна

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

Хочу написать функцию решающую так называемую "Задачу Вебера с притяжением и отталкиванием", суть которой состоит в том что есть набор 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].

Начинаем с точки [2, 2].

То же самое только точка [0, 0] отталкивающая.

То же самое только точка ноль, ноль отталкивающая.

Как и предыдущее но стартуем с [-1, -1]

Как и предыдущее но стартуем с [-1, -1]

Стартуем с [-1, 0] попадаем в локальный минимум

Стартуем с [-1, 0] попадаем в локальный минимум


Ответы (2 шт):

Автор решения: Pak Uula

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

Давайте для определённости возьмём задачу где выбрать съемную квартиру. В точке 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

Отвечаю на вопросы, заданные в исходном посте и в комментариях.

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

  1. В scipy.optimize есть функция minimize которая реализует несколько общих методов поиска минимума многомерной функции. В силу своей универсальности функция minimize не гарантирует нахождение глобального минимума даже без отталкивающих точек. Например, в конфигурации "кластер близких слабо притягивающих точек и удалённая супер-притягивающая точка" общий метод вполне может "застрять" в локальном минимуме в центре кластера, а не в глобальном возле супер-притягивающей точки.

  2. С отталкивающими точками в задаче Вебера глобальный минимум может существовать только в том случае, если сумма позитивных весов по модулю больше суммы отрицательных. В противном случае отрицательные веса "перевесят" и глобальный минимум будет -inf на бесконечности. Это как бы намекает, что даже специализированный метод поиска минимумов в задаче Вебера может "сломаться". Добавление отталкивающих точек полностью меняет задачу.

  3. Ну и в общем. Я категорически не согласен с применением простейшей линейной функции оценивания для реальных задач "пространственной" экономики. Функции оценивания, ИМХО, должны стремиться к константе на бесконечности - нам совершенно не важно, что там есть вдали. Есть и есть, как фон. Поэтому я за то, чтобы использовать сигмоидные функции, а это совсем другие методы поиска минимумов. Но и в этом случае универсальные минимизаторы из scipy.optimize.minimize смогут застрять в локальных минимумах.

  4. Не существуют универсальные методы, которые гарантированно находят глобальный минимум. Глобальные минимумы могут находить только специализированные методы, заточенные под конкретную задачу. Но эти методы сразу перестают работать, как только меняется форма функции оценивания. Тот же метод Вайсфельда работает с притягивающими точками, но ломается при отталкивающих. С сигмоидными функциями оценивания он, возможно, справится, но для более конкретного ответа нужно смотреть доказательство сходимости этого метода, какие требования он предъявляет к норме.

  5. Соответственно, я предлагаю вам попробовать использовать общие методы из scipy.optimize, и переходить к специализированным только тогда, когда вы наткнётесь на явные промахи.

→ Ссылка
Автор решения: gbg

Рассмотрим вариант с трассировкой лучей:

Все объекты изображаем на карте с учетом их реальных размеров. Из каждой точки карты выпускаем N=60 (например) лучей по всем направлениям.

Для каждого луча смотрим на список объектов, куда этот луч попал суммируем очки. В конце, суммируем очки по всем лучам для этой точки.

В этом примере все объекты на карте кроме веса получают реальные физические размеры, таким образом маленький сортир и огромный завод будут создавать вокруг себя более реалтстичный потенциал вони (а далеко стоящий сортир алгоритм вообще не заметит)

Дальше, можно усложнить алгоритм, добавив на карту дороги, и тогда вместо лучей нужно будет трассировать уже вдоль дорог, составляя список посещенных объектов ("Куда из этой точки можно приехать?").

→ Ссылка