Inteligência Artificial I

Universidade Federal de Campina Grande
Departamento de Sistemas e Computação
Disciplina: Inteligência Artificial I Prof.: Joseana Macêdo Fechine

Lista de Exercícios N° 08

Informação adicional: Exemplo de implementação de um AG utilizado para encontrar o ponto máximo da função: f(x) = x2, com f(x) sujeita às seguintes restrições:

0 ≤ x ≤ 31 x é inteiro

Observações:
Codificar x como vetor binário
Criar uma população inicial com 4 indivíduos
Aplicar Mutação com taxa de 1%
Aplicar Crossover com taxa de 60%
Usar seleção proporcional à aptidão (Roleta)
Por simplicidade, a aptidão será a própria função objetivo.
Usar 5 gerações.

Implemente (Utilizando a Linguagem de Programação que preferir) o AG tradicional:

1. Gerar a população inicial.
1. Avaliar cada indivíduo da população.
2. Enquanto critério de parada não for satisfeito faça
2.1 Selecionar os indivíduos mais aptos.
2.2 Criar novos indivíduos aplicando os operadores crossover e mutação.
2.3 Armazenar os novos indivíduos em uma nova população.
2.4 Avaliar cada cromossomo da nova população.

A partir das observações:

Cromossomo:

Cromossomos binários com 5 bits:
0 = 00000
31 = 11111

Aptidão: Por simplicidade, a aptidão será a própria função objetivo.
Exemplo: aptidão(00011) = f(3) = 9

População Inicial:

É aleatória (mas quando possível, o conhecimento da aplicação pode ser utilizado para definir a população inicial).

Cromossomos x f(x)
Prob. de seleção
A1 = 1 1 0 0 1
25
625
54,5 %
A2 = 0 1 1 1 1
15
225
19,6 %
A3 = 0 1 1 1 0
14
196
17,1 %
A4 = 0 1 0 1 0
10
100
8,7 %

Seleção proporcional à aptidão

Pais selecionados

A1 = 11001

A2 = 01111

A2 = 01111

A1 = 11001

Crossover

O crossover é aplicado com uma dada probabilidade denominada taxa de crossover (60% a 90%). Se o crossover é aplicado os pais trocam suas caldas gerando dois filhos, caso contrário os dois filhos