Табу поиск по угловым параметрам

Русские Блоги

Примечания к исследованию машинного обучения (12) Алгоритм поиска табу (поиск табу)

Алгоритм поиска табу (поиск табу)

Краткое изложение идей алгоритма табу-поиска TS.

1. Основа алгоритма запретного поиска: поиск по локальному домену.

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

Это основа табуированного поиска, и алгоритм TS улучшен на нем.

Преимущества: 1. Его легко понять, легко реализовать и он обладает большой универсальностью;

2. Сильные возможности местного развития и высокая скорость конвергенции.

Недостатки: 1. Слабые возможности глобального развития, поиск оптимальных решений возможен только на местном уровне;

2. Результат поиска полностью зависит от соотношения отображения между исходным решением и окрестностью. Чтобы

Анализируя метод восхождения на холм, выдвинулиАлгоритм поиска TS：

Улучшение 1. Принимайте плохие решения.

Улучшение 2: Введение списка табу.

Улучшение 3. Введение долгосрочных и среднесрочных таблиц.

Во-вторых, характеристики алгоритма TS

2. Принцип «только наступать, а не отступать» реализуется через табуированный стол.

3. Не используйте локальную оптимальность в качестве критерия остановки.

4. Правило выбора соседства имитирует функцию памяти человека.

Три, компоненты алгоритма TS

(1) Метод кодирования

Разделите n различных предметов на m групп, коды, которые можно использовать:

а. Последовательное кодирование с разделителем

Используйте натуральные числа 1

n для представления n элементов соответственно, а n чисел плюс n-1 символов деления смешиваются вместе и располагаются случайным образом.

Б. Кодирование натуральными числами

Каждая цифра кода представляет элемент, а значение каждой цифры представляет группу элемента.

(2) Получение исходного решения

даСлучайное начальное решение, Вы также можете заранее использовать другие эвристики и другие алгоритмы, чтобы получить лучшее начальное решение. (Смешанный алгоритм)

(3) Мобильный район

Все ходы, которые могут быть сделаны из текущего решения, составляют окрестность, которую также можно понимать как область, в которую можно попасть за «один шаг» от текущего решения.

(4) Табу-стол

Роль списка табу: предотвращение цикла поиска

(1) Запишите точки, направления или целевые значения, которые были переданы на предыдущих шагах,Без возврата

(2) Таблица динамически обновляется

(3) Длина стола называется размером табу.

Основные показатели табу-таблицы (два показателя)

Объекты табу: те изменяющиеся элементы, которые запрещены в таблице табу.

Длина табу: табу на количество шагов

Табу-объекты (три изменения)

Возьмите само состояние или изменение состояния как запретный объект

Возьмите компонент состояния и изменение компонента как объект табу.

Принять аналогичный контурный подход с изменением целевого значения как запретными объектами

Длина табу: это может быть фиксированная константа (T = c) или она может меняться динамически, и она может меняться в пределах интервала в соответствии с определенным правилом или формулой.

Продолжительность табу слишком мала, как только оно попадает в локальный оптимум, петля не может выйти;

Продолжительность табу слишком велика, и все возможные решения являются табу, что приводит к увеличению времени расчета и, возможно, к тому, что расчет не может продолжаться.

(5) Функция уровня желания

A (x, s) обычно является лучшим целевым значением, когда-либо достигнутым в истории. Если C (s (x))

(6) Критерии остановки

(1) Учитывая максимальное количество шагов итерации (наиболее часто используется)

(2) Установите максимальную частоту табу для объекта.

(3) Установите порог отклонения значения адаптации.

Четыре, блок-схема алгоритма TS

Пять, примеры TS

Изолятор, состоящий из 7 слоев различных изоляционных материалов, как расположить в порядке для получения наилучших изоляционных характеристик.

Метод кодирования: последовательное кодирование

Начальный код: 2-5-7-3-4-6-1

Целевое значение: максимальное целевое значение.

Источник

Локальный (соседний) поиск берет потенциальное решение проблемы и проверяет его непосредственных соседей (то есть решения, которые похожи, за исключением очень немногих мелких деталей) в надежде найти улучшенное решение. Методы локального поиска имеют тенденцию застревать в неоптимальных регионах или на плато, где многие решения одинаково подходят.

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

