} catch (IOException e1) {

}
        System.out.println("Success\r\n");
}

public static void main(String[] args) {
        GeneticAlgorithm a = new GeneticAlgorithm();
        a.Entrance();
}
}

輸入文件為:gadata.txt
內容為:
6 102
6 102
6 102
輸出文件為:galog.txt
下面是我機子上出現的一種結果:
剛完成精英主義前
84.45823768486332 13.734213877165864 8.995601149398595 6130.934874824773
84.45823768486332 13.734213877165864 8.995601149398595 6130.934874824773
36.911334415772814 65.37750347990035 69.6563480569634 0.0
36.911334415772814 65.37750347990035 69.6563480569634 0.0
36.911334415772814 65.37750347990035 69.6563480569634 0.0
8.469410421756518 13.734213877165864 46.36169514458831 6850.415380534821

1 3 6130.934874824773 0.0

1 3 6130.934874824773 0.0

剛完成精英主義后
84.45823768486332 13.734213877165864 8.995601149398595 6130.934874824773
84.45823768486332 13.734213877165864 8.995601149398595 6130.934874824773
8.469410421756518 13.734213877165864 46.36169514458831 6850.415380534821
8.469410421756518 13.734213877165864 46.36169514458831 6850.415380534821
8.469410421756518 13.734213877165864 46.36169514458831 6850.415380534821
8.469410421756518 13.734213877165864 46.36169514458831 6850.415380534821
這是j2se1.5上的結果,照理應該出現的是:
84.45823768486332 13.734213877165864 8.995601149398595 6130.934874824773
84.45823768486332 13.734213877165864 8.995601149398595 6130.934874824773
8.469410421756518 13.734213877165864 46.36169514458831 0.0
8.469410421756518 13.734213877165864 46.36169514458831 6850.415380534821
8.469410421756518 13.734213877165864 46.36169514458831 0.0
8.469410421756518 13.734213877165864 46.36169514458831 6850.415380534821
我不知道是不是函數elitist()中

else {
for (i = 0; i < NVARS; i++) {
              population[worst_mem].gene[i] = population[POPSIZE].gene[i];
}
{System.out.print("\n\n"best_mem"\t"worst_mem"\t"best"\t"worst"\n\n");
            population[worst_mem].fitness = population[POPSIZE].fitness;}
}

應該else語句只執行一吹才對呀,在此應該是
population[3].fitness = population[POPSIZE].fitness;但為什么其它的兩個也改變了?
請知道者告訴我一聲,本人實在是不懂。
萬分感謝！！！ 






自己寫的一個java 遺傳算法的程序2006年12月09日 星期六 20:43書上給的的一個算法,實現了一下

無約束條件 max f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2sin(20*pi*x2)

-3.0<x1<12.1

4.1<x2<5.8

1%的變異

25%交叉

旋轉轉輪選擇

