Более эффективный и надежный алгоритм минимизации цели со многими локальными минимумами. ⇐ Python

[Anonymous]

Справочная информация
Я написал скрипт Python (исключен, чтобы не загромождать этот пост), который вычисляет время, необходимое лучу света для распространения между две точки в некоторой сложной среде. Теперь я хочу использовать этот сценарий для решения проблемы Разницы во времени прибытия (TDoA) в этой среде. Постановка задачи следующая:
При известном местоположении некоторых N приемников (камер, датчиков, антенн и т.д.) и времени прибытия некоторых световой сигнал на каждом из этих приемников, я хочу определить координаты излучения сигнала. Поскольку время передачи сигнала неизвестно, все, что я действительно знаю, это попарные различия во времени прибытия (например, разница во времени прибытия сигнала между приемником A и приемником B).< /em>

Что я уже сделал
Я написал следующий скрипт в попытке чтобы решить эту проблему:

Код: Выделить всё

from dataclasses import dataclass
import numpy as np
from scipy.optimize import differential_evolution
from ray_tracer import RayTracer
from random import randrange

@dataclass
class Optimizer:
ice_model: np.ndarray # Parameters used by my RayTracer class to model complex medium
antenna_coordinates: np.ndarray

def __post_init__(self):
self.ray_tracer = RayTracer(self.ice_model)

def _objective(self, coords: np.ndarray, measured_times: np.ndarray) -> float:
"""Objective function to minimize the error between measured and predicted transit times."""
x, y, z = coords
predicted_times = np.array([
self.ray_tracer.transit_time([x, y, z], [nx, ny, nz])
for nx, ny, nz in self.antenna_coordinates
])

# Compute time difference matrices
measured_time_diff = np.abs(measured_times[:, None] - measured_times)
predicted_time_diff = np.abs(predicted_times[:, None] - predicted_times)

# Calculate error matrix and fill the diagonal with zeros
error_matrix = np.abs(measured_time_diff - predicted_time_diff)
np.fill_diagonal(error_matrix, 0)

# Return the maximum error
return np.nanmax(error_matrix)

def solve(self, measured_times: np.ndarray) -> np.ndarray:
"""Solve the optimization problem to find coordinates minimizing the objective function."""
bounds = [(-1000, 1000), (-1000, 1000), (-1000, 0)]

# Use differential evolution to minimize the objective function
result = differential_evolution(
self._objective,
bounds=bounds,
args=(measured_times,),
strategy='best1bin',  # Strategy for optimization
maxiter=5000,  # Maximum number of iterations
tol=1e-7,  # Tolerance for convergence
popsize=30,  # Population size
mutation=(0.5, 1),  # Mutation factor
recombination=0.7,  # Recombination constant
disp=True  # Display convergence messages
)

if result.success:
return result.x  # Return the optimized coordinates
else:
raise ValueError("Optimization failed: " + result.message)

# Example usage
if __name__ == "__main__":
# Define the ice model
ice_model = np.array([1.78, 0.454, 0.0132])

# Initialize RayTracer with the ice model
ray_tracer = RayTracer(ice_model)

# Generate random antenna coordinates
antenna_coordinates = np.array([[randrange(-100, 0) for _ in range(3)] for _ in range(10)])

# Generate random true coordinates and measured transit times
x, y, z = [randrange(-1000, 0) for _ in range(3)]
measured_times = np.array([
np.random.normal(ray_tracer.transit_time([x, y, z], [nx, ny, nz]) + 10, 1e-12)
for nx, ny, nz in antenna_coordinates
])

# Initialize the optimizer
optimizer = Optimizer(ice_model, antenna_coordinates)

# Attempt to find optimal coordinates
try:
optimal_coordinates = optimizer.solve(measured_times)
print("Optimal Coordinates (x, y, z):", optimal_coordinates)
print("True Coordinates (x, y, z):", x, y, z)
except ValueError as e:
print(e)

Пример вывода:

Код: Выделить всё

Optimal Coordinates (x, y, z): [-384.46240934  730.54140202 -612.43716286]
True Coordinates (x, y, z): -704 -408 -611

• Функция _objective вычисляет время прибытия сигнала в каждое из известных местоположений приемника для заданного предположения о координатах излучения сигнала. Класс RayTracer (вышеупомянутый скрипт Python) используется для вычисления времени прохождения. Затем я строю матрицы, содержащие попарные разницы во времени прибытия, вычитаю их друг из друга и возвращаю наибольшую абсолютную ошибку.
• Функцияsolve< /code> использует минимизатор дифференциальной эволюции SciPy (выбран просто потому, что это единственный минимизатор, который приблизился к решению этой проблемы) для определения неизвестных координат x,y,z.
• Основная «функция» генерирует некоторые примеры данных, выбирая случайные координаты приемника и источника, используя RayTracer для вычисления времени прибытия и передачи этих значений времени (вместе с некоторым гауссовским шумом и смещением 10, чтобы показать, что время прибытия не важно для этого алгоритма) решателю.

Проблема и попытки решения
Мне нужно решение, которое эффективен с точки зрения времени выполнения, поскольку (в идеале) в конечном итоге найдет применение практически в реальном времени. К сожалению, хотя я попробовал применить почти все оптимизаторы SciPy (тщательно учитывая каждую из их сильных и слабых сторон и параметров), а также некоторые свои собственные конструкции, мне не удалось точно восстановить расположение источника. Это не улучшается ни при использовании дополнительных приемников, ни при уменьшении гауссовского шума.
Целевая функция сильно нелинейна, и я пробовал применять различные методы сглаживания (сглаживание по Гауссу, потери Хубера, фильтры Савицкого-Голея) безрезультатно. Никакая другая разумная целевая функция не страдает от этой проблемы. Рассмотрим следующий график цели в z, созданный с использованием данных примера (и с фиксированными истинными значениями x и y):
< img alt="введите описание изображения здесь" src="https://i.sstatic.net/lQw8XyD9.png" />
Код, опубликованный выше, использует дифференциальную эволюцию решатель довольно надежно восстанавливает координату z (попадая в пределах единицы или около того примерно в 2/3 случаев и в противном случае не приближаясь к результату), но надежно не может точно восстановить координату x< Координаты /code> и y. Мне приходит в голову, что, возможно, было бы полезно написать какой-нибудь алгоритм, который сначала решает координату z (впоследствии сводя задачу к одному в двух измерениях), однако мне не удалось его написать (я пробовал например, выборка нескольких точек из набора срезов z и выбор среза с наименьшей ошибкой по различным показателям, однако это было медленно и ненадежно).

Какие альтернативные алгоритмы я мог бы использовать, которые были бы быстрее, точнее и надежнее?
Я бы предпочел алгоритм с минимальным настраиваемых параметров, так как мне бы хотелось, чтобы этот алгоритм можно было легко применить к различным значениям Ice_model, границ и т. д.

Подробнее здесь: https://stackoverflow.com/questions/790 ... -many-loca