Поскольку вы попросили в комментарии сделать это ответом, я позволил себе обобщить и мои предыдущие ответы, так что все это в одном месте. Ответ на конкретный вопрос «что такое штрафной термин» находится в пункте № 3 ниже.
Принцип работы стандартного генетического алгоритма заключается в том, что каждая «хромосома» является полным решением проблемы. В вашем случае заказ на работу будет представлен. Путаница, я думаю, сводится к тому, что, поскольку индивидуальный вклад в физическую форму, вносимый конкретной работой в этом графике, меняется в зависимости от остальной части графика, вам необходимо что-то «динамичное». Это не совсем так. С точки зрения ГА, единственное, что имеет пригодность, - это полное решение. Таким образом, динамическая проблема - это проблема, при которой пригодность всего графика может меняться со временем. Возвращаясь к TSP, динамической проблемой будет та, в которой путешествующие города в порядке A, B, C, D, а затем E фактически имеют разное расстояние каждый раз, когда вы пытаетесь это сделать. Несмотря на то, что стоимость тура через B зависит от того, какие города прибывают до и после B в туре, как только вы решите, что затраты статичны, и, поскольку GA всегда получает расходы только на целые туры, все, что он знает, это то, что [ A, B, C, D, E] имеет постоянную приспособленность. Динамический обман не требуется.
Теперь, ваш второй вопрос был о том, как справиться с такими ограничениями, как, например, для примера TSP, что, если вам нужно убедиться, что продавец прибудет в Париж к определенному времени? Как правило, есть три способа справиться с этим.
Никогда не позволяйте генерировать решение, в которое он не попадет до 2:00. Иногда это легко, а иногда очень сложно. Например, если ограничение было «он не может начать с города X», то довольно просто просто не генерировать решения, которые не начинаются с X. Часто, однако, просто найти правильные решения может быть сложно, и поэтому этот подход не действительно работает.
Разрешить нарушение ограничений, но исправить их позже. В примере TSP вы позволяете кроссоверу и мутации производить любой возможный тур, но затем просматриваете его, чтобы увидеть, не слишком ли поздно он добирается до Парижа. Если это так, поменяйте местами Париж с более ранним городом в туре. Опять же, иногда бывает сложно найти хороший способ исправить нарушения.
Наказать пригодность невыполнимого решения. Идея в том, что даже если я не смогу помешать ему приехать в Париж слишком поздно, и я не смогу это исправить, если он это сделает, я, по крайней мере, могу произвольно ухудшить физическую форму. Для TSP фитнес - это продолжительность тура. Таким образом, вы можете сказать, что если поездка приведет его в Париж слишком поздно, пригодность будет продолжительностью тура + 100. Это позволит решению остаться в народе (в противном случае оно может быть очень хорошим, поэтому вы хотите, чтобы у него был шанс передать некоторые из его генов), но вы уменьшаете вероятность его выбора, потому что ваши методы отбора и замены выбирают людей с лучшими показателями пригодности.
В случае вашей проблемы с JSP, как правило, вы стремитесь минимизировать время выполнения. Те же три варианта доступны для вас, если у вас есть некоторые ограничения. Но из того, что я могу сказать, у вас действительно нет таких ограничений. Я думаю, что вы пытаетесь внедрить слишком много знаний в процесс, вместо того, чтобы позволить эволюционному алгоритму придумать его самостоятельно. То есть вам не обязательно беспокоиться о том, чтобы сказать ГА, что некоторые рабочие места лучше, чем другие. Вы просто назначаете более высокую пригодность лучшим и позволяете процессу сходиться.
Тем не менее, ввод информации, подобной этой, часто очень полезен, но сначала нужно хорошо понять основной алгоритм. Допустим, мы знаем, что для TSP более вероятно, что хорошее решение соединит города, которые находятся близко друг к другу. То, как я использовал бы эту информацию внутри GA, состояло бы в том, чтобы генерировать случайные решения неравномерно (возможно, с жадной эвристикой). Я мог бы также заменить стандартные алгоритмы кроссовера и мутации чем-то настроенным. Мутация, как правило, легче сделать это, чем кроссовер. Чтобы изменить решение TSP, я мог бы выбрать два соединенных города, разорвать соединение, а затем искать способ их повторного соединения, которое было «ближе». То есть, если тур [A, B, C, D, E, F, G, H], я мог бы выбрать край [B, C] случайным образом, а затем искать другой край, возможно, [F, G ], так что когда я соединил их перекрестками, чтобы получить [A, B, G, D, E, F, C, H], общая длина тура была ниже. Я мог бы даже расширить эту мутацию за пределы одного шага - создать цикл, который будет пытаться разорвать и заново соединить края, пока он не сможет найти более короткий тур. Это приводит к тому, что обычно называют гибридным GA, потому что это GA, гибридизированный с локальным поиском; иногда также называется меметическим алгоритмом. Такого рода алгоритмы обычно превосходят GA черного ящика, потому что вы даете алгоритму «подсказки», чтобы склонить его к попыткам сделать то, что, как вы ожидаете, будет хорошим.
Я думаю, что эта идея меметического алгоритма довольно близка к тому, что вы затрагивали в своем первоначальном вопросе о том, как справиться с тем фактом, что вклад в фитнес от конкретной работы зависит от того, где находятся другие рабочие места. график. Единственным камнем преткновения является то, что вам немного не повезло в том, что несколько разумная идея думать об этом как о «динамическом» вводит вас в заблуждение, так как «динамический» на самом деле означает здесь нечто совершенно иное.
Таким образом, в вашей проблеме нет ничего "динамического", поэтому то, что люди делают с GA для динамических задач, будет совершенно бесполезным. Стандартный GA будет работать без каких-либо хитростей. Однако идея использования имеющейся у вас информации о том, какие графики работают лучше , может быть внедрена в генетические операторы и, вероятно, приведет к значительно лучшему общему алгоритму.