Классификатор генетического алгоритма в Java: система на основе правил

Question

Я кодировал с нуля генетический алгоритм со всеми функциями (выбор турнира, кроссовер, мутация, элитарность и т. Д.), Который успешно развивает решение проблемы «подсчета» - т.е. он манипулирует случайно сгенерированной популяцией бинарных хромосом, состоящей из 1s & 0s, пока не достигнут идеальный, заполненный 1s.

Теперь мне нужно применить этот алгоритм и создать классификатор. Система должна классифицировать двоичные данные в класс «0» или класс «1». У меня есть несколько комплектов обучающих данных, но здесь самое основное:

32 rows x 5 variables (+ class, space separated, CR EOL) 00000 0 00001 0 00010 0 00011 1 00100 0 00101 1 00110 1 00111 0 01000 0 01001 1 01010 1 01011 0 01100 1 01101 0 01110 0 01111 1 10000 0 10001 1 10010 1 10011 0 10100 1 10101 0 10110 0 10111 1 11000 1 11001 0 11010 0 11011 1 11100 0 11101 1 11110 1 11111 0

Как бы идти о применении генетического алгоритма я уже построил для такой задачи с контекстом на основе правил в форма IF x (AND y) THEN z? Я не уверен, с чего начать, я думаю, что мне, возможно, придется делать некоторые извлечения правил, но я не знаю, как это сделать в этом контексте.

EDIT: Кроме Код

public class Controller { 

public static void main(String[] args) { 
    final int P = 50;     // population size 
    final int N = 32;     // chromosome length 
    final double C = 0.95;    // crossover rate 
    final double M = (double) 1/P; // mutation rate 
    final int G = 50;     // # of generations 

    GA ga = new GA(P, N, C, M); 

    // Initialise population of random individuals 
    Individual[] population = ga.initPop(); 

    // "Counting ones" fitness evaluation 
    System.out.println("GEN0"); 
    ga.evaluatePop(population); 
    ga.printFitness(population); 

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

     System.out.println("\nGeneration: " + generation); 

     // Tournament selection 
     population = ga.tournament(population); 

     // Tournament winners fitness evaluation 
     ga.evaluatePop(population); 

     // Single-point crossover 
     population = ga.crossover(population); 

     // Crossover children fitness evaluation 
     ga.evaluatePop(population); 

     // Bit-wise mutation 
     population = ga.mutate(population); 

     // Post-mutation population fitness evaluation 
     ga.evaluatePop(population); 

     // Elitism replacement (remove the worst gene and replace with a copy of the best) 
     population = ga.elitism(population); 

     // Post-elitism population fitness evaluation 
     ga.evaluatePop(population); 
     ga.printFitness(population); 

     generation++; 

     if (ga.bestFitness(population) == N) { 
      break; 
     } 
    } 
} 

