Ao tratar o SCP, um critério importante para uma CAN é que ela represente o máximo de biodiversidade possível. Por este critério, uma CAN deveria conter pelo menos um exemplar de cada tipo de objeto de conservação presente na região de interesse.
Uma vez que há restrições, seria prudente escolher um conjunto de sítios que atin- gisse uma representação pelo mínimo custo, o que é chamado de Problema da Mínima Representação.
Quando é requerida pelo menos uma ocorrência de cada objeto de conservação e há um número finito de sítios discretos que podem ser escolhidos, este é um Problema de Cobertura de Conjuntos [177], conhecidamentente NP-difícil, clássico em Complexidade de Algoritmos.
O Problema da Mínima Representação é um problema de otimização que procura maximizar a representação da diversidade de objetos de conservação. Para atingir este propósito, ele tem sido formulado de duas maneiras [30]:
1. O problema da cobertura mínima de conjuntos: minimizar o número de sítios, área total ou custo, ao mesmo tempo em que se garante a representação de todas as características naturais (e.g., espécies) um dado número de vezes [183].
Dada a matriz Ai×j, onde i = 1, ..., m corresponde a sítios e j = 1, ..., n corresponde
a espécies a serem conservadas, com aij representando a quantidade de ocorrências
da característica j no sítio i. Seja xi ∈ {0, 1}, tal que, xi =
1, se o sítio i foi selecionado; 0, caso contrário.
Seja ci o custo do sítio i.
Seja rj o nível de representação desejado, e.g., o tamanho de uma população mínima
viável para a espécie j, ou seja, o número mínimo de indivíduos em uma população, necessário para garantir uma alta probabilidade de sobrevivência [239].
O problema de otimização consiste em minimizar a Equação 2.1:
m
∑
i=1
cixi (2.1)
Sujeita à restrição expressa na Equação 2.2 (para todo j, cada característica seja representada pelo menos rj vezes):
∀j ∈ {1, 2, ..., n},
m
∑
i=1
aijxi ≥ rj (2.2)
Deste caso geral, podem ser derivados problemas particulares:
(a) Minimizar o número de sítios necessários para a representação das caracterís- ticas naturais. Fazendo-se:
ci = 1, todos os sítios passam a ter o mesmo custo;
aij = 0 ou 1, se apenas a presença ou ausência da característica é considerada;
Se
rj = 1, tem-se a representação única do problema;
rj ≥ 1, tem-se a representação múltipla do problema.
(b) Minimizar a área total necessária à representação de cada característica a um nível rj. Tem-se:
ci = areai, o custo do sítio é sua área;
aij = área coberta pela característica j no sítio i;
rj = nível de representação nas unidades de área.
(c) Minimizar o custo total de representação de características. Assemelha-se à instância (a), mas o custo de um sítio é seu preço real (ci = custoi).
2. O problema da cobertura máxima: maximizar a representação de características naturais dado um limite para o número de sítios, o custo ou a área. O problema, conforme originalmente enunciado por Church e ReVelle [38] e apresentado por [12, 31, 40], tem a limitação imposta sobre o número de sítios e consiste em:
Dada a matriz Ai×j, onde i = 1, ..., m corresponde a sítios e j = 1, ..., n corresponde
a espécies a serem conservadas, com aij representando a ocorrência da espécie j no
sítio i, da seguinte forma: aij ∈ {0, 1}, tal que, aij =
1, se a espécie i está localizada no sítio j ; 0, caso contrário.
Sejam as variáveis de decisão xi e yj, tais que:
Para cada sítio i, xi =
1, se o sítio i foi selecionado; 0, caso contrário.
Para cada espécie j, yj =
1, se a espécies j está em pelo menos um sítio selecionado; 0, caso contrário.
O problema de selecionar k sítios a fim de maximizar a cobertura das espécies consiste em maximizar a Equação 2.3:
n ∑ j=1 yj (2.3) Sujeita às restrições 2.4, 2.5, 2.6 e 2.7: m ∑ i=1 aijxi ≥ yj, j = 1, ..., n (2.4) m ∑ i=1 xi = k (2.5) 0 ≤ yj ≤ 1, j = 1, ..., n (2.6)
xi = 0 ou 1, i = 1, ..., m (2.7)
Uma vez que a variável yj é igual a 1 apenas quando a espécie j é representada, a
Equação 2.3 mede o total de espécies cobertas pelos sítios selecionados. A Inequa- ção 2.4 garante que yj terá valor 1 apenas se aquela espécie é representada em pelo
menos um sítio selecionado, o que é válido desde que para um dado j, a quantidade ∑
i
aijxi seja o número de vezes que a espécie j é representada nos sítios selecionados.
Assim, se a espécie j não é coberta, yj terá valor 0; enquanto que yj receberá valor
1, seu limite superior, se a espécie é coberta ao menos uma vez. A Equação 2.5 restringe o número de células que podem ser selecionadas (k). A Inequação 2.6 fornece os limites para yi e indica que esta variável pode ser tratada como contínua,
uma vez que as Equações 2.3 e 2.4 forçarão yj para o valor 1 se a espécie é coberta
pela seleção, mas faz com que o valor de yj seja 0 se ela não é representada. A
Equação 2.7 estabelece como obrigatória a restrição binária sobre cada variável xi.
Outra maneira pela qual o problema pode ser enunciado é:
Seja S o conjunto de sítios a serem selecionados, n o número de características. O problema de otimização consiste em maximizar a Equação 2.8:
n
∑
j=1
Vj(S) (2.8)
Sujeita à restrição expressa na Equação 2.9:
∑
i∈S
ci ≤ k (2.9)
Onde:
Vj(S) é o valor da característica j na seleção S.
No caso mais simples:
Vj(S) =
1, se o nível de representação desejado para a característica j é atingido na seleção S; 0, caso contrário.
Vj(S) também pode ser utilizado para expressar a previsão de persistência da ca-
ci é o custo do sítio i, podendo ser definido como 1 – se apenas o número de sítios é
levado em consideração –, como a área do sítio, ou como seu custo real dependendo dos objetivos de otimização.
k é o recurso máximo disponível, contabilizado na mesma unidade de ci.
O problema da máxima cobertura é uma extensão do problema da mínima cobertura de conjuntos na qual há uma restrição no número de sítios (ou custo, ou área, etc.) tendo em vista o valor estabelecido para k (Equação 2.9). Por causa desta restrição, nem todas as características serão preservadas.
ReVelle at. al [192] apontam que o problema da máxima cobertura pode também ser tratado como uma modificação do problema p-medianas [161, 191, 213].
Enunciado o problema, foram desenvolvidos algoritmos para lidar com ele. Tais algo- ritmos envolviam a seleção de sítios complementares sequenciais, até que o objetivo de representação de todas as espécies fosse atingido.
Para conjuntos grandes de dados, a solução por inspeção é difícil de encontrar. E mesmo com a implementação de algoritmos para a automatização do processo, como se trata de um problema NP-difícil, alguns conjuntos grandes de dados podem ser computa- cionalmente intratáveis por métodos exatos [184, 198]. Quando se considera o problema da mínima cobertura de conjuntos, para um conjunto de oito sítios, são possíveis 28 = 256
soluções, variando entre a seleção de todos os sítios e a seleção de nenhum sítio. Para o exemplo trazido por Possingham et al. [177] para a ecorregião do Platô da Columbia (nos EUA), com 5.000 sítios, o número de sistemas de reservas possíveis é 25.000, um número tão
grande que é intratável. Quando se considera o problema da máxima cobertura, havendo, por exemplo, um total de n sítios, e sendo 2 a quantidade máxima de sítios que podem ser escolhidos (k = 2), o número de espécies cobertas por cada combinação de dois sítios do total de n pode ser calculado por (n
2
)
, e as combinações que fornecem a maior cobertura (maior número de espécies representadas) são, por definição, ótimas. Entretanto, como o número de tais combinações é (n
k
)
o uso de tais técnicas exaustivas se torna impraticável para todos os valores não triviais de k [12].
A abordagem mais óbvia seria utilizar um algoritmo guloso (greedy algorithm) como o Algoritmo 1 (adaptado de [53]).
O algoritmo funciona da seguinte forma: dado um conjunto de sítios com espécies desprotegidas Σ, o conjunto Λ\Λ′ contém, em cada etapa, o conjunto de elementos rema-
nescentes não-cobertos (espécies desprotegidas ainda não selecionadas para proteção). O conjunto Γ contém a cobertura sendo construída. A linha 4 é o passo de decisão gulosa: um sítio σk é escolhido de tal maneira que “cubra” tantas espécies desprotegidas quanto
Algoritmo 1: Algoritmo guloso para SCP Dados:
Seja Σ um conjunto de sítios, com σi ∈ Σ, i = 1, ..., m, sítios individuais.
Seja Λ um conjunto de espécies desprotegidas, com λj ∈ Λ, j = 1, ..., n,
correspondendo a espécies individuais. Seja Γ o conjunto de sítios já selecionados. Seja Λ′ o conjunto de espécies λ
j ∈ Λ representadas em Γ. Seja Xij = { 1, se λj ∈ σi 0, se λj ∈ σ/ i 1 begin 2 Γ ← ∅
/* executa o laço de repetição enquanto houver espécies não
representadas */
3 while Λ\Λ′ ̸= ∅ do
4 Selecione um σk∈ Σ, tal que, σk= max( ∑ λj∈Λ\Λ′
Xij) 5 Γ ← Γ ∪ {σk}
6 Atualize Λ′ 7 return Γ
é adicionado a Γ e as espécies desprotegidas nele representadas são adicionadas a Λ′ e
desconsideradas na próxima repetição (Λ\Λ′). Quando o algoritmo termina, o conjunto
Γ contém uma subfamília de Σ que cobre Λ, ou seja, que contém todas as espécies des- protegidas que se deseja salvaguardar.
O problema é que a solução encontrada com algoritmos gulosos é subótima e, portanto, ineficiente quando comparada a uma solução ótima. Todos algoritmos que escolhem sítios sequencialmente são ineficientes e não apresentam garantia de que se encontrará uma solução ótima [177]. Apesar disso, tal classe de algoritmos tem marcada importância na história do desenvolvimento de abordagens, algoritmos e ferramentas para SCP, o que será tratado na Seção 2.3.