Вопрос или проблема
У меня есть генетический алгоритм для задачи маршрутизации транспортного средства с временными окнами, и мне нужно реализовать определенные модификации. Я не уверен, какое будет лучшее представление хромосом.
У меня есть задачи, которые можно разделить на 3 подзадачи с определенными упорядоченными временными окнами, их нужно выполнять в порядке, и все 3 (они представляют сбор определенных товаров на складе, доставку их и возврат упаковки на другой склад). В части алгоритма, отвечающей за кроссовер, эти задачи комбинируются и оцениваются. Их необходимо обрабатывать в порядке в соответствии с их номером задачи, т.е. комбинация “A1, B1, B2, A2, B3, A3” является правильной, но “A1, B2, A2, B3, A3, B1” или “A1, A2, B1” – нет. Проблема в том, что я не знаю, как обеспечить соблюдение порядка событий. Как я могу отразить это требование в хромосомах? Или, где в алгоритме мне следует учитывать это требование?
В предыдущей версии алгоритма мы использовали только целую задачу A или B без различия подзадач, что теперь недостаточно. Я относительно новичок в генетических алгоритмах, поэтому извините, если это что-то очевидное.
Учитывая, что вы хотите максимизировать функцию приспособленности $\phi:\Bbb{R}^n\rightarrow\Bbb{R}$, сделайте $\phi(\vec{x})=-\infty\ \forall \vec{x}\ \notin X$, где область допустимых решений $X\subset \Bbb{R}^n$. Затем вы можете инициализировать популяцию $P=\{p\ |\ p\in X\}$ и если ГА попробует любое $p\notin X$, это решение будет устранено. Это заставляет ГА “учиться” области допустимых решений.
Ответ или решение
Оптимальное представление хромосом в генетическом алгоритме для задачи маршрутизации транспортных средств с временными окнами (VRPTW)
Введение
При разработке генетического алгоритма (ГА) для решения задачи маршрутизации транспортных средств с временными окнами важно правильно выбрать представление хромосом, чтобы соблюдать порядок выполнения подзадач и выполнять условия временных окон. В данной статье мы рассмотрим, как оптимально организовать представление хромосом для вашего сценария.
Понимание задачи
Вы имеете дело с задачами, разбитыми на три подзадачи, каждая из которых должна выполняться в строгом порядке, например, "A1, B1, B2, A2, B3, A3". Необходимо обеспечить, чтобы ГА не генерировал недопустимые последовательности, такие как "A1, B2, A2, B3, A3, B1", где подзадачи выполняются в неверной последовательности.
Представление хромосом
-
Списковое представление с метаданными:
Рекомендуется использовать векторное представление хромосом, где каждая хромосома представлена в виде списка, в котором содержится информация о подзадачах (например, "A1", "A2", "A3", "B1", "B2", "B3"). В этом списке следует также хранить информацию о приоритете задач или временных рамках выполнения, которые ограничивают порядок их следования. -
Использование специального формата:
Каждый элемент списка можно закодировать с использованием структуры, которая будет содержать:- Название задачи (например, "A1")
- Индекс самой подзадачи
- Временные ограничения (например, время начала и время окончания)
Пример такого представления:
[ {"task": "A", "subtask": 1, "start_time": 0, "end_time": 10}, {"task": "B", "subtask": 1, "start_time": 10, "end_time": 20}, {"task": "B", "subtask": 2, "start_time": 20, "end_time": 30}, ]Это формат позволяет легко добавлять алгоритмы проверки на порядковость при операциях кроссовера и мутации.
-
Контроль за порядком задач:
Чтобы обеспечить корректный порядок выполнения, вы можете использовать алгоритм проверки на наличие дубликатов и нарушения последовательности. Например, в ходе кроссовера можно проверять на наличие "родительских" последовательностей и генерировать потомков только в том случае, если порядок подзадач не нарушен. Если последовательность не соответствует требованиям, она автоматически отвергается, и генерируется другая комбинация. -
Генерация начальной популяции:
Ваша начальная популяция должна формироваться таким образом, чтобы все хромосомы соответствовали требуемому порядку выполнения задач. Это может быть достигнуто путем создания алгоритма, который будет перемешивать подзадачи с соблюдением их порядка. Например, вы можете создать популяцию с 10% допускаемых нарушений, чтобы ГА мог исследовать пространство решений.
Заключение
Корректное представление хромосом в генетическом алгоритме для задачи маршрутизации транспортных средств с временными окнами требует учета последовательности подзадач и временных ограничений. Используя списковое представление с метаданными, вы не только обеспечите соблюдение порядка выполнения, но и создадите более гибкую и устойчивую структуру для кроссоверов и мутаций. Учтите, что алгоритм может быть адаптирован под специфические требования вашей задачи и потенциальные изменения в логистических схемах.