本文引自:http://luchi007.iteye.com/blog/2263061
最近需要学习神经网络,对于神经网络问题的求解其中需要用到遗传算法,所以今天学习了一下遗传算法,主要参看了 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.genetic;
- import java.util.ArrayList;
- import java.util.List;
- /*
- * 基因载体类
- * */
- public class Genome {
- private List<Double> genomeList=new ArrayList<Double>(); //存放基因序列
- private double fitness; //适应度函数值
- public List<Double> getGenomeList() {
- return genomeList;
- }
- public void setGenomeList(List<Double> genomeList) {
- this.genomeList = genomeList;
- }
- public double getFitness() {
- return fitness;
- }
- public void setFitness(double fitness) {
- this.fitness = fitness;
- }
- public Genome(){
- super();
- }
- public Genome(List<Double> genomeList, double fitness) {
- super();
- this.genomeList = genomeList;
- this.fitness = fitness;
- }
- }
主要算法类:
- package com.luchi.genetic;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.List;
- import java.util.Random;
- import javax.swing.plaf.synth.SynthSeparatorUI;
- /*
- * 遗传算法
- * @author:luchi
- * @date:2015/12/9
- * @description:使用遗传算法求解最值问题
- * */
- public class GeneticAlgorithm {
- //放置所有的种群基因信息
- private List<Genome> population=new ArrayList<Genome>();
- //种群数量信息
- private int popSize;
- //每条染色体总数目
- private int chromoLength;
- //种群总的适应度数值
- private double totalFitness;
- //种群最好的适应度
- private double bestFitness;
- //种群最坏的适应度
- private double worstFitness;
- //种群平均的适应度
- private double averageFitness;
- //最好的适应度的对应的染色体
- private Genome bestGenome;
- //基因突变概率
- private double mutationRate;
- //基因交叉概率
- private double crossoverRate;
- //遗传的代数(第几代)
- private int generation;
- //最大变异步长
- private double maxPerturbation;
- //种群适应度的范围,left为左,right为右边
- private double leftPoint;
- private double rightPoint;
- //遗传最大的迭代次数
- private int iterNum;
- public int getIterNum() {
- return iterNum;
- }
- public void setIterNum(int iterNum) {
- this.iterNum = iterNum;
- }
- private Random random=new Random();
- private MathCalc mathCalc=new MathCalc();
- public List<Genome> getPopulation() {
- return population;
- }
- public void setPopulation(List<Genome> population) {
- this.population = population;
- }
- public int getPopSize() {
- return popSize;
- }
- public void setPopSize(int popSize) {
- this.popSize = popSize;
- }
- public int getChromoLength() {
- return chromoLength;
- }
- public void setChromoLength(int chromoLength) {
- this.chromoLength = chromoLength;
- }
- public double getTotalFitness() {
- return totalFitness;
- }
- public void setTotalFitness(double totalFitness) {
- this.totalFitness = totalFitness;
- }
- public double getBestFitness() {
- return bestFitness;
- }
- public void setBestFitness(double bestFitness) {
- this.bestFitness = bestFitness;
- }
- public double getWorstFitness() {
- return worstFitness;
- }
- public void setWorstFitness(double worstFitness) {
- this.worstFitness = worstFitness;
- }
- public double getAverageFitness() {
- return averageFitness;
- }
- public void setAverageFitness(double averageFitness) {
- this.averageFitness = averageFitness;
- }
- public Genome getBestGenome() {
- return bestGenome;
- }
- public void setBestGenome(Genome bestGenome) {
- this.bestGenome = bestGenome;
- }
- public double getMutationRate() {
- return mutationRate;
- }
- public void setMutationRate(double mutationRate) {
- this.mutationRate = mutationRate;
- }
- public double getCrossoverRate() {
- return crossoverRate;
- }
- public void setCrossoverRate(double crossoverRate) {
- this.crossoverRate = crossoverRate;
- }
- public int getGeneration() {
- return generation;
- }
- public void setGeneration(int generation) {
- this.generation = generation;
- }
- public double getMaxPerturbation() {
- return maxPerturbation;
- }
- public void setMaxPerturbation(double maxPerturbation) {
- this.maxPerturbation = maxPerturbation;
- }
- public double getLeftPoint() {
- return leftPoint;
- }
- public void setLeftPoint(double leftPoint) {
- this.leftPoint = leftPoint;
- }
- public double getRightPoint() {
- return rightPoint;
- }
- public void setRightPoint(double rightPoint) {
- this.rightPoint = rightPoint;
- }
- //构造函数初始化参数值
- 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) {
- super();
- this.popSize = popSize;
- this.chromoLength = chromoLength;
- this.totalFitness = totalFitness;
- this.bestFitness = bestFitness;
- this.worstFitness = worstFitness;
- this.averageFitness = averageFitness;
- this.mutationRate = mutationRate;
- this.crossoverRate = crossoverRate;
- this.generation = generation;
- this.maxPerturbation = maxPerturbation;
- this.leftPoint = leftPoint;
- this.rightPoint = rightPoint;
- this.iterNum=iterNum;
- }
- /*转盘赌函数
- *注意:这里的转盘赌方法仅适用于适应度的值大于0的染色体序列
- *
- *
- * */
- //初始化种群信息
- public void init(){
- //清空
- population.clear();
- List list;
- double sum=0.0;
- //赋予种群最初的信息
- for(int i=0;i<popSize;i++){
- double gene=random.nextDouble()*(rightPoint-leftPoint)+leftPoint;
- list=new ArrayList<Double>();
- list.add(gene);
- double fitness=mathCalc.calcFunction(list);
- sum+=fitness;
- Genome genome=new Genome(list, fitness);
- population.add(genome);
- }
- setGenInfo();
- printGenInfo();
- }
- //转盘赌算法
- public Genome getChromoRoulette(){
- double slice=random.nextDouble()*totalFitness;
- Genome choseGenome=null;
- 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){
- break;
- }
- }
- return choseGenome;
- }
- //基因突变
- 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){
- raw=leftPoint;
- }else if(raw>rightPoint){
- raw=rightPoint;
- }
- 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=null;
- }
- 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=genom;
- }
- if(genom.getFitness()<worstGenome.getFitness()){
- worstGenome=genom;
- }
- }
- 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.iterNum;
- this.init();
- for (int gen=0;gen<this.iterNum;gen++){
- this.Epoch(this.population);
- setGenInfo();
- printGenInfo();
- }
- }
- }
测试类:
- package com.luchi.genetic;
- public class MainTestClass {
- public static void main(String[]args){
- GeneticAlgorithm genAL=new GeneticAlgorithm(50, 1, 0.0,
- 0.0, 99999999, 0.0, 0.8,
- 0.8, 0, 0.004, 0, 4, 100);
- genAL.geneticAlgorithmPorcess();
- }
- }
结果如下:
- the generation is: 101
- the best fitness is: 5.648238442785841
- the worst fitness is: 5.277698361050879
- the average fitness is: 5.460200891763737
- the total fitness is: 273.0100445881869
迭代次数为101次(多了一次是因为迭代从0开始的)
需要说明的是:遗传算法对初始群体的选取还有遗传父母的个体还是很敏感的,每次运行会有不同的结 果,这里使用(0,4)区间并不是最好的选择,因为其适应值函数包含了负数,这会影响到转盘赌方法的 准确性,因此如果需要遗传算法得到一个很好的效果,还是需要对初始群体和遗传交叉过程进行优化
今天就写到这儿,有问题再议,源代码见附件
参考文献
1,http://blog.csdn.net/emiyasstar__/article/details/6938608
2, http://blog.csdn.net/b2b160/article/details/4680853/
相关推荐
Java遗传算法排课系统是一种利用遗传算法解决复杂优化问题的软件应用。在教育领域,排课是一个典型的组合优化问题,需要考虑多方面的约束条件,如教师时间冲突、教室容量限制、课程时间安排等。遗传算法作为一种启发...
在这个“遗传算法经典Java实现”的压缩包中,我们可以期待找到一个用Java编程语言实现的遗传算法框架,它可能包含了一系列核心的类和方法,用于表示、操作和演化种群。 遗传算法的基本步骤包括初始化种群、选择、...
在Java中实现遗传算法,通常涉及以下几个关键步骤和概念: 1. **编码**: 在遗传算法中,个体通常被编码为一串数字或字符串,代表可能的解决方案。在Java中,我们可以使用数组、列表或者自定义类来表示这些编码。...
一个二元最优化问题的遗传算法用java实现的代码
遗传算法java实现 遗传算法是一种搜索启发式算法,它模拟自然选择和遗传过程,通过选择、交叉、变异等操作来搜索最优解。在交通路线和方式规划问题中,遗传算法可以用来解决 Vehicle Routing Problem(VRP),即...
经典遗传算法的Java实现以及遗传算法实现自动组卷+源码,适合毕业设计、课程设计、项目开发。项目源码已经过严格测试,可以放心参考并在此基础上延申使用~ 经典遗传算法的Java实现以及遗传算法实现自动组卷+源码,...
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和...经典遗传算法的Java实现以及遗传算法实现自动组卷(源码+项目说明).zip
### Java遗传算法寻找最优路径 #### 一、遗传算法概览 ...综上所述,这段Java代码通过遗传算法成功地实现了寻找最优路径的目标,通过对代码的具体分析我们可以更加深入地理解遗传算法的基本思想及其实现细节。
遗传算法的步骤: (1)染色体的编码与解码 对于区间[a,b]上的值x进行解码表示;对于某一个个体的编码为b1,b2,...,bn,解码后对应的参数x值为: x=a+(b-a)/(2^n-1)sum(bk*2^(k-1)).....k=1,2,...n; (2)个体适应...
通过分析和理解这个Java实现的遗传算法,开发者可以学习如何在实际项目中应用遗传算法解决优化问题。同时,也可以在此基础上扩展和改进算法,如引入精英保留策略、自适应调整参数等,以适应不同场景的需求。
《遗传算法在旅行商问题(TSP)中的应用——基于Java实现》 旅行商问题(Traveling Salesman Problem,简称TSP)是一个经典的组合优化问题,它询问的是:给定一个城市列表,一个旅行商如何规划一条路线,使得他能...
在Java实现中,可以创建一个表示二进制串的类,包含生成、交叉、变异的方法,并在主循环中不断更新种群,直到找到满足条件的解或者达到预设的迭代次数。 **总结** 遗传算法结合Java语言,可以构建出高效且易于维护...
二、Java实现遗传算法的关键点 1. 类的设计:创建代表个体的类,包含其基因(解决方案的表示)和适应度值。可以使用数组、列表或其他数据结构来存储基因。 2. 编写适应度函数:根据问题定义,计算个体的适应度值。...
Java基于遗传算法的自动排课系统源码.zipJava基于遗传算法的自动排课系统源码.zipJava基于遗传算法的自动排课系统源码.zipJava基于遗传算法的自动排课系统源码.zipJava基于遗传算法的自动排课系统源码.zipJava基于...
Java是一种高性能、跨平台的面向...自动内存管理(垃圾回收): Java具有自动内存管理机制,通过垃圾回收器自动回收不再使用的对象,使得开发者不需要手动管理内存,减轻了程序员的负担,同时也减少了内存泄漏的风险。
### 遗传算法在Java中的实现 #### 知识点概述 本文将详细解析一个用Java语言编写的遗传算法程序。遗传算法(Genetic Algorithm, GA)是一种模拟自然界生物进化过程的搜索算法,用于解决优化问题。它通过选择、交叉...
在给定的文件名列表中,"TSP.java"可能是实现旅行商问题的类,包含了遗传算法的主要逻辑,而"Main.java"则是程序的入口,负责调用"TSP"类,初始化参数,运行算法,并可能包含结果的打印和分析。 总的来说,通过遗传...
经典遗传算法的Java实现以及遗传算法实现自动组卷_GADemo
用java语言实现遗传算法,并对一个算例进行运算