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

Пример SUS

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

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

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

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

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

Где Население [0..я] - это набор лиц с индексом массива от 0 до i (включительно).

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

Смотрите также

Рекомендации

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