Trouvez l'emplacement d'installation du capteur qui maximise la quantité de données acquises

Ce que vous voulez faire

Il y a une zone comme indiqué ci-dessous.

image

--Un capteur sera installé au centre de ce triangle pour collecter des données.

  • ** Le but est de maximiser la quantité totale de données acquises **. ――Un seul capteur peut être placé dans un triangle.
  • Vous pouvez obtenir la quantité de données ** 3 ** en mettant un capteur. ―― L'endroit où le capteur doit être installé et l'endroit où le capteur ne doit pas être installé sont décidés à l'avance. ――Comme indiqué dans le tableau ci-dessous, s'il y a un autre capteur à côté, cela provoquera des interférences et la quantité de données acquises diminuera chacune ** 1 **. (Diminution totale ** 2 **) ――Par conséquent, s'il y a deux capteurs ou plus autour, il vaut mieux ne pas les installer.
Nombre de capteurs autour Quantité de données acquises Quantité de données d'interférence La quantité de données qui augmente dans son ensemble
0 3 0 3
1 3 2 1
2 3 4 -1
3 3 6 -3

Optimisation par problème d'optimisation d'entiers mixtes (approche par problème mathématique)

Modélisons-le comme un problème d'optimisation d'entiers mixtes (MIP). Veuillez consulter Utiliser l'optimisation de la combinaison pour la formulation et le concept.

Formulation

Maximiser $ Quantité de données acquises \\ = 3 \ fois S'il faut installer-2 \ fois S'il faut interférer $
Variables $ (Sensor) Indique s'il faut installer \ in \ {0, 1 \} \ forall Emplacement d'installation $
$ S'il faut interférer \ ge 0 \ forall Adjacent $
Contraintes $ S'il faut installer _1 + S'il faut installer _2 --S'il faut interférer \ le 1 $

Optimisation par problème de coupe minimum (approche par problème typique)

[Problème de coupe minimale] dans la théorie des graphes (https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%83%E3%83%88_(%E3%82%B0%E3%83] % A9% E3% 83% 95% E7% 90% 86% E8% AB% 96) # .E6.9C.80.E5.B0.8F.E3.82.AB.E3.83.83.E3.83.88) Il ya quelque chose.

Considérez le graphe s-t suivant. Trouver la coupe minimale s-t pour ce graphique orienté vous donnera la meilleure solution au problème d'installation du capteur d'origine. Le problème original est le problème de la maximisation, mais en considérant la "quantité de données acquises en 3" comme le coût, il peut être considéré comme le problème de minimisation. Pour plus de détails, consultez le site de référence ci-dessous.

graphe s-t

image

-La figure ci-dessus montre trois exemples de (0,0), (0,1), (1,0).

  • À partir du nœud de départ "s", dessinez un côté de chaque partie (triangle). Dessinez également un côté de chaque emplacement vers le nœud terminal "t". --Dans le triangle supérieur ((0,0) et (1,0) sur la figure ci-dessus), le côté de s signifie «installé» et le côté à t signifie «non installé». --Dans le triangle inférieur ((0,1) sur la figure ci-dessus), le côté de s signifie «non installé» et le côté à t signifie «installé».
  • Le poids du côté installé est de 0 et le poids du côté non installé est de 3. (Le poids est "3-Quantité de données acquises".) ――Pour tous les points adjacents, tracez un côté de poids 2 du triangle inférieur au triangle supérieur. -Lors de la fixation avec «Installation», supprimer (couper) le côté «Installation» et faire en sorte que le poids du côté «Non-installation» soit suffisamment important. -Lors de la fixation avec "Non-installé", supprimez (coupez) le côté "Non-installé" et augmentez suffisamment le poids du côté "Installé".

Signification du graphe s-t

  • Afin de couper s-t, le côté installé ou non installé doit être coupé à chaque emplacement. On considère que le coupé est sélectionné. --Pour que la coupe s-t fonctionne, si les deux emplacements adjacents sont installés, il est nécessaire de couper le côté de l'interférence, et la quantité d'interférence peut être exprimée. (Cela fonctionne bien en le divisant en triangles supérieur et inférieur.)

À propos du problème de coupe minimale

Le problème de coupe minimale est un problème facile à résoudre qui peut être résolu en temps polymorphe. Dans le programme décrit plus loin, il sera résolu en utilisant networkx de Python. Soit dit en passant, le problème de coupure minimale problème de la dualité est le problème de débit maximal.

Exemple d'exécution par python

Sois prêt.

python3


