gp.java

Genetic Programming。GP算法在方程逼近求解上的应用。

import java.util.*;


public class GP extends Observable implements Runnable {

        public static int popsize;
        public static int maxdepth;
        public static int crossovermaxdepth;
        public static int mutatemaxdepth;
        public static double pcross;
        public static double preproduction;
        public static double pmutation;
        public static String rawText;
        public static int Gene_Method;
        public static int Select_Method;
        public static int Function_Number=0; 
         
        //fitnessCases Indication
        public Original_Function_Point_Set fitnessCases;
        //Function Set and Terminal Set
        public Set terminalSet;
        public Set functionSet;

        Thread thread = null;
        
        Tree[] population;
        
        int currentGeneration = 0;
        
        Tree bestOfRunIndividual = null;
        
        int generationOfBestOfRunIndividual = 0;
        
        static final int MAX_GENERATIONS = 1000;

        // 创建随机数生成器
       
        static final int SEED = 12345;
        static Random random = new Random(SEED);
        
        public GP_State state=new GP_State();

        //initialize basic syntax
        public GP(int index) {
        try{
        
        Function_Number=index;
        init_syntax();
        
        
        }
        catch(Exception e){
        	e.printStackTrace();
        	System.out.println("Exception Occurred During Init");}
        }

        public void  init_syntax() throws Exception
        {        
        
                  System.out.println("GP initializing here...");
                  popsize=Integer.parseInt(Config.popsize);
                  maxdepth=Integer.parseInt(Config.newind_maxdepth);
                  crossovermaxdepth=Integer.parseInt(Config.maxdepth_after_cross);
                  mutatemaxdepth=Integer.parseInt(Config.maxdepth_subtreeofmutation);
                  pcross=Double.parseDouble(Config.pcross);
                  preproduction=Double.parseDouble(Config.preproduction);
                  pmutation=Double.parseDouble(Config.pmutation);
                  
                  //set original points
                  rawText=Config.rawText;
                  fitnessCases=new Original_Function_Point_Set(rawText);
                  
                  Gene_Method=Config.Gene_Choice;
                  Select_Method=Config.Select_Choice;
                  
                  
                  //User Chosen Selections for Terminals and Functions              
                  int[] terminalSelections = Config.term_selections;
                  int[] functionSelections = Config.func_selections;
                  
                  System.out.print("Function Selections are:");
                  for(int i=0;i<functionSelections.length;i++)
                  {
                  	
                  	System.out.print(functionSelections[i]+"");
                  	
                  	}
                  System.out.print("Terminal Selections are:");
                  for(int i=0;i<terminalSelections.length;i++)
                  {
                  	System.out.print(terminalSelections[i]+"");
                  	}
               //初始化终结符集合
                Class[] terminals = {new Constant_Value().getClass(),new Variable().getClass()};
                terminalSet = new Set(terminals, terminalSelections);
                
                //初始化函数集合
                Class[] functions = {new Addition().getClass(),new Subtraction().getClass(),
                                     new Multiplication().getClass(), new Division().getClass(),
                                     new Sine().getClass(),new Cosine().getClass(),new Exp().getClass()};
                functionSet = new Set(functions, functionSelections);
                
                System.out.println("GP Initializing Finished Here...");
        }
        
        
        public synchronized void start() {
                thread = new Thread(this);
                thread.setPriority(Thread.NORM_PRIORITY - 1);//make user interface can draw immed
                thread.start();
                state.setState(1);
                //notifyObservers(new GPMessageStateChanged(state, ""));
        }

        //选择终结符号集中的元素x或者常数
        Terminal get_Terminal()  {
                Terminal choice=null;
                try{
                int index = random.nextInt(terminalSet.selections.length);
                Class cls = terminalSet.getSelectedItem(index);
                choice = (Terminal)(cls.newInstance());
                }
                catch(Exception e){System.out.println("Exception Caught");}
                return choice;
        }
        
        //选择函数集中的元素add,sub,mul,div,exp,sin,cos
        Function get_Function()
        {  
           Function function=null;
           try{
           int choice = random.nextInt(functionSet.selections.length);
           Class cls = functionSet.getSelectedItem(choice);//Runtime Class Binding
           function = (Function)cls.newInstance();}
           catch(Exception e){System.out.println("Exception Caught");}
           return function;
        }
        
        Function get_Function(int choice)
        {
        	Function function=null;
        	try{
        	Class cls = functionSet.getSelectedItem(choice);//Runtime Class Binding
            function = (Function)cls.newInstance();
            }
            catch(Exception e){System.out.println("Exception Caught");}
            return function;
        	}
        
   
        void create_func_args(Function function,int current_depth,boolean fullP)
        {
                for (int i = 0; i < function.Subtree.length; i++) {
                        function.Subtree[i] = create_tree(current_depth,false,fullP);
                }
        }

