Отбор выжившей популяции в генетическом алгоритме "избирателя"
Я работал над генетическим алгоритмом, в котором есть популяция, состоящая из людей с цветом и предпочтением. Предпочтение и цвет происходят из небольшого числа конечных состояний, вероятно, около 4 или 5. (пример: 1|1, 5|2, 3|3 и т. Д.)
Каждый человек голосует за свои предпочтения, что помогает тем людям, у которых этот голос является их цветом.
Моя текущая идея состоит в том, чтобы циклически проходить через каждого человека и вычислять вероятность его выживания, основываясь на количестве голосов и т. Д., А затем бросить кубик, чтобы увидеть, живут ли они.
В настоящее время я делаю это так, что если v[x] представляет процент голосов за цвет x, индивидуальный k с цветом c имеет v[c] шанс выжить. Однако это означает, что если есть равные числа всех 5 типов (a | a) особей, 4/5 из них погибают, и это не хорошо.
Есть ли у кого-нибудь представление о методе случайности, который я мог бы использовать, чтобы определить шанс выжить? Например, алгоритм, который для v голосует за c, v люди с цветом c выжить (в среднем по статистике).
2 ответа
Присвойте свою пригодность (вероятность выживания в вашем случае) каждому человеку, как есть, затем сортируйте их по убыванию пригодности и используйте двоичный выбор турнира или что-то подобное, чтобы выбрать другую популяцию выбранного размера.
Ну, вы можете взвесить вероятности в соответствии со значением, возвращенным путем передачи каждого члена совокупности в функцию стоимости.
Это кажется мне самым простым способом, совместимым с генетической метаэвристикой.
Однако более распространенным является деление текущей совокупности на сегменты на основе значения, возвращаемого при передаче их функции стоимости.
Так, например, если каждое поколение состоит из 100 членов, то верхние N (N это просто пользовательский параметр, часто что-то около 5-10% от общего числа) членов с результатом функции с наименьшей стоимостью) переносятся на следующее поколение, как они есть (элитарность). Возможно, это то, что вы подразумеваете под "выжить". Если это так, то опять же, эти "выжившие" определяются путем ранжирования членов населения в соответствии со значением функции стоимости и выбора этих членов выше определенной вами константы доли элитарности. Остальные (большинство) следующего поколения создаются либо путем мутации, либо путем кроссинговера.
мутация:
# one member of the current population:
[4, 5, 1, 7, 4, 2, 8, 9]
# small random change in one member of prior generation, to create mutant that is
# a member of the next generation
[4, 9, 1, 7, 4, 2, 8, 9]
кроссовер:
# two of the 'top' members of the current generation
[4, 5, 1, 7, 4, 2, 8, 9]
[2, 3, 6, 9, 2, 1, 6, 4]
# offpsring is a member of the next generation
[4, 5, 1, 7, 2, 1, 6, 4]