selectioncrossover.java

一个很好的LIBSVM的JAVA源码。对于要研究和改进SVM算法的学者。可以参考。来自数据挖掘工具YALE工具包。

/*
 *  YALE - Yet Another Learning Environment
 *  Copyright (C) 2001-2004
 *      Simon Fischer, Ralf Klinkenberg, Ingo Mierswa, 
 *          Katharina Morik, Oliver Ritthoff
 *      Artificial Intelligence Unit
 *      Computer Science Department
 *      University of Dortmund
 *      44221 Dortmund,  Germany
 *  email: [e-mail]
 *  web:   http://yale.cs.uni-dortmund.de/
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as 
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version. 
 *
 *  This program is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 *  USA.
 */
package edu.udo.cs.yale.operator.features.ga;

import edu.udo.cs.yale.example.AttributeWeightedExampleSet;
import edu.udo.cs.yale.tools.RandomGenerator;
import edu.udo.cs.yale.operator.features.*;

import java.util.List;
import java.util.Iterator;
import java.util.LinkedList;

/** Crossover operator for the used bitlists of example sets. An example set is selected
 *  with a given fixed propability and a mating partner is determined randomly. Crossover
 *  can be either one pint or uniform.
 *  Only useful if all example sets have the same attributes.
 *
 *  @author simon, ingo
 *  @version 29.05.2001 
 */
public class SelectionCrossover implements PopulationOperator {

    protected static final String[] CROSSOVER_TYPES = { "one_point", "uniform" };

    public static final int ONE_POINT = 0;
    public static final int UNIFORM   = 1;

    private int type;
    private double prob;

    public SelectionCrossover(int type, double prob) {
	this.prob = prob;
	this.type = type;
    }

    /** The default implementation returns true for every generation. */
    public boolean performOperation(int generation) { return true; }

    public int getType() { return type; }

    public void crossover(AttributeWeightedExampleSet es1, AttributeWeightedExampleSet es2) {
	switch (type) {
	case ONE_POINT:
	    int n = 1+RandomGenerator.getGlobalRandomGenerator().nextInt(es1.getNumberOfAttributes()-1);
	    n = es1.getExampleTable().getBlockEndIndex(n);
	    for (int i = n; i < es1.getNumberOfAttributes(); i++) {
		boolean dummy = es1.isAttributeUsed(i);
		es1.setAttributeUsed(i, es2.isAttributeUsed(i));
		es2.setAttributeUsed(i, dummy);
	    }		
	    break;
	case UNIFORM:
	    boolean[] swap = new boolean[es1.getNumberOfAttributes()];
	    for (int i = 0; i < swap.length; i++) {
		boolean blockBoolean = RandomGenerator.getGlobalRandomGenerator().nextBoolean();
		int endIndex = es1.getExampleTable().getBlockEndIndex(i);
		for (int j = i; j <= endIndex; j++) {
		    if (j < swap.length)
			swap[j] = blockBoolean;
		}
		i = endIndex;
	    }
	    for (int i = 0; i < swap.length; i++) {
		if (swap[i]) {
		    boolean dummy = es1.isAttributeUsed(i);
		    es1.setAttributeUsed(i, es2.isAttributeUsed(i));
		    es2.setAttributeUsed(i, dummy);
		}
	    }		
	    break;
	default:
	    break;
	}
    }

    public void operate(Population population) {
	if (population.getNumberOfIndividuals() < 2) return;
	
	LinkedList matingPool = new LinkedList();
	for (int i = 0; i < population.getNumberOfIndividuals(); i++) 
	    matingPool.add(population.get(i).clone());

	List l = new LinkedList();

	while (matingPool.size() > 1) {
	    AttributeWeightedExampleSet p1 =
		(AttributeWeightedExampleSet)matingPool.remove(RandomGenerator.getGlobalRandomGenerator().nextInt(matingPool.size()));
	    AttributeWeightedExampleSet p2 = 
		(AttributeWeightedExampleSet)matingPool.remove(RandomGenerator.getGlobalRandomGenerator().nextInt(matingPool.size()));
	    
	    if (RandomGenerator.getGlobalRandomGenerator().nextDouble() < prob) {
		AttributeWeightedExampleSet clone1 = (AttributeWeightedExampleSet)p1.clone();
		AttributeWeightedExampleSet clone2 = (AttributeWeightedExampleSet)p2.clone();
		crossover(clone1, clone2);
		if (clone1.getNumberOfUsedAttributes() > 0) l.add(clone1);
		if (clone2.getNumberOfUsedAttributes() > 0) l.add(clone2);
	    } else {
		l.add(p1);
		l.add(p2);
	    }
	}

	l.addAll(matingPool);

	population.clear();
	Iterator i = l.iterator();
	while (i.hasNext())
	    population.add((AttributeWeightedExampleSet)i.next());
    }
}