遺傳演算法 (Genetic Algorithm)

訊息

參考文獻

簡體版

English

程式專案下載：(C#) GeneticAlgorithm.cs
程式專案下載：(Java) GeneticAlgorithm.java , GeneticAlgorithmTest.java

簡介

遺傳演算法是模仿兩性生殖的演化機制，使用交配、突變等機制，不斷改進群體適應的一種演算法。此方法廣泛被用在各個人工智慧領域，尤其是在最佳化問題上，遺傳演算法的表現往往相當優異。

原理

傳演算法具有保存良好基因的特性，並且藉由下列公式不斷改進。這個公式就是交配 (Crossover) 機制所造成的效果。

良好基因 (父) + 良好基因 (母) = 更好的個體

然後，藉由『物競天擇、適者生存』的選擇與淘汰機制，良好的個體會被保留下來，繼續繁衍，而不好的個體則會被淘汰，因而絕種。因此，遺傳演算法乃是透過優勝劣敗的生存法則所設計出來的一個競爭性演算法。

當然，在某些問題上，上述的公式不成立時，遺傳演算法也就失效了，因此將無法具有良好的表現。

實作

using System;
using System.Collections.Generic;

public class GeneticAlgorithm
{
    static void Main(string[] args)
    {
        run(new SqrtChromosome(), 100, 100);
    }

    public static void run(Chromosome prototype, int size, int maxGen)
    {
        Population pop = new Population();
        pop.initialize(prototype, size);
        for (int genIdx = 0; genIdx < maxGen; genIdx++)
        {
            pop = pop.reproduction();
            Console.WriteLine("================Population {0}================", genIdx);
            pop.print();
        }
    }
}

public class Population : List<Chromosome> {
  static Random random = new Random(7);
  double mutationRate = 0.0;

  public void initialize(Chromosome prototype, int popSize) {
    this.Clear();
    for (int i=0; i<popSize; i++) {
      Chromosome newChrom = prototype.randomInstance();
      newChrom.calcFitness();
      this.Add(newChrom);
    }
  }

  public Chromosome selection() {
    int shoot  = random.Next((Count*Count) / 2);
    int select = (int) Math.Floor(Math.Sqrt(shoot*2));
    return (Chromosome) this[select];
  }

  private static int compare(Chromosome a, Chromosome b)
  {
      if (a.fitness > b.fitness) return 1;
      else if (a.fitness < b.fitness) return -1;
      else return 0;
  }

  public Population reproduction()
  {
      this.Sort(compare);
      Population newPop = new Population();
      for (int i = 0; i < Count; i++)
      {
          Chromosome parent1 = selection();
          Chromosome parent2 = selection();
          Chromosome child = parent1.crossover(parent2);
          double prob = random.NextDouble();
          if (prob < mutationRate) child.mutate();
          child.calcFitness();
          newPop.Add(child);
      }
      newPop.Sort(compare);
      return newPop;
  }

  public void print()
  {
      int i=1;
      foreach (Chromosome c in this)
      {
          Console.WriteLine("{0:##} : {1}", i, c.ToString());
          i++;
      }
  }
}

public abstract class Chromosome {
  public double fitness;
  abstract public double calcFitness();
  abstract public Chromosome crossover(Chromosome spouse);
  abstract public void mutate();
  abstract public Chromosome randomInstance();
}

public class SqrtChromosome : Chromosome
{
    public static Random random = new Random(7);

    public string value;
    public double k = 2;

    public override double calcFitness()
    {
        double x = double.Parse(value);
        fitness = -1 * Math.Abs(x * x - k);
        return fitness;
    }

    public override Chromosome crossover(Chromosome spouse)
    {
        SqrtChromosome ss = spouse as SqrtChromosome;
        int cutIdx = random.Next(value.Length);
        String head = value.Substring(0, cutIdx);
        String tail = ss.value.Substring(cutIdx);
        SqrtChromosome child = new SqrtChromosome();
        child.value = head + tail;
        return child;
    }

    public override void mutate()
    {
        double v = double.Parse(value);
        v += random.NextDouble() - 0.5;
        value = String.Format("{0:00.0000}", v);
    }

    public override Chromosome randomInstance()
    {
        SqrtChromosome chrom = new SqrtChromosome();
        double v = random.NextDouble() * 10;
        chrom.value = String.Format("{0:00.0000}", v);
        return chrom;
    }

    public override string ToString()
    {
        return String.Format("chromosome={0} fitness={1:F4}", value, fitness);
    }
}

Facebook

page revision: 12, last edited: 18 Sep 2010 07:24

Edit Rate (0) Tags Discuss (0) History Files Print Site tools + Options

金門大學：免費電子書、教材、程式、動畫

訊息

簡介

原理

實作

Facebook

Facebook

Wikidot

Post preview:

Other interesting sites