ga.java

新型模拟退火算法解决TSP优化问题。自能退火。可用于大多数情况下的优化问题。

package test;

import java.util.*;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class GA
    implements GAInterface {
    int propagate; //人口，种群大小
    int generation; //代
    Vector solutions;

    double crossRate; //变异与杂交比例
    double varRate; //变异与杂交比例

    CityInfo cityInfo;

    public GA(CityInfo cInfo, int pop, int gen) {
        this.cityInfo = cInfo;
        this.propagate = pop;
        this.generation = gen;
    }

    /**
     * population
     *
     * @todo Implement this test.GAInterface method
     */
    public void propagate() {
        for (int i = 0; i < propagate; i++) {
            TSPSolutionWithSA solution = new TSPSolutionWithSA(cityInfo, 0.01,
                1000000);
            solution.randomPath(10000);
            solutions.add(solution);
        }
    }

    /**
     * variation
     *
     * @todo Implement this test.GAInterface method
     */
    public void variation() {
        TSPSolutionWithSA solution = (TSPSolutionWithSA) solutions.get( (int) (
            Math.random() * solutions.size()));
        solution.disturb(solution.cityInfo.cityCount);
    }

    /**
     * cross
     *
     * @todo Implement this test.GAInterface method
     */
    public void cross() {
        TSPSolutionWithSA solutionA = (TSPSolutionWithSA) solutions.remove( (int) (
            Math.random() * solutions.size()));
        TSPSolutionWithSA solutionB = (TSPSolutionWithSA) solutions.remove( (int) (
            Math.random() * solutions.size()));
    }

    /**
     * evolution
     *
     * @todo Implement this test.GAInterface method
     */
    public void evolution() {
        int time = (int) (propagate * (varRate + crossRate));
        double border = varRate / (varRate + crossRate);

        for (int i = 0; i < generation; i++) {

            for (int j = 0; j < time; j++) {
                if (Math.random() < border) {
                    variation();
                }
                else {
                    cross();
                }
            }

            //采用随机联赛制恢复群大小
            randomLeague();
        }
    }

    void randomLeague() {
        while (solutions.size() > propagate) {
            TSPSolutionWithSA solutionA = (TSPSolutionWithSA) solutions.remove( (int) (
                Math.random() * solutions.size()));
            TSPSolutionWithSA solutionB = (TSPSolutionWithSA) solutions.remove( (int) (
                Math.random() * solutions.size()));

            if (solutionA.potentialEnergy < solutionB.potentialEnergy) {
                solutions.add(solutionA);
            }
            else {
                solutions.add(solutionB);
            }
        }
    }
}