程式實作：遺傳演算法 (採用 C# 實作)

最佳化方法

簡介

歷史

確定性搜尋

基本搜尋法

逐漸深入法

α-β 修剪

A* 搜尋法

隨機搜尋

單粒子隨機搜尋

貪婪演算法

爬山演算法

模擬退火法

禁忌搜尋法

多粒子隨機搜尋

演化策略

鳥群演算法

蟻群演算法

蜂群演算法

程式實作

基本搜尋法

爬山演算法

基因演算法

鳥群演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

原理

本程式採用遺傳演算法計算平方根問題，在程式中我們計算的是 k=2 的平方根。

程式碼

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);
    }
}

執行結果

================Population 0================
1 : chromosome=08.8322 fitness=-76.0078
2 : chromosome=08.7188 fitness=-74.0175
3 : chromosome=08.6914 fitness=-73.5404
4 : chromosome=08.6667 fitness=-73.1117
5 : chromosome=08.6198 fitness=-72.3010
6 : chromosome=08.5150 fitness=-70.5052
7 : chromosome=08.2884 fitness=-66.6976
8 : chromosome=08.2031 fitness=-65.2908
9 : chromosome=08.2028 fitness=-65.2859
10 : chromosome=08.2024 fitness=-65.2794
11 : chromosome=07.9344 fitness=-60.9547
12 : chromosome=07.6752 fitness=-56.9087
13 : chromosome=07.1876 fitness=-49.6616
14 : chromosome=06.6633 fitness=-42.3996
15 : chromosome=06.6380 fitness=-42.0630
16 : chromosome=06.6091 fitness=-41.6802
17 : chromosome=06.5332 fitness=-40.6827
18 : chromosome=05.9871 fitness=-33.8454
19 : chromosome=05.7787 fitness=-31.3934
20 : chromosome=05.6675 fitness=-30.1206
21 : chromosome=05.6541 fitness=-29.9688
22 : chromosome=05.6074 fitness=-29.4429
23 : chromosome=05.2503 fitness=-25.5657
24 : chromosome=05.2380 fitness=-25.4366
25 : chromosome=04.9494 fitness=-22.4966
26 : chromosome=04.8541 fitness=-21.5623
27 : chromosome=04.8034 fitness=-21.0727
28 : chromosome=04.7317 fitness=-20.3890
29 : chromosome=04.7137 fitness=-20.2190
30 : chromosome=04.4482 fitness=-17.7865
31 : chromosome=04.4142 fitness=-17.4852
32 : chromosome=04.0206 fitness=-14.1652
33 : chromosome=04.0201 fitness=-14.1612
34 : chromosome=03.8592 fitness=-12.8934
35 : chromosome=03.8359 fitness=-12.7141
36 : chromosome=03.8329 fitness=-12.6911
37 : chromosome=03.7494 fitness=-12.0580
38 : chromosome=03.7003 fitness=-11.6922
39 : chromosome=03.6914 fitness=-11.6264
40 : chromosome=03.6914 fitness=-11.6264
41 : chromosome=03.6687 fitness=-11.4594
42 : chromosome=03.6645 fitness=-11.4286
43 : chromosome=03.5339 fitness=-10.4884
44 : chromosome=03.5150 fitness=-10.3552
45 : chromosome=03.3536 fitness=-9.2466
46 : chromosome=03.3381 fitness=-9.1429
47 : chromosome=03.3381 fitness=-9.1429
48 : chromosome=03.3381 fitness=-9.1429
49 : chromosome=03.1755 fitness=-8.0838
50 : chromosome=03.0957 fitness=-7.5834
51 : chromosome=03.0617 fitness=-7.3740
52 : chromosome=02.9717 fitness=-6.8310
53 : chromosome=02.8695 fitness=-6.2340
54 : chromosome=02.8072 fitness=-5.8804
55 : chromosome=02.2398 fitness=-3.0167
56 : chromosome=02.0821 fitness=-2.3351
57 : chromosome=02.0821 fitness=-2.3351
58 : chromosome=01.9934 fitness=-1.9736
59 : chromosome=00.2404 fitness=-1.9422
60 : chromosome=00.2457 fitness=-1.9396
61 : chromosome=00.2480 fitness=-1.9385
62 : chromosome=00.2488 fitness=-1.9381
63 : chromosome=00.2488 fitness=-1.9381
64 : chromosome=00.2617 fitness=-1.9315
65 : chromosome=01.9717 fitness=-1.8876
66 : chromosome=00.4482 fitness=-1.7991
67 : chromosome=01.9487 fitness=-1.7974
68 : chromosome=00.4595 fitness=-1.7889
69 : chromosome=01.9401 fitness=-1.7640
70 : chromosome=00.5185 fitness=-1.7312
71 : chromosome=00.5185 fitness=-1.7312
72 : chromosome=00.5226 fitness=-1.7269
73 : chromosome=01.9204 fitness=-1.6879
74 : chromosome=00.6560 fitness=-1.5697
75 : chromosome=00.6560 fitness=-1.5697
76 : chromosome=01.8708 fitness=-1.4999
77 : chromosome=01.8708 fitness=-1.4999
78 : chromosome=01.8695 fitness=-1.4950
79 : chromosome=00.7900 fitness=-1.3759
80 : chromosome=00.8204 fitness=-1.3269
81 : chromosome=00.8386 fitness=-1.2968
82 : chromosome=00.8628 fitness=-1.2556
83 : chromosome=01.8031 fitness=-1.2512
84 : chromosome=00.8695 fitness=-1.2440
85 : chromosome=01.7439 fitness=-1.0412
86 : chromosome=01.7363 fitness=-1.0147
87 : chromosome=01.0902 fitness=-0.8115
88 : chromosome=01.0988 fitness=-0.7926
89 : chromosome=01.1195 fitness=-0.7467
90 : chromosome=01.6430 fitness=-0.6994
91 : chromosome=01.6404 fitness=-0.6909
92 : chromosome=01.6404 fitness=-0.6909
93 : chromosome=01.2398 fitness=-0.4629
94 : chromosome=01.2398 fitness=-0.4629
95 : chromosome=01.2488 fitness=-0.4405
96 : chromosome=01.5185 fitness=-0.3058
97 : chromosome=01.5185 fitness=-0.3058
98 : chromosome=01.5175 fitness=-0.3028
99 : chromosome=01.4603 fitness=-0.1325
100 : chromosome=01.4595 fitness=-0.1301
...
================Population 10================
1 : chromosome=01.5185 fitness=-0.3058
2 : chromosome=01.5005 fitness=-0.2515
3 : chromosome=01.4683 fitness=-0.1559
4 : chromosome=01.4655 fitness=-0.1477
5 : chromosome=01.4607 fitness=-0.1336
6 : chromosome=01.4607 fitness=-0.1336
7 : chromosome=01.4607 fitness=-0.1336
8 : chromosome=01.4606 fitness=-0.1334
9 : chromosome=01.4605 fitness=-0.1331
10 : chromosome=01.4605 fitness=-0.1331
11 : chromosome=01.4605 fitness=-0.1331
12 : chromosome=01.4603 fitness=-0.1325
13 : chromosome=01.4603 fitness=-0.1325
14 : chromosome=01.4603 fitness=-0.1325
15 : chromosome=01.4600 fitness=-0.1316
16 : chromosome=01.4496 fitness=-0.1013
17 : chromosome=01.4487 fitness=-0.0987
18 : chromosome=01.4487 fitness=-0.0987
19 : chromosome=01.4487 fitness=-0.0987
20 : chromosome=01.4487 fitness=-0.0987
21 : chromosome=01.4487 fitness=-0.0987
22 : chromosome=01.4487 fitness=-0.0987
23 : chromosome=01.4487 fitness=-0.0987
24 : chromosome=01.4487 fitness=-0.0987
25 : chromosome=01.4486 fitness=-0.0984
26 : chromosome=01.4486 fitness=-0.0984
27 : chromosome=01.4486 fitness=-0.0984
28 : chromosome=01.4485 fitness=-0.0982
29 : chromosome=01.4485 fitness=-0.0982
30 : chromosome=01.4485 fitness=-0.0982
31 : chromosome=01.4485 fitness=-0.0982
32 : chromosome=01.4485 fitness=-0.0982
33 : chromosome=01.4485 fitness=-0.0982
34 : chromosome=01.4485 fitness=-0.0982
35 : chromosome=01.4485 fitness=-0.0982
36 : chromosome=01.4485 fitness=-0.0982
37 : chromosome=01.4485 fitness=-0.0982
38 : chromosome=01.4484 fitness=-0.0979
39 : chromosome=01.4484 fitness=-0.0979
40 : chromosome=01.4484 fitness=-0.0979
41 : chromosome=01.4484 fitness=-0.0979
42 : chromosome=01.4457 fitness=-0.0900
43 : chromosome=01.4457 fitness=-0.0900
44 : chromosome=01.4457 fitness=-0.0900
45 : chromosome=01.4457 fitness=-0.0900
46 : chromosome=01.4457 fitness=-0.0900
47 : chromosome=01.4457 fitness=-0.0900
48 : chromosome=01.4456 fitness=-0.0898
49 : chromosome=01.4456 fitness=-0.0898
50 : chromosome=01.4456 fitness=-0.0898
51 : chromosome=01.4456 fitness=-0.0898
52 : chromosome=01.4456 fitness=-0.0898
53 : chromosome=01.4456 fitness=-0.0898
54 : chromosome=01.4456 fitness=-0.0898
55 : chromosome=01.4455 fitness=-0.0895
56 : chromosome=01.4455 fitness=-0.0895
57 : chromosome=01.4455 fitness=-0.0895
58 : chromosome=01.4455 fitness=-0.0895
59 : chromosome=01.4455 fitness=-0.0895
60 : chromosome=01.4455 fitness=-0.0895
61 : chromosome=01.4455 fitness=-0.0895
62 : chromosome=01.4455 fitness=-0.0895
63 : chromosome=01.4455 fitness=-0.0895
64 : chromosome=01.4455 fitness=-0.0895
65 : chromosome=01.4455 fitness=-0.0895
66 : chromosome=01.4407 fitness=-0.0756
67 : chromosome=01.4407 fitness=-0.0756
68 : chromosome=01.4405 fitness=-0.0750
69 : chromosome=01.4405 fitness=-0.0750
70 : chromosome=01.4005 fitness=-0.0386
71 : chromosome=01.4005 fitness=-0.0386
72 : chromosome=01.4005 fitness=-0.0386
73 : chromosome=01.4005 fitness=-0.0386
74 : chromosome=01.4005 fitness=-0.0386
75 : chromosome=01.4005 fitness=-0.0386
76 : chromosome=01.4005 fitness=-0.0386
77 : chromosome=01.4005 fitness=-0.0386
78 : chromosome=01.4005 fitness=-0.0386
79 : chromosome=01.4006 fitness=-0.0383
80 : chromosome=01.4006 fitness=-0.0383
81 : chromosome=01.4006 fitness=-0.0383
82 : chromosome=01.4006 fitness=-0.0383
83 : chromosome=01.4007 fitness=-0.0380
84 : chromosome=01.4055 fitness=-0.0246
85 : chromosome=01.4055 fitness=-0.0246
86 : chromosome=01.4055 fitness=-0.0246
87 : chromosome=01.4085 fitness=-0.0161
88 : chromosome=01.4085 fitness=-0.0161
89 : chromosome=01.4085 fitness=-0.0161
90 : chromosome=01.4195 fitness=-0.0150
91 : chromosome=01.4187 fitness=-0.0127
92 : chromosome=01.4187 fitness=-0.0127
93 : chromosome=01.4186 fitness=-0.0124
94 : chromosome=01.4186 fitness=-0.0124
95 : chromosome=01.4186 fitness=-0.0124
96 : chromosome=01.4185 fitness=-0.0121
97 : chromosome=01.4185 fitness=-0.0121
98 : chromosome=01.4185 fitness=-0.0121
99 : chromosome=01.4184 fitness=-0.0119
100 : chromosome=01.4184 fitness=-0.0119
...

