Java и повышение эффективности генетических алгоритмов

Question

Hey Guys, Мне было интересно, могу ли я получить совет по повышению общей эффективности программы, которая реализует генетический алгоритм. Да это вопрос назначения, но я уже выполнил задание самостоятельно и я просто искал способ, чтобы заставить его работать лучше Problem Description

Моей программы в данный момент читает данная цепь изготовлен из типов составляющие, h или p. (Пример hphpphhphpphphhpphph). Для каждого H и P он генерировал случайный ход (вверх, вниз, влево, вправо) и добавляет перемещение к списку элементов массива, содержащемуся в объекте «Хромосома». На старте программа генерирует 19 ходов 10000 хромосом

SecureRandom sec = new SecureRandom(); 
    byte[] sbuf = sec.generateSeed(8); 
    ByteBuffer bb = ByteBuffer.wrap(sbuf); 
    Random numberGen = new Random(bb.getLong()); 
    int numberMoves = chromosoneData.length(); 
    moveList = new ArrayList(numberMoves); 
    for (int a = 0; a < numberMoves; a++) { 
     int randomMove = numberGen.nextInt(4); 
     char typeChro = chromosoneData.charAt(a); 
     if (randomMove == 0) { 
      moveList.add(Move.Down); 
     } else if (randomMove == 1) { 
      moveList.add(Move.Up); 
     } else if (randomMove == 2) { 
      moveList.add(Move.Left); 
     } else if (randomMove == 3) { 
      moveList.add(Move.Right); 
     } 

    } 

После этого идет отбор хромосом от населения до кроссовера. Моя функция кроссовера выбирает первую хромосому случайным образом из наиболее приспособленных 20% населения, а другая случайным образом из-за пределов 20%. Затем выбранные хромосомы пересекаются и вызывается функция мутации. Я считаю, что область, в которой я принимаю наибольший успех, - это расчет пригодности каждой хромосомы. В настоящее время моя функция фитнеса создает 2d-массив для работы в качестве сетки, перемещает по порядку из списка перемещения, сгенерированного функцией, показанной выше, а затем перебирает массив для вычисления пригодности. (IE найден и H в местоположении [2,1] является шнуром [1,1] [3,1] [2,0] или [2,2] также H, и если H найден, он просто увеличивает счетчик обнаружены облигации)

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

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

Как было предложено в комментариях, я запустил профайлер в своем приложении (никогда не использовал его раньше, только студент CS первого курса), и мое первоначальное предположение о том, где у меня проблемы, было несколько неправильным. Похоже, что профайлер говорит мне, что большие горячие точки:

1) При сравнении новой хромосомы с остальными в популяции, чтобы определить ее положение. Я делаю это, реализуя Comparable.

public int compareTo(Chromosome other) { 
    if(this.fitness >= other.fitness) 
        return 1; 
     if(this.fitness ==other.fitness) 
        return 0; 
      else 
        return -1; 



} 

2) Другая область проблемы, описанная в моей фактической функции эволюции, потребляя около 40% процессорного времени. Codesample из указанного метода ниже

double topPercentile = highestValue; 
    topPercentile = topPercentile * .20; 
    topPercentile = Math.ceil(topPercentile); 
    randomOne = numberGen.nextInt((int) topPercentile); 
    //Lower Bount for random two so it comes from outside of top 20% 
    int randomTwo = numberGen.nextInt(highestValue - (int) topPercentile); 
    randomTwo = randomTwo + 25; 
    //System.out.println("Selecting First: " + randomOne + " Selecting Second: " + randomTwo); 
    Chromosome firstChrom = (Chromosome) populationList.get(randomOne); 
    Chromosome secondChrom = (Chromosome) populationList.get(randomTwo); 
    //System.out.println("Selected 2 Chromosones Crossing Over"); 
    Chromosome resultantChromosome = firstChrom.crossOver(secondChrom); 
    populationList.add(resultantChromosome); 
    Collections.sort(populationList); 
    populationList.remove(highestValue); 
    Chromosome bestResult = (Chromosome) populationList.get(0); 

3) Другой основной Палатка хита является Начальным высева населения, которое осуществляется с помощью первого образца кода в посте

Answer 1

Вместо того, чтобы повторно сортировать свое население, используйте коллекцию, содержащую уже отсортированное содержимое. (например, TreeSet)

Answer 2

Я считаю, что область, в которой я принимая наибольший успех, рассчитываем пригодность каждой хромосомы

Если вы не уверены, то я предполагаю, что вы еще не запускали профайлер программы.
Если вы хотите улучшить производительность, профилирование - это первое, что вам нужно сделать.

Answer 3

Если ваш показатель пригодности согласован между поколениями (т.не зависит от других членов населения), то я надеюсь, по крайней мере, что вы храните это в объекте Chromosome, поэтому вы рассчитываете его только один раз для каждого члена населения. При этом вы будете только вычислять пригодность для вновь созданной/собранной хромосомы на каждой итерации. Без дополнительной информации о том, насколько пригодна для расчета, трудно быть в состоянии предложить какие-либо оптимизации в этой области.

Answer 4

Ваше семя генератора случайных чисел не должно быть криптографически сильным.

Random numberGen = new Random(); 

Answer 5

Несовершеннолетнего убыстрение при посеве вашего населения, чтобы удалить все испытания и разветвление:

static Move[] moves = {Move.Down, Move.Up, Move.Left, Move.Right}; 

    ... 

    moveList.add(moves[randomMove]);