Alguém tem idéia de como é feito?
E qual a diferença ou vantagem que esse algoritmo genético para esse exemplo traz?
Putz… Isso é matar uma formiga com uma bomba H.
Se você quer usar algoritmos genéticos, escolha um problema melhor, como o problema do caixeiro viajante.
mas preciso necessariamente para esse problema…
Tenho esse código para equação do 1º grau, mas preciso alterar para equação do 2º grau:
/*
- Solucionar equações do primeiro grau,
*/
public class Eq1Grau {
private double[] individuo; // população (cromossomos) de indivíduos. Individuo = double
private int numIndividuos = 10; // número da propulação (optei como nào alterável ao longo do processo)
private double txSelecao = .50; // % da população que vai sobreviver à próxima geração (através da seleção)
private double txMutacao = .10; // % da população corrente que vai sofrer mutacão
private double minValor = -100; // mínimo valor possível (estimado) de um indivíduo
private double maxValor = +100; // mínimo valor possível (estimado) de um indivíduo
private double a,b; // coeficientes da equação
private static double PRECISAO = 0.01; // uma casa decimal
public Eq1Grau(double a, double b) {
this.a = a;
this.b = b;
// gerando população inicial (aleatória, entre os extremos minValor e maxValor
individuo = new double[numIndividuos];
for(int i=0;i<numIndividuos;i++)
individuo[i] = minValor+Math.random()*(maxValor-minValor);
}
public void selecao() {
double[] individuoNovaPop = new double[numIndividuos];
// montando roleta
double[] roleta = new double[numIndividuos];
roleta[0] = fitnessRelativa(0);
for(int i=1;i<numIndividuos;i++) {
roleta[i] = roleta[i-1] + fitnessRelativa(i); // define os componentes da roleta, que se distribuirá de forma proporcional
}
int numSel = (int)Math.ceil(numIndividuos*txSelecao); // número de indivíduos a serem selecionados
// gira a roleta "numSel" vezes
for(int i=0;i<numSel;i++) {
double seta = Math.random()*100; // girou a roleta (0 a 100)
for(int j=0;j<roleta.length;j++) {
if(roleta[j]>=seta) { // selecionado
individuoNovaPop[i] = individuo[j];
break;
}
}
} // fim da roleta
individuo = individuoNovaPop;
return;
}
public double fitness(int ind) { // função de aptidão
double funcao = a*individuo[ind] + b; // para raiz, funcao = 0;
return Math.abs(1/funcao); // quando mais perto do zero, maior o valor e maior a aptidão (valor absoluto)
}
private double fitnessRelativa(int ind) {
return 100 * fitness(ind)/somaFitness();
}
private double somaFitness() {
double soma = 0;
for(int i=0;i<numIndividuos;soma += fitness(i++));
return soma;
}
public double getAptidaoMedia(){
return somaFitness()/numIndividuos;
}
public void cruzamento() {
int numSel = (int)Math.ceil(numIndividuos*txSelecao); // número de indivíduos que foram selecionados
int dif = 1; // diferenca entre posição entre os pais
int pos = 0; // começa do primeiro elemento selecionado
for(int i=numSel;i<numIndividuos;i++){
double filho = (individuo[pos] + individuo[pos+dif])/2; // um filho por "casal"
individuo[i] = filho; // adicionado à nova população
pos++; // incrementando a posição no vetor
if(pos>numSel-dif) {// implica que não vai ter parceiro, então ...
pos = 0; // reinicia do primeiro elemento
dif++; // incrementa a diferença de posição entre pais a se cruzarem
}
}
}
public void mutacao() {
int nMut = (int) Math.ceil(numIndividuos*txMutacao);
for(int i=0;i<nMut;i++) {
// selecionando o indivíduo (índice)
int indice = (int) Math.round(Math.random()*(numIndividuos-1));
// realizando a mutação (raiz aleatória)
individuo[indice] = minValor+Math.random()*(maxValor-minValor);
}
}
public boolean criterioParada() {
Double solucao = getSolucao();
return solucao==null?false:true;
}
public Double getSolucao() {
for(int i=0;i<numIndividuos;i++) {
double valor = a*individuo[i]+b; // se raiz, valor = 0 (ou aproximado, a depender da precisao
if (Math.abs(valor)<=PRECISAO) // precisão de uma casa
return individuo[i]; // retorna o indivíduo-solucao;
}
return null;
}
public static void main(String[] args) {
Eq1Grau e = new Eq1Grau(3,10);
System.out.println("Populacao 0: (AM="+round(e.getAptidaoMedia(),3)+")"+ stringIndividuos(e.individuo));
int it=1;
while(!e.criterioParada()&&it<100000) { // até que o critério de parada seja atingido (ou 100.000 iterações)
e.selecao(); // seleciona os mais aptos
e.cruzamento(); // cruzamento dos indivíduos
e.mutacao(); // mutação aleatória dos indivíduos
if(it%10000==0 || (it%1000==0&&it<=10000) || (it%100==0&&it<=1000) || (it%10==0&&it<=100) || it<=10)
System.out.println("Populacao "+it+": (AM="+round(e.getAptidaoMedia(),3)+")"+stringIndividuos(e.individuo)); // mostra nova população
it++;
}
// imprimindo solução
System.out.println("Populacao "+it+": (AM="+round(e.getAptidaoMedia(),2)+")"+stringIndividuos(e.individuo)); // mostra nova população
System.out.println("Solução: "+round(e.getSolucao(),2));
}
public static double round(double valor,int numCasasDecimais) {
double n = Math.pow(10,numCasasDecimais);
return Math.round(valor*n)/n;
}
public static String stringIndividuos(double[] individuo){
String todos = "";
for(int i=0;i<individuo.length;todos += " " + round(individuo[i++],3));
return todos;
}
}
Caro Portuga,
isso é feio!!!
estou fazendo, caso eu termine até amanhã lhe passo…
Feio é não saber e ficar quieto…se puder me ajudar ficarei grato…valeu!
Voce que implementou para a esquação de 1° grau?
Se quiser aprender mais sobre algoritmos genéticos voce pode ver no seguinte blog http://sofiaia.wordpress.com/2008/07/13/algoritmos-geneticos/
Tem 4 artigos sobre isso… o problema que é em C.
E sim… isso é matar formigas com uma bomba de anti-matéria o.0
[size=18][color=orange][b]Caro luizfgaspar , resumirei o uso e o tradeoff dos Algoritmos Geneticos:
Vantagem:
Busca Direcionada Paralela(Testa varias soluçoes sempre indo em direção a mais apta)
Mutação e Crossover(Contornam o problema do minimo local de funções)
Geralmente usados em problemas NP(Solução em Tempo Polinomial) ou seja dificeis de computar
Pode rodar facilmente em GRIDS(Computação Paralela)
Desvantagem:
Necessita de um bom projeto pra função de fitness
Necessita de um otimo projeto para seus cromossomos(soluções)
Pode necessitar de muito poder computacional
Espero ter ajudado![/b][/color][/size]
No caso de equações do segundo grau, sinto em dizer que não há vantagens em utilizar o algoritmo genético.
Só desvantagens:
- Não garante um resultado correto;
- Envolve um alto custo computacional;
- Complexidade enorme - o que reduz as chances de manutenção do código;
Eu tenho o framework de IA do SofiaIA em Java. Mas acho que seu professor quer que você implemente mesmo.
Se seu algoritmo foi bem implementado, para alterar de primeiro para segundo grau bastará alterar a função de fitness.
Outra coisa, sempre que for postar código, por favor, utilize a tag code. Se ainda não sabe usar esse recurso, leia o seguinte tópico:
http://www.guj.com.br/posts/list/50115.java
Assim seu código aqui aparecerá colorido e formatado. O tópico também ensina a usar outros recursos do fórum. 