Universidade Federal do ABC
Bacharelado em Ciência e Tecnologia
Inteligência Artificial Prof. Jerônimo Pellegrini
André Filipe de Moraes Batista
DIURNO
2008.2
LISTA DE EXERCÍCIO
Situação Problema
Você está organizando uma série de palestras e mini-cursos Há um grande número de
candidatos com propostas de palestras e mini-cursos. Você já fez uma consulta ao
público e sabe quantos estão interessados em cada palestra e mini-curso. Além disso,
cada convidado cobra um preço fixo pelo trabalho (palestra ou curso). Agora é
necessário escolher quais professores você confirmará para o evento, levando em conta
que:
O custo total deve ficar dentro do orçamento do evento;
Para deixar o máximo de pessoas contentes, você deve mantê-las em atividade
tanto quanto possível, maximizando a quantidade de pessoas por hora em sala;
Só há uma semana disponível, das 9:00 às 18:00 (com uma hora de almoço) para
alocar os eventos;
Modele este problema para ser resolvido por um algoritmo genético, mostrando como
codificá-lo:
Primeiro, usando representação binária;
Depois, tentando usar alguma codificação específica para o problema. Descreva
aqui os operadores de mutação e recombinação, e diga que estratégia você usaria
para a população (e justifique).
Resolução
Vamos considerar alguns fatos para a resolução deste problema:
Existe apenas uma (1) sala;
Existem oito cursos, e estes tem que ser distribuídos em uma semana
(segunda à sexta), em horários de 1 hora cada
O sistema já possui de algum modo uma espécie de tabela contendo o
valor do curso, e da quantidade dos interessados em cada curso;
1
Universidade Federal do ABC
Bacharelado em Ciência e Tecnologia
Inteligência Artificial Prof. Jerônimo Pellegrini
André Filipe de Moraes Batista
DIURNO
2008.2
Uma possível codificação binária para um indivíduo seria da forma
001001100
Onde os três primeiros dígitos (vermelho) representam um determinado
curso, os três dígitos intermediários (laranja) representam um horário da
semana, e os três últimos dígitos o dia da semana.
Como nesta modelagem existem oito cursos. Estes serão representados
pela faixa de valores que vai de 000 até 111. Os horários dos cursos serão
representados pela faixa que vai de 000 (09:00), 001 (10:00)... 011(13:00)1 ....
110(16:00). Para representar os dias da semana (segunda à sexta) temos a
faixa 000 até 100.
Podemos usar esta mesma codificação para desenvolver a segunda parte do
problema. Neste caso, os operadores de mutação e recombinação (cross-over)
podem ser desenvolvidos da seguinte maneira:
Cross-Over - Para cada indivíduo selecionado na função de aptidão
(fitness, que será explicada ao fim deste documento) , o mecanismo de
recombinação funcionará da seguinte maneira:
o Suponha que temos dois indivíduos selecionados, quais sejam:
011101100 pai
001001010 mãe
o O cross-over ocorrerá trocando o grupo de informações, de acordo com a
seguinte regra: O individuo filho de uma recombinação será formado pela
seguinte estrutura: Receberá os genes que indicam o curso de seu pai, os
genes que indicam o dia da semana da sua mãe, e os genes que indicam o
horário serão herdados com uma probabilidade de 50%, ou seja, às vezes do
pai, outras da mãe.
1
Observe que o horário do meio dia não é utilizado. Das 12h00 até 13h00 temos o almoço.
2
Universidade Federal do ABC
Bacharelado em Ciência e Tecnologia
Inteligência Artificial Prof. Jerônimo Pellegrini
André Filipe de Moraes Batista
DIURNO
2008.2
Um exemplo gráfico,
011101100 pai
50%
001XXX010
50%
001001010 mãe
É possível gerar outro indivíduo com o que “sobra” dos genes do pai e da
mãe, aumentando a diversidade da população. Juntamente para aumentar a
diversidade de uma população e evitar que esta se torne estagnada em
máximos locais, podemos usar o operador genético de mutação, que terá o
seguinte mecanismo de funcionamento:
Os indivíduos gerados pela recombinação terão 1% de chance de realizar uma
mutação. Esta mutação ocorrerá de forma aleatória em algum dos genes de um
grupo, ou seja, em um determinado momento um bit dos três genes que indicam uma
característica (curso, horário ou dia da semana) sofrerá mutação, tendo seu valor
invertido. Exemplo:
Considere o indivíduo:
011101100
após uma mutação no 2º bit do grupo de bits (genes) que indicam
o dia da semana, este ficará com a seguinte estrutura: 011101110.
Aproveitando este exemplo, é possível esclarecer outro ponto desta
proposta. Observe que após uma mutação, um indivíduo ficou com a seguinte
estrutura: 011101110, isto indica que o mesmo representa o curso três, que
será oferecido no horário das 15:00hrs e no dia da semana 110! Mas este dia
não existe, pois sexta-feira é representada como 100. Logo, por 110 ser maior
que 100 este indivíduo é inválido para nossa solução. Para isto, entra a função
fitness, que além de outras coisas (tais como o melhor custo, melhor alocação
de número de interessados etc.) irá avaliar se este indivíduo atende ao cenário
do problema. Neste exemplo, como o indivíduo não corresponde ao que
queremos o mesmo é eliminado da população.
3
Universidade Federal do ABC
Bacharelado em Ciência e Tecnologia
Inteligência Artificial Prof. Jerônimo Pellegrini
André Filipe de Moraes Batista
DIURNO
2008.2
A estratégia de população utilizada nesta modelagem, consiste em
que o algoritmo genético não irá retornar apenas um indivíduo, e sim uma
população de indivíduos, que serão otimizados durante o algoritmo para
atender a todos os requisitos do sistema da melhor forma possível. Para tanto,
a função fitness irá qualificar um grupo de n (por exemplo, 10) melhores
indivíduos a cada iteração.
4