Я решаю задачу Static Flow-Shop Scheduling, я рассмотрел 10 задач и 3 машины. в перестановке я сталкиваюсь со многими возможными последовательностями, через которые задачи должны проходить машины. теперь я рассматриваю следующие две последовательности, и я хотел бы, чтобы они пересекались, чтобы получить неповторяющиеся дочерние хромосомы.
первая последовательность = T3 T2 T5 T6 T9 T1 T4 T7 T8 T10
вторая последовательность = T3 T2 T6 T8 T1 T5 T4 T7 T9 T10
теперь, как сделать дочернюю последовательность, чтобы в ней не было повторений, и все задачи присутствовали и в дочерней последовательности.
Ответ 1 · рейтинг 1 · Patrick Trentin
Ваш вопрос не содержит какой-либо код для проверки, поэтому я делаю вывод, что для этого вам нужна общая идея.
Возможное решение:
Это был бы канонический подход для перехода на основе позиции. Гены в одном и том же положении у обоих родителей не перемещаются, тогда как гены, занимающие разные положения, обмениваются друг с другом с двухэтапным переходом:
клон: создать дочернюю копию c1 p1 и c2 копию p2
срез: вычислить набор индексов, для которых c1 и c2 имеют разные значения в одной и той же позиции.
рандомизировать: выбрать случайный idx из этого набора и удалить его из набора
swap: выберите случайный индекс idx в этом наборе: если v1 находится в позиции idx в c1 и v2 находится в позиции idx в c2, поменяйте местами значения так, чтобы v1 теперь находится в позиции idx в c2, а v2 находится в позиции idx в c1
компенсировать: найти индекс idy s.t. v2 находится на позиции idy в p1 и индексе idz s.t. v1 находится в позиции idz в p2 и компенсирует операцию обмена так, что теперь v1 находится в позиции idy в c1 и v2 находится на позиции idz в c2. Удалите как idy, так и idz из набора индексов точек 2/3.
повторить: с вероятностью p вернуться к шагу 3.
Пример:
// idx = 8, indexes start from 0
|3 2| 9 6 5 8 |4 7| 1 |10| // c1
/ |
|3 2| 6 1 8 9 |4 7| 5 |10| // c2
=
|3 2| 9 6 1 8 |4 7| 5 |10| // c1
|3 2| 6 5 8 9 |4 7| 1 |10| // c2
Соображения:
Как видите, кроссовер вырождается в управляемую мутацию, и это происходит из-за ограничения, заключающегося в том, чтобы не вводить повторы в ваш генетический код. Тем не менее, это все же отличается от мутации, так как последняя также влияет на гены, которые находятся в одном и том же положении у обоих родителей.
