gajava.txt

这是一个应用遗传算法解决的函数优化问题

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