Reorganização

[jcoelho72]

TProcura - classe com métodos de estatísticas, parâmetros e outros, para suporte a procuras, independente do algoritmo
TProcuraConstrutiva - algoritmos construtivos
TProcuraMelhorativa - algoritmos melhorativos --- definir classes para codificações mais utilizadas, já com os operadores habituais implementados: lista binária, inteira, reais, permutação, árvore
TProcuraAdversa - jogos

Colocar tudo num só repositório, eventualmente com mais que um projeto, para teste dos algoritmos construtivos/melhorativos/adversos. Classes com exemplos em pastas específicas, os ficheiros a incluir em projetos novos, na raiz.

Necessário rever os exemplos todos, acertar documentação

[jcoelho72]

Funcionalidades base de TProcura estão feitas, falta agora a documentação, teste exemplo, e revisão das restantes classes.

[jcoelho72]

Notas de tarefas a realizar neste âmbito:

• rever/refazer exemplos (e também testes de validação)
  - TProcura
  - TProcuraConstrutiva
  - TProcuraAdversa
  - (ainda não TProcuraMelhorativa)

• TProcuraMelhorativa
  - classes de representação e operadores

  • representação para subconjuntos (com restrição de cardinalidade)
  • exemplos TProcuraMelhorativa
  • algoritmos evolutivos (livro de Evolocionary Computing )
  • outros algoritmos (livro de Search Methodologies)
  • rever atividades
    1:10 -R Resultados/out -P P1=1:12 x P6=1:3
    1:10 -R Resultados/outSort -P P1=2 P3=1:10 x P6=1:3
  • ponderar:
    • classe TProcura - gestão de parâmetros e indicadores, executa testes paramétricos para diferentes conjuntos de parâmetros e instâncias, gerando resultados em CSV prontos para análise em relatórios dinâmicos. Atualmente em série, previsto a versão MPI.
      class TProcuraConstrutiva - herda de TProcura - algoritmos construtivos (exatos) e diferentes parâmetros implementados, bastando definir geração de sucessores e função heurística
      classe TProcuraMelhorativa - herda de TProcura - grande variedade de algoritmos evolutivos e melhorativos de solução única, bastando definir representação, operadores e avaliação do estado
      classe TRepresentacaoBinaria - herda de TProcuraMelhorativa - representação binária e variedade de operadores implementados, bastando definir avaliação de estado
      classe TRepresentacaoInteira - herda de TProcuraMelhorativa - representação inteiros e variedade de operadores implementados, bastando definir avaliação de estado
      classe TRepresentacaoReal - herda de TProcuraMelhorativa - representação em números reais e variedade de operadores implementados, bastando definir avaliação de estado
      classe TRepresentacaoPermutacao - herda de TProcuraMelhorativa - representação permutação e variedade de operadores implementados, bastando definir avaliação de estado
      classe TRepresentacaoArvore - herda de TProcuraMelhorativa - representação em árvore e variedade de operadores implementados, bastando definir avaliação de estado
      classe TProcuraAdversa - herda de TProcuraConstrutiva - para procuras adversas com algoritmos minimax e diferentes opções implementadas (Monte Carlo previsto), bastando definir geração de sucessores e função heurística
  • ler manuais + adicionar issues
  • colocar referência aos 3 manuais no github
  • TProcuraMelhorativa --- colocar posteriormente mais métodos
    • colocar nova solução como uma aleatória, e explorar os operadores?
  • definir operadores (parâmetros para depois)
  • codificação/representação:
    • todas as codificações representam uma solução, todas as soluções têm uma codificação
    • representação binária
      • mutação:
        • bitwise mutation: cada bit pode mudar com probabilidade p_m (um aleatório para cada bit)
          • entre em média existir uma mutação por cada filho, ou uma mutação por cada geração
      • cruzamento/recombinação
        • One-Point crossover: escolher um ponto aleatório, e copiar uma parte de cada pai, até ao ponto, invertendo após o ponto
        • N-Point crossover: idêntico para N pontos, alternando
        • Uniform corssover: aleatório para cada bit, escolhendo do pai/mãe aleatoriamente
    • representação inteira
      • Random resetting: each position, with probability p_m, a new value is selected at random --- good for cardinal atributes
      • Creep Mutation: adiciona um valor pequeno (positivo ou negativo) a cada gene, de uma distribuição de média zero, com probabilidade p_m
        • pode haver saltos pequenos e grandes
      • cruzamento/recombinação: igual à representação binária
    • representação real (cada gene com limites distintos)
      • mutação uniforme: com probabilidade de p_m, gerar um valor aleatório dentro dos limites do gene
      • mudação não-uniforme: adicionar um valor da guassiana N(0,?) o desvio padrão é parâmetro (respeitando os limites) - desvio padrão é o "mutation step size" -- normal aplicar sempre este operador por gene, sendo o desvio padrão que controla o efeito
      • mutação adaptativa: adiciona o sigma à codificação <x1,...,xn,sigma)
        • pode haver um sigma por cada dimensão <x1,...,xn,sigma_1,...,sigma_n>
      • mutações correlacionadas
      • cruzamento/recombinação:
        • idêntico a binário, selecionando um valor - mas assim apenas a mutação permite adicionar valores -- recombinação discreta
        • junção de genes por media: z_i=alfa x_i + (1-alfa) y_i --- o range de cada gene vai diminuindo com o tempo --- recombinação aritmética
        • junção de genes gerando um perto de um dos pais (mutação garantida) - blend recombination
    • representação permutação
      • pode haver simetrias, caso do TSP em que a cidade de arranque não é importante (fixar uma cidade de arranque)
      • swap mutation: duas posições aleatórias, trocar os elementos
      • insert mutation: duas posições aleatórias, um deles é movido para junto do primeiro (os outros deslocam-se)
      • scramble mutation: tudo, ou um subconjunto, é baralhado
      • inversion mutation: entre duas posições, inverter a ordem desses elementos
      • cruzamento/recombinação:
        • partially Mapped Crossover (PMX): fig. 4.12 a 4.14)
        • edge crossover:
        • order crossover: copy a segment from P1; copy the remaining numbers as they appear in P2, to the end of the list
        • cycle crossover: swap cycles between parentes
    • representação em árvore
      • function set + terminmal set
      • mutation: escolhe um nó e troca a sub-árvore
      • crossover:
        • sbutree crossover: o ponto de crossover são nós nas árvores
  • population management:
    • generacional model: tamanho da população,matting pool, descendência dos pais > população substituída pelos melhores descendentes
    • steady-state model: apenas teta indivíduos, são substituídos por teta descendentes - generational gap - pode ser teta=1
  • parente selection (fitness assumed to be the greater the better, and not negative)
    • fitness proportional selection: fitness(i)/SUM fitness(k), para todo o k -- using a window, subtracting beta (can be the worst value)
    • raking selection: sort the population by fitness, and set probabilities depending on rank
  • selection probabilities:
    • roulette wheel: select parentes by the probability function, the number times needed.
    • stochastic universal sampling: generate a random number, but then consider teta equal intervals
    • tournemant selection: seleciona dois aleatoriamente (com ou sem reposição), e vê qual deles é o melhor, repetindo até teta indivíduos
      • o torneio pode ser de tamanho superior a 2, escolhendo sempre o melhor - quanto maior o tamanho do tormeio, maior é a pressão da escolha
      • probabilidade p do melhor elemento ser escolhido (de omissão 1, mas pode ser menor)
    • uniform parent selection: todos com a mesma probabilidade de serem selecionados
    • overselection for large populations: dividir a população em topo x% e o restante. Selecionar 80% do primeiro grupo, e o restante do segundo.
  • Survivor selection
    • age-based replacement: utiliza apenas a idade, de modo a que cada elemento fique o mesmo tempo na população (mas pode haver cópias)
      • no modelo geracional, este tempo é 1, já que é tudo substituído
      • no steady-state, substituir o mais antigo (FIFO)
    • fitness based replacement:
      • replace worst
      • elitism: mantém o melhor caso a descendência não seja igual ou melhor (um descendente não se mantém)
      • round-robin tournement: each individual is evaluated against q others - the ones with most wins are selected (q=10)
      • miu+teta selection: pais e descendência são juntos, e o topo N é escolhido para a próxima geração
      • miu.teta selection:
    • selection pressure
  • Diversity:
    • fitness sharing: distance in phenotypic if possible, otherwise genotypic
      • The fitness is divided byh the number of individuals close to the individual

      should use fitness proportionate selection

    • Crowding: select for replacement a set of individuals at random, and replace the most similar of those.
      • peaks became with the same number of individuals
    • automatic specialization: population contains multiple species, and matting only with the same specie
      • distância é utilizada para não cruzar elementos demasiado distantes
    • multiple populations
      • em ambientes paralelos (ou em série).
      • após umas quantas gerações (época), uns quantos elementos são trocados com as populações vizinhas (migração)
      • quando trocar indivíduos
      • quantos trocar ? poucos é melhor
      • como dividir a população em sub-populações? -- desde que tenha um mínimo, quantas mais populações, melhor
      • parâmetros distintos em cada subpopulação
    • distribuição espacial
      • cada indivíduo tem um ponto, que permite recombinar apenas com os vizinhos
      • distribuição toroidal grid
      • cruzamento entre indivíduos perto, substituindo um no mesmo quadrado