Метод имитации отжига задача коммивояжера python

Окончательный результат выполнения выглядит следующим образом

Диаграмма пути выглядит следующим образом:

Теперь мы пытаемся улучшить алгоритм SA:

Сначала мы изменим начальный путь, чтобы начальный путь также генерировался случайным образом:

paths=list(np.random.permutation(paths))

Затем мы улучшаем функцию соседства и устанавливаем функцию, чтобы поменять местами несколько пар узлов в соответствии с температурой, чтобы увеличить вероятность пересечения целого.

for j in range(int(T0/500)): a=0 b=0 while a==b: a=np.random.randint(0,len(paths)) b=np.random.randint(0,len(paths)) te=newPaths[a] newPaths[a]=newPaths[b] newPaths[b]=te newLength=utils.CalLength(citys,newPaths,start,end)

Тогда мы можем установить процесс прогрева, то есть есть определенная вероятность того, что температура снова поднимется, чтобы избежать застоя алгоритма на локальном минимуме. Мы устанавливаем вероятность повторного нагрева до 0,15.

back=np.random.uniform(low=0,high=1) if back>=0.85: T=T*2 continue

В итоге наша модель SA выглядит следующим образом:

paths=list(np.random.permutation(paths)) while T>Tmin: for i in range(k): newPaths=paths for j in range(int(T0/500)): a=0 b=0 while a==b: a=np.random.randint(0,len(paths)) b=np.random.randint(0,len(paths)) te=newPaths[a] newPaths[a]=newPaths[b] newPaths[b]=te newLength=utils.CalLength(citys,newPaths,start,end) if newLength=0.85: T=T*2 continue t+=1 print t T=T0/(1+t) print length

Выполните алгоритм и получите результат:

Источник

Метод имитации отжига в Python

Метод имитации отжига является эвристическим алгоритмом оптимизации, вдохновленным процессом отжига в металлургии. Этот метод используется для решения задач оптимизации, таких как коммивояжер, упаковка и другие.

Основные идеи метода имитации отжига

1. Генерация начального решения
2. Оценка качества решения
3. Изменение текущего решения
4. Принятие или отклонение нового решения на основе вероятности
5. Повторение шагов 3-4 до достижения критерия остановки

Реализация метода имитации отжига на Python

import random import math def simulated_annealing(init_state, eval_func, perturb_func, T, cooling_func, max_iter): state = init_state state_eval = eval_func(state) best_state = state best_eval = state_eval for i in range(max_iter): T = cooling_func(T, i) if T == 0: break new_state = perturb_func(state) new_eval = eval_func(new_state) delta_eval = new_eval - state_eval if delta_eval < 0 or random.random() < math.exp(-delta_eval / T): state = new_state state_eval = new_eval if state_eval < best_eval: best_state = state best_eval = state_eval return best_state, best_eval

Пример применения метода имитации отжига

Рассмотрим пример решения задачи коммивояжера с использованием метода имитации отжига:

import numpy as np def distance(city1, city2): return np.linalg.norm(city1 - city2) def total_distance(cities, tour): dist = 0 for i in range(len(tour) - 1): dist += distance(cities[tour[i]], cities[tour[i + 1]]) dist += distance(cities[tour[-1]], cities[tour[0]]) return dist def perturb_tour(tour): i, j = random.sample(range(len(tour)), 2) new_tour = tour[:] new_tour[i], new_tour[j] = new_tour[j], new_tour[i] return new_tour def cooling_schedule(T, i): return 0.99 * T cities = np.random.rand(10, 2) init_tour = list(range(len(cities))) best_tour, best_dist = simulated_annealing(init_tour, lambda tour: total_distance(cities, tour), perturb_tour, T=100, cooling_func=cooling_schedule, max_iter=10000) print("Лучший маршрут:", best_tour) print("Расстояние:", best_dist) 

Заключение

Метод имитации отжига является универсальным подходом к решению задач оптимизации. В данной статье была представлена реализация этого метода на языке программирования Python, а также пример его применения для решения задачи коммивояжера. Метод имитации отжига может быть адаптирован для решения других задач оптимизации с помощью соответствующих функций оценки и возмущения.

Источник

Метод отжига в Python

Метод отжига, также известный как алгоритм имитации отжига, является эвристическим алгоритмом оптимизации, основанным на метафоре процесса отжига металла. В контексте Python, этот метод можно использовать для решения задач оптимизации.

Принцип работы метода отжига

1. Инициализация начального состояния
2. Выбор случайного соседнего состояния
3. Вычисление изменения энергии между текущим и соседним состоянием
4. Принятие или отклонение нового состояния на основе изменения энергии и температуры
5. Понижение температуры и повторение процесса с шага 2 до выполнения условий остановки

Пример реализации алгоритма отжига на Python

import random import math def simulated_annealing(cost_function, initial_state, temperature, cooling_rate, stopping_temperature): current_state = initial_state current_cost = cost_function(current_state) while temperature > stopping_temperature: neighbour_state = generate_neighbour(current_state) neighbour_cost = cost_function(neighbour_state) delta_cost = neighbour_cost - current_cost acceptance_probability = math.exp(-delta_cost / temperature) if delta_cost < 0 or random.random() < acceptance_probability: current_state, current_cost = neighbour_state, neighbour_cost temperature *= cooling_rate return current_state def generate_neighbour(state): # Реализация функции генерации соседнего состояния pass def cost_function(state): # Реализация функции оценки стоимости состояния pass

В приведенном выше коде функции generate_neighbour и cost_function являются заглушками, которые необходимо заменить на реализации, соответствующие вашей конкретной задаче оптимизации.

Заключение

Метод отжига - это эффективный алгоритм оптимизации, который можно использовать для решения различных задач, таких как задача коммивояжера, оптимизациярасписаний и размещение элементов. Реализация алгоритма отжига на языке Python довольно проста и понятна. Важно выбрать подходящую функцию стоимости и функцию генерации соседних состояний, чтобы алгоритм работал эффективно для вашей конкретной задачи оптимизации.

Преимущества и недостатки метода отжига

Метод отжига имеет следующие преимущества:

• Простота реализации
• Способность находить глобальные минимумы
• Хорошая работа с задачами большой размерности и сложностью

Однако, существуют также и недостатки:

• Не гарантирует нахождение оптимального решения
• Зависимость от правильного выбора параметров алгоритма (начальная температура, скорость охлаждения)
• Требует больше времени на выполнение, чем некоторые другие оптимизационные алгоритмы

Несмотря на недостатки, метод отжига остается популярным и полезным инструментом для решения сложных задач оптимизации в Python и других языках программирования.

Источник