Реализация запретного поиска использует структуры памяти, которые описывают посещенные решения или предоставленные пользователем наборы правил. Если потенциальное решение было ранее посещено в течение определенного краткосрочного периода или если оно нарушило правило, оно помечается как « табу » (запрещено), чтобы алгоритм не учитывал эту возможность повторно.

СОДЕРЖАНИЕ

Задний план

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

Основное описание

Типы памяти

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

Псевдокод

Следующий псевдокод представляет упрощенную версию алгоритма поиска запретов, как описано выше. Эта реализация имеет элементарную кратковременную память, но не содержит структур промежуточной или долговременной памяти. Термин «соответствие» относится к оценке возможного решения, воплощенного в целевой функции для математической оптимизации.

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

Пример: задача коммивояжера

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

Источник

Метод поиска с запретами для оптимизационных задач

Аннотация

В данной статье рассматривается метод поиска с запретами и его применение для решения оптимизационных задача, приводится алгоритм вероятностного поиска с запретами в виде псевдо-кода.

Метод поиска с запретами (Tabu Search) является одним из наиболее эффективных метаэвристических методов. Он был предложен Ф. Гловером в 80-е годы 2. Отличительной чертой этого метода является процесс введения и снятия некоторых искусственных ограничений задачи в процессе поиска решения [5].

Метод поиска с запретами и его вариации нашли широкое применение в решении разных оптимизационных задач NP-сложности: задач о составлении расписания 6, задач об упаковке [8, 5], задач о выборе оптимального маршрута [9], задач о размещении 14 и ряда других оптимизационных задач 18.

Работы 13 посвящены проблеме размещения базовых станций в сетях стандарта 3G.

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

Алгоритм метода локального поиска

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

Для оптимизации потенциального решения задачи необходимо наличие двух составляющих:

Ниже (см. алгоритм 1) представлен простейший алгоритм локального поиска для задачи максимизации. Предполагается, что вектор x – решение некоторой оптимизационной задачи. Множество всех возможных векторов обозначим X. Пусть требуется максимизировать некоторую функцию f(x) на множестве X.

Алгоритм 1. Простейший алгоритм локального поиска (задача максимизации) [5].

Возможные условия останова:

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

Окрестность решений N(x) для вектора x представляет собой некоторое множество решений, которые являются в некотором смысле близкими по отношению к x.

Алгоритм метода поиска с запретами

Основным недостатком метода локального поиска является его остановка при достижении локального оптимума (см. условие останова № 3). Под локально оптимальными понимаются такие решения, окрестность которых не содержит лучших по отношению к целевой функции решений, т.е. f(x_opt) > f(y), y ∈ N(x_opt), где x_opt – локальный оптимум [5]. Нашим же искомым решением является глобальный оптимум. Очевидно, что глобальный оптимум является также и локальным, поэтому для успешного поиска решений мы должны как-то переходить от одного локального оптимума к другому.

В методе поиска с запретами с целью преодолеть вышеописанный недостаток вводится т.н. список запретов (Tabu List). Этот список хранит некоторое количество предыдущих решений, и при выборе нового решения запрещается выбирать из окрестности решения, содержащиеся в списке запретов.

Ниже (см. алгоритм 2) представлен общий алгоритм поиска с запретами для задачи максимизации. Предполагается, что вектор x(i) – решение задачи на итерации i. Список запретов обозначим как TL(i). Пусть N'(x(i), TL(i)) – множество соседних решений для x(i) за вычетом содержащихся в списке запретов.

Алгоритм 2. Общий алгоритм поиска с запретами [5].

Окрестность решения

Одним из главных понятий в методах локального поиска и поиска с запретами является окрестность соседних решений N(x) для решения x. Но с практической точки зрения лучше определить не все множество соседних решений N(x), а множество изменений, которым мы можем подвергнуть наше решение [20].

Вероятностный поиск с запретами

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

Для таких случаев был разработан вероятностный поиск с запретами. В нем мы исследуем не окрестность N'(x(i), TL(i)), а вероятностную окрестность N’_p(x(i), TL(i), p). Каждая точка N'(x(i), TL(i)) с вероятностью p включается в N’_p(x(i), TL(i), p) независимо от других точек. Новая окрестность, в принципе, может оказаться пустой, или, например, содержать всего одну точку.

Самым простым способом формирования вероятностной окрестности является генерация случайным образом некоего заранее определенного числа соседних решений (см. алгоритм 3).

Алгоритм 3. Общий алгоритм вероятностного поиска с запретами

Neighbour(R) – функция, которая случайным образом генерирует одно решение из окрестности некоторого решения R>.

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

Список запретов

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

Выбор длины списка запретов зависит от размерности решаемой задачи и мощности окрестности. При коротком списке запретов алгоритм может зациклиться. При длинном списке может оказаться так, что большая часть окрестности будет запрещена, что также не приведет к хорошим результатам [8].

Источник

Табу поиск по угловым параметрам

Дискретные задачи размещения Оптимизационные алгоритмы

Главная страница библиотеки Демонстрационная версия Оптимизационные алгоритмы

Основоположником алгоритма поиска с запретами (Tabu search) является Ф. Гловер, который предложил принципиально новую схему локального поиска [1, 2]. Она позволяет алгоритму не останавливаться в точке локального оптимума, как это предписано в стандартном алгоритме локального спуска, а путешествовать от одного локального оптимума к другому в надежде найти среди них глобальный оптимум. Основным механизмом, позволяющим алгоритму выбираться из локального оптимума, является список запретов Tabu(i_k). Он строится по предыстории поиска, то есть по нескольким предшествующим решениям i_k, i_k–1,…, i_k–l+1₁, и запрещает часть окрестности текущего решения N(i_k). Точнее на каждом шаге алгоритма очередная точка i_k+1 является оптимальным решением подзадачи

Список запретов Tabu_l(i_k) Ì N (i_k) учитывает специфику задачи и, как правило, запрещает использование тех «фрагментов» решения (ребер графа, координат вектора, цвета вершин), которые менялись на последних l шагах алгоритма. Константа l ³ 0 задает длину списка запретов. При l = 0 получаем стандартный локальный спуск.

Существует много вариантов реализации основной идеи поиска с запретами [4]. Приведем один из них, для которого удается установить асимптотические свойства. Рассмотрим рандомизированную окрестность N_p(i) Ì N(i), где каждый элемент окрестности j Î N(i) включается в множество N_p(i) с вероятностью p независимо от других элементов. С ненулевой вероятностью множество N_p(i) может совпадать с N(i), может оказаться пустым или содержать ровно один элемент. Общая схема алгоритма поиска с запретами может быть представлена следующим образом.

Алгоритм поиска с запретами

2. Пока не выполнен критерий остановки делать следующее.

Параметры p и l являются управляющими для данного алгоритма и выбор их значений зависит от размерности задачи и мощности окрестности. Примеры адаптации этой схемы к разным задачам комбинаторной оптимизации можно найти, например, в [3].

1. Glover F. Tabu search: part I. ORSA J. Comp. v1 (1989). pp 190–206.

2. Glover F. Tabu search: part II. ORSA J. Comp. v2 (1990). pp 4–32.

3. Glover F.(Ed.) Tabu search methods for optimization. Feature Issue of Europen J. Oper. Res. v106 (1998), N2–3.

4. Glover F., Laguna. M. Tabu search. Boston: Kluwer Acad. Publ. 1997.

Главная страница библиотеки Демонстрационная версия Оптимизационные алгоритмы

Источник

Русские Блоги

Алгоритм поиска табу (TABU) для решения задачи планирования маршрута (CVRP)

Каталог статей

Алгоритм поиска табу решает проблему планирования маршрута

Определение проблемы

Основной пакет CVRP этой книги определяется следующим образом:

Алгоритм решения проблемы CVRP

Алгоритм поиска табу

Две стратегии локального поиска

1) Выберите допустимое начальное решение и определите окрестность. Найдите лучшее решение в окрестности и сравните его с начальным решением, а затем возьмите наименьшее решение в качестве нового начального решения. Эта итерация останавливается до тех пор, пока решение не будет удовлетворять определенным условиям.
2) Случайный метод. Случайным образом выберите точку в окрестности начального допустимого решения, сравните ее с начальным решением и выполните цикл, пока качество решения не достигнет определенного уровня.

Недостатки локального поиска

1) Нет гарантии, что будет получено глобальное оптимальное решение.
2) Качество решения зависит от выбора начальной точки и области.
3) Чтобы получить высококачественное решение, необходимо сравнить различные структуры соседства и исходные решения. Только при наличии достаточного количества вариантов можно гарантировать оптимальное решение.

Предложение алгоритма поиска табу

Блок-схема алгоритма поиска табу