================Population 99================
1 : chromosome=01.4154 fitness=-0.0034
2 : chromosome=01.4154 fitness=-0.0034
3 : chromosome=01.4154 fitness=-0.0034
4 : chromosome=01.4154 fitness=-0.0034
5 : chromosome=01.4154 fitness=-0.0034
6 : chromosome=01.4154 fitness=-0.0034
7 : chromosome=01.4154 fitness=-0.0034
8 : chromosome=01.4154 fitness=-0.0034
9 : chromosome=01.4154 fitness=-0.0034
10 : chromosome=01.4154 fitness=-0.0034
11 : chromosome=01.4154 fitness=-0.0034
12 : chromosome=01.4154 fitness=-0.0034
13 : chromosome=01.4154 fitness=-0.0034
14 : chromosome=01.4154 fitness=-0.0034
15 : chromosome=01.4154 fitness=-0.0034
16 : chromosome=01.4154 fitness=-0.0034
17 : chromosome=01.4154 fitness=-0.0034
18 : chromosome=01.4154 fitness=-0.0034
19 : chromosome=01.4154 fitness=-0.0034
20 : chromosome=01.4154 fitness=-0.0034
21 : chromosome=01.4154 fitness=-0.0034
22 : chromosome=01.4154 fitness=-0.0034
23 : chromosome=01.4154 fitness=-0.0034
24 : chromosome=01.4154 fitness=-0.0034
25 : chromosome=01.4154 fitness=-0.0034
26 : chromosome=01.4154 fitness=-0.0034
27 : chromosome=01.4154 fitness=-0.0034
28 : chromosome=01.4154 fitness=-0.0034
29 : chromosome=01.4154 fitness=-0.0034
30 : chromosome=01.4154 fitness=-0.0034
31 : chromosome=01.4154 fitness=-0.0034
32 : chromosome=01.4154 fitness=-0.0034
33 : chromosome=01.4154 fitness=-0.0034
34 : chromosome=01.4154 fitness=-0.0034
35 : chromosome=01.4154 fitness=-0.0034
36 : chromosome=01.4154 fitness=-0.0034
37 : chromosome=01.4154 fitness=-0.0034
38 : chromosome=01.4154 fitness=-0.0034
39 : chromosome=01.4154 fitness=-0.0034
40 : chromosome=01.4154 fitness=-0.0034
41 : chromosome=01.4154 fitness=-0.0034
42 : chromosome=01.4154 fitness=-0.0034
43 : chromosome=01.4154 fitness=-0.0034
44 : chromosome=01.4154 fitness=-0.0034
45 : chromosome=01.4154 fitness=-0.0034
46 : chromosome=01.4154 fitness=-0.0034
47 : chromosome=01.4154 fitness=-0.0034
48 : chromosome=01.4154 fitness=-0.0034
49 : chromosome=01.4154 fitness=-0.0034
50 : chromosome=01.4154 fitness=-0.0034
51 : chromosome=01.4154 fitness=-0.0034
52 : chromosome=01.4154 fitness=-0.0034
53 : chromosome=01.4154 fitness=-0.0034
54 : chromosome=01.4154 fitness=-0.0034
55 : chromosome=01.4154 fitness=-0.0034
56 : chromosome=01.4154 fitness=-0.0034
57 : chromosome=01.4154 fitness=-0.0034
58 : chromosome=01.4154 fitness=-0.0034
59 : chromosome=01.4154 fitness=-0.0034
60 : chromosome=01.4154 fitness=-0.0034
61 : chromosome=01.4154 fitness=-0.0034
62 : chromosome=01.4154 fitness=-0.0034
63 : chromosome=01.4154 fitness=-0.0034
64 : chromosome=01.4154 fitness=-0.0034
65 : chromosome=01.4154 fitness=-0.0034
66 : chromosome=01.4154 fitness=-0.0034
67 : chromosome=01.4154 fitness=-0.0034
68 : chromosome=01.4154 fitness=-0.0034
69 : chromosome=01.4154 fitness=-0.0034
70 : chromosome=01.4154 fitness=-0.0034
71 : chromosome=01.4154 fitness=-0.0034
72 : chromosome=01.4154 fitness=-0.0034
73 : chromosome=01.4154 fitness=-0.0034
74 : chromosome=01.4154 fitness=-0.0034
75 : chromosome=01.4154 fitness=-0.0034
76 : chromosome=01.4154 fitness=-0.0034
77 : chromosome=01.4154 fitness=-0.0034
78 : chromosome=01.4154 fitness=-0.0034
79 : chromosome=01.4154 fitness=-0.0034
80 : chromosome=01.4154 fitness=-0.0034
81 : chromosome=01.4154 fitness=-0.0034
82 : chromosome=01.4154 fitness=-0.0034
83 : chromosome=01.4154 fitness=-0.0034
84 : chromosome=01.4154 fitness=-0.0034
85 : chromosome=01.4154 fitness=-0.0034
86 : chromosome=01.4154 fitness=-0.0034
87 : chromosome=01.4154 fitness=-0.0034
88 : chromosome=01.4154 fitness=-0.0034
89 : chromosome=01.4154 fitness=-0.0034
90 : chromosome=01.4154 fitness=-0.0034
91 : chromosome=01.4154 fitness=-0.0034
92 : chromosome=01.4154 fitness=-0.0034
93 : chromosome=01.4154 fitness=-0.0034
94 : chromosome=01.4154 fitness=-0.0034
95 : chromosome=01.4154 fitness=-0.0034
96 : chromosome=01.4154 fitness=-0.0034
97 : chromosome=01.4154 fitness=-0.0034
98 : chromosome=01.4154 fitness=-0.0034
99 : chromosome=01.4154 fitness=-0.0034
100 : chromosome=01.4154 fitness=-0.0034

結語

讀者可以看到 100 代之後，整個群體都收斂了，因此用 Genetic Algorithm 所解出來 2 的平方根是 1.4154。

Facebook
aicodecsharpgeneticalgorithm
page revision: 3, last edited: 18 Sep 2010 07:24
Edit Rate (0) Tags Discuss (0) History Files Print Site tools + Options
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License