Муравьиная система

Муравьиная система

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

Изначально муравьи беспорядочно бродят по окружающей среде. Как только пища найдена, муравей начинает выделять феромоны в окружающую среду. Совершается много поездок между пищей и колонией, и если следовать тому же маршруту к пище, откладываются дополнительные феромоны. Феромоны разлагаются в окружающей среде, поэтому с меньшей вероятностью будут следовать старым методам. Другие муравьи могут обнаружить тот же путь к еде и, в свою очередь, могут следовать по нему, а также откладывать феромоны. Процесс положительной обратной связи направляет все больше и больше муравьев на продуктивные пути, которые, в свою очередь, совершенствуются в процессе использования.

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

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

муравьиная система

где τ_i,j представляет собой феромон для компонента (края в график) (i; j), ρ — коэффициент затухания, m — количество муравьев, а сумма дельт — это сумма 1/S_cost (максимизация стоимости решения) для решений, включающих компонент i,j. Алгоритм показывает это уравнение как эквивалент двухэтапного процесса затухания с последующим обновлением для простоты.

Пошаговое построение вероятностного решения использует как историю (феромоны), так и эвристические данные для конкретной задачи, чтобы постепенно построить решение по частям. Каждый компонент может быть выбран только в том случае, если он еще не был выбран (для большинства комбинаторных задач), а для компонентов, которые могут быть выбраны (при текущем компоненте i), вероятность их выбора определяется следующим образом:

муравьиная система

где η_i,j — максимальный вклад в общую оценку выбора компонента (например, 1/расстояние для задачи коммивояжера), α — эвристический коэффициент, τ_i,j — значение феромона для компонента, β — история коэффициент , а c – набор используемых компонентов.

муравьиная система

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

Коэффициент истории (α) контролирует, насколько история влияет на вероятность выбора компонента, и обычно устанавливается на 1,0. Эвристический коэффициент (β) контролирует количество вклада эвристической информации, относящейся к конкретной задаче, в вероятность выбора компонента и обычно составляет от 2 до 5, например 2,5. Коэффициент затухания (ρ) определяет скорость потери исторической информации и обычно устанавливается равным 0,5. Общее количество муравьев (m) обычно задается количеством проблемных компонентов, например, количеством городов в TSP.

Делиться
ru_RURU
%d такие блоггеры, как: