algoritmos geneticos (2)

Prévia do material em texto

*
*
Algoritmos Genéticos 
Seminário de MAC5758 
Introdução ao Escalonamento e Aplicações
Cleber Miranda Barboza 
cleberc@linux.ime.usp.br
http://www.linux.ime.usp.br/~cleberc
*
*
Introdução
Um Algoritmo Genético (AG), conceitualmente, segue passos inspirados no processo biológico de evolução natural segundo a teoria de Darwin
Algoritmos Genéticos seguem a idéia de SOBREVIVÊNCIA DO MAIS FORTE (melhores soluções a cada geração)
*
*
Background
Cromossomos
Todo organismo vivo consiste de células. 
Em cada célula, existe o mesmo conjunto de cromossomos
Cromossomos consistem de genes –seqüências de DNA- que servem para determinar as características de um indivíduo
*
*
Background (Cont.)
Reprodução
Durante o processo de reprodução ocorre-se a recombinação (ou crossover –cruzamento-). Genes dos pais se combinam para formar novos cromossomos.
Os descendentes criados podem sofrer mutações, ou seja, os elementos do DNA podem ser trocados
A adaptação de um organismo pode ser medida pelo sucesso do mesmo em sua vida
*
*
Idéia básica 
Começar com um conjunto de soluções (representado por cromossomos) chamado população
Soluções de uma população são escolhidas e usadas para formar uma nova população (reprodução)
Espera-se que a nova população seja “melhor” que a anterior
*
*
Idéia básica (Cont.)
Soluções que são escolhidas para formar novas soluções (descendentes) são escolhidas de acordo com uma função de adaptação (função objetiva - custo)
O processo é repetido até que uma condição seja satisfeita 
*
*
Questões importantes
Como criar cromossomos e qual tipo de codificação usar?
Como escolher os pais para a realização do crossover?
A geração de uma população a partir de duas soluções pode causar a perda da melhor solução. O que fazer?
*
*
Esboço do algoritmo 
[Início] Geração aleatória de uma população de n cromossomos 
[Adaptação] Verificar a função objetiva f(x) de cada cromossomo x 
[População] Cria-se uma nova população pela repetição a seguir: 
[Seleção] Selecione um par de cromossomos da população de acordo com a adaptação de cada um (os mais bem adaptados tem maior chance de serem escolhidos) 
[Crossover] Produza dois descendentes (filhos) realizando crossover com os cromossomos dos pais. O ponto para a realização do crossover deve ser aleatório. 
[Mutação] Com uma certa probabilidade, o descendente sofre mutação em cada locus (posição no cromossomo). 
[Aceitação] Coloque os descendentes em uma nova população, juntamente com a melhor solução da geração velha
*
*
Esboço do algoritmo (Cont.)
[Troca] Substitua a população velha pela nova
[Teste] Se a condição de finalização é satisfeita, pare, e retorne a melhor solução da população atual 
[Adaptação]
[Laço] Volte ao passo 1
*
*
Codificação
Como realizar a codificação de cromossomos?
É a primeira pergunta que deve ser feita ao resolver um problema com AG
A codificação dependerá fortemente do problema
*
*
Codificação binária
É a mais comum devido a sua simplicidade
Cada cromossomo é uma string de bits – 0 ou 1
	Crom: A = 1 0 1 1 0 0 1 0 1 1
 	Crom: B = 1 1 1 1 1 1 0 0 0 0
Exemplo de uso: problema da mochila
Codificação: Cada bit diz se um elemento está ou não na mochila
*
*
Codificação por permutação
Mais usado em problemas de ordenação
Cada cromossomo é uma string de números que representa uma posição numa seqüência
Crom A: 1  5  3  2  6  4  7  9  8 
Crom B: 8  5  6  7  2  3  1  4  9 
Exemplo de uso: problema do caxeiro viajante
Codificação: os cromossomos descrevem a ordem em que o caxeiro irá visitar as cidades
*
*
Codificação por valor
Usado em problemas onde valores mais complicados são necessários
Cada cromossomo é uma seqüência de valores
Crom A: 1.2324 5.3243 0.4556 2.3293 2.4545 
Crom B: ABDJEIFJDHDIERJFDLDFLFEGT 
Crom C: (back), (back), (right), (forward), (left) 
*
*
Codificação por valor (Cont.)
Exemplo de uso: dada uma estrutura, encontrar pesos para uma rede neural
Codificação: Valores reais num cromossomo representam pesos em uma rede neural
*
*
Crossover
Após decidir qual codificação usar, procede-se com a operação crossover
A operação deve ser realizada sobre os cromossos dos pais para a criação de descendentes
Crom1:	11010 | 00100110110
Crom2:	11011 | 11000011110
Filho 1:	11010 | 11000011110
Filho 2:	11011 | 00100110110
*
*
Mutação
O objetivo da mutação é evitar que as soluções na população fiquem apenas num mínimo local
Filho1 antes	: 1101111000011110
Filho2 antes	: 1101100100110110
Filho1 depois	: 1100111000011110
Filho2 depois	: 1101101100110110
*
*
Problema da grade horária
Escalonar salas, professores e classes em um número fixo de períodos de tal maneira que nenhum professor, classe ou sala sejam usados mais de uma vez num mesmo período
Suposições para resolver o problema
Uma classe consiste de um certo número de estudantes
As classes são disjuntas, ou seja, não há estudantes em comum
*
*
Problema da grade horária (Cont.)
Em cada período uma matéria é lecionada a uma classe 
É possível que uma matéria apareça mais de uma vez em um período
Uma combinação particular de (professor, matéria, sala, classe) é chamada de tupla
A tarefa de realizar a combinação (professor, matéria, sala, classe) para formar uma tupla é feita à parte
*
*
Problema da grade horária (Cont.)
*
*
Problema da grade horária (Cont.)
Para medir a qualidade da grade horária (função objetiva - custo), calcular o número de colisões em qualquer grade. 
A grade aceitável tem custo 0
 O custo de cada período pode ser dado pela soma dos três componentes: custo da classe, custo do professor e custo da sala
*
*
Problema da grade horária (Cont.)
O custo das classes é o número de vezes em que cada classe aparece num período menos 1.
Se uma classe não aparece em nenhum período seu custo é 0
A mesma idéia se aplica para os professores e salas
Assim, o custo da grade é a soma dos custos de cada período
*
*
Problema da grade horária (Cont.)
Como fazer o mapeamento entre a grade e os cromossomos?
Representação do problema usando tuplas:
*
*
Problema da grade horária (Cont.)
Mapeamento das tuplas em períodos (representação de uma grade – indivíduo):
*
*
Problema da grade horária (Cont.)
Representação de tuplas usando cromossomos:
*
*
Problema da grade horária (Cont.)
Reprodução:
*
*
Problema da grade horária (Cont.)
Mutação:
*
*
Problema da grade horária (Cont.)
Problema causado pela perda de tuplas:
*
*
Problema da grade horária (Cont.) - Algoritmo
Enquanto número de gerações < limite e não houver indivíduo perfeito faça
Para cada filho a ser gerado faça
Escolha dois indivíduos aleatórios da população velha
Crie um filho vazio
Para cada período dos pais faça
Realize os crossover dos períodos correspondentes, produzindo um novo período
Copie o novo período para a posição correspondente do filho
*
*
Problema da grade horária (Cont.) - Algoritmo
Arrumar a perda e duplicação de tuplas
Aplicar mutação selecionando aleatóriamente um período e uma tupla
Medir o custo do indivíduo
Se custo < mínimo permitido 
Matar o filho 
Se não
Colocar o filho na população nova
População velha = População nova
*
*
Problema da grade horária (Cont.)
Resultados:
*
*
Problema da grade horária (Cont.)
Paralelizando a reprodução:
*
*
Referências
H.Firas. Handwritten Numeral Recognition Using Neural Networks, em: http://ise.stanford.edu/class/ee368a_proj00/project2/node4.html
GENETIC ALGORITHMS, em: http://cs.felk.cvut.cz/~xobitko/ga/main.html
D.Abramson, J.Abela. A Parallel Genetic Algorithm for Solving the School Timetabling Problem, em: http://citeseer.nj.nec.com/abramson92parallel.html
D. Abramson. Constructing School Timetables using Simulated Annealing: Sequential andParallel Algorithms, em: http://citeseer.nj.nec.com/abramson91constructing.html
J.E.Boggess. USING GENETIC ALGORITHMS FOR SCHEDULING ENGINEERING MISSIONS, em: http://citeseer.nj.nec.com/55397.html