kernel.java.bak

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

package kernel;
import java.util.*;
import java.util.Observer;
import java.util.Observable;

//遗传设计程序的运算内核，包括初始化群体，
//遗传操作
public class Kernel  extends Observable implements Runnable
{
	Individual[] programs;
	Parameters para;
	public Evaluate evaluate;	
	SetInterface set;
	boolean stop = false;
	//当前代
	public int currentGeneration = 0;
	//适应度最好的个体
	public Individual bestOfRunIndividual = null;
	//适应度最好的个体所在的代
	int generationOfBestOfRunIndividual = 0;
	/**
	* 随机数生成器
	*/
	public static final int SEED = 45678;
	public static Random random = new Random(SEED);
	public Kernel(Parameters para,SetInterface set, Evaluate evaluate)
	{
		
		this.para = para;
		this.set = set;
		this.evaluate = evaluate;		
	}
	
	/**
	* @返回一个叶子节点，该叶子节点是从TerminalSet集合中随机选取
	*/
	Terminal chooseFromTerminalSet() {
		Terminal choice;
		try 
		{
			choice = null;
			int index = random.nextInt(set.TerminalSet.length);
			Class cls = set.TerminalSet[index];
			choice = (Terminal) (cls.newInstance());
		} 
		catch(Exception e) 
		{
			choice = null;
		}
		return choice;
	}
	
	/**
	* @返回一个非叶子节点，该叶子节点是从FunctionSet集合中随机选取
	*/
	Function chooseFromFunctionSet() {
		Function choice;
		try 
		{
			
			int index = random.nextInt(set.FunctionSet.length);
			Class cls = set.FunctionSet[index];
		    choice = (Function)(cls.newInstance());
		} 
		catch(Exception e) 
		{
			choice = null;
		}
		return choice;
	}
	
	/**
	*为一个非叶子节点建立其参数
	*/
	void createArgumentsForFunction(
		Function function,
		int allowableDepth,
		boolean fullP) 
	{
		for (int i = 0; i < function.SubItems.length; i++) 
		{
			function.SubItems[i] = createIndividualProgram(
					allowableDepth,
					false,
					fullP);
		}
	}
	
	
    /**
	* 递归建立一棵语法树，返回头节点对象
	* 参数allowableDepth是语法树允许的深度。如果等于0我们只能选择叶子节点
	* 参数topNodeP 如果为真我们只能建立头节点。这是为了避免使用叶子节点的
	* 集合建立头节点
	* 参数fullP 指示建立树时是建立一棵满树或者不是
	*/
	Program createIndividualProgram(
		int allowableDepth,
		boolean topNodeP,
		boolean fullP
		) 
	{
		Program p;
		int choice;
		Function function;
        //如果允许深度小于等于0，则返回一个叶子节点对象。
		if (allowableDepth <= 0) {
  		//	We've reached maxdepth, so just pack a terminal.
			p = chooseFromTerminalSet();
		} 
		else
		{
			//如果是建立满树，或者是建立头节点
			if (fullP || topNodeP) 
			{
  			    //此时只能选择非叶子节点	
				function = chooseFromFunctionSet();
				createArgumentsForFunction(
						function,
						allowableDepth - 1,
						fullP);
				p = function;
			} 
			else 
			{
				//从FunctionSet和TerminalSet中任选一个
				choice = random.nextInt(set.FunctionSet.length + set.TerminalSet.length);
				if (choice < set.FunctionSet.length) 
				{
					//我们选择一个非叶子节点
					try 
					{
						Class cls =  set.FunctionSet[choice];
						function = (Function)cls.newInstance();
					} 
					catch(Exception e) 
					{
						function = null;
					}
					createArgumentsForFunction(
							function,
							allowableDepth - 1,
							fullP);
					p = function;
				} 
				else 				
				{
					//	我们选择一个叶子节点
					try
					{
						Class cls  = set.TerminalSet[choice - set.FunctionSet.length];
					    p = (Terminal)cls.newInstance();
					}
					catch(Exception e)
					{
						p = null;
					}

				}
			}
		}
		return p;
	}

