유전자 프로그래밍 구현
-
09-09-2019 - |
문제
나는 유전 프로그래밍의 일반성에 대해 잘 알고 있지만 유전 프로그래밍 구현에 대한 세부 사항을 보여주는 정보를 어디서 찾을 수 있는지 궁금합니다.저는 C#과 .NET 3.5를 사용하고 있으며 길 찾기와 같은 작업에 유전 프로그래밍을 사용하고 싶고 일반적으로 이것이 무엇을 할 수 있는지 알고 싶습니다.편집하다:내가 찾고 있는 것이 무엇인지 명확히 해야 할 것 같습니다.나는 구문 트리를 저장하는 데 어떤 종류의 데이터 구조가 사용되는지, 번식 작업이 어떻게 수행되는지 등에 관심이 있습니다.
해결책
다음은 그 중 하나의 빠른 재 작성입니다 C ++ Helloworld 유전자 프로그래밍을 배우는 데 도움이되는 예 :
using ga_vector = List<ga_struct>;
class ga_struct
{
public ga_struct(string str, uint fitness)
{
Str = str;
Fitness = fitness;
}
public string Str { get; set; }
public uint Fitness { get; set; }
}
class Program
{
private const int GA_POPSIZE = 2048;
private const int GA_MAXITER = 16384;
private const float GA_ELITRATE = 0.10f;
private const float GA_MUTATIONRATE = 0.25f;
private const float GA_MUTATION = 32767 * GA_MUTATIONRATE;
private const string GA_TARGET = "Hello world!";
private static readonly Random random = new Random((int)DateTime.Now.Ticks);
static void Main(string[] args)
{
ga_vector popAlpha = new ga_vector();
ga_vector popBeta = new ga_vector();
InitPopulation(ref popAlpha, ref popBeta);
ga_vector population = popAlpha;
ga_vector buffer = popBeta;
for (int i = 0; i < GA_MAXITER; i++)
{
CalcFitness(ref population);
SortByFitness(ref population);
PrintBest(ref population);
if (population[0].Fitness == 0) break;
Mate(ref population, ref buffer);
Swap(ref population, ref buffer);
}
Console.ReadKey();
}
static void Swap(ref ga_vector population, ref ga_vector buffer)
{
var temp = population;
population = buffer;
buffer = temp;
}
static void InitPopulation(ref ga_vector population, ref ga_vector buffer)
{
int tsize = GA_TARGET.Length;
for (int i = 0; i < GA_POPSIZE; i++)
{
var citizen = new ga_struct(string.Empty, 0);
for (int j = 0; j < tsize; j++)
{
citizen.Str += Convert.ToChar(random.Next(90) + 32);
}
population.Add(citizen);
buffer.Add(new ga_struct(string.Empty, 0));
}
}
static void CalcFitness(ref ga_vector population)
{
const string target = GA_TARGET;
int tsize = target.Length;
for (int i = 0; i < GA_POPSIZE; i++)
{
uint fitness = 0;
for (int j = 0; j < tsize; j++)
{
fitness += (uint) Math.Abs(population[i].Str[j] - target[j]);
}
population[i].Fitness = fitness;
}
}
static int FitnessSort(ga_struct x, ga_struct y)
{
return x.Fitness.CompareTo(y.Fitness);
}
static void SortByFitness(ref ga_vector population)
{
population.Sort((x, y) => FitnessSort(x, y));
}
static void Elitism(ref ga_vector population, ref ga_vector buffer, int esize)
{
for (int i = 0; i < esize; i++)
{
buffer[i].Str = population[i].Str;
buffer[i].Fitness = population[i].Fitness;
}
}
static void Mutate(ref ga_struct member)
{
int tsize = GA_TARGET.Length;
int ipos = random.Next(tsize);
int delta = random.Next(90) + 32;
var mutated = member.Str.ToCharArray();
Convert.ToChar((member.Str[ipos] + delta)%123).ToString().CopyTo(0, mutated, ipos, 1);
member.Str = mutated.ToString();
}
static void Mate(ref ga_vector population, ref ga_vector buffer)
{
const int esize = (int) (GA_POPSIZE*GA_ELITRATE);
int tsize = GA_TARGET.Length, spos, i1, i2;
Elitism(ref population, ref buffer, esize);
for (int i = esize; i < GA_POPSIZE; i++)
{
i1 = random.Next(GA_POPSIZE/2);
i2 = random.Next(GA_POPSIZE/2);
spos = random.Next(tsize);
buffer[i].Str = population[i1].Str.Substring(0, spos) + population[i2].Str.Substring(spos, tsize - spos);
if (random.Next() < GA_MUTATION)
{
var mutated = buffer[i];
Mutate(ref mutated);
buffer[i] = mutated;
}
}
}
static void PrintBest(ref ga_vector gav)
{
Console.WriteLine("Best: " + gav[0].Str + " (" + gav[0].Fitness + ")");
}
약간의 오류가있을 수 있지만 그렇지 않으면 잘 작동하는 것 같습니다. 또한 C#의 정신으로 더 잘 작성 될 수는 있지만 세부 사항 일뿐입니다. :)
다른 팁
Roger Alsing의 Mona Lisa 프로젝트는 아주 좋은 예입니다.http://rogeralsing.com/2008/12/07/genetic-programming-evolution of-mona-lisa/
편집 : 내가 예를 좋아하는 이유는 작고 이해하기 쉽기 때문입니다. 유전자 프로그래밍의 개념을 파악하는 빠르고 쉬운 방법입니다.
당신은 볼 수 있습니다 적자 생존:Windows Forms를 사용한 자연 선택.
편집하다:이것 좀 봐 이전 SO 질문, 방금 찾았습니다.거의 중복이네요.링크를 이해하지 못해서 죄송합니다(질문에서 그러한 내용을 언급하는 것이 좋습니다).또한 답변이 수락되었음에도 불구하고 추가 답변/수정을 위해 다른 질문이 여전히 열려 있습니다.
Sean Luke 's ECJ 의이 C# .NET 4.0 포트 (Java의 진화 계산)를 사용해 볼 수 있습니다.
http://branecloud.codeplex.com
매우 유연하고 강력한 소프트웨어입니다! 그러나 많은 작업용 콘솔 샘플 (및 전환 중에 개발 된 많은 유용한 단위 테스트)이 포함되어 있기 때문에 비교적 쉽게 시작할 수 있습니다.
벤