Стохастическая универсальная выборка

Стохастическая универсальная выборка ( SUS ) — это метод, используемый в генетических алгоритмах для выбора потенциально полезных решений для рекомбинации. Его представил Джеймс Бейкер. ^[1]

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

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

Описанный в виде алгоритма псевдокод для SUS выглядит так:

SUS(Population, N)
    F := total fitness of Population
    N := number of offspring to keep
    P := distance between the pointers (F/N)
    Start := random number between 0 and P
    Pointers := [Start + i*P | i in [0..(N-1)]]
    return RWS(Population,Pointers)

RWS(Population, Points)
    Keep = []
    for P in Points
        I := 0
        while fitness sum of Population[0..I] < P
            I++
        add Population[I] to Keep
    return Keep

Где Population[0..I] - это набор людей с индексом массива от 0 до (включительно) Я.

Здесь RWS() описывает основную часть пропорционального выбора по приспособленности (также известного как « выбор колеса рулетки ») – в истинном пропорциональном выборе по приспособленности параметр Очки всегда представляют собой (отсортированный) список случайных чисел от 0 до Ф. Приведенный выше алгоритм носит иллюстративный, а не канонический характер.

См. также

Ссылки

^ Бейкер, Джеймс Э. (1987). «Уменьшение предвзятости и неэффективности алгоритма выбора». Материалы второй международной конференции по генетическим алгоритмам и их применению . Хиллсдейл, Нью-Джерси: L. Erlbaum Associates: 14–21.

[baker-1] Бейкер, Джеймс Э. (1987). «Уменьшение предвзятости и неэффективности алгоритма выбора». Материалы второй международной конференции по генетическим алгоритмам и их применению . Хиллсдейл, Нью-Джерси: L. Erlbaum Associates: 14–21.

[1]