алгоритм — C ++ Инвертированный взвешенный случайный порядок / случайный

Как сказал @Dukeling, нам нужно больше информации. Как то, как вы интерпретируете и используете шанс выбора.

По крайней мере, в области эволюционного алгоритма, фитнес-масштабирование (или масштабирование вероятности выбора) — значительная тема.

Предположим, вы начали с негодность Гол

B[i] = how badly you don't want to select the i-th item

И цель состоит в том, чтобы рассчитать фитнес/ оценка выбора S[i] который я предполагаю, что вы должны использовать его в колесо рулетки мода.

Как вы говорите, одним из очевидных способов является использование мультипликативного обратного:

S[i] = 1 / B[i]

Однако с этим может быть небольшая проблема.
Такое же количество изменений в B[i] с низким значением имеет гораздо большее влияние, чем такое же количество изменений, когда B[i] уже имеет высокую ценность.

Задай себе вопрос:

Say
B[1] = 1     ->     S[1] = 1
B[2] = 2     ->     S[2] = 0.5
So item 1 is twice times as likely to be selected compared to item 2

But with the same amount of change
B[3] = 1000  ->     S[3] = 0.001
B[4] = 1001  ->     S[4] = 0.000999001
Item 3 is only 1.001 times as likely to be selected compared to item 4

Я просто покажу здесь одну из возможных альтернативных схем.

S[i] = max(B) - B[i] + 1

+ 1 помогает деталь, поэтому ни у одного предмета нет шансов быть выбранным.

Это завершает часть расчета оценки выбора.

---

Далее давайте разберемся, как использовать счет выбора в режиме колеса рулетки.
Предположим, мы решили использовать Противоположное число схема.

B[1] = 1     ->     S[1] = 1001
B[2] = 2     ->     S[2] = 1000
B[3] = 1000  ->     S[3] = 2
B[4] = 1001  ->     S[4] = 1

Затем представьте, что каждое очко в счете соответствует лотерейному билету.
Давайте назначим тикету бегущие идентификаторы.

| Item | Score = #ticket |   ticket ID  |         win chance       |
|   1  |      1001       | 0    to 1000 |  1001/2004 ~ 0.499500998 |
|   2  |      1000       | 1001 to 2000 |  1000/2004 ~ 0.499001996 |
|   3  |         2       | 2001 to 2002 |     2/2004 ~ 0.000998004 |
|   4  |         1       | 2003 to 2003 |     1/2004 ~ 0.000499002 |

Всего билетов 2004 года.

Чтобы сделать выбор, выберите идентификатор выигрышного билета случайным образом, то есть случайный диапазон составляет [0,2004).
Бинарный поиск может быть использован для быстрого поиска того, какому предмету принадлежит выигрышный билет, как вы уже видели в этот вопрос. Что нужно искать с помощью бинарного поиска, так это граница значения идентификатора билета, которые 1001,2001,2003 а не сами баллы.

---

Для сравнения, вот шанс выбора в случае мультипликативный обратный схема используется.

| Item |                    win chance         |
|   1  |           1/1.501999001 ~ 0.665779404 |
|   2  |         0.5/1.501999001 ~ 0.332889702 |
|   3  |       0.001/1.501999001 ~ 0.000665779 |
|   4  | 0.000999001/1.501999001 ~ 0.000665114 |

Вы можете заметить, что в аддитивной обратной схеме 1 единица плохости последовательно соответствует разнице в 0,0005 в вероятности выбора.

В то время как в мультипликативной обратной схеме 1 единица плохости приводит к варьируя разница выбора шанса.