Выбор колеса рулетки для генетического алгоритма в 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)

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

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

Следующий код - это моя модификация rouletteWheelSelection:

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% отличается от того, что мне нужно, я сделал его отрицательным, чтобы вставить его в конец отсортированного списка.


java genetic-algorithm genetic-programming roulette-wheel-selection
person Ramrod    schedule 08.10.2012    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

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

Простой подход будет примерно таким:

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

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

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

Этот BTW, очень хорошо объясняет, почему, < em> с такой функцией фитнеса, rouletteWheelSelection () благоприятствует плохим характеристикам хромосом.

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

person mjv    schedule 08.10.2012
comment
Мой totalFitness, вычисляемый в настоящее время, представляет собой сумму абсолютных значений индивидуальных показателей пригодности. Пример: totalFitness [20,5, -15] равно 40. Я позаботился о проблеме randNum (я думаю), убедившись, что она положительная, и вычтя абсолютное значение пригодности. - person Ramrod; 08.10.2012
comment
Мое довод в пользу того, что я не возвращаю все процентные точности как положительные, состоит в том, что я могу отсортировать по точности, при этом 100% является оптимальным ... и попытаться отсеять что-либо более 100% из желаемого результата. - person Ramrod; 08.10.2012
comment
Я не решаю особо сложную проблему, но она, похоже, быстро сходитс воедино ... примерно за четыре поколения ... ха-ха. Спасибо за помощь. - person Ramrod; 08.10.2012

arrow_upward
0
arrow_downward

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

person Andreas    schedule 09.10.2012