Выбор колеса рулетки для генетического алгоритма в Java

Я реализую метод выбора колеса рулетки для генетического алгоритма. Мой вопрос, по сути, довольно прост, но я не могу сосредоточиться на этом. В моей функции пригодности, если ответ крайне неправильный, он может вернуть около -3000%. Моя проблема в том, что, когда я пытаюсь назначить вероятности для своих результатов, они искажаются в сторону неправильных ответов.

Например: если мои проценты находятся в массиве и составляют [92, 68, 5, -4, -3546] (от высокого к низкому), мне нужно дать числам в более низких индексах больший шанс быть выбранным, чем числа с более высокими показателями.

Игнорируя мою функцию пригодности, как мне создать вероятность, основанную на этом, принимая во внимание большие отрицательные числа?

Некоторый основной код, с которым я возился, я нашел в другом вопросе:

public Individual rouletteWheelSelection() { 
    double randNum = m_rand.nextDouble() * this.totalFitness; 
    int idx; 
    for (idx=0; idx<POP_SIZE && randNum>0; ++idx) { 
        randNum -= m_population[idx].getFitnessValue(); 
    } 
    return m_population[idx-1]; 
}

(оригинальная ссылка здесь: GA написано на Java)

Моя ГА работала на другой метод выбора, но теперь я пытаюсь изменить этот метод, чтобы он работал. Любая помощь будет принята с благодарностью.

***Редактировать

Следующий код - моя рулетка WheelSelection, которую я изменил:

private Chromosome rouletteWheelSelection(){
    double randNum = Math.abs(rand_num.nextDouble() * totalFitness);
    int idx;
    for (idx=0;idx<NUM_CHROMOSOMES && randNum>0;++idx){
        randNum -= Math.abs(population[idx].getFitness());
    }
    return population[NUM_CHROMOSOMES-idx];
}

Вот моя фитнес-функция:

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 percentAccuracy = (1- Math.abs(((ScratchGA.getDesired() - result)/ScratchGA.getDesired())))*100;
    if (percentAccuracy <= 100)
    {
    return percentAccuracy;
    }
    else
    {
    return -percentAccuracy;
    }
}

Мысль заключалась в том, что это значение более чем на 100% отличается от того, что мне было нужно, и я отрицательно отнес его к концу моего отсортированного списка.

Источник

2 ответа

Решение

Метод выбора, показанный в вопросе, неявно работает только с положительными или нулевыми значениями пригодности.

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

Более серьезная проблема возникает, когда значение randNum [предполагается уменьшить], но каким-то образом отрицательные значения пригодности приводят к повторному росту RandNum.

Было бы предложено изменить функцию пригодности, чтобы она возвращала только положительные значения.

Простой подход будет что-то вроде:

if (fitValue >= -5000)
  fitValue += 5000;
else
  fitvalue = 0;

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

Редактировать с учетом добавленных фрагментов и ваших замечаний
Эффективно, работая с Abs. ценит вашу версию rouletteWheelSelection() заботится о "более серьезной" проблеме, указанной в моем первоначальном ответе.
Тем не менее getFitness() Функция, как подозревается, очень искажена в пользу отрицательных значений. Его рабочий диапазон [some_potentially_very_negative_value, +100].
См. Код: наибольшее возвращаемое значение равно +100, но существует возможность возврата очень больших отрицательных значений, когда значение для ScratchGA.functionTest(x1,x2) сильно отличается от ScratchGA.getDesired() значение.
По-видимому, существует необходимость в некоторой нормализации сортов, чтобы отрицательные результаты не превышали 100 (в абсолютном значении).

Это, кстати, очень хорошо объясняет, почему при такой функции пригодности рулетка колеса () способствует низкоэффективным хромосомам.

Представьте, например, что у вас есть популяция из 5 хромосом с соответствующим значением пригодности 80, 70, 30, 20 и -250. Сумма составляет 450, с 200 для всех четырех хромосом с положительной пригодностью и 250 для одной хромосомы с отрицательной приспособленностью. В этом примере лучше, чем даже шанс выбрать худшее из хромосом!
Идея выбора колеса рулетки заключается в том, чтобы предложить возможность выбора хромосом с менее чем оптимальной приспособленностью, но вероятность выбора любой хромосомы должна быть пропорциональна количеству, которое хромосома вносит в общую сумму значений приспособленности. Реализация, которую вы используете, эффективно делает это, но проблема в том, что значение, внесенное в сумму для отрицательных результатов, кажется несоразмерным тому, что обеспечивают положительные значения пригодности.

Источник

Вы можете использовать оконную функцию в том смысле, что вы всегда прибавляете или вычитаете худшую пригодность населения. Так что диапазон для выбора расширяется от 0 до положительных значений. У худшего человека никогда не будет шансов быть отобранным (аналогично выбору турнира). Потому что, если вы не укажете свои значения, то человек с пригодностью 98 будет испытывать почти такое же давление выбора, что и тот, у кого 95 и 96. Это хорошо, если ваше население включает решения низкого качества, но когда все решения находятся в 90-х годах. давление отбора значительно снизится. По мере того, как ваше население подходит к оптимальному решению, вы все больше будете действовать как случайный поиск. Вы можете провести направленное исследование, только если учтете все более мелкие детали (различия) в вашем населении.

Источник
Другие вопросы по тегам