Instruções

O projecto deverá ser resolvido em grupos de três alunos. Todos os grupos deverão enviar um mail para lcf@math.ist.utl.pt indicando quem são os elementos do grupo. Na volta receberão a letra que identificará o grupo.

A entrega do projecto decorrerá no dia 21 de Dezembro de 2006 (5ª feira) entre as 12h00 e as 13h00, na sala P1.12 (sala de dúvidas do Departamento de Matemática). As orais serão marcadas por ordem de entrega dos projectos.

Os alunos que não puderem comparecer neste horário deverão avisar antecipadamente um docente da disciplina por forma a combinar a entrega antes daquele prazo. Em situação alguma serão aceites projectos entregues após as 13h00 de dia 21 de Dezembro de 2006.

A resolução deverá conter:

  • um relatório incluindo a especificação dos tipos de dados utilizados, as principais opções de implementação, a listagem do programa e exemplos de execução do programa desenvolvido;
  • um CD contendo os ficheiros de código desenvolvidos (todos os pacotes necessários e o programa principal).
Todos os projectos deverão vir claramente identificados com o nome, número mecanográfico e curso de todos os elementos do grupo e ainda a letra que foi atribuída ao grupo aquando da inscrição.

Instruções

O projecto deverá ser resolvido em grupos de três alunos. Todos os grupos deverão enviar um mail para lcf@math.ist.utl.pt indicando quem são os elementos do grupo. Na volta receberão a letra que identificará o grupo.

A entrega do projecto decorrerá no dia 21 de Dezembro de 2006 (5ª feira) entre as 12h00 e as 13h00, na sala P1.12 (sala de dúvidas do Departamento de Matemática). As orais serão marcadas por ordem de entrega dos projectos.

Os alunos que não puderem comparecer neste horário deverão avisar antecipadamente um docente da disciplina por forma a combinar a entrega antes daquele prazo. Em situação alguma serão aceites projectos entregues após as 13h00 de dia 21 de Dezembro de 2006.

A resolução deverá conter:

  • um relatório incluindo a especificação dos tipos de dados utilizados, as principais opções de implementação, a listagem do programa e exemplos de execução do programa desenvolvido;
  • um CD contendo os ficheiros de código desenvolvidos (todos os pacotes necessários e o programa principal).
Todos os projectos deverão vir claramente identificados com o nome, número mecanográfico e curso de todos os elementos do grupo e ainda a letra que foi atribuída ao grupo aquando da inscrição.

Introdução

Na construção de estradas em terreno montanhoso, o traçado da estrada tem de ter em conta o relevo do terreno que atravessa. Por um lado, fazer aterros, viadutos e túneis é mais caro que construir ao nível do terreno, mas em contrapartida quanto mais curto for o percurso mais barata fica a construção da estrada. Para determinar o traçado da estrada é necessário ter estes dois factores em conta e tentar encontrar um percurso que por um lado minimize as variações em altura dos terrenos que atravessa, mas que também não faça desvios demasiadamente grandes.

Na figura da esquerda mostra-se o relevo dum terreno quadrado (a gradação de cor num ponto corresponde à cota desse ponto). Pretende-se construir uma estrada que atravesse este terreno do canto inferior esquerdo ao canto superior direito; por conveniência, convencionou-se tomar para unidade de comprimento a medida do lado do terreno. A figura da direita mostra um exemplo dum traçado possível para a estrada que representa um bom compromisso entre os dois factores acima descritos. Note que esta estrada é mais comprida que uma linha recta, mas em compensação evita variações grandes de nível.

Problema

O objectivo deste projecto é, utilizando princípios de Programação Evolutiva, desenvolver em Mathematica um programa para encontrar uma solução para o problema acima.

O relevo do terreno é dado por uma função Φ : [0,1]×[0,1]→ℜ. No exemplo da figura acima, Φ(x,y) = (y−x/3(32x2−48x+19))2. A estrada é uma curva parametrizada por dois polinómios p,q : [0,1]→[0,1] de grau máximo gm, ou seja, é o conjunto dos pontos {(p(t),q(t)) : t∈[0,1]}.

