/** * Project Name:GeneticAlgorithm * File Name:Individual.java * Package Name: * Date:2017年9月23日下午5:02:00 * Copyright (c) 2017, 2692613726@qq.com All Rights Reserved. * */ /** * ClassName:Individual * Function: 个体类 * Reason: TODO ADD REASON. * Date: 2017年9月23日 下午5:02:00 * @author michael * @version * @since JDK 1.7 * @see */ public class Individual { //定义染色体,染色体是要很多基因组成 private int[] chromosome; //定义个体实现度,默认值是-1 private double fitness = -1; /* * 通过特定染色体创建个体 * */ public Individual(int[] chromosome){ this.chromosome = chromosome; } /* * 通过随机基因创建个体:染色上的基因是随机数产生的 * */ public Individual(int chromosomeLength){ this.chromosome = new int[chromosomeLength]; for (int gene = 0; gene < chromosomeLength; gene++) { if(0.5<Math.random()){ this.setGene(gene, 1); } else { this.setGene(gene, 0); } } } /* * get 个体的基因 * */ public int[] getChromosome(){ return this.chromosome; } /* * get 基因的长度 * */ public int getChromosomeLength(){ return this.chromosome.length; } /* * 在特定的地方设置基因 * */ public void setGene(int offset,int gene){ this.chromosome[offset] = gene; } /* * 在特定的地方得到基因 * */ public int getGene(int offset){ return this.chromosome[offset]; } /* * 设置个体适应度 * */ public void setFitness(double fitness){ this.fitness = fitness; } /* * 得到个体适应度 * */ public double getFitness(){ return this.fitness; } /* * 染色体(即所有基因)以字符串的形式打印 * */ public String toString(){ String output = ""; for (int gene = 0; gene < this.chromosome.length; gene++) { output +=this.chromosome[gene]; } return output; } }
import java.util.Arrays; import java.util.Comparator; import java.util.Random; import org.apache.jasper.tagplugins.jstl.core.If; /** * Project Name:GeneticAlgorithm * File Name:Population.java * Package Name: * Date:2017年9月23日下午7:44:55 * Copyright (c) 2017, 2692613726@qq.com All Rights Reserved. * */ /** * ClassName:Population * Function: 种群类 * Reason: TODO ADD REASON. * Date: 2017年9月23日 下午7:44:55 * @author michael * @version * @since JDK 1.7 * @see */ public class Population { //种群:所有个体的集合 public Individual[] population; //种群适应度 public double populationFitness=-1; /* * 初始化一个空的种群,参数是种群的大小 * */ public Population(int populationSize){ this.population = new Individual[populationSize]; } /* * 初始化种群,参数是:(1)种群的大小,(2)染色体的长度 * */ public Population(int populationSize,int chromosomeLength){ //新建一个种群,即所有个体的集合 this.population = new Individual[populationSize]; //创建种群中的每个个体 for (int individualCount = 0; individualCount < populationSize; individualCount++) { //调用Individual类的构造方法,创建个体 Individual individual = new Individual(chromosomeLength); //将该个体添加到种群中 this.population[individualCount] = individual; } } /* * 从种群中得到所有个体 * */ public Individual[] getIndividuals(){ return this.population; } /* *通过个体适应度选择一个个体 *先将种群进行排序,最后获得第offset位置的个体 *按适应度顺序排列个体 * */ public Individual getFittest(int offset){ //对种群中的个体按照适应度进行排序 Arrays.sort(this.population, new Comparator<Individual>() { @Override public int compare(Individual o1, Individual o2) { if(o1.getFitness()>o2.getFitness()){ return -1; } else if(o1.getFitness()<o2.getFitness()){ return 1; } return 0; } //Arrays.sort(数组,比较器<数组类型>) }); //返回排序第offset的个体 return this.population[offset]; } /* * 得到种群适应度 * */ public double getPopulationFitness() { return populationFitness; } /* * 设置种群适应度 * */ public void setPopulationFitness(double populationFitness) { this.populationFitness = populationFitness; } /* * 得到种群的大小 * */ public int size(){ return this.population.length; } /* * 在第offset位置设置个体 * */ public Individual setIndividual(int offset,Individual individual){ return population[offset] = individual; } /* * 得到第offset位置的个体 * */ public Individual getIndividual(int offset){ return population[offset]; } /* * * */ public void shuffle(){ Random random = new Random(); for (int i = population.length-1; i >=0; i--) { int index = random.nextInt(i+1); Individual individual = population[index]; population[index] = population[i]; population[i] = individual; } } }
import com.sun.org.apache.bcel.internal.generic.PopInstruction; /** * Project Name:GeneticAlgorithm * File Name:GeneticAlgorithm.java * Package Name: * Date:2017年9月23日下午8:25:25 * Copyright (c) 2017, 2692613726@qq.com All Rights Reserved. * */ /** * ClassName:GeneticAlgorithm * Function: 遗传算法的核心 * Reason: TODO ADD REASON. * Date: 2017年9月23日 下午8:25:25 * @author michael * @version * @since JDK 1.7 * @see */ public class GeneticAlgorithm { /*种群大小*/ private int populationSize; /*变异概率*/ private double mutationRate; /*交叉概率*/ private double crossoverRate; /*精英个体数:种群中最强的个体数。保持原样,不参与交叉和变异*/ private int elitismCount; /*构造函数*/ public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount) { super(); this.populationSize = populationSize; this.mutationRate = mutationRate; this.crossoverRate = crossoverRate; this.elitismCount = elitismCount; } /* * 调用population的构造方法,使用染色体长度初始化种群 * */ public Population initPopulation(int chromosomeLength){ Population population = new Population(this.populationSize, chromosomeLength); return population; } /* * 计算一个个体的适应度 * */ /* public double calcFitness(Individual individual){ //计算有多个正确的 int correctGenes = 0; for (int geneIndex = 0; geneIndex < individual.getChomosomeLength(); geneIndex++) { if(individual.getGene(geneIndex) == 1){ correctGenes += 1; } } //计算适应度 double fitness = (double)correctGenes / individual.getChomosomeLength(); individual.setFitness(fitness); return fitness; }*/ public double calcFitness(Individual individual) { // Track number of correct genes int correctGenes = 0; // Loop over individual's genes for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) { // Add one fitness point for each "1" found if (individual.getGene(geneIndex) == 1) { correctGenes += 1; } } // Calculate fitness double fitness = (double) correctGenes / individual.getChromosomeLength(); // Store fitness individual.setFitness(fitness); return fitness; } /* * 遍历每个个体并评估它们 * */ public void evalPopulation(Population population){ double populationFitness = 0; for (Individual individual : population.getIndividuals()) { populationFitness += calcFitness(individual); } population.setPopulationFitness(populationFitness); } /* * 判断终止的条件 * */ public boolean isTerminationConditionMet(Population population){ for (Individual individual : population.getIndividuals()) { if(individual.getFitness() == 1){ return true; } } return false; } /* * 选择交叉的个体 * */ public Individual selectParent(Population population){ //得到种群中所有个体 Individual[] individuals = population.getIndividuals(); //轮盘赌选择 double populationFitness = population.getPopulationFitness(); //种群适应度 double rouletteWheelPosition = Math.random()*populationFitness; //轮盘赌的位置 //找交叉的个体 double spinWheel = 0; for(Individual individual:individuals){ spinWheel += individual.getFitness(); if(spinWheel >= rouletteWheelPosition){ return individual; } } return individuals[population.size()-1]; } /* * 交叉返回一个新的种群 * */ public Population crossoverPopulation(Population population){ //创建新种群 Population newPopulation = new Population(population.size()); //通过适应度遍历当前种群 for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) { Individual parent1 = population.getFittest(populationIndex); //是否对这个个体交叉 if(this.crossoverRate > Math.random()&&populationIndex >=this.elitismCount){ //初始化下一代 Individual offspring = new Individual(parent1.getChromosomeLength()); //找第二个交叉个体 Individual parent2 = selectParent(population); //遍历第一个个体的基因 for (int geneIndex = 0; geneIndex < parent1.getChromosomeLength(); geneIndex++) { //如果随机数小于0.5,则使用第一个个体的基因 if(0.5>Math.random()){ offspring.setGene(geneIndex, parent1.getGene(geneIndex)); }else{} offspring.setGene(geneIndex, parent2.getGene(geneIndex)); } //将子类添加到新种群中 newPopulation.setIndividual(populationIndex, offspring); } else{ newPopulation.setIndividual(populationIndex, parent1); } } return newPopulation; } /*变异得到新种群*/ public Population mutatePopulation(Population population){ Population newPopulation = new Population(this.populationSize); //通过适应度遍历当前种群 for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) { //按照从小到大的顺序选择个体 Individual individual = population.getFittest(populationIndex); //遍历个体的基因 for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) { if(populationIndex>this.elitismCount){ //判断该基因是否变异 if(this.mutationRate>Math.random()){ int newGene = 1; if(individual.getGene(geneIndex)==1){ newGene = 0; } //变异基因 individual.setGene(geneIndex, newGene); } } } newPopulation.setIndividual(populationIndex, individual); } return newPopulation; } }
/** * Project Name:GeneticAlgorithm * File Name:AllOnesGA.java * Package Name: * Date:2017年9月23日下午9:36:01 * Copyright (c) 2017, 2692613726@qq.com All Rights Reserved. * */ /** * ClassName:AllOnesGA * Function: TODO ADD FUNCTION. * Reason: TODO ADD REASON. * Date: 2017年9月23日 下午9:36:01 * @author michael * @version * @since JDK 1.7 * @see */ public class AllOnesGA { public static void main(String[] args) { //程序开始运行的时间 long startTime = System.currentTimeMillis(); //种群中个体有100个,变异概率0.001,交叉概率0.95,精英个体2个 GeneticAlgorithm geneticAlgorithm = new GeneticAlgorithm(100, 0.001, 0.95, 2); //初始化种群,染色体长度为50 Population population = geneticAlgorithm.initPopulation(50); //评估种群 geneticAlgorithm.evalPopulation(population); //记录第几代 int generation = 1; /* * 开始进化 * */ while(geneticAlgorithm.isTerminationConditionMet(population)==false){ //打印种群中适应度好的个体 System.out.println("最好的方法:"+population.getFittest(0).toString()); //交叉 population = geneticAlgorithm.crossoverPopulation(population); //变异 population = geneticAlgorithm.mutatePopulation(population); //评估种群 geneticAlgorithm.evalPopulation(population); generation++; } System.out.println("找到最终的方案,在第"+generation+"代"); System.out.println("最好的方法:"+population.getFittest(0).toString()); //结束时间 long endTime = System.currentTimeMillis(); System.out.println("总共运行了"+(endTime-startTime)+"ms"); } }