	/**
	* 创建随机化的程序群体
	* 数组大小为sizeOfPopulation.
	*/
	void createPopulation() 
	{
		int allowableDepth;
		boolean fullP;
		//下面创建一个哈希表，为了对比是否创建了重复的程序用
		Hashtable generation0UniquifierTable = new Hashtable();
        //程序群体数组
		programs = new Individual[para.populationSize];
		//最小深度
		int minimumDepthOfTrees = 1;
		//用于half-half生长方式，一次生成全子树，第二次生成非全子树，如此循环
		boolean fullCycleP = false;
		int maxDepthForNewIndivs = para.max_depth_for_new_individuals;
		int attemptsAtThisIndividual = 0;
		int individualIndex = 0;
		while (individualIndex < programs.length) 
		{
			switch (para.method_of_generation) 
			{
				//FULL方法生成一棵满的树
			    case Parameters.FULL:
					allowableDepth = maxDepthForNewIndivs;
					fullP = true;
					break;
				//GROW方法生成不满的树
			    case Parameters.GROW:
					allowableDepth = maxDepthForNewIndivs;
					fullP = false;
					break;
			    case Parameters.RAMPED_HALF_AND_HALF:
					//这是斜坡式生长法，树的深度由低到高又由高到低变化
					//满FULL与不满GROW也随之反复变化
                    //这是最常用的一种生长方式，因为这样生成的树的多样性最大，最有可能
                    //搜索到合适的答案
					allowableDepth =
							minimumDepthOfTrees +
							(individualIndex %
							(maxDepthForNewIndivs - minimumDepthOfTrees + 1));
					if (attemptsAtThisIndividual == 0 &&
							individualIndex % 
							(maxDepthForNewIndivs - minimumDepthOfTrees + 1) == 0) {
						fullCycleP = !fullCycleP;
					}
					fullP = fullCycleP;
					break;
			default:
					allowableDepth = maxDepthForNewIndivs;
					fullP = false;
					break;
			}
            //这里根据上面的参数，生成新的语法树
			Program newProgram = createIndividualProgram(
					allowableDepth,  
					true,
					fullP);

			//检查是否创建了一个重复的语法树。
			//如果没有重复，则将其加入群体数组，否则继续生成。
			//检查的方法是，用toString方法求出每一个语法树个体的
			//字符串表现形式，再将其与已经存入哈希表中的其他语法树
			//个体的字符串形式比较，如果有相同的则是重复的语法树，如果
			//没有相同的则将其存入哈希表，用于下次查找
			String hashKey = newProgram.toString();
			if (!generation0UniquifierTable.containsKey(hashKey)) 
			{
								
				programs[individualIndex] = new Individual(newProgram);
				//为每一个语法树的节点进行编号，并设置每节点的父节点引用
				programs[individualIndex].setParent();
				individualIndex++;
				generation0UniquifierTable.put(hashKey, newProgram);
				attemptsAtThisIndividual = 0;
			} 
			else 
			{
				attemptsAtThisIndividual++;
				if (attemptsAtThisIndividual > 20) 
				{
					//如果重复的多余20个，那么这个深度的语法树已经被生成完毕了，
					//则最小深度加1
					minimumDepthOfTrees++;
					maxDepthForNewIndivs = Math.max(maxDepthForNewIndivs, minimumDepthOfTrees);
					attemptsAtThisIndividual = 0;
				}
			}
		}
	}
	
	/**
	* 对语法树的某随机编号的节点进行变异，并返回变异后的语法树
	*/
	Program mutate(Program program) 
	{
		//获得随机编号
		program.setParent();
        int mutationPoint = random.nextInt(program.countNodes(false))  + 1;
 		//建立一棵新语法树，用于粘贴到原语法树节点编号为mutationPoint处
		Program newSubtree = createIndividualProgram(
				para.max_depth_for_new_subtrees_in_Mutants,
				true,
				false);
		//如果是头节点
	    if(mutationPoint == 1)
	    {
	    	return newSubtree;
	    }
        Program p = null;
        //求出节点mutationPoint处的引用
        p = program.indexOf(mutationPoint, false);
        p.parent.SubItems[p.index] = newSubtree;
		return program;
	}
	
	/**
	*对两棵语法树进行遗传交叉操作并返回两个新的后代。（模仿两性繁殖）
	*传进来的参数是两棵父代语法树，返回两棵子代语法树
	*语法树上的交叉点是任意选取的，但根据经验证明，如果交叉点是非叶子
	*节点，会更加有利于搜索到最优解，所以设置了一个非叶节点处交叉的概率
	*为0.9。两父代从交叉点处获得的两子树将从原树处切下并粘贴到另一子树的
	*交叉点上。
	*生成子树后，必须对子树进行验证，以使子树的最大深度不能超过一个最大值，
	*这用validateCrossover函数进行，如果超过了，则用其任意父代代替
	*/
	Program[] crossover(Program male, Program female) {
		//CrossoverAtFunctionFraction是在非叶节点处交叉的概率
		double CrossoverAtFunctionFraction = 0.9;
		boolean crossoverAtFunction;
		//交叉前首先将父代复制给子代
		Program[] offspring = new Program[2];
		offspring[0] = (Program)male.DeepClone();
		offspring[1] = (Program)female.DeepClone();
        offspring[0].setParent();
        offspring[1].setParent();
		int malePoint, femalePoint;
		Program maleHook,femaleHook;
		//确定是否在非叶节点处进行交叉
		crossoverAtFunction = (random.nextDouble() < CrossoverAtFunctionFraction);
		if (crossoverAtFunction) 
		{
			//在非叶子节点处交叉,maleHook返回交叉点处节点引用
			malePoint = random.nextInt(offspring[0].countNodes(true)) + 1;
			maleHook = offspring[0].indexOf(malePoint,true);
		} 
		else 
		{
			malePoint = random.nextInt(offspring[0].countNodes(false)) + 1;
			maleHook = offspring[0].indexOf(malePoint,false);
		}
		crossoverAtFunction = (random.nextDouble() < CrossoverAtFunctionFraction);
		if (crossoverAtFunction) 
		{
			femalePoint = random.nextInt(offspring[1].countNodes(true)) + 1;
			femaleHook = offspring[1].indexOf(femalePoint,true);
		} 
		else 
		{
			femalePoint = random.nextInt(offspring[1].countNodes(false)) + 1;

			femaleHook = offspring[1].indexOf(femalePoint,false);
		}
		//进行交叉操作
		if (maleHook.parent == null) {
			femaleHook.parent = null;
			offspring[0] = femaleHook;
		} else {
			maleHook.parent.SubItems[maleHook.index] = femaleHook;
		}
		if (femaleHook.parent == null) 
		{
			maleHook.parent = null;
			offspring[1] = maleHook;
		}
		else 
		{
			femaleHook.parent.SubItems[femaleHook.index] = maleHook;
		}
        offspring[0].setParent();
        offspring[1].setParent();
		validateCrossover(male, female, offspring);
		return offspring;
	}
	
	/**
	* 返回语法树的最大深度
	*/
	int maxDepthOfTree(Program tree) 
	{
		int maxDepth = 0;
		if (tree.SubItems != null) 
		{
			for (int i = 0; i < tree.SubItems.length; i++)