Para resolver o problema, começa-se por gerar no instante zero uma população de ν indivíduos, todos representando um caminho em linha recta (ou seja, p(t) = q(t) = t), e fazê-la evoluir até ao instante final τ. A cada indivíduo z está associado um conforto φ(z)=e−η∑i=1N|Φ[p(i/N),q(i/N)]−Φ[p(i−1/N),q(i−1/N)]|, que intuitivamente é proporcional à soma das variações médias de declives ao longo de N troços do percurso.

Cada indivíduo z evolui de acordo com o seu conforto através dos mecanismos aleatórios seguintes.

  • Morte, com tempo médio −log(1−φ(z))μ entre eventos.
  • Reprodução, com tempo médio −log(φ(z))ρ entre eventos. A reprodução é sempre efectuada com o melhor indivíduo da população. Da reprodução surge um novo indivíduo cujo caminho é parametrizado por polinómios obtidos da seguinte forma: primeiro, toma-se para coeficiente de xk a média aritmética dos coeficientes de xk nos polinómios correspondentes dos dois progenitores; em seguida divide-se o polinómio obtido pelo seu valor no ponto 1.
  • Mutação, com tempo médio −log(φ(z))δ entre eventos. Uma mutação consiste em alterar um coeficiente (que não o do termo independente) ou em um ou em ambos os polinómios; o novo coeficiente é um número aleatório no intervalo de amplitude 2log(φ(z))ω/1+gm centrado no valor original do coeficiente. Cada polinómio assim obtido é de novo dividido pelo seu valor no ponto 1.

A população evolui em função da evolução individual dos seus elementos e ainda por ocorrência de epidemias. Quando o número de indivíduos excede um máximo &\nu;max, ocorre uma epidemia. À epidemia sobrevive a fracção s dos indivíduos com maior conforto, em que s é um número aleatório no intervalo [ω12] (com 0<ω12<1).

Programa

O programa a desenvolver deve resolver este problema. Para tal, deve:
  • receber interactivamente o conjunto seguinte de dados:
    • função de relevo Φ
    • grau máximo gm dos polinómios a utilizar;
    • instante final τ(>0) da evolução;
    • lista de parâmetros ν,N,η,μ,ρ,δ, ω, νmax, ω1 e ω2;
  • devolver o indivíduo z com maior conforto e os coeficientes dos polinómios que parametrizam o seu caminho;
  • mostrar, quando solicitado, o resultado de 20 observações da população igualmente espaçadas no tempo.
    • Modo gráfico: sequência de fotografias, mostrando o relevo do terreno e o melhor percurso encontrado até ao momento.
    • Modo textual: sequência de tuplos incluindo o instante actual, o número de eventos já realizados, a dimensão da população, os coeficientes dos polinómios que parameterizam o caminho do melhor indivíduo encontrado e o conforto deste indivíduo.
Desenvolva o programa seguindo o método de programação por camadas centrado nos dados.
  1. Comece por identificar os objectos de trabalho, nomeadamente polinómio, indivíduo e população. Especifique equacionalmente os tipos de dados correspondentes.
  2. Desenvolva de seguida o programa abstracto pretendido sobre a camada que disponibiliza estes objectos.
  3. Implemente as camadas identificadas em 1. sobre a camada básica do Mathematica, nomeadamente recorrendo a listas, disponibilizando-as sob a forma de pacote.
  4. Integre o programa obtido em 2. com os pacotes desenvolvidos em 3.
  5. Experimente o programa desenvolvido em 4. com diversos conjuntos de dados à sua escolha. Em particular, considere o conjunto:
    • Φ(x,y) = (y−x/3(32x2−48x+19))2;
    • grau máximo dos polinómios: gm=5;
    • τ=4;
    • parâmetros de evolução: ν=10, N=1000, η=3/4, μ=200, ρ=δ=1, ω=10, νmax=100, ω1=0.4 e ω2=0.6.

Apêndice

Relativamente à simulação de variáveis aleatórias, recorra à função Random da linguagem Mathematica do modo seguinte:

  • para simular a observação duma variável aleatória exponencial com valor médio m use a expressão -m Log[Random[]];
  • para gerar aleatoriamente (com distribuição uniforme) um número inteiro positivo até k use a expressão Random[Integer,{1,k}];
  • para gerar aleatoriamente um número real entre a e b com distribuição uniforme use a expressão Random[Real,{a,b}].