Skip to content

Instantly share code, notes, and snippets.

@cironunes
Forked from alexsandro-xpt/gist:3015464
Created June 29, 2012 03:22
Show Gist options
  • Save cironunes/3015471 to your computer and use it in GitHub Desktop.
Save cironunes/3015471 to your computer and use it in GitHub Desktop.
Algoritmo genético
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace AG
{
public class Pais
{
public Cromossomo Pai { get; private set; }
public Cromossomo Mae { get; private set; }
public int Locus { get; private set; }
public Pais(Cromossomo p, Cromossomo m)
{
if (p.Count != m.Count)
{
throw new Exception("Os pais não pode conter diferentes quantidades de locus.");
}
Pai = p;
Mae = m;
Locus = p.Count;
}
public Cromossomo EscolheCromossomo()
{
Random r = new Random();
if (r.Next() % 2 == 0)
{
return Mae;
}
else
{
return Pai;
}
}
}
interface ICromossomo : IList<bool>
{
Genotipo[] Genotipos { get; set; }
}
public class Cromossomo : List<bool>, ICromossomo
{
/*public Cromossomo(Genotipo[] genotipos) {
this.Genotipos = genotipos;
}*/
public Cromossomo(bool[] locus, Genotipo[] genotipos)
{
int comprimentoGenotipo = 0;
foreach (Genotipo g in genotipos)
{
comprimentoGenotipo += g.GetQuantidadeLocus();
}
if (comprimentoGenotipo != locus.Length)
{
//throw new Exception("As quantidade de locus deve ser " + comprimentoGenotipo + " e não " + locus.Length + " pois a soma do seus genótipos contem este valor.");
//Console.WriteLine("As quantidade de locus deve ser " + comprimentoGenotipo + " e não " + locus.Length + " pois a soma do seus genótipos contem este valor.");
}
this.Genotipos = genotipos;
this.AddRange(locus);
}
/*public Cromossomo(bool[] locus) {
this.AddRange(locus);
}*/
/// <summary>
/// Força ou Qualidade ou Pureza do Cromossomo
/// </summary>
/// <remarks>Somar os valores da decoficacao dos fenotipos.</remarks>
/// <returns></returns>
public int Forca()
{
int result = 0;
int start = 0;
foreach (Genotipo g in this.Genotipos)
{
result += g.Fenotipo[this.GetRange(start, g.GetQuantidadeLocus()).ToArray()].Key;
start = g.GetQuantidadeLocus();
}
return result;
}
#region ICromossomo Members
public Genotipo[] Genotipos { get; set; }
#endregion
public static string Decodifica(Cromossomo c)
{
string result = string.Empty;
int start = 0;
foreach (Genotipo g in c.Genotipos)
{
result += g.Fenotipo[c.GetRange(start, g.GetQuantidadeLocus()).ToArray()].Value;
start = g.GetQuantidadeLocus();
}
return result;
}
public static bool ExiteCromossomo(Cromossomo c)
{
int start = 0;
foreach (Genotipo g in c.Genotipos)
{
if (!g.Fenotipo.ContainsKey(c.GetRange(start, g.GetQuantidadeLocus()).ToArray()))
{
return false;
}
start = g.GetQuantidadeLocus();
}
return true;
}
}
public class Genotipo
{
public string Nome { get; private set; }
public Dictionary<bool[], KeyValuePair<int, string>> Fenotipo { get; private set; }
public Genotipo(string nome)
{//, KeyValuePair<int, string> fenotipo
Nome = nome;
Fenotipo = new Dictionary<bool[], KeyValuePair<int, string>>(new FenotipoValueCompare());
//Fenotipo.Add(fenotipo.Key,fenotipo.Value);
}
public int GetQuantidadeLocus()
{
Dictionary<bool[], KeyValuePair<int, string>>.KeyCollection kc = Fenotipo.Keys;
return (kc.ToArray() as bool[][])[0].Length;
}
private class FenotipoValueCompare : IEqualityComparer<bool[]>
{
#region IEqualityComparer<bool[]> Members
public bool Equals(bool[] x, bool[] y)
{
int qtIgualdade = 0;
for (int n = 0; x.Length == y.Length && n < x.Length; n++)
{
if (x[n] == y[n])
{
qtIgualdade++;
}
}
return qtIgualdade == x.Length;
}
public int GetHashCode(bool[] obj)
{
int result = 0;
if (obj == null) return 0;
foreach (bool b in obj)
{
result += b.GetHashCode();
}
return result;
}
#endregion
}
}
public static class AlgoritmoGenetico
{
public static int vezes = 0;
public static int Corte { get; private set; }
public static Cromossomo Evoluir(List<Pais> listaDePais, int corte, int PossivelSolucao)
{
vezes++;
AlgoritmoGenetico.Corte = corte;
foreach (Pais parente in listaDePais)
{
ICromossomo Filho1, Filho2;
Filho1 = new Cromossomo(parente.Mae.GetRange(0, AlgoritmoGenetico.Corte).ToArray(), parente.Mae.Genotipos);
Filho2 = new Cromossomo(parente.Pai.GetRange(0, AlgoritmoGenetico.Corte).ToArray(), parente.Pai.Genotipos);
for (int n = AlgoritmoGenetico.Corte; n < parente.Locus; n++)
{
Filho1.Add(parente.Pai[n]);
Filho2.Add(parente.Mae[n]);
}
AlgoritmoGenetico.MutarFilhos(Filho1, Filho2);
Cromossomo Mae = (Cromossomo)Filho1;
Cromossomo Pai = (Cromossomo)Filho2;
//Verifico antes de mutar?
if (Cromossomo.ExiteCromossomo(Mae) && Mae.Forca() > PossivelSolucao)
{
return Mae;
}
if (Cromossomo.ExiteCromossomo(Pai) && Pai.Forca() > PossivelSolucao)
{
return Pai;
}
if (Cromossomo.ExiteCromossomo(Mae) && Cromossomo.ExiteCromossomo(Pai))
{
Pais novoPais = new Pais(Mae, Pai);
return AlgoritmoGenetico.Evoluir(new List<Pais>() { novoPais }, AlgoritmoGenetico.Corte, PossivelSolucao);
}
else if (Cromossomo.ExiteCromossomo(Mae) || Cromossomo.ExiteCromossomo(Pai))
{
Cromossomo sobrevivente = Cromossomo.ExiteCromossomo(Mae) ? Mae : Pai;
//Pode cruzar com próprio pai se for sorteado.
return AlgoritmoGenetico.Evoluir(new List<Pais>() { new Pais(sobrevivente, listaDePais[(new Random()).Next(0, listaDePais.Count - 1)].EscolheCromossomo()) }, AlgoritmoGenetico.Corte, PossivelSolucao);
}
else
{
return AlgoritmoGenetico.Evoluir(new List<Pais>() { new Pais(listaDePais[(new Random()).Next(0, listaDePais.Count - 1)].EscolheCromossomo(), listaDePais[(new Random()).Next(0, listaDePais.Count - 1)].EscolheCromossomo()) }, AlgoritmoGenetico.Corte, PossivelSolucao);
}
}
return null;
}
private static void MutarFilhos(ICromossomo filho1, ICromossomo filho2)
{
Random r = new Random();
int i = r.Next(0, filho1.Count - 1);
filho1[i] = !filho1[i];
filho2[i] = !filho2[i];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment