(Назад)
(Cкачать работу)температуры одновременно уменьшается вероятность. Стоит заметить, что переход в состояние с большей энергией, не всегда оказывается отрицательное воздействие, так как он приводит к нахождению состояния с меньшей энергией, чем начальная. С точки зрения задачи коммивояжера алгоритм принимает следующий вид:
· Задается число итераций (температура) и случайное начальное решение;
· Случайным образом меняются местами две точки;
· Сравниваются длины старого и нового путей. Во время сравнения учитывается разницанового пути и текущего с учетом количества итераций. Чем меньше число итераций, тем больше вероятность принять текущий путьдля сравнения его с последующим на новой итерации;
· Пройдя все итерации, последний найденный путь считается наилучшим;
Главным недостатком данного алгоритма является, то, что в «холодном» состоянии алгоритм становится жадным, а значит, за горячую фазу он должен успеть попасть в ту область, где локальный максимум окажется решением задачи. Поэтому каждый раз необходима адаптация параметров под конкретную задачу, зависимость качества решения от времени его получения.
Генетический алгоритм.Подход генетического алгоритма начинается с генерации популяции (множества маршрутов), затем к элементам(особям) популяции применяются операции скрещивания и мутации [5]. Скрещивание из выбранных маршрутов формирует дочерний. Скрещивание бывает двух видов:
. Частично отображаемое скрещивание. Случайным образом находятся две точки разрыва, далее при формировании потомков производится обмен частей находящихся между двумя этими, затем расставляются оставшиеся позиции от соответствующих хромосом по порядку до возникновения конфликта, после чего записывается номер соседней хромосомы. Алгоритм повторяется до тех пор, пока все конфликты не будут решены;
. В циклическом скрещивании, формирование потомка идет по шагам. Сначала в самую верхнюю свободную позицию ставится элемент из самой верхней позиции родителя, который не вызывал бы конфликт с уже проставленными элементами, затем в самую нижнюю свободную позицию ставится элемент из самой нижней позиции другого родителя, который, в свою очередь, не вызывал бы конфликт с уже проставленными в ребёнке элементами. Так продолжается до тех пор, пока не будут заняты все позиции;
Разнообразие скрещивания необходимо для того чтобы, из-за однотипности популяции не выделялся один возможный генотип представляющий собой локальный максимум. Это приводит к тому, что все остальные элементы популяции проигрывают ему отбор, в результате алгоритм зависает на локальном максимуме и выдает решение далекое от оптимального.
Мутация в свою очередь меняет местами участки внутри ранее созданного дочернего маршрута.После чего происходит отсечение худших маршрутов и выполняется следующая итерация. Чем больше количество итераций, тем ближе решение задачи к оптимальному решению.
Генетический алгоритм выделяется в основномсамым быстрым нахождением приближенного маршрута в сравнении с другими алгоритмами, например,на оптимизацию пути через 200 точек приходится около одной минуты, в то время как муравьиный алгоритм затрачивает на такое же количество точек 7 минут. Поэтому данный алгоритм целесообразно использовать для расчета
Похожие работы
Интересная статья: Основы написания курсовой работы