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

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

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

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

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

SUS(  Население  ,  N  )     F  := общая приспособленность  популяции      N  := количество потомков, которое необходимо сохранить     P  := расстояние между указателями (  F  /  N  )     Start  := случайное число от 0 до  P      Указатели  := [  Start  +  i  *  P  |  я   в  [0..(  N  -1)]]     вернуть  RWS(  Население  ,  Указатели  )RWS(  Население  ,  Очки  )     Держите  = []     для   P   в   точках          I  := 0         в то время как  сумма приспособленности  населения  [0..  I  ] <  P              I  ++        добавить  население  [  I  ] в  Keep      return   Keep

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

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

См. также

Ссылки

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

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

[1]