博客分类：
最近需要学习神经网络，对于神经网络问题的求解其中需要用到遗传算法，所以今天学习了一下遗传算法，主要参看了 http://blog.csdn.net/emiyasstar__/article/details/6938608这篇博客的文章，同时将其使用C++实现的程序用Java再次实现了一遍，不足之处还请指出多包涵
遗传算法：也称进化算法 。 遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识
遗传算法教科书上的步骤：
1.评估每条染色体所对应个体的适应度。
2.遵照适应度越高，选择概率越大的原则，从种群中选择两个个体作为父方和母方。
3.抽取父母双方的染色体，进行交叉，产生子代。
4.对子代的染色体进行变异。
5.重复2，3，4步骤，直到新种群的产生。
我下面说下我所理解的遗传算法，我所理解的遗传算法其实就是“广撒网多捞鱼”,怎么讲？遗传算法一般是先确定初始的群体，群体的每个个体都有两部分组成：1，染色体，也就是基因序列，2，适应性函数 也就是进化能力 ，其中基因序列指的是在实际问题中的一些起主要决定作用的一些特征的编码，主要分为两种：二进制编码和浮点数编码，这种所谓的编码其实就是对应着该“个体”的特征值，而确定了特征编码之后，因为遗传算法还需要进行进化，那么就需要对个体的“适应环[size=medium]境的能力”进行考量，在实际问题中其实也就是距离真正最优解的度量。我理解这个部分的内容为“广撒网阶段”
在确定初始群体之后，就需要进行选择和进化，其实是选择其中的优胜者得到下一代，选择是依据进化论的“物竞天择”理论，也就是适应度越好的个体越容易被选出来，在算法的实现过程中这一部分一般使用“转盘赌”算法实现，所谓“转盘赌”算法，比如现在有四个个体，适应度分别是3,6,9,12 ，那么选择下一代就相当于在一个四个区域的转盘上转指针，其中3的区域占3/(3+6+9+12)=10%，以此类推，当指针停在哪个区域上表示选中哪个个体，显然，适应度越高的个体越容易被选中，在编程中，一般使用这样的算法：
第一步：选择一个介于0（本文讨论的内容适应度大多为正，因为为负的话这种转盘赌方法不适用）和总适应度的适应度，也就是可以描述为：rand(0,1)乘以总的适应度，
第二步骤:将种群的所有个体的适应度进行累加，如果当加到某个个体的时候累加的适应度大于了第一步所得到的适应度，那么就将这个个体取出来
其实有人会质疑，这种算法实现的转盘赌是不是真的是有效的，我不太清除如何使用使用数学概率推导说明，但是这种方法实现的转盘赌还是有一定道理的，直观的理解就是，假设在前N-1步到了比步骤一的数字小的累加和，那么第N步能够超越步骤一的累加和的数字肯定是偏向适应度大的 那个个体(没有数学上的证明，只是直观想像)
好了，选择出杂交的后代接下来就是进行产生后代了，产生后代的过程过程其实是染色体交换和基因变异的过程，对于二进制编码而言，染色体交换是交换父母的一部分序列，基因变异是其中几个序列由1变成0或者0变为1的过程；对于浮点数编码的话，那么染色体交换是一样的（在下文的例子中间因为基因只有一个浮点数的编码，所以没有用到染色体交换），基因突变是指在原有的浮点数基础上加一点随机噪音（加一点变化步长）
交叉重组的过程可以用下图表示
这样再循环就算是遗传算法了。
结合一个例子：求解 f=x*sin(10PI*x)+2在[0,4]之间的最大值 这个例子来源于这个博客：http://blog.csdn.net/emiyasstar__/article/details/6938608，题目的背景和步骤都在原博客里面交代的很清楚，这里我主要给出一个Java版本的实现过程：（本人对C++面向对象部分的编程不是很熟悉，所以使用Java实现）
阶梯思路是先随机在0-4之间选择一个种群，以横坐标作为其基因序列，以函数值作为其适应度，然后不断的选择-交叉重组-变异，去除适应度（函数值）低的留下适应度高的，然后不断迭代找到最优解
package com.luchi.
import java.util.ArrayL
import java.util.L
* 基因载体类
public class Genome {
private List&Double& genomeList=new ArrayList&Double&();
//存放基因序列
//适应度函数值
public List&Double& getGenomeList() {
return genomeL
public void setGenomeList(List&Double& genomeList) {
this.genomeList = genomeL
public double getFitness() {
public void setFitness(double fitness) {
this.fitness =
public Genome(){
public Genome(List&Double& genomeList, double fitness) {
this.genomeList = genomeL
this.fitness =
主要算法类：
package com.luchi.
import java.util.ArrayL
import java.util.A
import java.util.L
import java.util.R
import javax.swing.plaf.synth.SynthSeparatorUI;
* 遗传算法
* @author：luchi
* @description：使用遗传算法求解最值问题
public class GeneticAlgorithm {
//放置所有的种群基因信息
private List&Genome& population=new ArrayList&Genome&();
//种群数量信息
private int popS
//每条染色体总数目
private int chromoL
//种群总的适应度数值
private double totalF
//种群最好的适应度
private double bestF
//种群最坏的适应度
private double worstF
//种群平均的适应度
private double averageF
//最好的适应度的对应的染色体
private Genome bestG
//基因突变概率
private double mutationR
//基因交叉概率
private double crossoverR
//遗传的代数(第几代)
//最大变异步长
private double maxP
//种群适应度的范围,left为左，right为右边
private double leftP
private double rightP
//遗传最大的迭代次数
private int iterN
public int getIterNum() {
return iterN
public void setIterNum(int iterNum) {
this.iterNum = iterN
private Random random=new Random();
private MathCalc mathCalc=new MathCalc();
public List&Genome& getPopulation() {
public void setPopulation(List&Genome& population) {
this.population =
public int getPopSize() {
return popS
public void setPopSize(int popSize) {
this.popSize = popS
public int getChromoLength() {
return chromoL
public void setChromoLength(int chromoLength) {
this.chromoLength = chromoL
public double getTotalFitness() {
return totalF
public void setTotalFitness(double totalFitness) {
this.totalFitness = totalF
public double getBestFitness() {
return bestF
public void setBestFitness(double bestFitness) {
this.bestFitness = bestF
public double getWorstFitness() {
return worstF
public void setWorstFitness(double worstFitness) {
this.worstFitness = worstF
public double getAverageFitness() {
return averageF
public void setAverageFitness(double averageFitness) {
this.averageFitness = averageF
public Genome getBestGenome() {
return bestG
public void setBestGenome(Genome bestGenome) {
this.bestGenome = bestG
public double getMutationRate() {
return mutationR
public void setMutationRate(double mutationRate) {
this.mutationRate = mutationR
public double getCrossoverRate() {
return crossoverR
public void setCrossoverRate(double crossoverRate) {
this.crossoverRate = crossoverR
public int getGeneration() {
public void setGeneration(int generation) {
this.generation =
public double getMaxPerturbation() {
return maxP
public void setMaxPerturbation(double maxPerturbation) {
this.maxPerturbation = maxP
public double getLeftPoint() {
return leftP
public void setLeftPoint(double leftPoint) {
this.leftPoint = leftP
public double getRightPoint() {
return rightP
public void setRightPoint(double rightPoint) {
this.rightPoint = rightP
//构造函数初始化参数值
public GeneticAlgorithm(int popSize, int chromoLength, double totalFitness, double bestFitness, double worstFitness,
double averageFitness, double mutationRate, double crossoverRate, int generation, double maxPerturbation,
double leftPoint, double rightPoint,int iterNum) {
this.popSize = popS
this.chromoLength = chromoL
this.totalFitness = totalF
this.bestFitness = bestF
this.worstFitness = worstF
this.averageFitness = averageF
this.mutationRate = mutationR
this.crossoverRate = crossoverR
this.generation =
this.maxPerturbation = maxP
this.leftPoint = leftP
this.rightPoint = rightP
this.iterNum=iterN
/*转盘赌函数
*注意：这里的转盘赌方法仅适用于适应度的值大于0的染色体序列
//初始化种群信息
public void init(){
population.clear();
double sum=0.0;
//赋予种群最初的信息
for(int i=0;i&popSi++){
double gene=random.nextDouble()*(rightPoint-leftPoint)+leftP
list=new ArrayList&Double&();
list.add(gene);
double fitness=mathCalc.calcFunction(list);
Genome genome=new Genome(list, fitness);
population.add(genome);
setGenInfo();
printGenInfo();
//转盘赌算法
public Genome getChromoRoulette(){
double slice=random.nextDouble()*totalF
Genome choseGenome=
double sum=0.0;
for(int i=0;i&population.size();i++){
choseGenome=population.get(i);
sum+=choseGenome.getFitness();
if(sum&=slice && choseGenome.getFitness()&this.averageFitness){
return choseG
//基因突变
public void Mutate(List&Double& genomList){
for(int i=0;i&genomList.size();i++){
//根据指定的突变率选择突变与否
double randomRate=random.nextDouble();
if(randomRate&this.getMutationRate()){
double raw=(double) genomList.get(i);
raw+=(random.nextDouble()-0.5)*this.getMaxPerturbation();
if(raw&leftPoint){
}else if(raw&rightPoint){
raw=rightP
genomList.set(i, raw);
//进化核心方法,每个双亲生成两个子女
public void Epoch(final List&Genome& popList){
//选择父母，产生后代，注意这里需要size是双数，其实在选择父母的过程中就已经包含了淘汰的过程
List &Genome&newPopList=new ArrayList&Genome&();
while(newPopList.size()&this.getPopSize()){
Genome mum=this.getChromoRoulette();
Genome dad=this.getChromoRoulette();
//生成新的基因序列
List&Double& baby1=mum.getGenomeList();
List&Double& baby2=dad.getGenomeList();
this.Mutate(baby1);
this.Mutate(baby2);
Genome newBabyGenome1=new Genome(baby1,mathCalc.calcFunction(baby1));
Genome newBabyGenome2=new Genome(baby2,mathCalc.calcFunction(baby1));
newPopList.add(newBabyGenome1);
newPopList.add(newBabyGenome2);
popList.clear();
//产生新的一代
for(int i=0;i&newPopList.size();i++){
popList.add(newPopList.get(i));
newPopList=
public void setGenInfo(){
Genome bestGenome=population.get(0);
Genome worstGenome=population.get(0);
double totalFit=0.0;
for(int i=0;i&population.size();i++){
Genome genom=population.get(i);
totalFit+=genom.getFitness();
if(genom.getFitness()&bestGenome.getFitness()){
bestGenome=
if(genom.getFitness()&worstGenome.getFitness()){
worstGenome=
double averageFit=totalFit/population.size();
this.setTotalFitness(totalFit);
this.setBestFitness(bestGenome.getFitness());
this.setWorstFitness(worstGenome.getFitness());
this.setAverageFitness(averageFit);
this.setGeneration(this.getGeneration()+1);
public void printGenInfo(){
System.out.print("the generation is:\t");
System.out.println(this.generation);
System.out.print("the best fitness is:\t");
System.out.println(this.getBestFitness());
System.out.print("the worst fitness is:\t");
System.out.println(this.getWorstFitness());
System.out.print("the average fitness is:\t");
System.out.println(this.getAverageFitness());
System.out.print("the total fitness is:\t");
System.out.println(this.getTotalFitness());
//遗传算法具体操作步骤
public void geneticAlgorithmPorcess(){
int iterNum=this.iterN
this.init();
for (int gen=0;gen&this.iterNgen++){
this.Epoch(this.population);
setGenInfo();
printGenInfo();
package com.luchi.
public class MainTestClass {
public static void main(String[]args){
GeneticAlgorithm genAL=new GeneticAlgorithm(50, 1, 0.0,
0.0, .0, 0.8,
0.8, 0, 0.004, 0, 4, 100);
genAL.geneticAlgorithmPorcess();
结果如下：
the generation is: 101
the best fitness is: 5.841
the worst fitness is: 5.879
the average fitness is: 5.737
the total fitness is: 273.9
迭代次数为101次（多了一次是因为迭代从0开始的）
需要说明的是：遗传算法对初始群体的选取还有遗传父母的个体还是很敏感的，每次运行会有不同的结
果，这里使用（0,4）区间并不是最好的选择，因为其适应值函数包含了负数，这会影响到转盘赌方法的
准确性，因此如果需要遗传算法得到一个很好的效果，还是需要对初始群体和遗传交叉过程进行优化
今天就写到这儿，有问题再议，源代码见附件
1，http://blog.csdn.net/emiyasstar__/article/details/6938608
2， http://blog.csdn.net/b2b160/article/details/4680853/
下载次数: 102
浏览: 61919 次
来自: 北京
u 写道LinApex 写道应用场景在哪？最 ...
LinApex 写道应用场景在哪？最近在做文本分类的事情，正好 ...
应用场景在哪？
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'迷宫问题Java版本实现
如下是迷宫问题的求解思路，可以粘贴在Eclipse下执行，请各位同仁指正。
import java.util.S
public class MazePath {
int maze[][] = new int[10][10];
public MazePath(){
maze[1][3] = 1; maze[1][7] = 1;
maze[2][3] = 1; maze[2][7] = 1;
maze[3][5] = 1; maze[3][6] = 1;
maze[4][2] = 1; maze[4][3] = 1; maze[4][4] = 1;
maze[5][4] = 1;
maze[6][2] = 1; maze[6][6] = 1;
maze[7][2] = 1; maze[7][3] = 1; maze[7][4] = 1; maze[7][6] = 1; maze[7][7] = 1;
maze[8][1] = 1;
for (int j = 0; j & 10; j++) {
maze[0][j] = 1;
maze[9][j] = 1;
maze[j][0] = 1;
maze[j][9] = 1;
public void mazePath () {
Stack stack = new Stack();
int i = 1, j = 1;
stack.add(new PosEle(i, j, 1));
while (!stack.isEmpty()) {
if ((i == 8 && j == 8)) {
printStack(stack);
maze[i][j] = -1;
if (maze[i][j] == 0) {
stack.add(new PosEle(i, j, 1));
maze[i][j] = -1;
current = (PosEle) stack.pop();
} while (current.dir == 4 && !stack.isEmpty());
i = current.i;
j = current.j;
if (current.dir & 4) {
if (current.dir == 1) {
} else if (current.dir == 2) {
} else if (current.dir == 3) {
current.dir++;
stack.add(current);
void printStack(Stack stack) {
System.out.println("Print one path");
for (int i = 0; i & stack.size(); i++) {
System.out.println(stack.get(i));
public static void main(String[] args) {
new MazePath().mazePath();
class PosEle {
int dir = 0;
PosEle (int i, int j, int dir) {
this.dir =
public String toString() {
return i + ", " +
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！见证一个菜鸟的成长历程
迷宫算法（ＪＡＶＡ实现）
迷宫算法（ＪＡＶＡ实现）
对于走迷宫，人们提出过很多计算机上的解法。深度优先搜索、广度优先搜索是使用最广的方法。生活中，人们更愿意使用“紧贴墙壁，靠右行走”的简单规则。
下面的代码则采用了另一种不同的解法。它把走迷宫的过程比做“染色过程”。假设入口点被染为红色，它的颜色会“传染”给与它相邻的可走的单元。这个过程不断进行下去，如果最终出口点被染色，则迷宫有解。
在以下程序中“＃”代表不可通过，“．”代表可以通过。
public class Maze
class Cell//内部类
private C//指向父节点
public Cell(int row, int col, Cell from)
this.row =
this.col =
this.from =
char[][] maze =
{{'#','#','#','#','B','#','#','#','#','#','#','#'},
{'#','#','#','#','.','.','.','.','#','#','#','#'},
{'#','#','#','#','.','#','#','#','#','.','.','#'},
{'#','.','.','.','.','#','#','#','#','#','.','#'},
{'#','.','#','#','#','#','#','.','#','#','.','#'},
{'#','.','#','#','#','#','#','.','#','#','.','#'},
{'#','.','#','#','.','.','.','.','.','.','.','#'},
{'#','.','#','#','.','#','#','#','.','#','.','#'},
{'#','.','.','.','.','#','#','#','.','#','.','#'},
{'#','#','.','#','.','#','#','#','.','#','.','A'},
{'#','#','.','#','#','#','.','.','.','#','#','#'},
{'#','#','#','#','#','#','#','#','#','#','#','#'}};
public void show()
for(int i=0; i&maze. i++)
for(int j=0; j&maze[i]. j++)
System.out.print(" " + maze[i][j]);
System.out.println();
//把与from集合中相邻的可染色节点染色，被染色节点记入 dest
//一旦发现出口将被染色，则返回当前的“传播源”节点
public Cell colorCell(Set&Cell& from, Set&Cell& dest)
Iterator&Cell& it = from.iterator();
while(it.hasNext())
Cell a = it.next();
Cell[] c = new Cell[4];
c[0] = new Cell(a.row-1, a.col, a); //向上
c[1] = new Cell(a.row, a.col-1, a); //向左
c[2] = new Cell(a.row+1, a.col, a); //向下
c[3] = newCell(a.row, a.col+1, a); //向右
for(int i=0; i&4; i++)
if(c[i].row & 0 || c[i].row &= maze.length)
if(c[i].col & 0 || c[i].col &= maze[0].length)
char x = maze[c[i].row][c[i].col];
if(x=='B')
if(x=='.')
maze[c[i].row][c[i].col] = '?';//对可通过路径进行标记
dest.add(c[i]);
public void resolve()
Set&Cell& set = new HashSet&Cell&();
set.add(new Cell(9,11,null));
Set&Cell& set1 = new HashSet&Cell&();
Cell a = colorCell(set, set1);
if(a!=null)
System.out.println("找到解！");
while(a!=null)
maze[a.row][a.col] = '+';//标出通路路径
if(set1.isEmpty())
System.out.println("无解！");
set = set1;
public static void main(String[] args)
Maze m = new Maze();
m.resolve();
程序的输出结果为：＂＋＂代表通路
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！一个简单的java窗体下载小程序(完整代码)_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
赠送免券下载特权
10W篇文档免费专享
部分付费文档8折起
每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
一个简单的java窗体下载小程序(完整代码)
&&java窗体程序,实现最基本的下载文件功能。
阅读已结束，下载本文需要
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩5页未读，
定制HR最喜欢的简历
你可能喜欢}