        TreeNode create_tree(int current_depth,boolean root,boolean full)
         {
                TreeNode currentNode;
                int choice;
                Function f;
                if (current_depth == 0) {
                        currentNode = get_Terminal();//到达树的最大深度
                } else {
                        if (full||root)//头节点，选择函数集的元素 
                        {       f=get_Function();  
                                create_func_args(f,current_depth - 1,full);
                                currentNode = f;
                        } else {
                                choice = random.nextInt(terminalSet.selections.length + functionSet.selections.length);
                                if (choice < functionSet.selections.length) {
                                    f=get_Function(choice);//chooses function
                                    create_func_args(f,current_depth - 1,full);
                                        currentNode = f;
                                } else {
                                        currentNode = get_Terminal();//randomly chooses Terminal
                                }
                        }
                }
                return currentNode;
        }

        //产生初始种群
        void create_initial_pop(int maxdepth) {
                int number=0;
                int current_depth=0;
                population=new Tree[popsize];
                boolean full=false;
                boolean flag=false;
                while(number<popsize)
                {
                switch (Gene_Method) {
                        case Config.FULL:
                                        current_depth = maxdepth;
                                        full = true;
                                        break;
                        case Config.GROW:
                                        current_depth = maxdepth;
                                        full = false;
                                        break;
                        case Config.RAMPED_HALF_AND_HALF:
                                        current_depth =(number%maxdepth);
                                        if (number%(maxdepth)==0) {
                                                flag = !flag;
                                        }
                                        full = flag;
                                        break;
                        default:
                                        current_depth = maxdepth;
                                        full = false;
                                        break;
                        }
                        
                        TreeNode newProgram = create_tree(current_depth,true,full);
                        population[number] = new Tree(newProgram);
                        number++;
                   	}
                   	
                   	System.out.println("Finish Here");
                
        }

        TreeNode[] crossover(TreeNode male, TreeNode female) {
        	
        	   if(male==null)
        	   System.out.println("NULL HERE");
               double function_crossover=0.9;
               double value_male=random.nextDouble();
               double value_female=random.nextDouble();
               int counter=0;
               Walking_Crook crook_male=null;
               Walking_Crook crook_female=null;
               
               TreeNode [] offspring = new TreeNode[2];
		       offspring[0] = (TreeNode)male.clone();
		       offspring[1] = (TreeNode)female.clone();
               
               if(value_male<=function_crossover)
               {
               	crook_male=Get_Cross_Over_Point(offspring[0],isFunction);
               	}
               else 
               {
               	crook_male=Get_Cross_Over_Point(offspring[0],isProgram);
               	}
               if(value_female<=function_crossover)
               {
               	crook_female=Get_Cross_Over_Point(offspring[1],isFunction);               	
               	}
               else 
               {
               	crook_female=Get_Cross_Over_Point(offspring[1],isProgram);
               	}
         		//
		       if (crook_male.parent == null) {
			     offspring[0] = crook_female.subtree;
		        } else {
			    crook_male.parent.Subtree[crook_male.childIndex] = crook_female.subtree;
		        }
		       if (crook_female.parent == null) {
			    offspring[1] = 	crook_male.subtree;
		       } else {
			    crook_female.parent.Subtree[crook_female.childIndex] = crook_male.subtree;
			}

			validateCrossover(male, female, offspring);//判断没有超过最大长度
			return offspring;
               	
        }
        
         
        Walking_Crook Get_Cross_Over_Point(TreeNode ind,Condition cond)
		{
			int node_number=ind.countNodes(cond);
			int random_number=random.nextInt(node_number);
			
			if (node_number<=1)return new Walking_Crook(ind,null,-1);
			return getSubtree(ind,random_number,cond);
		}



        Walking_Crook getSubtree(TreeNode tree, int index, Condition cond) {
                int[] count = { index };
                return Walk(tree, count, cond, null, -1);
        }

        //get the random crossover or mutation point of the specific tree
        private Walking_Crook Walk(TreeNode tree, int[] count, Condition cond, Function parent, int childIndex) {
                if (cond.test(tree) && count[0] == 0) {
                        return new Walking_Crook(tree, parent, childIndex);
                } else {
                        Walking_Crook hook = null;
                        if (tree instanceof Function) {
                                Function func = (Function)tree;
                                for (int a = 0; a < func.Subtree.length && count[0] > 0; a++) {
                                        if (cond.test(func.Subtree[a])) {
                                                count[0]--;
                                        }
                                        hook = Walk(func.Subtree[a], count, cond, func, a);
                                }
                        }
                        return hook;
                }
        }
   
        
        
        //return the maxdepth of the tree
        int maxDepthOfTree(TreeNode tree) {
                int maxDepth = 0;
                if (tree instanceof Function) {
                        for (int a = 0; a < ((Function)tree).Subtree.length; a++) {
                                TreeNode s = ((Function)tree).Subtree[a];
                                int depth = maxDepthOfTree(s);
                                maxDepth = Math.max(maxDepth, depth);
                        }
                        return (1 + maxDepth);
                } else {
                        return 0;
                }
        }

        //check whether the crossover has exceeded the max depth
        void validateCrossover(TreeNode male, TreeNode female,