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

Question

Может ли кто-нибудь предоставить псевдокод для функции выбора рулетки? Как бы это реализовать:

Я не очень понимаю, как читать эту математическую запись. Я никогда не принимал никакой вероятности или статистики.

Answer 1

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

for all members of population
    sum += fitness of this individual
end for

for all members of population
    probability = sum of probabilities + (fitness / sum)
    sum of probabilities += probability
end for

loop until new population is full
    do this twice
        number = Random between 0 and 1
        for all members of population
            if number > probability but less than next probability 
                then you have been selected
        end for
    end
    create offspring
end loop

Сайт, с которого это произошло, можно найти здесь , если вам нужна дополнительная информация.

Answer 2

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

def select(fs):
    p = random.uniform(0, sum(fs))
    for i, f in enumerate(fs):
        if p <= 0:
            break
        p -= f
    return i

Кроме того, если вы накапливаете фс, вы можете найти более эффективное решение.

cfs = [sum(fs[:i+1]) for i in xrange(len(fs))]

def select(cfs):
    return bisect.bisect_left(cfs, random.uniform(0, cfs[-1]))

Это и быстрее, и очень лаконичный код. STL в C ++ имеет аналогичный алгоритм деления пополам, если вы используете этот язык.

Answer 3

Опубликованный псевдокод содержал некоторые неясные элементы, и он добавляет сложность генерации потомка вместо выполнения чистого выбора. Вот простая реализация этого псевдокода на python:

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        </125910/vybor-ruletki-v-geneticheskih-algoritmah
        -selection-in-genetic-algorithms/177278#177278>
    """
    total_fitness = float(sum(fitnesses))
    rel_fitness = [f/total_fitness for f in fitnesses]
    # Generate probability intervals for each individual
    probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))]
    # Draw new population
    new_population = []
    for n in xrange(num):
        r = rand()
        for (i, individual) in enumerate(population):
            if r <= probs[i]:
                new_population.append(individual)
                break
    return new_population

Answer 4

Это называется выбором колеса рулетки посредством стохастического принятия:

/// \param[in] f_max maximum fitness of the population
///
/// \return index of the selected individual
///
/// \note Assuming positive fitness. Greater is better.

unsigned rw_selection(double f_max)
{
  for (;;)
  {
    // Select randomly one of the individuals
    unsigned i(random_individual());

    // The selection is accepted with probability fitness(i) / f_max
    if (uniform_random_01() < fitness(i) / f_max)
      return i;
  }   
}

Среднее количество попыток, необходимых для одного выбора:

& тау; = f _max / avg (f)

• f _max - максимальная приспособленность населения
• avg (f) - средняя пригодность

& тау; не зависит явно от числа людей в популяции (N), но отношение может измениться с N.

Однако во многих приложениях (где пригодность остается ограниченной, а средняя пригодность не уменьшается до 0 для увеличения N) & tau; не увеличивается неограниченно с N и, следовательно, типичная сложность этого алгоритма составляет O (1) (выбор колеса рулетки с использованием алгоритмов поиска имеет сложность O (N) или O (log N)).

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

Подробнее см .:

• Выбор колеса рулетки посредством стохастического принятия (Адам Липоски, Дорота Липовска - 2011)

Answer 5

Вот код в C:

// Find the sum of fitnesses. The function fitness(i) should 
//return the fitness value   for member i**

float sumFitness = 0.0f;
for (int i=0; i < nmembers; i++)
    sumFitness += fitness(i);

// Get a floating point number in the interval 0.0 ... sumFitness**
float randomNumber = (float(rand() % 10000) / 9999.0f) * sumFitness;

// Translate this number to the corresponding member**
int memberID=0;
float partialSum=0.0f;

while (randomNumber > partialSum)
{
   partialSum += fitness(memberID);
   memberID++;
} 

**// We have just found the member of the population using the roulette algorithm**
**// It is stored in the "memberID" variable**
**// Repeat this procedure as many times to find random members of the population**

Answer 6

Выбор колеса рулетки в MatLab:

TotalFitness=sum(Fitness);
    ProbSelection=zeros(PopLength,1);
    CumProb=zeros(PopLength,1);

    for i=1:PopLength
        ProbSelection(i)=Fitness(i)/TotalFitness;
        if i==1
            CumProb(i)=ProbSelection(i);
        else
            CumProb(i)=CumProb(i-1)+ProbSelection(i);
        end
    end

    SelectInd=rand(PopLength,1);

    for i=1:PopLength
        flag=0;
        for j=1:PopLength
            if(CumProb(j)<SelectInd(i) && CumProb(j+1)>=SelectInd(i))
                SelectedPop(i,1:IndLength)=CurrentPop(j+1,1:IndLength);
                flag=1;
                break;
            end
        end
        if(flag==0)
            SelectedPop(i,1:IndLength)=CurrentPop(1,1:IndLength);
        end
    end

Answer 7

Вот компактная реализация Java, которую я недавно написал для выбора рулетки, надеюсь, полезной.

public static gene rouletteSelection()
{
    float totalScore = 0;
    float runningScore = 0;
    for (gene g : genes)
    {
        totalScore += g.score;
    }

    float rnd = (float) (Math.random() * totalScore);

    for (gene g : genes)
    {   
        if (    rnd>=runningScore &&
                rnd<=runningScore+g.score)
        {
            return g;
        }
        runningScore+=g.score;
    }

    return null;
}

Answer 8

Prof. Трун из Стэнфордской лаборатории ИИ также представил быстрый (er?) Код повторной выборки в python во время своего CS373 Udacity. Результат поиска Google привел к следующей ссылке:

http://www.udacity -forums.com / cs373 / вопросы / 20194 / быстрые передискретизации-алгоритм

Надеюсь, это поможет

Answer 9

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

Чтобы привести пример:

Случайный (сумма) :: Случайный (12) Итерируя по населению, мы проверяем следующее: random

Давайте выберем случайное число 7.

Index   |   Fitness |   Sum |   7 < Sum
0       |   2   |   2       |   false
1       |   3   |   5       |   false
2       |   1   |   6       |   false
3       |   4   |   10      |   true
4       |   2   |   12      |   ...

В этом примере наиболее подходящий (индекс 3) имеет самый высокий процент выбора (33%); поскольку случайное число должно приземлиться только в пределах 6-> 10, и оно будет выбрано.

    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
    }       
    double rand = (((double)rand() / (double)RAND_MAX) * sum);
    sum = 0;
    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
        if (rand < sum) {
            //breed i
            break;
        }
    }

Answer 10

Это расширение массива Swift 4 реализует взвешенный случайный выбор, a.k.a Выбор рулетки из ее элементов:

public extension Array where Element == Double {

    /// Consider the elements as weight values and return a weighted random selection by index.
    /// a.k.a Roulette wheel selection.
    func weightedRandomIndex() -> Int {
        var selected: Int = 0
        var total: Double = self[0]

        for i in 1..<self.count { // start at 1
            total += self[i]
            if( Double.random(in: 0...1) <= (self[i] / total)) { selected = i }
        }

        return selected
    }
}

Например, учитывая массив из двух элементов:

[0.9, 0.1]

weightedRandomIndex() вернет ноль 90% времени и один 10% времени.

Вот более полный тест:

let weights = [0.1, 0.7, 0.1, 0.1]
var results = [Int:Int]()
let n = 100000
for _ in 0..<n {
    let index = weights.weightedRandomIndex()
    results[index] = results[index, default:0] + 1
}
for (key,val) in results.sorted(by: { a,b in weights[a.key] < weights[b.key] }) {
    print(weights[key], Double(val)/Double(n))
}

выход:

0.1 0.09906
0.1 0.10126
0.1 0.09876
0.7 0.70092

Этот ответ в основном совпадает с ответом Эндрю Мао: https://stackoverflow.com/a/15582983/74975