Псевдокод алгоритма поиска табу

Результат алгоритма

статистические результаты

Подробные результаты

Результаты использования алгоритма табу-поиска для решения части CVRP следующие, источником тестового примера являетсяCapacitated Vehicle Routing Problem Library

A-n32-k5
Vehicle 1: 1(0)->13(21)->2(19)->17(18)->31(14)->1(0) totalDemand = 72.0
Vehicle 2: 1(0)->28(20)->25(24)->1(0) totalDemand = 44.0
Vehicle 3: 1(0)->22(12)->32(9)->20(24)->18(19)->14(16)->8(16)->27(2)->1(0) totalDemand = 98.0
Vehicle 4: 1(0)->7(12)->4(6)->3(21)->24(8)->5(19)->12(14)->29(15)->15(3)->1(0) totalDemand = 98.0
Vehicle 5: 1(0)->21(8)->6(7)->26(24)->11(8)->30(2)->16(22)->23(4)->10(16)->9(6)->19(1)->1(0) totalDemand = 98.0
Оптимальное решение: 787,08

A-n60-k9
Vehicle 1: 1(0)->42(21)->34(6)->39(14)->60(23)->53(18)->1(0) totalDemand = 82.0
Vehicle 2: 1(0)->17(11)->21(1)->4(7)->12(19)->41(11)->47(1)->26(18)->1(0) totalDemand = 68.0
Vehicle 3: 1(0)->35(9)->25(24)->59(9)->24(23)->48(17)->15(13)->1(0) totalDemand = 95.0
Vehicle 4: 1(0)->36(5)->56(9)->51(4)->40(19)->27(19)->18(24)->28(2)->30(17)->1(0) totalDemand = 99.0
Vehicle 5: 1(0)->5(11)->22(5)->54(21)->31(9)->50(2)->45(18)->29(17)->7(17)->1(0) totalDemand = 100.0
Vehicle 6: 1(0)->19(2)->8(21)->14(20)->38(2)->58(22)->9(23)->20(3)->1(0) totalDemand = 93.0
Vehicle 7: 1(0)->3(2)->2(16)->49(42)->23(20)->37(9)->32(11)->1(0) totalDemand = 100.0
Vehicle 8: 1(0)->16(5)->44(21)->57(18)->13(18)->52(24)->10(10)->33(2)->1(0) totalDemand = 98.0
Vehicle 9: 1(0)->11(6)->55(11)->6(9)->43(20)->46(48)->1(0) totalDemand = 94.0
Оптимальное решение: 1362,38

A-n80-k10
Vehicle 1: 1(0)->50(13)->37(12)->39(23)->67(11)->68(5)->74(12)->1(0) totalDemand = 76.0
Vehicle 2: 1(0)->2(24)->8(26)->22(13)->41(13)->1(0) totalDemand = 76.0
Vehicle 3: 1(0)->59(7)->77(14)->33(9)->46(23)->5(5)->23(26)->51(10)->71(5)->1(0) totalDemand = 99.0
Vehicle 4: 1(0)->14(12)->75(19)->30(10)->18(20)->32(2)->60(22)->28(4)->6(11)->1(0) totalDemand = 100.0
Vehicle 5: 1(0)->11(9)->72(12)->64(22)->63(18)->24(17)->45(6)->13(16)->1(0) totalDemand = 100.0
Vehicle 6: 1(0)->54(13)->4(23)->61(13)->40(21)->78(2)->43(23)->1(0) totalDemand = 95.0
Vehicle 7: 1(0)->73(2)->55(2)->10(23)->56(14)->57(7)->70(9)->66(2)->36(2)->27(4)->48(2)->20(12)->76(6)->21(15)->1(0) totalDemand = 100.0
Vehicle 8: 1(0)->52(3)->65(6)->34(1)->16(2)->42(13)->47(11)->26(12)->58(21)->62(22)->31(9)->1(0) totalDemand = 100.0
Vehicle 9: 1(0)->35(2)->3(22)->38(14)->9(9)->44(3)->17(6)->69(9)->79(2)->7(23)->25(7)->1(0) totalDemand = 97.0
Vehicle 10: 1(0)->12(14)->53(6)->29(20)->80(24)->49(7)->19(26)->15(2)->1(0) totalDemand = 99.0

Оптимальное решение: 1828,28

Оптимальное решение: 1315,22

Источник