`

public class GA { 

int populationSize; 
int chromosomeSize; 
double crossoverRate; 
double mutationRate; 
Random random = new Random(); 

public GA(int populationSize, int chromosomeSize, double crossoverRate, double mutationRate) { 
    this.populationSize = populationSize; 
    this.chromosomeSize = chromosomeSize; 
    this.crossoverRate = crossoverRate; 
    this.mutationRate = mutationRate; 
} 

public Individual[] initPop() { 
    Individual[] population = new Individual[populationSize]; 
    for (int i = 0; i < populationSize; i++) { 
     population[i] = new Individual(chromosomeSize); 
    } 
    return population; 
} 

public void evaluatePop(Individual[] population) {       
    for (int i = 0; i < population.length; i++) { 
     population[i].evaluate(); 
    } 
} 

public Individual[] tournament(Individual[] population) { 
    Individual[] selectionTemp = new Individual[populationSize]; 
    for (int i = 0; i < population.length; i++) { 

     Individual parent1 = population[random.nextInt(population.length)]; 
     Individual parent2 = population[random.nextInt(population.length)]; 

     if (parent1.getFitness() >= parent2.getFitness()) { 
      selectionTemp[i] = parent1; 
     } else { 
      selectionTemp[i] = parent2; 
     } 
    } 
    population = selectionTemp; 
    return population; 
} 

public Individual[] crossover(Individual[] population) { 
    for (int i = 0; i < population.length - 1; i += 2) { 
     Individual offspring1 = new Individual(population[0].getChromosome().length); 
     Individual offspring2 = new Individual(population[0].getChromosome().length); 

     int xpoint = 1 + random.nextInt(chromosomeSize - 1); 

     if (random.nextDouble() < crossoverRate) { 
      for (int j = 0; j < xpoint; j++) { 
       offspring1.setGene(j, population[i].getGene(j)); 
       offspring2.setGene(j, population[i+1].getGene(j)); 
      } 
      for (int j = xpoint; j < population[0].getChromosome().length; j++) { 
       offspring1.setGene(j, population[i+1].getGene(j)); 
       offspring2.setGene(j, population[i].getGene(j)); 
      } 
     } 
     population[i] = offspring1; 
     population[i+1] = offspring2; 
    } 
    return population; 
} 

public Individual[] mutate(Individual[] population) { 
    for (int i = 0; i < population.length; i++) { 
     for (int j = 0; j < population[i].getChromosome().length; j++) { 
      if (random.nextDouble() < mutationRate) { 
       population[i].mutate(j); 
      } 
     } 
    } 
    return population; 
} 

public Individual[] elitism(Individual[] population) { 
    Individual min = population[0]; 
    int minOffset = 0; 
    for (int i = 0; i < population.length; i++) { 
     if (population[i].getFitness() <= min.getFitness()) { 
      min = population[i]; 
      minOffset = i; 
     } 
    } 
    Individual max = population[0]; 
    int maxOffset = 0; 
    for (int i = 0; i < population.length; i++) { 
     if (population[i].getFitness() >= max.getFitness()) { 
      max = population[i]; 
      maxOffset = i; 
     } 
    } 
    population[minOffset] = population[maxOffset]; 
    return population; 
} 

// <editor-fold defaultstate="collapsed" desc="Debug logic..."> 
public int totalFitness(Individual[] population) { 
    int population_fitness = 0; 
    for (int i = 0; i < population.length; i++) { 
     population_fitness += population[i].getFitness(); 
    } 
    return population_fitness; 
} 

public double avgFitness(Individual[] population) { 
    return (double) totalFitness(population)/population.length; 
} 

public int bestFitness(Individual[] population) { 
    int max = population[0].getFitness(); 
    for (int i = 0; i < population.length; i++) { 
     if (population[i].getFitness() > max) { 
      max = population[i].getFitness(); 
     } 
    } 
    return max; 
} 

    public Individual bestIndividual(Individual[] population) { 
    Individual max = population[0]; 
    for (int i = 0; i < population.length; i++) { 
     if (population[i].getFitness() >= max.getFitness()) { 
      max = population[i]; 
     } 
    } 
    return max; 
} 

public void printFitness(Individual[] population) { 
    System.out.println("Total fitness: " + totalFitness(population)); 
    System.out.println("Average fitness: " + avgFitness(population)); 
    //System.out.println("Best fitness: " + bestFitness(population)); 
    System.out.println("Best individual: " + bestIndividual(population)); 
} 

public void printPop(Individual[] population) { 
    for (int i = 0; i < population.length; i++) { 
     System.out.println(Arrays.toString(population)); 
    } 
} 
// </editor-fold> 

` `

public class Individual { 

public int[] chromosome; 
public int fitness = 0; 
Random random = new Random(); 

public Individual(int chromosomeSize) { 
    this.chromosome = new int[chromosomeSize]; 
    for (int i = 0; i < chromosomeSize; i++) { 
     this.setGene(i, random.nextInt(2)); 
    } 
} 

// Initializes individual with a blank chromosome (all genes 0) 
public Individual(int chromosomeSize, boolean isBlank) { 
    this.chromosome = new int[chromosomeSize]; 
    Arrays.fill(chromosome, 0); 
} 

public void mutate(int offset) { 
    if (this.getGene(offset) == 1) { 
     this.setGene(offset, 0); 
    } else { 
     this.setGene(offset, 1); 
    } 
} 

public void evaluate() { 
    int count = 0; 
    for (int offset = 0; offset < this.chromosome.length; offset++) { 
     if (this.getGene(offset) == 1) { 
      count++; 
     } 
    } 
    this.setFitness(count); 
} 

public int getGene(int offset) { 
    return this.chromosome[offset]; 
} 

public void setGene(int offset, int gene) { 
    this.chromosome[offset] = gene; 
} 

public int[] getChromosome() { 
    return chromosome; 
} 

public int getFitness() { 
    return fitness; 
} 

public void setFitness(int fitness) { 
    this.fitness = fitness; 
} 

@Override 
public String toString() { 
    String output = "Binary gene representation: "; 
    for (int i = 0; i < this.chromosome.length; i++) { 
     output += this.getGene(i); 
    } 
    System.out.println(output); 
    System.out.println("Fitness: " + this.getFitness()); 
    return output; 
} 

Answer 1

Генетический алгоритм (ГА) является метаэвристического вдохновлен процессом естественного отбора , A metaheuristic определяется как процедура или эвристика более высокого уровня, предназначенная для поиска, генерации или выбора субэвристики или комбинации или перестановки подэвристик. Использование GA само по себе ничего не говорит о том, как и чем должны выглядеть субэвристики. Таким образом, можно переформулировать текущую реализацию как:

Я разработал metaheursitic рамки GA, но теперь мне нужно, чтобы определить и разработать суб-эвристический (ы), которые могли бы позволить мне решить эту конкретную проблему. Наверное, я только на полпути.

Это правильно. И теперь для второго важного понимания GA: Они лучше всего применяются в тех случаях, когда частичный успех (подрешение или неоптимальное решение) может быть дополнительно уточнен для получения еще лучших результатов.

GAs хорошо работают для решения математических оптимизаций, например, где часто существует непрерывность и локальность. Или, например, решить лабиринт, где хорошее частичное решение, безусловно, является хорошей отправной точкой для попытки полного решения.

К сожалению, в вашем конкретном случае проблема с четностью (четная или нечетная проблема) не является проблемой оптимизации или явно итерационной проблемой. Это проблема «все или ничего», и GA не является естественным сочетанием с бинарной хромосомой 0 или 1.

Это не означает, что вы не смогли бы заставить решение GA — вы могли бы создать различные правила поиска, которые используют модуль или XOR (например) и очень быстро развивают решение, которое работает. Но это почти похоже на обман, поскольку вы жестко закодировали существенную «проницательность» (модульную операцию или XOR), которые вы предпочли бы развиваться.Другим способом разобраться в GA в решении здесь было бы разработать «гены», которые кодируют «программный» синтаксис и фактически развивают небольшую программную функцию bool result = f(x), которая выводит истинное или ложное значение (ваша двоичная классификация). Но это добавляет много сложностей, таких как синтаксис и т. Д., И вы, скорее всего, окажетесь на территории STGP (строго типизированное генетическое программирование), и вы должны знать, что туземцы, которые там живут, будут накладывать на вас сильный временный налог за прохождение через свою землю неподготовленными.

Мой совет по проблеме паритета: опустите себя к использованию только нейронной сети. Они не настолько сексуальны или универсальны, но они выполнят свою работу, не требуя, чтобы вы либо обманывали, либо выполняли намного больше работы (STGP). Хорошо известно, что нейронные сети с достаточным количеством узлов могут изучать XOR и, следовательно, четность.

Edit:

Для классифицирует это как присвоение школы Г.А., я рекомендую принимать цифровой затвор стилизованного подход. Вам нужно перейти от бинарной схемы хромосомы к тройной схеме хромосом (которая не требует дополнительного кодирования, поскольку вы уже используете объявление int[] chromosome). Каждый Trit (Trinary цифра) может затем код следующих правил подстановки:

1: prior State AND B[next] 
2: prior State OR B[next] 
3: NOT 

Для заданного входного битового шаблона B[], тройная хромосома может быть оценена слева направо, на основе каждого бита, с начальным State переменная 0 (где State - внутренняя переменная внутри функции оценки) и неявная операция И происходит между каждым последовательным тритом (за исключением типа NOT). Так, к примеру, представьте, что вы эволюционировали тройное решение 2, 3, 3, 1, который будет представлять следующую последовательность операций в функции оценки (применяется один раз для каждого входного бита):

((!(!(prior State | B[next]))) & (prior State & B[next])) 

где State и B[next], очевидно, немного (bool). Обратите внимание, что операция AND рядом с серединой происходит из неявной операции И, которую мы определили, чтобы происходить между любыми тэтами, которые не относятся к типу NOT. Так, например, входные бита строка 100 при запуске с помощью функции оценки в отношении нашего примера хромосомы 2, 3, 3, 1 будет выглядеть следующим образом:

1. State = 0 
2. B[next] = 1, State = ((!(!(0 | 1))) & (0 & 1)) = 0 
3. B[next] = 0, State = ((!(!(0 | 0))) & (0 & 0)) = 0 
4. B[next] = 0, State = ((!(!(0 | 0))) & (0 & 0)) = 0 
5. Return final State value (0 here) from evaluation function. 

Вы можете произвольно определить результат 0 означают даже и результат от 1 до Если вам понравилось, вам будет нечему странно. Выбор не имеет значения, поскольку GA может легко научиться инвертировать результат с помощью дополнительного NOT trit в конце хромосомы.

Приятная вещь в этой функции оценки заключается в том, что она будет обрабатывать произвольно большие входные битовые строки, поскольку она применяется только для каждого бит в качении и не заботится об общей длине строки бит. И мы знаем, что теоретически он может разработать правильное решение с A XOR B = (A OR B) AND (NOT (A AND B)), а XOR - все, что необходимо для контроля четности.

Для того, чтобы это сработало, вам необходимо разрешить решения переменной длины (последовательности с измененной длиной), но ограничить хромосомы разумным верхним пределом (скажем, 15 трит или около того), чтобы предотвратить с ума со все более продолжительными решениями. И еще одна вещь, которую вам нужно будет сделать для того, чтобы это сработало: оценка на основе пакетной оценки многих входных битовых строк. Поскольку вывод функции оценки для любой входной битовой строки равен 0 или 1, результат будет либо на 100% правильным, либо на 0% правильным.Это само по себе не позволяет использовать полезную оценку, потому что у вас нет хорошего способа ранжировать различные последовательности тритов (решений) сравнительно, так как примерно половина будет на 100% правильной, а другая половина будет 0%. Но решение прост: просто запишите каждую последовательность trit на% всех входных строк, которые она правильно маркирует. Поэтому, если в вашем наборе данных имеется 100 строк ввода бит, а решение 1 правильно накладывает 57% входных битовых строк, тогда как решение 2 правильно набирает только 49% входов, теперь у вас есть хороший способ ранжировать вашу совокупность решений и выбрать для генетического кроссовера, мутации, выживаемости элитизма и т. д.