Вот моя проблема: я модифицирую код, который я нашел для генетических алгоритмов, чтобы выполнить численную оптимизацию функции. По существу, учитывая функцию F и наше желаемое значение, программа использует GA для поиска значений x и y, которые обеспечивают соответствующее желаемое значение. Я продолжаю возиться со своей фитнес-функцией, которая, как мне кажется, является корнем проблемы.
Основная разбивка кода:
Создать случайную популяцию хромосом
Используйте пузырьковую сортировку на основе пригодности каждой хромосомы
Проверьте, не решают ли какие-либо из них функцию
Если кто-то решит его, то остановитесь и распечатайте его
В противном случае Генерация детей на основе родителей Сортировка, проверка лучшего ответа, цикл
Я надеюсь, что кто-то может указать мне правильное направление, я собираюсь еще раз разобрать его сегодня вечером, но, похоже, я попал в затруднительное положение. Для более сложных функций, чем те, которые я жестко запрограммировал, кажется, что они сходятся вокруг случайного процента (обычно меньше 20)... но он должен быть намного ближе к 0. Простая закодированная функция продолжает возвращать разницу около 99%... так что я не на 100% в том, что случилось.
import java.util.*;
import java.util.Comparator;
import java.util.TreeMap;
/**
* Modified from a file created Jul 9, 2003
* Original @author Fabian Jones
* Modified @author Cutright
* @version 2
*/
public class ScratchGA
{
private static int NUM_CHROMOSOMES = 100; //num of chromosomes in population
private static double MUTATE = .01; //chance of a mutation i.e. 88.8%
private static int desiredValue = 60466176; //desired value of function
private static int cutoff = 1000; // number of iterations before cut off
private static int longPrint = 0; //1 means print out each iteration of the population
private boolean done = false;
private Chromosome[] population;
int iteration = 0;
/**
* Constructor for objects of class ScratchGA
*/
public ScratchGA()
{
generateRandomPopulation(NUM_CHROMOSOMES);
printPopulation();
}
/**
* Generate a random population of chromosomes - WORKS
*
*/
private void generateRandomPopulation(int pop)
{
System.out.println("Generating random population of " + pop + ", now." +"\n");
population = new Chromosome[pop];
for(int i=0; i<pop; i++)
{
int rand = (int)(Math.random()*4095); // Range 0 to 4095
population[i] = (new Chromosome(rand, 12));
}
}
/**
* Codesaver for generating a new line in the output
*/
private void newLine()
{
System.out.println("\n");
}
/**
* Prints the population (the chromosomes)
*/
private void printPopulation()
{
int x=1; // variable to print 10 chromosomes on a line
if (iteration==0)
{
System.out.println("Initial population: " + "\n" );
}
else
{
if (longPrint ==1)
{
System.out.println("Population " + iteration + " :" + "\n");
for(int i=0; i<=(NUM_CHROMOSOMES-1); i++)
{
System.out.print(population[i] + " ");
if(x == 10)
{
newLine();
x=1;
}
else
{
x++;
}
}
newLine();
}
else
{
System.out.println("Best answer for iteration " + iteration + " is: " + population[0] + " with a % difference of " +population[0].getFitness());
newLine();
}
}
}
/**
* Start
* Bubblesort initial population by their fitness, see if the first chromosome
* in the sorted array satisfies our constraint.
* IF done ==true or max num of iterations
* Print best solution and its fitness
* ELSE
* generate new population based on old one, and continue on
*/
public void start()
{
// System.out.println("Starting bubblesort... Please Wait.");
bubbleSort();
//System.out.println("After Bubblesort: " );
//printPopulation();
topFitness();
if(done || iteration==cutoff){
System.out.println("DONE!!");
System.out.println("Best solution: " + population[0] + " % Difference: " + population[0].getFitness());
}
else{
iteration++;
generateNewPopulation();
printPopulation();
start();
}
}
/**
* If the top chromosomes fitness (after being sorted by bubblesort) is 100%
* done == true
*/
private void topFitness()
{
if (population[0].getFitness() == 0)
{
done = true;
}
}
/**
* Called from chromosome,
* Tests the x and y values in the function and returns their output
*/
public static double functionTest(int x, int y)
{
return (3*x)^(2*y); // From our desired value we're looking for x=2, y=5
}
/**
* Returns the desired outcome of the function, with ideal x and y
* Stored above in a private static
*/
public static int getDesired()
{
return desiredValue;
}
/**
* Sort Chromosome array, based on fitness
* utilizes a bubblesort
*/
private void bubbleSort()
{
Chromosome temp;
for(int i=0; i<NUM_CHROMOSOMES; i++){
for(int j=1; j<(NUM_CHROMOSOMES-i); j++){
if(population[j-1].getFitness() > population[j].getFitness())
{
//swap elements
temp = population[j-1];
population[j-1] = population[j];
population[j] = temp;
}
}
}
}
/**
* Top 30: Elitism
* Next 60: Offspring of Elitists
* Next 10: Random
*/
private void generateNewPopulation(){
System.out.println("***Generating New Population");
Chromosome[] temp = new Chromosome[100];
for (int i = 0; i < 30; i++)
{
Chromosome x = population[i];
if (shouldMutate())
mutate(x);
temp[i]=x;
}
for (int i = 0; i < 30; i++)
{
temp[i+30] =cross1(population[i], population[i+1]);
temp[i+60] = cross2(population[i], population[i+1]);
}
for (int i = 90; i<100; i++)
{
int rand = (int)(Math.random()*4095); // Range 0 to 4095
Chromosome x = new Chromosome(rand, 12);
temp[i] = x;
}
population = temp;
}
/**
* First cross type, with two parents
*/
private Chromosome cross1(Chromosome parent1, Chromosome parent2){
String bitS1 = parent1.getBitString();
String bitS2 = parent2.getBitString();
int length = bitS1.length();
int num = (int)(Math.random()*length); // number from 0 to length-1
String newBitString = bitS2.substring(0, num) + bitS1.substring(num, length);
Chromosome offspring = new Chromosome();
offspring.setBitString(newBitString);
if(shouldMutate()){
mutate(offspring);
}
return offspring;
}
/**
* Second cross type, parents given in same order as first, but reverses internal workings
*/
private Chromosome cross2(Chromosome parent1, Chromosome parent2){
String bitS1 = parent1.getBitString();
String bitS2 = parent2.getBitString();
int length = bitS1.length();
int num = (int)(Math.random()*length); // number from 0 to length-1
String newBitString = bitS2.substring(0, num) + bitS1.substring(num, length);
Chromosome offspring = new Chromosome();
offspring.setBitString(newBitString);
if(shouldMutate()){
mutate(offspring);
}
return offspring;
}
/**
* Returns a boolean of whether a character should mutate based on the mutation value at top
*/
private boolean shouldMutate(){
double num = Math.random()*100;
return (num <= MUTATE);
}
/**
* Returns a boolean of whether a character should mutate based on the mutation value at top
*/
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);
}
/**
* Flips bits in a string 1 to 0, 0 to 1
*/
private String flip(String s){
return s.equals("0")? "1":"0";
}
}
import java.lang.Comparable;
import java.math.*;
/**
* Modified from a file created on Jul 9, 2003
* Unsure of original author
*
*/
public class Chromosome implements Comparable
{
protected String bitString;
/**
* Constructor for objects of class Chromosome
*/
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 double getFitness()
{
String working = bitString;
int x1 = Integer.parseInt(working.substring(0,6),2);
int x2 = Integer.parseInt(working.substring(6),2);
double result = ScratchGA.functionTest(x1,x2);
double percentDiff = ((ScratchGA.getDesired() - result)/ScratchGA.getDesired())*100;
if (percentDiff >= 0)
{
return percentDiff;
}
else
{
return -percentDiff;
}
}
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 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);
if(test.equals("1")){
sum = sum + 1;
}
}
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());
}
}