Inteligência Artificial
Professor: Jerônimo Cordoni Pellegrini
Aluno: Cláudio Antônio Peanho
Algoritmos Genéticos
Para a descrição do algoritmo adota-se:
● Serão realizadas 20 palestras de 2h cada na semana (5 dias).
● 30 palestrantes ofertaram seus serviços.
● Palestras com maior número de pessoas interessadas custam mais.
● O Orçamento do evento é X.
Representação Binária
Um alelo é formado por 5 bits que identificam a palestra. As palestras estão em ordem
nº de pessoas interessadas
crescente do valor retornado pela seguinte fórmula:
.
preço da palestra
Os horários são representados de forma contínua, ou seja, como cada dia apresenta
quatro horários disponíveis para palestras, o quinto horário corresponde à primeira palestra do
dia seguinte. A posição do alelo no cromossomo representa o horário que a palestra será
realizada. Assim o cromossomo é formado por uma seqüência de vinte alelos.
Cromossomo
HORÁRIO 1º
00001
2º
3º
...
19º
20º
01010
11100
...
10111
10100
Função de Avaliação ou Função de Fitness
Como a ordenação das palestras respeita a relação entre o número de pessoas
interessadas e o preço da palestra, busca-se a otimização dos recursos gastos mantendo o
maior número de pessoas em sala, ou seja, freqüentem a série de palestras de um mesmo dia.
No cromossomo, contando à partir do primeiro, cada seqüência de quatro alelos indica
as palestras de um único dia, assim, as strings que representam os alelos tem seus valores
convertidos para um número inteiro que são somados na seqüência que corresponde a um dia,
obtendo-se cinco valores é então realizada a comparação dos valores recebendo um valor
maior o cromossomo cujas parcelas estejam mais distribuídas, garantindo que o genótipo que
condiciona o fenótipo de maior número de pessoas em sala no mesmo dia tenha uma
vantagem evolutiva.
4 alelos
4 alelos
4 alelos
4 alelos
4 alelos
Valor
50
10
15
40
20
10
30
37
40
23
15
30
Para aplicar a restrição de respeito ao orçamento do evento a função soma os custos de
cada palestra no cromossomo, penalizando aqueles que ultrapassem este orçamento.
Para respeitar a restrição de que nenhuma palestra pode ser realizada duas vezes a
função varre o cromossomo em busca de alelos iguais, encontrando aplica a penalização.
A penalização consiste em diminuir o valor retornado pela função em 50%.
A seleção emprega o método da roleta viciada considerando o valor retornado pela
função de Fitness.
Operador de Combinação (Crossover)
Emprega-se o operador padrão de um corte, ou seja, realiza-se o sorteio de uma
posição de corte para o crossover. Aplica-se então uma função de reparo para os valores
inadmissíveis, aqueles sem representação real (ids de palestra 00000 e 11111), essa reparação
consiste em inverter um bit aleatório do alelo proibido.
Operador de Mutação
A cada geração é sorteado um número no intervalo de 0 à 9 se for 0 aplica-se o
operador que inverte um bit aleatório no cromossomo, logo o operador é aplicado 1% das
vezes.
Representação Específica
Para melhor codificar o problema emprega-se um alfabeto com o mesmo número de
caracteres que a quantidade de palestras disponíveis, ou seja, 30 caracteres
alfabeto arábico∪1,2,3 ,4 . Isto evita a existência de representações não admissíveis,
além de não ocorrer a destruição dos alelos como na representação binária.
As palestras mantém a ordenação da representação binário com os caracteres 1, 2, 3, 4
assumindo as últimas posições (vindo depois de z).
O cromossomo é representado por uma matriz 4X5 com as linhas representando os
horários e as colunas os dias. Cada elemento da matriz corresponde a um alelo.
Cromossomo
SEG
TER
QUAR
QUI
SEX
9H
A
R
H
W
Q
11H
3
D
O
X
4
14H
1
J
E
F
L
16H
G
1
P
Z
K
Operador de Recombinação
A recombinação é realizada em duas etapas na primeira é sorteado um valor booleano
que define se o corte será vertical ou horizontal. De acordo com o resultado é sorteado x ou y
com 1x 3 e 1 y4 que representa a posição de corte, então ocorre a recombinação.
Operador de Mutação
É sorteado um número inteiro entre 0 e 10, se 0 o operador é aplicado. Quando
aplicado realiza-se o sorteio de dois números que definirão o alelo a ser modificado
aleatoriamente.