/*
* IA.cpp
*
* Created on: 11/10/2008
*
* Trabalho de Inteligência Artificial
*
* Alunos:
* Alexandre Nogueira D´Amato Gomes - C100406
* Bruno Dutra - C100448
* Jonathan Moratelli de Carvalho - C100420
* Reinaldo Rodrigues Vieira - C100403
*
*/
#include <iostream>
using std::cout;
using std::endl;
#include <math.h>
#include "IA.h"
#include "Tabuleiro.h"
IA::IA(int numRainhas)
{
nr = numRainhas;
if (nr < 4) // validacao do numero de rainhas
{
cout << "O numero de rainhas deve ser superior ou igual a 4" << endl;
system("PAUSE");
exit(0);
}
}
vector<int> IA::aleatorio ()
{
vector<int> v(nr);
for (int i = 0; i < nr; i++)
{
v[i] = rand() % nr;
}
return v;
}
vector<int> IA::subidaEncosta ()
{
vector<int> vAtual(nr), vProximo(nr);
vAtual = aleatorio();
while(1)
{
vProximo = melhorVizinho(vAtual);
if (ataques(vProximo) < ataques(vAtual))
{
vAtual = vProximo;
}
else
{
return vAtual;
}
}
}
vector<int> IA::simulatedAnnealing()
{
vector<int> atual, proximo, melhor;
int dE, T = nr * 30;
atual = aleatorio();
melhor = atual;
for (int i = T; i > 0; i--)
{
if (i == 0)
{
return melhor;
}
proximo = aleatorio();
dE = ataques(proximo) - ataques(atual);
if (dE < 0)
{
atual = proximo;
}
else
{
if(((int) exp(-(dE/i))) == 1)
{
atual = proximo;
}
}
if (ataques(atual) < ataques(melhor))
{
melhor = atual;
}
}
return melhor;
}
vector<int> IA::genetico(const int algInicial)
{
vector<vector<int> > g1, g2, gf; // Matrizes com posibilidades
vector<int> tmp_v(nr), tmp_v2(nr); // vetores temporários
int ne = nr * 3; // número de estados
int nePar = 0; // variavel de controle da paridade dos estados
long numvezes = 0; // Armazena o numero de iterações
Tabuleiro tabuleiro; // Armagena o tabuleiro para desenha-lo na tela
for (int i = 0; i < ne; i++) // criação dos estados aleatoriamente
{
tmp_v = geraEstadoInicialGen(algInicial);
g1.push_back(tmp_v);
}
if (ne % 2 != 0) // Verifica se o número de estados gerados é impar
{
nePar = ne - 1;
}
else
{
nePar = ne;
}
while(ataques(g1[0]) != 0 || numvezes == 0)
{
/////////////////////////////////////////////////////////////////////
// cruzamento
/////////////////////////////////////////////////////////////////////
for (int i = 0; i < nePar; i++) // Cruza a primeira metade de um vetor com a segunda metade do proximo vetor
{
for (int j = 0; j < (nr / 2); j++)
{
tmp_v[j] = g1[i][j];
tmp_v2[j] = g1[i + 1][j];
}
for (int j = (nr / 2); j < nr; j++)
{
tmp_v[j] = g1[i + 1][j];
tmp_v2[j] = g1[i][j];
}
g2.push_back(tmp_v);
g2.push_back(tmp_v2);
i++; // incrementado denovo porque estamos cruzando de dois em dois
}
if (ne % 2 != 0) // Cruza o ultimo estado com o primeiro se o número de estados é impar
{
for (int j = 0; j < (nr / 2); j++)
{
tmp_v[j] = g1[0][j];
tmp_v2[j] = g1[ne - 1][j];
}
for (int j = (nr / 2); j < nr; j++)
{
tmp_v[j] = g1[ne - 1][j];
tmp_v2[j] = g1[0][j];
}
g2[0] = tmp_v;
g2.push_back(tmp_v2);
}
/////////////////////////////////////////////////////////////////////
// mutação
/////////////////////////////////////////////////////////////////////
for (unsigned int i = 0; i < g2.size(); i++)
{
if (ataques(g2[i]) > 0)
{
for (int j = 0; j < nr; j++)
{
if (rand() % 3 == 0) // 33% de chance de ocorrer uma mutação
{
g2[i][j] = rand() % nr;
}
}
}
}
gf.insert(gf.begin(), g1.begin(), g1.end());
gf.insert(gf.end(), g2.begin(), g2.end()); // junta todos os vetores
/////////////////////////////////////////////////////////////////////
// Pré seleção - Não existe nesse caso pois não são geradas posições de rainhas > nrainhas
/////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////
//Seleção
/////////////////////////////////////////////////////////////////////
gf = ordenaPorAtaques(gf); //ordena os vetores por ordem de ataques
/*
// Mostra estados ordenados
cout << endl;
for (unsigned int i = 0; i < gf.size(); i++)
{
for (int j = 0; j < nr; j++)
{
cout << gf[i][j] << " | ";
}
cout << "--> " << ataques(gf[i]) << endl;
}
*/
for (int i = 0; i < ne; i++) // Remove a segunda metade dos estados
{
gf.pop_back();
}
// Limpa os vetores
g1.clear();
g2.clear();
g1 = gf;
gf.clear();
// Desenha o tabuleiro na tela
tabuleiro.setTabuleiro(g1[0], nr); // Desenha o estado de menor número de ataques (primeiro da lista)
tabuleiro.desenha();
cout << "Numero de Ataques: " << ataques(g1[0]) << endl << endl;
numvezes++;
}
cout << "Numero de Iteracoes: " << numvezes << endl;
return g1[0];
}
int IA::ataques(vector<int> v)
{
int na = 0; // Número de Ataques
for (int i = 0; i < nr; i++)
{
for (int j = i + 1; j < nr; j++)
{
if (v[i] == v[j] || abs(v[i] - v[j]) == abs(i - j))
na++;
}
}
return na;
}
vector<int> IA::geraEstadoInicialGen(int alg) /// Gera o estado inicial para o algoritmo genético
{
if (alg < 1 || alg > 3) // valida o valor digitado
{
cout << "Algoritmo Inicial invalido" << endl;
system("PAUSE");
exit(0);
}
vector<int> v;
switch (alg)
{
case 1:
v = aleatorio();
break;
case 2:
v = subidaEncosta();
break;
case 3:
v = simulatedAnnealing();
break;
}
return v;
}
vector<int> IA::melhorVizinho(vector<int> v) // Escolhe o vizinho com menos ataques
{
unsigned int menor = ataques(v), atual = 0;
int aux = 0;
for (unsigned int i = 0; i < v.size(); i++)
{
aux = v[i];
for (unsigned int j = 0; j < v.size(); j++)
{
v[i] = j;
atual = ataques(v);
if (atual < menor)
{
menor = atual;
aux = j;
}
else
{
v[i] = aux;
}
}
}
return v;
}
vector<vector<int> > IA::ordenaPorAtaques(vector<vector<int> > v)
{
vector<int> aux(1);
for (unsigned int i = 0; i < v.size(); i++)
{
for (unsigned int j = 0; j < (v.size() - 1); j++)
{
if (ataques(v[j]) > ataques(v[j + 1]))
{
aux = v[j];
v[j] = v[j + 1];
v[j + 1] = aux;
aux.clear();
}
}
}
return v;
}