Cortes elipsoidais

Cortes elipsoidais para duas soluções

Partindo do princípio que soluções são vetores binários de tamanho fixo que sempre possuem N bits igual a um, os cortes elipsoidais podem ser extendidos facilmente a partir do conceito de uma elipse. Uma elipse possui dois focos (representados aqui por duas soluções) e os pontos da elipse são aqueles que estão em uma distância fixa D = R1+R2, onde R1 = distância do primeiro foco (primeira solução) e R2 = distância do segundo foco (segunda solução). Dada nossa representação de uma solução como um vetor de bits, a medida de distância entre duas soluções usada será a distancia de Hamming, ou seja, o número de bits diferentes entre as soluções - por exemplo 0011 e 0101 tem distância 2. E fácil perceber que, devido a restrição de N bits setados em 1, não existirão distancias ímpares.

Vamos exemplificar como funcionam os cortes elipsoidais, dadas duas soluções A e B de tamanho fixo 6 e que devem possuir sempre 3 bits setados:
A = 001011
B = 101010

Vamos começar gerando a elipse determinada pela distância D = 4. As soluções que se encontram nesta elipse são as soluções cuja distancia D(A) + D(B) = 2. As soluções que satisfazem essa igualdade são as seguintes:
C = 101001 (onde D(A) = 2 e D(B) = 2)
D = 100011 (onde D(A) = 2 e D(B) = 2)

Agora vamos gerar a elipse determinada pela distância D = 6. As soluções que se encontram nesta elipse são as soluções cuja distancia D(A) + D(B) = 3. As soluções que satisfazem essa igualdade são as seguintes:
E = 1X1X00 (onde D(A) = 2 e D(B) = 4)
F = 0X1X01 (onde D(A) = 2 e D(B) = 4)
G = 1X0X10 (onda D(A) = 4 e D(B) = 2)
H = 0X0X11 (onde D(A) = 4 e D(B) = 2)
Nestas soluções, usamos dois valores 'X' para indicar que um dos 'X' será 0 e o outro 'X' será 1. Cada uma das soluções anteriores representa, portanto, duas soluções, uma com o primeiro 'X' igual a 0 e o segundo igual a 1 e outra com o primeiro 'X' igual a 1 e o segundo igual a 0.

Agora vamos gerar a elipse determinada pela distância D = 8. As soluções que se encontram nesta elipse são as soluções cuja distancia D(A) + D(B) = 4. As soluções que satisfazem essa igualdade são as seguintes:
I = 1X0X01 (onde D(A) = 4 e D(B) = 4)
J = 010110 (onde D(A) = 6 e D(B) = 2)
K = 011100 (onda D(A) = 2 e D(B) = 6)

Agora vamos gerar a elipse determinada pela distância D = 10. As soluções que se encontram nesta elipse são as soluções cuja distancia D(A) + D(B) = 5. As soluções que satisfazem essa igualdade são as seguintes:
L = 110100 (onde D(A) = 6 e D(B) = 4)
M = 010101 (onde D(A) = 4 e D(B) = 6)

A elipse formada por D = 0 só existiria se R1+R2 fosse igual a zero, ou seja, as duas soluções fossem iguais. A elipse formada por D = 2 é trivial, contem somente as soluções A e B. A elipse formada por D = 12 exigiria uma solução que tem 3 bits setados completamente diferentes dos bits setados em A e B - nesse exemplo, esse conjunto é vazio.

Dadas duas soluções $A$ e $B$, encontrar as soluções $X$ que estão na elipsóide com distancia $D$ pode ser escrito como:

(1)

\begin{align} 2(N-\sum_{j \in N_1(A)}X_j}) + 2(N-\sum_{j \in N_1(B)}X_j}) = D \end{align}

Algumas observacoes:

• $N_1$ representa os indices dos bits da solucao $A$ que possuem valor 1.
• O primeiro termo representa a distancia de $X$ ate $A$ e o segundo representa a distancia de $X$ ate $B$. A distancia de Hamming e calculada somando o numero de elementos diferentes ($N$ menos os elementos que sao um em ambas as solucoes) e multiplicando por dois. Por exemplo, 0011 e 0101 tem 1 elemento em comum, o calculo seria $2(2-1)$, ou seja, a distancia entre eles e dois.
• Essa equacao pode ser extendida para encontrar solucoes mais proximas de $A$ e $B$ ou mais distantes, bastando trocar o sinal do corte para $\leq$ ou $\geq$. E facil perceber que o parametro $D$ pode ser usado para representar a liberdade (ou "folga") da nova solucao em relacao as duas solucoes originais.

Visualizando a vizinhanca

Como as solucoes sao vetores binarios de dimensao N, e dificil visualizar as vizinhancas elipsoidais. Algumas imagens que podem ajudar:

(COLOCAR O PLOT DAS ELIPSES)

Cortes elipsoidais para multiplas soluções

Uma extensao natural dos cortes descritos na secao anterior seria extende-los para multiplas soluções. Um corte elipsoidal de distancia no máximo $D$ gerado a partir de um conjunto de $K$ soluções $S = {S_a, S_b, S_c, ..., S_k}$ pode ser descrito como:

(2)

\begin{eqnarray} \sum_{Sol \in S} 2(N - \sum_{j \in N_1(Sol)} X_j) \leq D \\ \sum_{Sol \in S} 2N - 2\sum_{Sol \in S}\sum_{j \in N_1(Sol)} X_j \leq D \\ N|Sol| - \sum_{Sol \in S}\sum_{j \in N_1(Sol)} X_j \leq D/2 \\ -\sum_{Sol \in S}\sum_{j \in N_1(Sol)} X_j \leq D/2 - NK \\ \sum_{Sol \in S}\sum_{j \in N_1(Sol)} X_j \geq NK - D/2 \\ \end{eqnarray}

Por exemplo, se tivermos tres soluções com N = 3:
A = 001011
B = 101010
C = 111000

Podemos usar a equacao acima para calcular a distancia de uma solucao qualquer para o elipsoide formado pelas tres solucoes A, B e C. Por exemplo E = 100110 tem distancia igual a 10 - ou seja, ele esta na vizinhanca elipsoidal de valor 10. Podemos entao usar o valor de $D/2$ na equacao acima como uma folga $F$, temos entao o seguinte corte, que pode ser aplicado para qualquer conjunto de soluções:

(3)

\begin{align} \sum_{Sol \in S}\sum_{j \in N_1(Sol)} X_j \geq NK - F \\ \end{align}

Visualizando a vizinhanca