Применение переборных алгоритмов в рамках задачи оптимизации транспортной логистики. Задачи применения генетических алгоритмов. Особенности работы операторов скрещивания. Способы решения проблемы перекрестного скрещивания в задаче коммивояжера.
Аннотация к работе
ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА К РЕШЕНИЮ ЗАДАЧИ КОММИВОЯЖЕРАС возрастанием количества точек для развоза грузов переборные алгоритмы хотя и продолжают выдавать оптимальные результаты расчета, но делают это слишком медленно. В рамках этой задачи (оптимизации транспортной логистики) предполагается применение как переборных алгоритмов, таких как метод ветвей и границ, метод ближайшего соседа, так и введение эвристических алгоритмов (генетического алгоритма, алгоритма муравья, отжига), а также их комбинаций. Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Из полученного множества решений («поколения») с учетом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными) для последующего скрещивания. Работа операторов скрещивания: Одноточечное скрещивание: случайным образом выбираются точки разрыва родительских хромосом, которые потом «склеиваются» для получения потомства.