用遗传算法实现子集求和

Question

import java.util.Collections;
import java.util.Vector;

public class Metaheuristic {
    private static int[] DATA;  
    private static int NUM_CHROMOSOMES ;
    private static int MAX_POWER;
    private static int MAX_NUMBER;
    private static int FITNESS_THRESHOLD;
    private static float MUTATE = (float) .05;
    private Vector population;
    private boolean done = true;
    int numRuns = 0;
    public void GeneticAlgorithm (int[] data, int target, int n){
        NUM_CHROMOSOMES = n;
    MAX_POWER = data.length;
    MAX_NUMBER = (int) Math.pow(2, MAX_POWER) - 1;
    FITNESS_THRESHOLD = target;
    DATA = new int[data.length];
        DATA = data;

        Metaheuristic s = new Metaheuristic();
        s.start();
        //System.out.println("s");
        }


    public Metaheuristic(){
        generateRandomPopulation();
    }

    private void generateRandomPopulation(){
    System.out.println("***Randomly Generating population with: " + NUM_CHROMOSOMES + " Chromosome(s)***");
    population = new Vector();
    for(int i = 0; i < NUM_CHROMOSOMES; ++i){
            int randomValue = (int) (Math.random()*MAX_NUMBER);
            population.add(new Chromosome(randomValue, MAX_POWER));
    }
        System.out.println("First Population: " + population +"n");
    }

    public void start(){
    Collections.sort(population);
    Chromosome fitess = (Chromosome) population.lastElement();
    done = fitess.fitness(DATA, FITNESS_THRESHOLD) >= MAX_POWER? true:false;
    if(done){
            System.out.println("DONE, solution found: " + fitess);  
    }
        else{
            numRuns++;
            System.out.println("FITESS: " + fitess + " fitness: " + fitess.fitness(DATA, FITNESS_THRESHOLD ));
            generateNewPopulation();
            start();
        }
    }
    private void generateNewPopulation(){
        System.out.println("***Generating New Population");
        Vector temp = new Vector();
        for(int i = 0; i < population.size()/2; ++i){
            Chromosome p1 = selectParent();
            Chromosome p2 = selectParent();
            temp.add(cross1(p1, p2));
            temp.add(cross2(p1, p2));
        }
        population.clear();
        population.addAll(temp);
        System.out.println("New Population: " + population + "n");
    }
    private Chromosome selectParent(){
        int delta = population.size();
        delta = NUM_CHROMOSOMES - NUM_CHROMOSOMES/2;
        int num = (int) (Math.random()*10 + 1);
        int index;
        if(num >= 4){
            index = (int) (Math.random()*delta + NUM_CHROMOSOMES/2);
        }
        else{
            index = (int) (Math.random()*delta);    
        }
        return (Chromosome) population.get(index);
    }
    private Chromosome cross1(Chromosome parent1, Chromosome parent2){
        String bitS1 = parent1.getBitString();
        String bitS2 = parent2.getBitString();
        int length = bitS1.length();
        String newBitString = bitS1.substring(0, length/2) + bitS2.substring(length/2, length);
        Chromosome offspring = new Chromosome();
        offspring.setBitString(newBitString);
        if(shouldMutate()){
            mutate(offspring);
        }
        return offspring;
    }
    private Chromosome cross2(Chromosome parent1, Chromosome parent2){
        String bitS1 = parent1.getBitString();
        String bitS2 = parent2.getBitString();
        int length = bitS1.length();
        String newBitString = bitS2.substring(0, length/2) + bitS1.substring(length/2, length);
        Chromosome offspring = new Chromosome();
        offspring.setBitString(newBitString);
        if(shouldMutate()){
            mutate(offspring);
        }
        return offspring;
    }
    private boolean shouldMutate(){
        double num = Math.random();
        int number = (int) (num*100);
        num = (double) number/100;
        return (num <= MUTATE);
    }
    private void mutate(Chromosome offspring){
        String s = offspring.getBitString();
        int num = s.length();
        int index = (int) (Math.random()*num);
        String newBit = flip(s.substring(index, index+1));
        String newBitString = s.substring(0, index) + newBit + s.substring(index+1, s.length());
        offspring.setBitString(newBitString);
    }
    private String flip(String s){
        return s.equals("0")? "1":"0";
    }
    public static void main(String[] args) {
        double average = 0;
        int sum = 0;
        for(int i = 0; i < 10; ++i){
            Metaheuristic s = new Metaheuristic();
            s.start();
            sum = sum + s.numRuns;
            average = (double) sum / (double)(i+1); 
            System.out.println("Number of runs: " + s.numRuns);
        }
        System.out.println("average runs: " + average);
    }
}
    import java.lang.Comparable;
