Стохастическая универсальная выборка ( SUS ) - это метод, используемый в генетических алгоритмах для выбора потенциально полезных решений для рекомбинации. Его представил Джеймс Бейкер. [1]
SUS - это разработка метода пропорционального отбора по фитнесу (FPS), который не демонстрирует предвзятости и минимального разброса. Если FPS выбирает несколько решений из совокупности путем повторной случайной выборки, SUS использует одно случайное значение для выборки всех решений, выбирая их через равные промежутки времени . Это дает возможность выбора более слабым членам населения (в зависимости от их физической формы).
FPS может иметь плохую производительность, когда член популяции имеет действительно большую физическую форму по сравнению с другими членами. Используя гребенчатую линейку, SUS начинает с небольшого случайного числа и выбирает следующих кандидатов из остальной части населения, не позволяя наиболее приспособленным членам заполнять пространство кандидатов.
Описанный как алгоритм, псевдокод для SUS выглядит так:
SUS ( Население , N ) F : = общая приспособленность популяции N : = количество потомков, которые нужно сохранить P : = расстояние между указателями ( F / N ) Начало : = случайное число между 0 и P Указатели : = [ Начало + i * P | я в [0 .. ( N -1)]] return RWS ( Население , указатели )RWS ( Population , Points ) Keep = [] для P в точках i : = 0, в то время как сумма пригодности для населения [ 0 .. i] < P i ++ добавить Population [i] в Keep return Keep
Где Population [0 .. i] - это набор лиц с индексом массива от 0 до (включительно) i.
Здесь RWS () описывает основную часть отбора пригодности пропорционального (также известный как «рулетка выбор колес») - в истинной пригодности пропорционального отборе Параметр Очки всегда (отсортировано) список случайных чисел от 0 до F . Вышеупомянутый алгоритм предназначен для иллюстрации, а не канонического характера.
См. Также [ править ]
Ссылки [ править ]
- ^ Бейкер, Джеймс Э. (1987). «Снижение смещения и неэффективности алгоритма выбора». Труды Второй Международной конференции по генетическим алгоритмам и их применению . Хиллсдейл, Нью-Джерси: L. Erlbaum Associates: 14–21.