/**
 * 實現Michalewicz
 * 
 * @author not attributable
 * @version 1.0
 */

 public class JGA {  bestindival bd = null;  String[] ipop = new String[10];  int gernation = 0;  public JGA() {
  this.ipop = inialPops();
 }  double calculatefitnessvalue(String str) { // str為染色體，前面18個為x1表示部分，后面15個為x2表示部分
  String str1 = str.substring(0, 18);
  // System.out.println(str1);
  String str2 = str.substring(18);
  // System.out.println(str2);
  int b1 = Integer.parseInt(str1, 2);
  // System.out.println(b1);
  int b2 = Integer.parseInt(str2, 2);
  // System.out.println(b2);
  double x1 = -3.0 + b1 * (12.1 - (-3.0)) / (Math.pow(2, 18) - 1);
  // System.out.println(x1);
  double x2 = 4.1 + b2 * (5.8 - 4.1) / (Math.pow(2, 15) - 1);
  // System.out.println(x2);
  double fitness = 21.5 + x1 * Math.sin(4 * 3.1415926 * x1) + x2
    * Math.sin(20 * 3.1415926 * x2);
  //System.out.println("eval=f(" + x1 + "," + x2 + ")=" + fitness);
  return fitness;
 }  String inialPop() { // 初始化10個字符串
  String res = "";
  for (int i = 0; i < 33; i++) {
   if (Math.random() > 0.5) {
    res += "0";
   } else {
    res += "1";
   }   }
  return res;
 }  String[] inialPops() {
  String[] ipop = new String[10];
  for (int i = 0; i < 10; i++) {
   ipop[i] = inialPop();
  }
  return ipop;  }  void select() {
  double evals[] = new double[10];// 所有染色體適應值
  double p[] = new double[10];// 各染色體選擇概率
  double q[] = new double[10];// 累計概率
  double F = 0;
  for (int i = 0; i < 10; i++) {
   evals[i] = calculatefitnessvalue(ipop[i]);
   if (bd == null) {
    bd = new bestindival();
    bd.fitness = evals[i];
    bd.generations = 0;
    bd.str = ipop[i];
   } else {
    if (evals[i] > bd.fitness)// 最好的記錄下來
    {
     bd.fitness = evals[i];
     bd.generations = gernation;
     bd.str = ipop[i];
    }    }
   F = F + evals[i];// 所有染色體適應值總和   }
  for (int i = 0; i < 10; i++) {
   p[i] = evals[i] / F;
   if (i == 0)
    q[i] = p[i];
   else {
    q[i] = q[i - 1] + p[i];
   }
  }
  for (int i = 0; i < 10; i++) {    double r = Math.random();
   if (r <= q[0]) {
    ipop[i] = ipop[0];    } else {
    for (int j = 1; j < 10; j++) {
     if (r < q[j]) {
      ipop[i] = ipop[j];
      break;
     }
    }
   }
  }  }  void cross() { // 交叉率為25%，平均為25%的染色體進行交叉
  String temp1, temp2;
  for (int i = 0; i < 10; i++) {
   if (Math.random() < 0.25) {
    double r = Math.random();
    int pos = (int) (Math.round(r * 1000)) % 33;
    if (pos == 0) {
     pos = 1;
    }
    temp1 = ipop[i].substring(0, pos)
      + ipop[(i + 1) % 10].substring(pos);
    temp2 = ipop[(i + 1) % 10].substring(0, pos)
      + ipop[i].substring(pos);
    ipop[i] = temp1;
    ipop[(i + 1) / 10] = temp2;    }   }
 }  void mutation() {
  // 1%基因變異m*pop_size 共330個基因，為了使每個基因都相投機會發生變異，需要產生[1--330]上均勻分布的
  for (int i = 0; i < 4; i++) {
   int num = (int) (Math.random() * 330 + 1);
   int chromosomeNum = (int) (num / 33) + 1; // 染色體號
   int mutationNum = num - (chromosomeNum - 1) * 33; // 基因號
   if (mutationNum == 0)
    mutationNum = 1;
   //System.out.println(num + "," + chromosomeNum + "," + mutationNum);
   chromosomeNum = chromosomeNum - 1;
   if(chromosomeNum>=10)
    chromosomeNum=9;
   //System.out.println("變異前" + ipop[chromosomeNum]);
   String temp;
   if (ipop[chromosomeNum].charAt(mutationNum - 1) == '0') {
    if (mutationNum == 1) {
     temp = "1" + ipop[chromosomeNum].substring(mutationNum);
    } else {
     if (mutationNum != 33) {
      temp = ipop[chromosomeNum]
        .substring(0, mutationNum - 1)
        + "1"
        + ipop[chromosomeNum].substring(mutationNum);
     } else {
      temp = ipop[chromosomeNum]
        .substring(0, mutationNum - 1)
        + "1";
     }
    }
   } else {
    if (mutationNum == 1) {
     temp = "0" + ipop[chromosomeNum].substring(mutationNum);
    } else {
     if (mutationNum != 33) {
      temp = ipop[chromosomeNum]
        .substring(0, mutationNum - 1)
        + "0"
        + ipop[chromosomeNum].substring(mutationNum);
     } else {
      temp = ipop[chromosomeNum]
        .substring(0, mutationNum - 1)
        + "1";
     }
    }    }
   ipop[chromosomeNum] = temp;
   //System.out.println("變異后" + ipop[chromosomeNum]);   }  }
 
 void process()
 {
  for(int i=0;i<1000000;i++)
  {
   select();
   cross();
   mutation();
   gernation=i;
   
  }
  System.out.println("最優值"+bd.fitness+",代數"+bd.generations);
 }  public static void main(String args[]) {
  JGA j = new JGA();
  // System.out.println(j.calculatefitnessvalue("000001010100101001101111011111110"));
  j.process();  }
} class bestindival { // 存儲最佳的
 public int generations;  public String str;  public double fitness; }
 











了解遺傳算法



遺傳算法是一種最優化算法，所謂最優化問題，就是這樣一類問題，滿足它的解（稱為可行解）有很多（通常是極多）對于每一種解有一個評價函數得到一個評價值，也就確定了解集的一個偏序關系，在這個偏序關系的求最小值（或最大值）或者近似最小值（或最大值）。因為通常可行解非常之多，所以確定性算法很難做到這一點，而遺傳算法是模擬了生物學中物種進化的過程的一種最優化算法，簡單來說，遺傳算法=遺傳操作+遺傳選擇。







在算法開始之前要做一下準備工作：編碼。

對于不同的問題有不同的解的形式，但要運行遺傳算法就要對其進行抽象的編碼，也就是確定染色體的形式，這里的染色體就是用某種特定的編碼方式描述一個解，通常一個具體的解也稱為個體。而多個不同的個體就組成一個種群，一個種群內有統一的編碼方式。這些概念都完全等同于生物學中的概念，它們是平行的。

例如，N個城市的旅行商問題(TSP)，假如用1,2,...N表示這N個城市，那對于任意這樣的一個排列1p2p3...pN就表示了一個解，這個串就可以認為是一個染色體，它表示一個個體的基因。







遺傳算法有一些基本的操作，如選擇、交叉和變異等。



選擇操作：

首先要知道適應度函數，所謂的適應度函數就是評價函數，通常是問題的目的函數（或它的倒數），它描述了個體的優劣程度同時也決定了選擇操作的概率，設fi表示第i個個體的適應度值，那選擇第i個個體的概率就是fi/∑fj，簡單來說，這個概率的大小就決定了該個體是被淘汰還是被保留。通常的具體做法是用類似賭盤的方法，每個個體占它的適應度那么寬的轉盤大小，每次擲色子，落到哪一格就選哪一格對應的個體。



交叉操作：

交叉操作就是讓2個以上的染色體進行交叉產生后代的過程，具體的交叉操作要看具體的問題。不過我覺得有一個原則，就是要有對稱性，交叉得到的后代中的基因要來源于父代的所有個體中，也就是說n個個體進行交叉是和它們的排列沒關系，這樣子代才有機會得到更優秀的基因。交叉操作是遺傳算法中最重要的操作。最簡單的基本方式是交換父代中染色體片段。



變異操作：

生物可以突變，有時候突變是好的，有時候卻是壞的，但正是因為有了突變才讓有限的種群中基因庫可以非常豐富，也保證了種群的適應能力。變異操作通常是翻轉個體中某段染色體，編碼后的染色體在計算機中都是01串，也就可以隨機的翻轉某個（或多個）bit上的值。



交叉和變異不是一定要發生在選擇了的個體上，而是按一定控制概率發生的，交叉概率比較高通常是0.6~0.95，而變異概率比較低通常是0.001~0.01。







這些操作就確定了子代，就構成了種群進化的方式。于是遺傳算法一般的結構是：



1，產生初始種群G

2，選擇G，交叉、變異->G'

3，是否滿足某個終止條件，如果沒有重復上面過程。







遺傳算法的收斂：

一般的遺傳算法不一定收斂，但給一個條件，讓每代中最優秀的個體直接進入到子代，就能保證一定收斂。







遺傳算法的性能：

可以收斂和收斂得有多快是兩碼事，這方面的研究還在進行中，也是當今一大課題。但可以知道和哪些因素有關，首先是種群規模，也就是種群中個體的數目，如果太小，顯然不利于快速收斂，如果太大又會花更多的時間計算，很矛盾，通常選擇100左右的種群規模。其次，父代可不可以有機會進入子代？如果某次交叉產生的子代比父代還差，那是否還要這個新個體？當然不，父代也要有機會進入子代。然后就是終止條件，一般運用遺傳算法時，對最優解是不了解的，那我們就不知道算法何時停止，一般使用的終止條件是在進化m代后，每代中的最優個體沒有提高時停止，這里的m的選取有時候會誤導你，如果種群中有一個個體早熟，而其它個體沒有，那它將作為最優個體保持m代，而事實上它卻不是最優解，改進的方法可以考慮種群中適應度平均值和最大值兩個方面，而m的選取，不能太小，太大又浪費時間，適中選取。







舉個簡單的例子，用遺傳算法求根號2，（是不是有種殺雞焉用牛刀的感覺，呵呵~）



求根號2，也就是求方程f(x)=x*x-2=0的正整數解，x=1時f(1)<0，x=2時f(2)>0，由介值定理，則1到2中間存在一個根，根據代數基本定理和根的對稱性知這就是我們要找的根（廢話，初中生都知道是1.414左右），由目標函數得到適應度函數，我們選擇個體都在[1,2]之間，那適應度函數我可以取

j(x)=40/(2+|x*x-2|)-10，由x的取值范圍知j的范圍是(0,10)

x和y交叉就用取平均(x+y)/2，交叉概率取0.9，變異概率為0，最后得到的C++程序：






   最近研究了一下遺傳算法，挺有意思的，在一個老外的網站上看到了這個小例子，比較有趣，自己用java實現了一下（老外是用c++實現的）。
    問題：有10張紙牌，編號分別是1到10，現在要將這10張紙牌分為2堆，其中一堆求和為36，另一堆求積為360，問應該怎么分？（也就是說，最終的結果應該是：一堆為2+7+8+9+10=36，另一堆為1*3*4*5*6=360。當然，如果修改題目中的參數，改為32和360，那么結果就是2+3+4+6+7+10=32 和 1*5*8*9=360）
原文地址：http://www.codeproject.com/KB/recipes/Genetic_Algorithm.aspx
另外，這個算法不保證每次都有結果，一般多運行幾次是會得到結果的，當然，如果本身無解，那自然是永遠也找不到結果的。


package andycpp;

import java.util.Random;

public class CardGA {

    /**
     * @param args
     */
    public static void main(String[] args) {
        new CardGA().run();
    }

    private final int pop_size = 30;        //人口池容量
    private final int chrom_length = 10;    //染色體長度
    private final float crossover_rate = 0.6f;  //雜交率
    private final float mutation_rate = 0.01f;  //變異率
    private final int max_generation = 1000;    //繁殖次數的上限
    private final int sum_tagart = 32;          //紙牌求和的目標值
    private final int product_targart = 360;    //紙牌求積的目標值
    private static Random rand = new Random();  //隨機數產生器
    
    private int[][] population = new int[pop_size][chrom_length];   //人口池
    
    public void run() {
        int generation = 0;
        initPopuation(population);
        int winner = 0, loser = 0;
        while(generation < max_generation) {
            generation++;
            winner = rand.nextInt(pop_size);
            loser = rand.nextInt(pop_size);
            if(getFitness(winner) > getFitness(loser)) {
                int temp = winner;
                winner = loser;
                loser = temp;
            }
            if(isAnswer(winner))
                break;
            crossover(winner, loser);
            mutation(loser);
            if(isAnswer(loser)) {
                winner = loser;
                break;
            }
        }
        if(generation == max_generation)
            System.out.println("沒找到合適的結果");
        else
            System.out.println("在第"+generation+"代"+parseToString(winner));