gp.java

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

                TreeNode[] 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 >crossovermaxdepth) {
                                int whichParent = random.nextInt(2);
                                if (whichParent == 0) {
                                        offspring[i] = (TreeNode)male.clone();
                                } else {
                                        offspring[i] = (TreeNode)female.clone();
                                }
                        }
                }
        }

        //mutate the tree by adding a brand new tree at a random point
        TreeNode mutate(TreeNode program) {
                //	Pick the mutation point.
                int mutationPoint = random.nextInt(program.countNodes());
                //	Create a brand new subtree.
                TreeNode newSubtree = create_tree(mutatemaxdepth,true,false);
                TreeNode newProgram = (TreeNode)program.clone();
                //	Smash in the new subtree.
                Walking_Crook hook = getSubtree(program, mutationPoint, isProgram);
                if (hook.parent == null) {
                        newProgram = hook.subtree;
                } else {
                        hook.parent.Subtree[hook.childIndex] = newSubtree;
                }
                return newProgram;
        }

        //选择，交叉，变异操作
        void breedNewPopulation() {
                TreeNode[] newPrograms;
                double fraction;
                int index;
                Tree individual1, individual2;
                int i;
                double sumOfFractions = this.pcross +
                                this.preproduction +
                                this.pmutation;
                double pcross = this.pcross / sumOfFractions;
                double reproductionFraction = this.preproduction / sumOfFractions;
                //double pmutation = this.pmutation/ sumOfFractions;

                newPrograms = new TreeNode[population.length];
                fraction = 0.0;
                index = 0;

                //Elitism
                newPrograms[index] = (TreeNode)bestOfRunIndividual.program.clone();
                index++;
                   
                while (index < population.length) {
                        fraction = (double)index / (double)population.length;
                        
                        //Proportionate Select or Tournament Selection     
                        individual1 = findIndividual();
                        
                        if (fraction < pcross) {
                                individual2 = findIndividual();
                                TreeNode[]	offspring = crossover(individual1.program, individual2.program);
                    newPrograms[index] = offspring[0];
                                index++;
                                if (index < population.length) {
                            newPrograms[index] = offspring[1];
                                        index = index++;
                                }
                        } else {
                                if (fraction < 	reproductionFraction + pcross) {
                                        newPrograms[index] = (TreeNode)individual1.program.clone();
                                        index ++;
                                } else {
                                        newPrograms[index] = mutate(individual1.program);
                                        index++;
                                }
                        }
                }
                for (index = 0; index < population.length; index++) {
                        population[index].program = newPrograms[index];
                }
        }

        //clean out the former fitness
        void zeroizeFitnessMeasuresOfPopulation() {
                for (int i = 0; i < population.length; i++) {
                        population[i].standardizedFitness = 0.0;
                        population[i].adjustedFitness = 0.0;
                        population[i].normalizedFitness = 0.0;
                        population[i].hits = 0;
                }
        }

     
        void evaluateFitnessOfPopulation() {
                for (int i = 0; i < population.length; i++) {
                        fitnessFunction(population[i], i);
                }
        }

     
        void normalizeFitnessOfPopulation() {
                double sumOfAdjustedFitnesses = 0.0;
                for (int i = 0; i < population.length; i++) {
                        //	Set the adjusted fitness.
                        population[i].adjustedFitness =
                            1.0 / (population[i].standardizedFitness + 1.0);
                        //	Add up the adjusted fitnesses so that we can normalize them.
                        sumOfAdjustedFitnesses =
                                        sumOfAdjustedFitnesses + population[i].adjustedFitness;
                }
                //	Loop through population normalizing the adjusted fitness.
                for (int i = 0; i < population.length; i++) {
                        population[i].normalizedFitness =
                                        population[i].adjustedFitness / sumOfAdjustedFitnesses;
                }
        }

        //sort method
        private void sort(int low, int high) {
                int index1, index2;
                double pivot;
                Tree temp;

                index1 = low;
                index2 = high;
                pivot = population[(low + high) / 2].normalizedFitness;
                do {
                        while (population[index1].normalizedFitness > pivot) {
                                index1++;
                        }
                        while (population[index2].normalizedFitness < pivot) {
                                index2--;
                        }
                        if (index1 <= index2) {
                                temp = population[index2];
                                population[index2] = population[index1];
                                population[index1] = temp;
                                index1++;
                                index2--;
                        }
                } while (index1 <= index2);
                if (low < index2) {
                        sort(low, index2);
                }
                if (index1 < high) {
                        sort(index1, high);
                }
        }

        //sort the pop by fitness
        void sortPopulationByFitness() {
                sort(0, population.length - 1);
        }

        //eval the fitness of an individual
        void fitnessFunction(Tree ind, int individualNr) {
                double rawFitness = 0.0;
                ind.hits = 0;
                RealPoint[] testCases = new RealPoint[fitnessCases.get().length];
                for (int index = 0; index < fitnessCases.get().length; index++) {
                        double x = fitnessCases.get()[index].x;
                        double valueFromProgram = ind.program.eval(x);
                        double difference = Math.abs(valueFromProgram - fitnessCases.get()[index].y);
                        rawFitness = rawFitness + difference;
                        if (difference < 0.01) {
                                ind.hits++;
                        }
                        testCases[index] = new RealPoint(x, valueFromProgram);
                }
                ind.standardizedFitness = rawFitness;

        }

        //max generation judge
        boolean terminationPredicate() {
                return currentGeneration >= MAX_GENERATIONS;
        }

        //evolve
        void evolve() {
                Tree bestOfGeneration;
                if (currentGeneration > 0) {
                   breedNewPopulation();
                }
                zeroizeFitnessMeasuresOfPopulation();
                evaluateFitnessOfPopulation();
                normalizeFitnessOfPopulation();
                //	Sort the population so that the roulette wheel selection is easy:
                sortPopulationByFitness();

                //	Keep track of best-of-run individual:
                bestOfGeneration = population[0];
                if (bestOfRunIndividual == null ||
                          bestOfRunIndividual.standardizedFitness >
                                bestOfGeneration.standardizedFitness) {
                        bestOfRunIndividual = bestOfGeneration.copy();
                        generationOfBestOfRunIndividual = currentGeneration;
                        RealPoint[] testCases = new RealPoint[fitnessCases.get().length];
                        for (int i = 0; i < fitnessCases.get().length; i++) {
                                double x = fitnessCases.get()[i].x;
                                double y = bestOfRunIndividual.program.eval(x);
                                testCases[i] = new RealPoint(x, y);
                        }
                        
                        //System.out.println("Notification Here");
                        notifyObservers(new Best_Tree(bestOfRunIndividual.copy(),currentGeneration,testCases));
                        
                }

                double[] fitness = new double[population.length];
                for (int i = 0; i < fitness.length; i++) {
                        fitness[i] = population[i].adjustedFitness;
                }

                currentGeneration++;
        }

        //find individual compare proportionate values
        Tree findFitnessProportionateIndividual(double afterThisFitness) {

                int indexOfSelectedIndividual;
                double sumOfFitness = 0.0;
                int index = 0;
                while (index < population.length && sumOfFitness < afterThisFitness) {
                        //	Sum up the fitness values.
                        sumOfFitness = sumOfFitness + population[index].normalizedFitness;
                        index++;
                }
                if (index >= population.length) {
                        indexOfSelectedIndividual = population.length - 1;
                } else {
                        indexOfSelectedIndividual = index - 1;
                }
                return population[indexOfSelectedIndividual];
        }

        //pick ind using tournament
        Tree findIndividualUsingTournamentSelection() {
                int TournamentSize = Math.min(population.length, 7);

                Hashtable table = new Hashtable();
                while (table.size() < TournamentSize) {
                        int key = random.nextInt(population.length);
                        table.put(new Integer(key), population[key]);
                }
                Enumeration e = table.elements();
                Tree best	= (Tree)e.nextElement();
                double bestFitness = best.standardizedFitness;
                while (e.hasMoreElements()) {
                        Tree individual = (Tree)e.nextElement();
                        double thisFitness = individual.standardizedFitness;
                        if (thisFitness < bestFitness) {
                          best = individual;
                                bestFitness = thisFitness;
                        }
                }
                return best;
        }

        //find ind according to selection method
        Tree findIndividual() {
                Tree ind = null;
                switch (Select_Method) {
                        case Config.TOURNAMENT:
                                ind = findIndividualUsingTournamentSelection();
                                break;
                        case Config.FITNESS_PROPORTIONATE:
                                ind = findFitnessProportionateIndividual(random.nextDouble());
                                break;
                }
                return ind;
        }

        //thread running method
        public void run() {
                //	Prime the random generator with the same seed for each run,
                //	so that we get reproducible results:
                random.setSeed(SEED);

                generationOfBestOfRunIndividual = 0;
                bestOfRunIndividual = null;
                System.out.println(maxdepth);
                create_initial_pop(maxdepth);
                currentGeneration = 0;
                System.out.println(population[0].program); 
                 
                 
                 
                while (!terminationPredicate()) {
                        try {   
                             //   System.out.print("EVOLVE HERE");
                                evolve();
                                thread.sleep(1);
                        } catch(Exception e) {
                              e.printStackTrace();
                               
                             
                        }
                }
                thread.stop();
                state.setState(2);
                notifyObservers(state);
        }

        //notify main frame observers
        public void notifyObservers(Object data) {
                setChanged();//change the flag
                super.notifyObservers(data);
        }
        
        static final Condition isProgram = new IsTreeNode();
        static final Condition isFunction = new IsFunction();

}