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