Построение рейтинга с генетическим алгоритмом,

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

Я добавлю некоторую информацию о синтаксических элементах - как вы делаете кроссовер и/или мутацию таким образом, чтобы это имело смысл. Очевидно, как вы заметили с параллелью с TSP, у вас есть проблема с перестановкой. Поэтому, если вы хотите использовать ГА, естественное представление возможных решений — это просто упорядоченный список ваших точек, избегающий повторения, то есть перестановки.

Одной из таких задач перестановки является TSP, и существует ряд операторов кроссовера (например, Кроссовер Edge Assembly), который можно взять из алгоритмов TSP и использовать напрямую. Однако, я думаю, у вас будут проблемы с этим подходом. По сути, проблема вот в чем: в TSP важным качеством решений является смежность. То есть abcd имеет ту же пригодность, что и cdab, потому что это тот же тур, только начинающийся и заканчивающийся в другом городе. В вашем примере абсолютная позиция гораздо важнее, чем понятие относительной позиции. abcd в некотором смысле означает, что a — лучшая точка — важно, чтобы она была первой в списке.

Главное, что вам нужно сделать, чтобы получить эффективный оператор кроссовера, — это учесть, какие свойства есть у родителей, которые делают их хорошими, и попытаться извлечь и скомбинировать именно эти свойства. Ник Рэдклифф назвал это "уважительной рекомбинацией" (обратите внимание, что статья довольно старая, и теория теперь понимается немного по-другому, но принцип здравый). Взяв оператора, разработанного TSP, и применив его к своей проблеме, вы в конечном итоге получите потомство, которое попытается сохранить нерелевантную информацию от родителей.

В идеале вам нужен оператор, который пытается сохранить абсолютную позицию в строке. Лучший из известных мне навскидку известен как Cycle Crossover (CX). Мне не хватает хорошей ссылки, но я могу указать вам на некоторый код, в котором я реализовал это как часть своей дипломной работы. Основную идею CX довольно сложно описать, и ее гораздо легче увидеть в действии. Возьмите следующие два пункта:

abcdefgh
cfhgedba

1. Выберите начальную точку в родительском элементе 1 случайным образом. Для простоты я просто начну с позиции 0 с «а».

2. Теперь перейдите прямо к родителю 2 и посмотрите на значение там (в данном случае «c»).

3. Теперь ищем «c» в родительском элементе 1. Мы находим его в позиции 2.

4. Теперь снова опуститесь прямо вниз и обратите внимание на букву «h» в родительском элементе 2, позиция 2.

5. Снова найдите этот «h» в родительском элементе 1, найденном в позиции 7.

6. Опуститесь прямо вниз и обратите внимание на букву «а» в родительском элементе 2.

7. В этот момент обратите внимание, что если мы ищем «а» в родительском, мы достигаем позиции, в которой мы уже были. Продолжая прошлое, это будет просто цикл. На самом деле, мы называем последовательность позиций, которые мы посетили (0, 2, 7), «циклом». Обратите внимание, что мы можем просто поменять местами значения в этих позициях между родителями как группой, и оба родителя сохранят свойство перестановки, потому что у нас есть одни и те же три значения в каждой позиции цикла для обоих родителей, только в разном порядке.

8. Произвести перестановку позиций, входящих в цикл.

Обратите внимание, что это только один цикл. Затем вы повторяете этот процесс, каждый раз начиная с новой (непосещенной) позиции, пока все позиции не будут включены в цикл. После одной итерации, описанной в предыдущих шагах, вы получите следующие строки (где «X» обозначает позицию в цикле, где значения были заменены между родительскими элементами.

cbhdefga
afcgedbh
X X    X

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

Код, который я связал со своей учетной записью на github, будет тесно связан с моей собственной метаэвристической структурой, но я думаю, что это достаточно простая задача — извлечь базовый алгоритм из кода и адаптировать его для вашей собственной системы.

Обратите внимание, что вы можете получить довольно много, если сделаете что-то более индивидуальное для вашего конкретного домена. Я думаю, что что-то вроде CX станет лучшим алгоритмом черного ящика, чем что-то, основанное на операторе TSP, но черные ящики обычно используются в крайнем случае. Предложения других людей могут привести вас к лучшему общему алгоритму.

Я работал над несколько похожей проблемой ранжирования и следовал методике, подобной той, что я описываю ниже. Это работает для вас:

Предположим, что неизвестное value объекта отличается от вашей оценки посредством некоторого распределения, скажем, нормального распределения. Интерпретируйте ваши утверждения о ранжировании, такие как a > b, 0.9, как утверждение «Значение a лежит в 90%-м процентиле распределения с центром в b».

Для каждого утверждения:

def realArrival = calculate a's location on a distribution centered on b
def arrivalGap = | realArrival - expectedArrival | 
def fitness = Σ arrivalGap

Фитнес-функция MIN(fitness)

FWIW, моя проблема на самом деле была проблемой упаковки в корзину, где эквивалентом ваших утверждений о «ранге» были рейтинги, предоставленные пользователями (1, 2, 3 и т. д.). Так что не совсем TSP, а NP-Hard. OTOH, bin-packing имеет псевдополиномиальное решение, пропорциональное допустимой ошибке, что я в конечном итоге и использовал. Я не совсем уверен, что это сработает с вашими заявлениями о вероятностном ранжировании.

Какая интересная проблема! Насколько я понимаю, вы действительно спрашиваете:

«Для взвешенного ориентированного графа, где каждый вес ребра в графе представляет вероятность того, что дуга нарисована в правильном направлении, вернуть полную последовательность узлов с максимальной вероятностью быть топологическим видом графа».

Таким образом, если ваш граф имеет N ребер, существует 2 ^ N графов с различной вероятностью, причем некоторые порядки появляются более чем в одном графе.

Я не знаю, поможет ли это (очень краткие поиски в Google не просветили меня, но, возможно, вы добьетесь большего успеха с большей настойчивостью), но я думаю, что поиск «топологической сортировки» в сочетании с любым из «вероятностных» , "случайный", "шум" или "ошибка" (поскольку веса ребер можно рассматривать как фактор надежности).

Однако я сильно сомневаюсь в вашем утверждении в вашем примере, что P (a> c) не нужен. Вы лучше знаете свое прикладное пространство, но мне кажется, что указание P(a>c) = 0,99 даст другую пригодность для f(abc), чем указание P(a>c) = 0,01.

Возможно, вы также захотите добавить «Байесовский», поскольку вы можете начать выводить значения для (в вашем примере) P (a> c) с учетом ваших условий и гипотетических решений. Проблема в том, что «топологическая сортировка» и «байесовский подход» дадут вам целую кучу хитов, связанных с цепями Маркова и задачами решения Маркова, которые могут быть полезными, а могут и не быть.