ART DECO

Os algoritmos evolucionários não se destinam a resolver todo o tipo de problemas. Estão vocacionados para resolver problemas que ou não têm solução analítica ou que, tendo, o espaço de soluções candidatas tem uma dimensão muito elevada, que torna intratatável computacionalmente o uso de técnicas exactas. Por isso, perante um problema, a primeira questão a resolver é a de se saber se os AE são ou não adequados. Se a resposta for afirmativa, a questão seguinte que se coloca é a de saber que instância concreta iremos usar. Para responder, recordemos a versão genérica de um AE.



Resulta claro que existem várias componentes do algoritmos que precisamos definir:

1- Como definir a população inicial
2- Como seleccionar os pais para reprodução
3- Como seleccionar de entre pais e filhos os sobreviventes para a geração seguinte
4- Que operadores genéticos vamos usar para alterar os pais que foram seleccionados
5- Como avaliar a qualidade das soluções candidatas
6- Como determinar o fim do processo evolutivo
7- Que parâmetros usar (e.g., tamanho da população, probabilidades dos operadores de variação)

Mas antes de mais temos que escolher uma representação para os indivíduos (cromossomas) da nossa população. Esta é, aliás, a questão primeira a resolver e, claramente, a mais importante de todas. As representações são essencialmente de dois tipos: lineares e não lineares. Podem ainda ser detalhadas: vectores binários, de inteiros, de reais, árvores, grafos, etc.. Uma boa representação deve ter quatro características:


1- económica: reduzir a dimensão do espaço de procura;
2- eficaz e deficiente: permitir encontrar a solução e encontrá-la em tempo curto (em associação com os operadores de variação);
3- completa: deve permitir representar todas as soluções;
4- ligada: ligar qualquer par de soluções (em associação com os operadores de variação)

A partir do momento que representação e operadores estão escolhidos, temos que ter em atenção as consequências, em particular saber distinguir:

- O espaço de procura conceptual;
- O espaço de procura real, consequência da representação;
- O espaço de procura efectivo, consequência dos operadores

Tipicamente estas três situações encontram-se numa situação de inclusão ou identidade. A figura abaixo tenta ilustrar a situação.





Exemplos

Vejamos exemplos concretos.

(1) Comecemos pelo problema OneMax. Neste exemplo o conjunto de todas as cadeias binárias é o espaço conceptual. Usando uma representação baseada em cadeias binárias, é claro que o espaço real coincide com o espaço conceptual. O espaço efectivo depende dos operadores. Se usarmos mutação por comutação de um bit e cruzamento de um ponto, todos os indivíduos se ligam entre si de modo directo ou, mais comum, de modo indirecto. O espaço efectivo é o mesmo que os dois anteriores.

(2) Passemos ao caso de procura do máximo (ou do mínimo) de uma função f: R^n --> R. O conjunto de todos os vectores de reais de tamanho será o nosso espaço conceptual. Admitamos que escolhemos uma representação directa, pelo que qualquer indivíduo é um vector de números reais de tamanho n. Podemos ser levados a concluir que, com esta representação, o espaço conceptual e o real coincidem. Mas tal não é verdadeiro, pois as limitações da representação de reais pelo computador fazem com que apenas uma parte possa ser representada. O espaço efectivo é também, em geral, um subconjunto do espaço real. Admitamos, por exemplo, que usamos apenas um operador de mutação que soma ou diminui uma unidade ao valor de cada componente do vector. Os vectores se podem ligar entre si, através deste operador, vão neste caso depender dos indivíduos da população inicial. É claro que por mutação de um elemento [1,2,3] nunca poderemos chegar a um elemento [1.5,2,3].

(3) Finalmente consideremos o problema das N-rainhas. O espaço conceptual é o espaço de todos os tabuleiros nXn com n rainhas colocadas, e tem por dimensão n ao quadrado levantado a n (maior que 4 milhares de milhões, para n = 8). Admitamos que decidimos representar as soluções considerando que existe apenas uma rainha em cada linha. Agora a dimensão será n levantado a n (maior que 16 milhões, para n=8). Se continuarmos com restrições, impondo que cada coluna só pode ter uma rainha, a dimensão do espaço de procura baixa (?) para “apenas” n factorial (igual a 40320, para n=8). Fixemos esta última representação. Fica claro que o espaço conceptual e o real são distintos, o primeiro contendo o segundo. E o espaço efectivo? Uma vez mais depende dos operadores usados. Admitamos escolher operadores, seja de mutação seja de cruzamento que garantem que os indivíduos resultantes da sua aplicação sejam permutações. Fica apenas por garantir que qualquer permutação pode ser obtida a partir de qualquer outra, ou seja, que independentemente da população inicial podemos chegar a qualquer ponto do espaço de procura real. Caso os operadores sejam liberais, isto é, possam produzir indivíduos que não sejam permutações, estamos a alterar o espaço de procura real, aumentando a sua dimensão. Temos que ter as consequências disso bem presente, em particular, determinar em que medida a qualidade destes indivíduos é medida de modo diverso do da qualidade dos indivíduos que são permutações.

Viáveis e Inviáveis

A questão que discutimos tem associada uma outra nuance, bem complexa. Em muitos problemas do mundo real, por exemplo problemas de escalonamento da produção, existem restrições que têm que ser respeitadas (e.g., uma máquina não pode estar a ser usada em dois processos diferentes). Se a nossa representação não incluir as restrições ao problema (no caso das n-rainhas que vimos acima, a representação por permutação permite incorporar duas das três restrições na representação) então é possível que o espaço real contenha aquilo a que chama soluções inviáveis. Nestes casos podemos optar por escolher os operadores de modo a que o espaço efectivo apenas contenha viáveis. No entanto, pode acontecer que o espaço das soluções viáveis esteja particionado, como se ilustra na figura abaixo.





Se por acaso todos os indivíduos pertencerem a um sub-espaço que não contém a solução óptima, e não for possível passar de um sub-espaço viável para outro igualmente viável, estaremos em maus lençóis. Muitas vezes permite-se então que se guardem soluções inviáveis, na esperança que estas nos ajudem a transitar entre espaços. Agora, como já foi referido mais acima, ficamos com a questão de saber como avaliar esses indivíduos. Uma técnica consiste em penalizá-los, por forma a que tenham baixa qualidade mas se possam manter temporariamente na população.