kernel.java.bak

这是用遗传编程算法来拟合曲线的一个经典程序

			{
				Program s = tree.SubItems[i];
				int depth = maxDepthOfTree(s);				
				maxDepth = Math.max(maxDepth, depth);
			}
			return (1 + maxDepth);
		} 
		else 
		{
			return 0;
		}
	}
	
	
	



	/**
	* 参数是双亲和两个交叉操作后的后代
	* 检查两个后代的语法树的最大深度，是否超过了预定深度，如果超过了，
	* 就用父辈的任一棵语法树代替
	*/
	void validateCrossover(Program male, Program female,
		Program[] offspring)
	{
		int depth;
		for (int i = 0; i < offspring.length; i++) 
		{
			//如果未产生后代
			if (offspring[i] == null) 
			{
				depth = 0;
			} 
			else 
			{
				//否则，求出最大深度
				depth = maxDepthOfTree(offspring[i]);
			}
			if (depth < 1 || depth > para.max_depth_for_individuals_after_crossover) 
			{
				int whichParent = random.nextInt(2);
				if (whichParent == 0) 
				{
					offspring[i] = (Program)male.DeepClone();
				} 
				else 
				{
					offspring[i] = (Program)female.DeepClone();
				}
			}
		}
	}
	
	/**
	* 清除种群中所有的fitness 
	*/
	void zeroizeFitnessMeasuresOfPopulation() 
	{
		for (int i = 0; i < programs.length; i++) 
		{ 
			programs[i].standardizedFitness = 0.0;
			programs[i].adjustedFitness = 0.0;
			programs[i].normalizedFitness = 0.0;
			programs[i].hits = 0;
		}
	}

	/**
    *对种群中每一个元素进行适应度测试，设置值
	*/
	void evaluateFitnessOfPopulation() 
	{
		for (int i = 0; i < programs.length; i++) 
		{
			evaluate.Evaluate(programs[i]);
		}
	}

	
	/**
	* 计算每棵语法树的正规化的适应度normalizedFitenss（在0到1之间）
	* 和调整后的适应度adjustedFitness
	*	standardizedFitness越大，适应度越差，
	*nomalizedFitness越小。适应性大小与normalizedFitness成正比
	*/
	void normalizeFitnessOfPopulation() 
	{
		double sumOfAdjustedFitnesses = 0.0;
		for (int i = 0; i < programs.length; i++) {
			//设置调整后适应度
			programs[i].adjustedFitness = 
    			1.0 / (programs[i].standardizedFitness + 1.0);
			
			sumOfAdjustedFitnesses =
					sumOfAdjustedFitnesses + programs[i].adjustedFitness;
		}
		//求出正规化后适应度,该适应度是在0到1之间
		for (int i = 0; i < programs.length; i++) 
		{
			programs[i].normalizedFitness =
					programs[i].adjustedFitness / sumOfAdjustedFitnesses;
		}
	}
	
	/**
	* 用快速排序法将种群按nomalizedFitness倒序排列,这样，
	*适应度最高的就在第0个
	*/
	private void sort(int low, int high) 
	{
		int index1, index2;
		double pivot;
		Individual temp;

		index1 = low;
		index2 = high;
		pivot = programs[(low + high) / 2].normalizedFitness;
		do 
		{
			while (programs[index1].normalizedFitness > pivot) 
			{
				index1++;
			}
			while (programs[index2].normalizedFitness < pivot) 
			{
				index2--;
			}
			if (index1 <= index2) 
			{
				temp = programs[index2];
				programs[index2] = programs[index1];
				programs[index1] = temp;
				index1++;
				index2--;
			}
		} 
		while (index1 <= index2);
		if (low < index2) 
		{
			sort(low, index2);
		}
		if (index1 < high) 
		{
			sort(index1, high);
		}
	}
		
	/**
	* 用快速排序法将种群按nomalizedFitness倒序排列
	*/
	void sortprogramsByFitness() 
	{
		sort(0, programs.length - 1);
	}
	
	/**
	* 从父代进化出新一代
	*/
	void evolve() 
	{
		Individual bestOfGeneration;
		//如果不是第0代，则进行遗传操作来进化出新一代
		if (currentGeneration > 0) 
		{
   		    breedNewPopulation();
		}
		//将适应度清零
		zeroizeFitnessMeasuresOfPopulation();
		//对新群体赋给适应度
		evaluateFitnessOfPopulation();
		normalizeFitnessOfPopulation();
		//按nomalizedFitness逆序，便于轮盘赌式选择新一代
	    sortprogramsByFitness();

		//保存最佳个体
		bestOfGeneration = programs[0];
		if (bestOfRunIndividual == null ||
  			bestOfRunIndividual.standardizedFitness >
				bestOfGeneration.standardizedFitness) 
		{
			bestOfRunIndividual = bestOfGeneration.copy();
			generationOfBestOfRunIndividual = currentGeneration;
		}
		//繁殖代数加1
		currentGeneration++;
	}
	
	
	/**
	* 对群体进行选择，交叉，变异并产生新一代
	*/
	void breedNewPopulation() {
		Program[] newPrograms;
		double fraction;
		int index;
		Individual individual1, individual2 = null;
		int i;
		double sumOfFractions = para.crossoverFraction +
				para.fitnessProportionateReproFraction +
				para.mutationFraction;
		double crossoverFraction = para.crossoverFraction / sumOfFractions;
		double reproductionFraction = para.fitnessProportionateReproFraction / sumOfFractions;
		double mutationFraction = para.mutationFraction / sumOfFractions;

		newPrograms = new Program[programs.length];
		fraction = 0.0;
		index = 0;

		//用第0个位置保存上一代的最佳子树
		newPrograms[index] = (Program)bestOfRunIndividual.program.DeepClone();
		index++;
		
		while (index < programs.length) 
		{
			fraction = (double)index / (double)programs.length;
			individual1 = findIndividual();
			if (fraction < crossoverFraction) {
				individual2 = findIndividual();
				Program[]	offspring = crossover(individual1.program, individual2.program);
    		newPrograms[index] = offspring[0];
				index++;
				if (index < programs.length) {
    			newPrograms[index] = offspring[1];
					index = index++;
				}
			} else {
				if (fraction < 	reproductionFraction + crossoverFraction) {
					newPrograms[index] = (Program)individual1.program.DeepClone();
					index ++;
				} else {
					newPrograms[index] = mutate(individual1.program);
					index++;
				}
			}
			individual1.setParent();
			individual2.setParent();
		}
		for (index = 0; index < programs.length; index++) {
			programs[index].program = newPrograms[index];
		}
	}
	
	/**
	* 如果到终止条件了，返回真
	*/
	boolean terminationPredicate(int currentGeneration) 
	{
		for(int i = 0; i < programs.length; i++)
		{
			if(evaluate.Termination_Criterion(
				programs[i],currentGeneration,para.best_fitness))
				return true;
		}
		return false;
	}
	
	
	/**
	*返回落在某适应值区间的语法树，是轮盘赌方式
	*/
	Individual findFitnessProportionateIndividual(double afterThisFitness) {
	
		int indexOfSelectedIndividual;
		double sumOfFitness = 0.0;
		int index = 0;
		while (index < programs.length && sumOfFitness < afterThisFitness) {
			//将适应值累加
			sumOfFitness = sumOfFitness + programs[index].normalizedFitness; 
			index++;
		}
		if (index >= programs.length) 
		{
			indexOfSelectedIndividual = programs.length - 1;
		} else 
		{
			indexOfSelectedIndividual = index - 1;
		}
		return programs[indexOfSelectedIndividual];
	}

	/**
	* 任意挑选7个，然后从中选出最好的返回
	*/
	Individual findIndividualUsingTournamentSelection() 
	{
		int TournamentSize = Math.min(programs.length, 7);

		Hashtable table = new Hashtable();
		while (table.size() < TournamentSize) 
		{
			//任意挑选7个
			int key = random.nextInt(programs.length);
			table.put(new Integer(key), programs[key]);
		}
		Enumeration e = table.elements();
		Individual best	= (Individual)e.nextElement();
		double bestFitness = best.standardizedFitness;
		while (e.hasMoreElements()) {
			Individual individual = (Individual)e.nextElement();
			double thisFitness = individual.standardizedFitness;
			if (thisFitness < bestFitness) {
	  		best = individual;
				bestFitness = thisFitness;
			}
		}
		return best;
	}

	/**
	* 使用锦标赛法或者轮盘赌法挑选基因
	*/
	Individual findIndividual() {
		Individual ind = null;
		switch (para.method_of_selection) 
		{
			case Parameters.TOURNAMENT:
				ind = findIndividualUsingTournamentSelection();
				break;
			case Parameters.FITNESS_PROPORTIONATE:
				ind = findFitnessProportionateIndividual(random.nextDouble());
				break;
		}
		return ind;
	}
	
	public void stopEvo()
	{
		stop = true;
	}
	/**
	* 这是运行语法树群体进化的函数
	*/
	public void run() 
	{
		//设置随机数种子
		random.setSeed(SEED);
		
		generationOfBestOfRunIndividual = 0;
		bestOfRunIndividual = null;
		//初始化种群
		createPopulation();
		//当前代为第0代
		currentGeneration = 0;
		stop = false;
        //当未达到终止条件时，继续进化
		while (!terminationPredicate(currentGeneration) || !stop) {
		    evolve();
		   setChanged();
           //通知观察者
           notifyObservers(new MessageGp(currentGeneration,evaluate,bestOfRunIndividual));
		}
	}
 

	
}