public class Chromosome implements Comparable{
    protected String bitString;
    public static int[] DATA;
    public int TARGET;
    public Chromosome(){
    }

    public Chromosome(int value, int length){
    bitString = convertIntToBitString(value, length);
    }

    public void setBitString(String s){
    bitString = s;
    }

    public String getBitString(){
    return bitString;
    }

    public int compareTo(Object o) {
    Chromosome c = (Chromosome) o;
    int num = countOnes(this.bitString) - countOnes(c.getBitString()); 
    return num;
    }

    public int fitness(int[] data, int target){
    DATA = new int[data.length];
        System.arraycopy(data, 0, DATA, 0, data.length);
        TARGET = target;
        return countOnes(bitString);
    }

    public boolean equals(Object o){
    if(o instanceof Chromosome){
            Chromosome c = (Chromosome) o;
            return c.getBitString().equals(bitString);
        }
    return false;
    }

    public int hashCode(){
    return bitString.hashCode();
    }

    public String toString(){
    return "Chromosome: " + bitString;
    }

    public static int countOnes(String bits){
    int sum = 0;
    for(int i = 0; i < bits.length(); ++ i){
            String test = bits.substring(i, i+1);
            sum = sum + (DATA[i]*Integer.parseInt(test));
        }
    return sum;
    }

    public static String convertIntToBitString(int val, int length){
    int reval = val;
    StringBuffer bitString = new StringBuffer(length);
        for(int i = length-1; i >=0; --i ){
            if( reval - (Math.pow(2, i)) >= 0 ){
                bitString.append("1");
                reval = (int) (reval - Math.pow(2, i));
            }
            else{
                bitString.append("0");
            }
    }
    return bitString.toString();
    }

   /* public static void main(String[] args){
    //System.out.println(convertIntToBitString(2046, 10));
    Chromosome c = new Chromosome(1234, 10);
    System.out.println(c.fitness());
    }*/

}

我的适应度函数是f(x ) = s · (C − P(x )) + (1 − s) · P(x )，其中C是我要达到的目标值，P(*x ) = (Sigma) wixi，其中wi是元素的集合，xi是0或1(选择或不选择元素(。s也是0或1取决于p(x(值。请帮我写这篇健身文章。我刚试过，但程序运行时出错了。

Answer 1

您的代码中有几个问题，显然您没有调试它。

第一个NUM_CHROMOSOMES是0，因为它是(不使用的GeneticAlgorithm的(未初始化字段。

由于NUM_CHROMOSOMES为0，因此此for循环无效：

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

然后，这一行：

int randomValue = (int) (Math.random() * MAX_NUMBER);

由于MAX_NUMBER从未被手动初始化(与NUM_CHROMOSOMES相同，其值为0，randomValue也是

不管怎样，population是空的，因为你不测试空性，所以这行：

Chromosome fitess = (Chromosome) population.lastElement();

抛出异常，因为在空的population Vector中没有最后一个元素。

附带说明一下，StringBuffer和Vector是过时的类，您永远不需要导入Comparable，因为它属于java.lang包。