昨天惹老婆生气了，实在不应该了。

老婆在天津吃苦受罪我这还光气她，该死该死。。希望老婆大人大量了。请老婆再次相信我可以痛改前非为做好爸爸做准备。

 

正想怎么表达对老婆的歉意时看到CB上一篇关于遗传算法绘制Firefox图标的文章 深受启发，试验如下。

 

目标 生成一句话 "HuaHua I Love You".

过程 首先随机生成与目标等长的随机字符串，每一个字符串作为一个生物，共N只。

每两只生物可以产生n只生物后死亡(这里只是任意两只 没考虑公母-____-)，新一代生物必须经过选择后才可以生存并繁衍。

这里的选择就是靠近目标那句话，n>=2 也就是说种群不会越来越少。  为了保持种群数量不变 n>时 所有子代(N / 2 * n) 都会被排序。

其中最近似目标的N个予以保留 其他就被淘汰掉，周而复始子代越来越靠近目标，这就是整个过程。理论上需要90^17 = 1.6677181699666569e+33才会随机出现目标。。。 那遗传算法呢？

测试后结果如下。

初始种群数N      子代个数n      年代        匹配度(运行200次后平均值)

100                 4                100        0.588

100                 2                100        0.118

100                 8                100        0.647

100                 20               100       0.529

200                 2                100        0.118

200                 4                 100       0.823

200                 8                100        0.882

100                 4                 200       0.588

100                 4                 400       0.588

200                 4                 400       0.823

自己机器不咋滴没敢算太大的数 子代20 的那个已经是算了半天了。

从结果看种群数和子代数对结果影响比较大，但年代从200到400结果没有任何变化。

问题在于我使用的子代产生的算法比较简单没有增加“突变”在这里，父母直接遗传给子代。

导致若干年后子代之间没有任何差距，生物也就不再进化了。

结果里面 子代数20 时 匹配度降低不太容易解释可能是“近亲结婚”的原因，以后再研究。

现在的算法基本 种群数400 子代4 年代100  匹配度就可以达到0.9了。

 

代码如下：

 

import java.util.Random;

public class Life {

 public int familySize = 100;
 public int chindren_count = 4;
 public int era = 100;
 public char[][] families = null;

 public String result = "HuaHua I Love You";

 public Random gods = new Random(System.currentTimeMillis());
 private int max_match = 0;

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int results = 0;
  long t = System.currentTimeMillis();
  for (int i = 0; i < 200;i++) {
   Life l = new Life(200,4, 200);
   l.start();
   l.outputResult();
   results += l.max_match;
  }
  System.out.println((System.currentTimeMillis() - t )/1000);
  System.out.println((double)(results/200)/17);
 }

 public Life(int familySize, int chindren_count, int era) {
  this.familySize = familySize;
  this.chindren_count = chindren_count;
  this.era = era;

 }

 public void outputResult() {
  System.out.println("Init " + familySize);
  System.out.println("Run " + era + " years");
  System.out.println("Chindren " + chindren_count);
  System.out.println("Result " + max_match);
 }

 public void dump(char[][] f) {
  int i = 0;
  for (char[] s : f) {
   System.out.println((i++) + " " + new String(s));
  }
 }

 public void dump(int[] f) {
  int i = 0;
  for (int s : f) {
   System.out.println((i++) + " " + s);
  }
 }

 public void start() {
  families = new char[familySize][result.length()];
  char[] sb = new char[result.length()];
  // init family
  for (int i = 0; i < familySize; i++) {
   for (int j = 0; j < result.length(); j++) {
    char c = (char) (gods.nextInt(90) + ' ');
    sb[j] = c;
   }
   families[i] = sb.clone();
  }

  char[][] children = new char[families.length * chindren_count / 2][result
    .length()];
  int[] matchResult = new int[families.length * chindren_count / 2];

  int g = 0;
  boolean found = false;
  while (g++ < era && !found) {
   disorder(families);
   for (int i = 0; i < familySize / 2; i++) {
    char[] f = families[i];
    char[] m = families[familySize / 2 + i];
    for (int j = 0; j < chindren_count; j++) {
     children[i * chindren_count + j] = markChild(f, m);
    }
   }

   for (int i = 0; i < children.length; i++) {
    matchResult[i] = match(children[i]);
    if (max_match < matchResult[i]) {
     max_match = matchResult[i];
    }
    if (matchResult[i] == result.length()) {

     found = true;
    }
   }
   markChoice(matchResult, children);
   System.arraycopy(children, 0, families, 0, families.length);
  }

  // dump(families);
  // dump(matchResult);
  if (found) {
   System.out.println("got! " + g);
  }

 }

 public void markChoice(int[] data, char[][] strs) {
  int temp;
  char[] t = null;
  for (int i = 0; i < data.length - 1; i++) {
   for (int j = i + 1; j < data.length; j++) {
    if (data[i] < data[j]) {
     temp = data[j];
     t = strs[j];
     data[j] = data[i];
     strs[j] = strs[i];
     data[i] = temp;
     strs[i] = t;
    }
   }
  }

 }

 public int match(char[] s) {
  int v = 0;
  for (int i = 0; i < s.length; i++) {
   if (s[i] == result.charAt(i)) {
    v++;
   }
  }
  return v;
 }

 public void disorder(char[][] type) {
  int size = type.length;
  int p1 = 0;
  int p2 = 0;
  char[] temp;
  for (int i = 0; i < size * 4; i++) {
   p1 = gods.nextInt(size);
   p2 = gods.nextInt(size);
   temp = type[p1];
   type[p1] = type[p2];
   type[p2] = temp;
  }
 }

 public char[] markChild(char[] f, char[] m) {
  char[] son = new char[f.length];
  for (int i = 0; i < son.length; i++) {
   if (son[i] == 0) {
    int j = gods.nextInt(2);
    if (j == 1) {
     son[i] = f[i];
    } else {
     son[i] = m[i];
    }
   }
  }
  return son;
 }

}