import numpy as np, networkx as nx
from pulp import *
def addvar(lowBound=0, var_count=[0], *args, **kwargs):
    """Utilitaire de création de variables"""
    var_count[0] += 1
    return LpVariable('v%d' % var_count[0], lowBound=lowBound, *args, **kwargs)
def calc(a, r):
    """Calculez la quantité de données acquises avec r comme emplacement d'installation"""
    b = a.copy()
    b[b > 1] = 0
    for x, y in r:
        b[y, x] = 1
    s = b.sum() * 3
    for y in range(0, b.shape[0], 2):
        for x in range(b.shape[1]):
            s -= 2 * b[y, x] * b[y+1,x]
            if x:
                s -= 2 * b[y, x] * b[y+1,x-1]
            if y:
                s -= 2 * b[y, x] * b[y-1,x]
    return s

résoudre_by_mip est une solution MIP. Renvoie l'emplacement d'installation.

python3


def solve_by_mip(a):
    """Résolvez le problème avec MIP et renvoyez l'emplacement d'installation"""
    nm, nn = a.shape
    b = a.astype(object)
    vv1 = [addvar(cat=LpBinary) for _ in range((b > 1).sum())]
    b[b > 1] = vv1
    vv2 = []
    m = LpProblem(sense=LpMaximize)
    for y in range(0, nm, 2):
        for x in range(nn):
            chk(m, vv2, b[y,x] + b[y+1,x])
            if x: chk(m, vv2, b[y,x] + b[y+1,x-1])
            if y: chk(m, vv2, b[y,x] + b[y-1,x])
    m += 3 * lpSum(vv1) - 2 * lpSum(vv2)
    m.solve()
    return [(x, y) for x in range(nn) for y in range(nm)
            if isinstance(b[y,x], LpVariable) and value(b[y, x]) > 0.5]
def chk(m, vv2, e):
    """Ajouter une contrainte pour réduire la fonction objectif de 2 si e contient des variables"""
    if isinstance(e, LpAffineExpression):
        v = addvar()
        vv2.append(v)
        m += e - v <= 1

résoudre_by_graph est une solution de coupe minimale. Renvoyez également l'emplacement d'installation.

python3


def solve_by_graph(a):
    """Résolvez le problème avec le problème de coupure minimum et renvoyez l'emplacement d'installation"""
    nm, nn = a.shape
    g = nx.DiGraph()
    for y in range(0, nm, 2):
        for x in range(nn):
            if a[y, x] == 0: # off
                g.add_edge('s', (x,y), capacity=7)
            elif a[y, x] == 1: # on
                g.add_edge((x,y), 't', capacity=7)
            else:
                g.add_edge('s', (x,y), capacity=0)
                g.add_edge((x,y), 't', capacity=3)
            if a[y+1, x] == 0: # off
                g.add_edge((x,y+1), 't', capacity=7)
            elif a[y+1, x] == 1: # on
                g.add_edge('s', (x,y+1), capacity=7)
            else:
                g.add_edge('s', (x,y+1), capacity=3)
                g.add_edge((x,y+1), 't', capacity=0)
            g.add_edge((x,y+1), (x,y), capacity=2)
            if x:
                g.add_edge((x-1,y+1), (x,y), capacity=2)
            if y:
                g.add_edge((x,y-1), (x,y), capacity=2)
    r = []
    for s in nx.minimum_cut(g, 's', 't')[1]:
        b = 's' in s
        for t in s:
            if isinstance(t, str): continue
            x, y = t
            if a[y, x] > 1 and b == (y%2 != 0):
                r.append((x, y))
    return sorted(r)

Comparons les résultats en définissant aléatoirement des points fixes d'une taille de 40 x 80.

python3


nn, nm = 40, 80 #Horizontal Vertical
np.random.seed(1)
a = np.random.randint(0, 6, (nm, nn)) # 0; fix off, 1: fix on, ow:select

%time rmip = calc(a, solve_by_mip(a))
%time rgrp = calc(a, solve_by_graph(a))
print(rmip == rgrp)
>>>
Wall time: 455 ms
Wall time: 185 ms

True

―― Vous pouvez voir que les deux méthodes ont la même quantité de données acquises (rmip == rgrp). --MIP est plus de deux fois plus lent.

  • En général, les solveurs dédiés sont plus rapides que les solveurs à usage général. ――Lorsque je l'ai confirmé séparément, le temps de calcul du solveur MIP seul était légèrement plus long que le temps de calcul de la coupe minimale. ――Bien que la théorie soit inconnue, la quantité de données acquises ne change pas même si le MIP est relâché linéairement, et le temps de calcul est légèrement plus rapide.

Site de référence

c'est tout

Recommended Posts