Поиск с запретами — Tabu Search (TS)
53
0
Содержание
Введение
Алгоритм работает следующим образом: начинается с выбора начального решения и последующего исследования соседних вариантов, где предпочтение отдается тем, которые улучшают текущий результат. Для предотвращения возврата к уже исследованным неудачным решениям используется табу-лист — структура, фиксирующая "запрещенные" перемещения. Это позволяет избежать циклических процессов и более эффективно исследовать пространство поиска. Например, в задаче о рюкзаке алгоритм может поочередно добавлять или удалять предметы, стремясь максимизировать их ценность, при этом избегая возврата к ранее рассмотренным комбинациям.
Основой табу-поиска является адаптивная память, которая не только предотвращает возврат к уже найденным решениям, но и управляет процессом поиска, учитывая предыдущие шаги. В дальнейшем над развитием этого алгоритма работали и другие исследователи, такие как Мануэль Лагуна и Рафаэль Марти, значительно расширив его применение в различных областях — от производственного планирования до финансового анализа и телекоммуникаций. Табу-поиск до сих пор остается актуальным инструментом для решения сложных комбинаторных задач, требующих глубокого анализа и сложных вычислений.
Таким образом, табу-поиск является отличным примером того, как новаторские идеи могут преобразовать методы оптимизации поиска, открывая новые возможности в науке и технике. Хотя алгоритм был изначально разработан для решения специфических комбинаторных задач, таких как задача коммивояжера и задача о рюкзаке, в статье рассматривается модификация классического алгоритма, позволяющая ему решать более общие задачи оптимизации, включая задачи в непрерывном пространстве поиска.
Реализация алгоритма
Рассмотрим общие формулы и механизмы, используемые в алгоритме поиска табу для решения задач комбинаторной оптимизации (классический вариант алгоритма):
1. Общая формулировка задачи оптимизации:
- Оптимизация f (x) - целевая функция.
- x ∈ X, где X - множество ограничений на вектор переменных x.
2. Окрестность решений:
- N (x) - множество решений, достижимых из текущего решения x с помощью одного "хода".
- N* (x) - модифицированная окрестность, которая учитывает историю поиска (краткосрочную и долгосрочную память).
3. Краткосрочная память:
- Отслеживание атрибутов (характеристик решений), изменявшихся в недавнем прошлом.
- Запрет на посещение решений, содержащих "табу-активные" атрибуты.
4. Долгосрочная память:
- Подсчет частот изменения/присутствия атрибутов в посещенных решениях.
- Использование этих частот для управления диверсификацией поиска.
5. Интенсификация:
- Выбор лучшего хода из модифицированной окрестности N* (x).
- Возврат к перспективным областям пространства решений.
6. Диверсификация:
- Выбор ходов, вводящих в новые атрибуты, не встречавшихся ранее.
- Направления поиска в области, отличной от уже исследованных.
7. Стратегические колебания:
- Изменение правил выбора ходов при приближении к "критическому уровню".
- Переход через этот уровень с последующим возвратом.
8. Связывание путей:
- Генерация траекторий, соединяющих высококачественные опорные решения.
- Выбор ходов, максимально приближающих текущее решение к направляющим решениям.
Для решения задач оптимизации мы опустим пункт 8 и сосредоточимся на основной идее алгоритма, пытаясь реализовать модификацию табу-поиска, сохраняя, по возможности, пункты 1-7. Оригинальный алгоритм работает с дискретными решениями, стремясь найти кратчайший путь между узлами. Чтобы адаптировать его к задачам в непрерывном пространстве поиска, необходимо каким-то образом дискретизировать допустимые области для каждого оптимизируемого параметра. Проблема в том, что мы не можем пометить каждое возможное решение, так как количество меток будет колоссальным, что делает решение практически невозможным.
Вместо табу-списка мы введем понятия "белого списка" и "черного списка" для каждого параметра, разбив их диапазоны на сектора (заданное количество секторов для каждого оптимизируемого параметра). Таким образом, мы сможем добавлять "галочку" в белый список при удачном решении и делать пометку в черном списке, если решение не улучшилось по сравнению с предыдущим шагом. Сектора с перспективными решениями будут накапливать пометки, что позволит более тщательно исследовать область и уточнять решение. Однако в удачном секторе могут находиться и крайне неудачные решения, и в этом случае пометка этого сектора попадет в черный список. Это означает, что один и тот же сектор может содержать как пометки в белом списке, так и в черном.
Выбор секторов для генерации следующего решения должен осуществляться с вероятностью, пропорциональной количеству меток в белом списке. После генерации нового решения мы проверяем соответствующий сектор по черному списку и вычисляем вероятность, пропорциональную отметкам черного списка как доле от суммы с отметками белого списка. Если вероятность исполняется, мы выбираем другой случайно выбранный сектор.
Таким образом, учитывая особенности поверхности оптимизируемой функции, алгоритм динамически формирует вероятности для исследования всех доступных областей в пространстве поиска, не задерживаясь на каком-либо конкретном секторе. Даже если алгоритм окажется рядом с глобальным оптимальным решением, он не сможет бесконечно улучшать результаты. Это, в свою очередь, приведёт к увеличению отметок в черном списке данного сектора, что вынудит алгоритм сменить сектор и продолжить поиск в других областях гиперпространства.
По задумке, такой подход обеспечит диверсификацию уточнения найденных решений и широкое исследование задач. Это также должно свести к минимуму количество внешних параметров алгоритма, обеспечивая ему свойства самоадаптации к исследуемой функции задачи.
Выделим основные моменты идеи модифицированной реализации классического табу-поска:
1. Дискретизация. Разделение пространства поиска на сектора позволяет более эффективно исследовать области.
2. Белый и черный списки. Успешные и неудачные решения фиксируются отдельно, обеспечивая динамическое отслеживание перспективности секторов.
3. Динамическое исследование. Алгоритм формирует вероятности для исследования всех доступных областей, избегая застревания на неэффективных секторах.
4. Адаптивность. Алгоритм реагирует на накопление отметок в черном списке, что заставляет его менять направление поиска и обеспечивать диверсификацию.
Таким образом наш вариант алгоритма сочетает в себе элементы поиска с запретами (табу-поиск) и эволюционных алгоритмов. Он использует механизм памяти в виде черных и белых списков для направления поиска в перспективные области пространства решений и избегания областей, которые привели к ухудшению решения.
Для наглядности изобразим схематично белый и черные списки секторов по каждой из координат. Для примера возьмем три координаты каждая из которых разбита на 4 сектора. Белые и черные списки записываются отдельно для каждой координаты.
Например, по координате "0" в секторе "3)" в белом списке имеется пять "галочек", что является наибольшим количеством среди всех секторов этой координаты. Это означает, что сектор будет выбран на следующей итерации с наивысшей вероятностью. Однако этот же сектор имеет шесть "пометок" в черном списке, что приведет к увеличению вероятности его замены при генерации нового решения, несмотря на то что он считается наиболее перспективным. Таким образом, может возникнуть ситуация, когда сектор, обладающий меньшим потенциалом, будет иметь меньшую вероятность быть заменённым другим сектором при выборе секторов (это не очевидно на первый взгляд).
Как видно, происходит постоянная ребалансировка вероятностей в процессе исследования пространства поиска, что позволяет учитывать особенности поверхности. Это направление представляется весьма перспективным, так как оно мало зависит от внешних параметров алгоритма, что делает его действительно самоадаптивным.
0: |0)____VVV_____|1)____VV______|2)_____V______|3)____VVVVV____| 1: |0)_____VV_____|1)_____V______|2)____VVV_____|3)_____VVV_____| 2: |0)______V_____|1)____VVV_____|2)_____V______|3)_____VVV_____| 0: |0)_____ХХХ____|1)_____ХХ_____|2)_____XX_____|3)____XXXXXX___| 1: |0)______X_____|1)_____XXX____|2)____XXXXX___|3)______X______| 2: |0)_____XX_____|1)_____XXXX___|2)______X_____|3)____XXXXX____|
Теперь мы можем составить псевдокод модифицированной версии алгоритма, который обозначим как TSm:
1. Инициализация популяции:
Для каждого агента в популяции:
Задаем случайные координаты в пределах заданного диапазона.
Устанавливаем начальное значение предыдущей пригодности как минимально возможное.
2. Основной цикл алгоритма:
Пока не достигнуто условие завершения, повторяем:
а) Если это первая итерация:
Выполняем начальную инициализацию популяции.
б) Иначе:
Генерируем новые координаты для агентов:
Для каждого агента и каждой координаты:
С определенной вероятностью копируем координату лучшего известного решения.
В противном случае:
Выбираем сектор из белого списка агента.
Генерируем новую координату в этом секторе.
Если выбранный сектор находится в черном списке, выбираем случайный сектор и генерируем координату в нем.
Проверяем, чтобы новая координата не выходила за границы допустимого диапазона.
в) Оцениваем пригодность каждого агента с новыми координатами.
г) Обновляем черные и белые списки:
Для каждого агента:
Сравниваем текущую пригодность с предыдущей.
Если пригодность улучшилась, увеличиваем счетчик в белом списке для соответствующего сектора.
Если ухудшилась, увеличиваем счетчик в черном списке.
Сохраняем текущую пригодность как предыдущую для следующей итерации.
д) Обновляем лучшее найденное решение, если найден агент с лучшей пригодностью.
3. По завершении цикла возвращаем лучшее найденное решение.
Теперь приступим к написанию кода. Опишем две структуры: "S_TSmSector" и "S_TSmAgent", которые используются для работы с секторами и агентами в стратегии поиска.
1. S_TSmSector - структура содержит массив целых чисел "sector []", который будет хранить "галочки" для соответствующего сектора (по сути - это массив счетчиков).
2. S_TSmAgent - эта структура более сложная, описывающая поискового агента в алгоритме, включает в себя:
- blacklist [] - массив черных списков по секторам для каждой координаты.
- whitelist [] - массив белых списков по секторам для каждой координаты.
- fPrev - переменная хранит значение предыдущей приспособленности агента.
Метод "Init" инициализирует экземпляр " S_TSmAgent ". Параметры:
- coords - количество координат.
- sectorsPerCord - количество секторов на каждую координату.
Логика:
1. Изменение размера массивов "blacklist" и "whitelist" до количества координат.
2. Инициализация каждого сектора в цикле по всем координатам:
- Изменяем размер массива "sector" для черного списка текущей координаты.
- Аналогично для белого списка.
- Инициализируем все элементы белого и черного списка нулями (это счетчики, которые впоследствии будут инкрементироваться на единицу).
3. Инициализация "fPrev" - устанавливает значение "fPrev" на "-DBL_MAX", что представляет собой минимально возможное значение. Это используется для обозначения того, что агент еще не имел приспособленности.
Код создает структуру агента, который может управлять черными и белыми списками для секторов различных измерений пространства поиска, где необходимо отслеживать разрешенные и запрещенные сектора для посещения агентов.
//—————————————————————————————————————————————————————————————————————————————— struct S_TSmSector { int sector []; }; //—————————————————————————————————————————————————————————————————————————————— //—————————————————————————————————————————————————————————————————————————————— struct S_TSmAgent { S_TSmSector blacklist []; //черный лист по секторам каждой координаты S_TSmSector whitelist []; //белый лист по секторам каждой координаты double fPrev; //предыдущая приспособленность void Init (int coords, int sectorsPerCord) { ArrayResize (blacklist, coords); ArrayResize (whitelist, coords); for (int i = 0; i < coords; i++) { ArrayResize (blacklist [i].sector, sectorsPerCord); ArrayResize (whitelist [i].sector, sectorsPerCord); ArrayInitialize (blacklist [i].sector, 0); ArrayInitialize (whitelist [i].sector, 0); } fPrev = -DBL_MAX; } }; //——————————————————————————————————————————————————————————————————————————————
Опишем класс "C_AO_TSm", который наследуется от базового класса "C_AO".
1. Конструктор устанавливает начальные значения для переменных:
- popSize - (размер популяции) равен 50.
- sectorsPerCoord - (количество секторов на координату) равен 100.
- bestProbab - (вероятность выбора лучшего решения) равна 0.8.
- Создает и инициализирует массив "params" с тремя параметрами, которые соответствуют вышеуказанным переменным.
2. Метод "SetParams" - устанавливает значения параметров из массива "params" обратно в соответствующие переменные класса.
3. Метод "Init" - инициализирует алгоритм с заданными диапазонами и шагами поиска.
4. Moving () - метод отвечает за перемещение агентов в пространстве поиска, а Revision () - выполняет проверку и обновление текущих решений, используя логику табу-поиска.
5. Члены класса:
- S_Agent agents [] - массив агентов представляют решения задачи в процессе поиска.
6. Приватные методы:
- InitializePopulation () - метод для инициализации популяции агентов.
- UpdateLists () - метод для обновления черных и белых списков секторов для агентов.
- GenerateNewCoordinates () - метод для генерации новых координат в процессе поиска.
- GetSectorIndex () - метод для получения индекса сектора на основе координаты и размерности.
- ChooseSectorFromWhiteList () - метод для выбора сектора из белого списка для данного агента и размерности.
- GenerateCoordInSector () - метод для генерации координаты в заданном секторе.
- IsInBlackList () - метод для проверки исполнения вероятности выбора другого сектора с влиянием на выбор белого и черного списков.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_TSm : public C_AO { public: //-------------------------------------------------------------------- C_AO_TSm () { ao_name = "TSm"; ao_desc = "Tabu Search M"; ao_link = "https://www.mql5.com/ru/articles/15654"; popSize = 50; sectorsPerCoord = 100; bestProbab = 0.8; ArrayResize (params, 3); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "sectorsPerCoord"; params [1].val = sectorsPerCoord; params [2].name = "bestProbab"; params [2].val = bestProbab; } void SetParams () { popSize = (int)params [0].val; sectorsPerCoord = (int)params [1].val; bestProbab = params [2].val; } bool Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0); void Moving (); void Revision (); //---------------------------------------------------------------------------- int sectorsPerCoord; double bestProbab; S_TSmAgent agents []; private: //------------------------------------------------------------------- void InitializePopulation (); void UpdateLists (); void GenerateNewCoordinates (); int GetSectorIndex (double coord, int dimension); int ChooseSectorFromWhiteList (int agentIndex, int dimension); double GenerateCoordInSector (int sectorIndex, int dimension); bool IsInBlackList (int agentIndex, int dimension, int sectorIndex); }; //——————————————————————————————————————————————————————————————————————————————
Рассмотрим метод "Init" класса "C_AO_TSm", который отвечает за инициализацию алгоритма табу-поиска. Давайте разберем его по частям:
1. Метод сначала вызывает "StandardInit", передавая ему массивы минимальных и максимальных значений и шагов. Это стандартная инициализация, которая настраивает параметры алгоритма. Далее происходит изменение размера массива "agents" на основе значения "popSize", определяет количество агентов в популяции. Далее цикл, который проходит по каждому агенту в массиве "agents". Для каждого агента вызывается метод "Init", который инициализирует его параметры, такие как координаты "coords" и количество секторов на координату "sectorsPerCoord".
2. Если все этапы инициализации прошли успешно, метод возвращает "true", указывая на успешную инициализацию алгоритма.
Метод "Init" является ключевым для подготовки алгоритма табу-поиска к работе. Он устанавливает диапазоны поиска, инициализирует массив агентов и подготавливает их к дальнейшему поиску решений. Если на любом этапе инициализации возникнет ошибка, метод завершает выполнение и возвращает "false".
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_TSm::Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- ArrayResize (agents, popSize); for (int i = 0; i < popSize; i++) agents [i].Init (coords, sectorsPerCoord); return true; } //——————————————————————————————————————————————————————————————————————————————
Рассмотрим далее метод "Moving" класса "C_AO_TSm". Логика метода:
- if (!revision) - здесь происходит проверка логической переменной "revision". Если она равна "false" (т.е. еще не была выполнена инициализация), выполняется следующий блок кода.
- InitializePopulation () - отвечает за инициализацию популяции агентов.
На второй и последующих итерациях алгоритма вызывается метод "GenerateNewCoordinates ()", генерирующий новые координаты (новые решения) для агентов в процессе поиска.
Метод "Moving" управляет процессом перемещения агентов в алгоритме табу-поиска. Он сначала проверяет, была ли выполнена инициализация популяции. Если нет, инициализирует популяцию, в противном случае метод генерирует новые координаты для агентов.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_TSm::Moving () { //---------------------------------------------------------------------------- if (!revision) { InitializePopulation (); revision = true; return; } //---------------------------------------------------------------------------- GenerateNewCoordinates (); } //——————————————————————————————————————————————————————————————————————————————
Метод "Revision" отвечает за обновление текущего лучшего решения в процессе табу-поиска. Он проходит по всем решениям в популяции, сравнивает их оценки с текущим наилучшим значением и, если находит лучшее решение, обновляет соответствующие переменные. В конце метода происходит обновление белого и черного списков, что необходимо для дальнейшего выполнения алгоритма.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_TSm::Revision () { //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c); } } //---------------------------------------------------------------------------- UpdateLists (); } //——————————————————————————————————————————————————————————————————————————————
Следующий метод "InitializePopulation" отвечает за инициализацию популяции агентов табу-поиска. Он генерирует случайные значения для каждой координаты агентов в заданных диапазонах, а также устанавливает начальное значение для предыдущей оценки каждого агента. Это необходимо для дальнейших итераций алгоритма, где будет происходить оценка и обновление решений.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_TSm::InitializePopulation () { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } agents [i].fPrev = -DBL_MAX; } } //——————————————————————————————————————————————————————————————————————————————
Далее следует метод "UpdateLists" класса "C_AO_TSm". Логика метода:
- Внешний цикл проходит по всем агентам в популяции, где "popSize" — это размер популяции.
- Внутренний цикл проходит по всем координатам каждого агента.
- Для каждой координаты "c" агента "a [i]" вычисляется индекс сектора с помощью метода "GetSectorIndex". Это необходимо для классификации значений в определенные сектора для последующего анализа.
- Если текущая оценка агента "a [i].f" больше его предыдущей оценки "agents [i].fPrev", это означает агент улучшил свое решение. В этом случае увеличивается счетчик в белом списке "whitelist" для соответствующего сектора.
- Если текущая оценка меньше предыдущей, это означает, что агент ухудшил свое решение, и счетчик в черном списке "blacklist" для соответствующего сектора увеличивается.
- После обработки всех координат для агента обновляется его предыдущая оценка на текущую, чтобы в следующей итерации можно было сравнить с новым значением.
Метод "UpdateLists" отвечает за обновление списков (белого и черного) для каждого агента в популяции на основе их текущих и предыдущих оценок. Это позволяет алгоритму табу-поиска отслеживать, какие сектора были успешными (белый список) и какие — неудачными (черный список). Таким образом, метод помогает в дальнейшем управлении поиском решений, избегая повторного посещения неэффективных областей пространства решений.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_TSm::UpdateLists () { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { int sectorIndex = GetSectorIndex (a [i].c [c], c); if (a [i].f > agents [i].fPrev) { agents [i].whitelist [c].sector [sectorIndex]++; } else if (a [i].f < agents [i].fPrev) { agents [i].blacklist [c].sector [sectorIndex]++; } } agents [i].fPrev = a [i].f; } } //——————————————————————————————————————————————————————————————————————————————
Теперь разберем метод "GenerateNewCoordinates" класса "C_AO_TSm". Логика метода:
- Внешний цикл проходит по всем агентам в популяции, где "popSize" — это размер популяции.
- Внутренний цикл проходит по всем координатам каждого агента.
- Сначала проверяется вероятность, используя метод "RNDprobab". Если вероятность исполняется, то агент получает координату из лучшего глобального решения "cB [c]".
- Если вероятность не исполнилась - выбирается сектор из белого списка с помощью метода "ChooseSectorFromWhiteList ()".
- Затем генерируется новая координата в этом секторе с помощью метода "GenerateCoordInSector ()".
- Если выбранный сектор находится в черном списке - выбирается новый сектор случайным образом с помощью "u.RNDminusOne ()", и в нем генерируется новая координата.
- Проверяется, находится ли новая координата в пределах заданных границ и с требуемым шагом.
Метод "GenerateNewCoordinates" отвечает за генерацию новых координат для каждого агента в популяции. Он использует вероятностный подход для выбора между лучшими известными координатами и случайной генерацией в секторах, основанных на белом и черном списках. Также метод обеспечивает корректность координат, проверяя их на соответствие заданным границам.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_TSm::GenerateNewCoordinates () { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < bestProbab) { a [i].c [c] = cB [c]; } else { int sectorIndex = ChooseSectorFromWhiteList (i, c); double newCoord = GenerateCoordInSector (sectorIndex, c); if (IsInBlackList (i, c, sectorIndex)) { sectorIndex = u.RNDminusOne (sectorsPerCoord); newCoord = GenerateCoordInSector (sectorIndex, c); } newCoord = u.SeInDiSp (newCoord, rangeMin [c], rangeMax [c], rangeStep [c]); a [i].c [c] = newCoord; } } } } //——————————————————————————————————————————————————————————————————————————————
Разберем код функции "GetSectorIndex", которая определяет индекс сектора для заданной координаты в указанном измерении. Логика работы функции:
- Если максимальное и минимальное значение диапазона для данного измерения равны, это означает, что диапазон не имеет длины. В этом случае функция сразу возвращает 0, так как нет возможности разделить диапазон на сектора.
- Далее вычисляется длина одного сектора "sL", которая получается путем деления длины диапазона на количество секторов "sectorsPerCoord".
- Индекс сектора "ind" вычисляется по формуле, которая определяет, в какой сектор попадает заданная координата. Сначала от координаты вычитается минимальное значение диапазона, затем результат делится на длину сектора, и полученное значение округляется вниз до ближайшего целого числа.
- Если координата равна максимальному значению диапазона, функция возвращает индекс последнего сектора.
- Далее проверки гарантируют, что индекс не выйдет за пределы допустимых значений. Если индекс больше или равен количеству секторов, возвращается последний сектор. Если индекс меньше 0, возвращается 0.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_TSm::GetSectorIndex (double coord, int dimension) { if (rangeMax [dimension] == rangeMin [dimension]) return 0; double sL = (rangeMax [dimension] - rangeMin [dimension]) / sectorsPerCoord; int ind = (int)MathFloor ((coord - rangeMin [dimension]) / sL); // Особая обработка для максимального значения if (coord == rangeMax [dimension]) return sectorsPerCoord - 1; if (ind >= sectorsPerCoord) return sectorsPerCoord - 1; if (ind < 0) return 0; return ind; } //——————————————————————————————————————————————————————————————————————————————
Переходим к методу "ChooseSectorFromWhiteList", который выбирает сектор из "белого списка" секторов для заданного агента и измерения. Метод возвращает индекс выбранного сектора. Логика работы метода:
- Переменная "totalCount" инициализируется нулем. Она используется для подсчета общего количества "галочек" в секторах белого списка.
- Если "totalCount" равен нулю, это означает, что сектора ещё не содержат "галочек" и все сектора равноценны. В этом случае метод выбирает случайный сектор из всех доступных секторов и возвращает его.
- Далее в цикле происходит накопительный подсчет количества "галочек". Если случайное значение "randomValue" меньше или равно текущему кумулятивному значению, метод возвращает индекс текущего сектора "s". Это позволяет выбирать сектор пропорционально его весу в белом списке.
Метод "ChooseSectorFromWhiteList" позволяет выбирать сектор из белого списка для агента, основываясь на вероятностном распределении имитируя рулеточный отбор.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_TSm::ChooseSectorFromWhiteList (int agentIndex, int dimension) { int totalCount = 0; for (int s = 0; s < sectorsPerCoord; s++) { totalCount += agents [agentIndex].whitelist [dimension].sector [s]; } if (totalCount == 0) { int randomSector = u.RNDminusOne (sectorsPerCoord); return randomSector; } int randomValue = u.RNDminusOne (totalCount); int cumulativeCount = 0; for (int s = 0; s < sectorsPerCoord; s++) { cumulativeCount += agents [agentIndex].whitelist [dimension].sector [s]; if (randomValue <= cumulativeCount) { return s; } } return sectorsPerCoord - 1; } //——————————————————————————————————————————————————————————————————————————————
Разберем метод "GenerateCoordInSector", который генерирует случайную координату в заданном секторе для определенного измерения. Логика работы метода:
- Вычисляется размер сектора для заданного измерения.
- sectorStart вычисляется как минимальное значение диапазона для данного измерения плюс смещение, равное индексу сектора, умноженному на размер сектора. "sectorEnd" определяется как "sectorStart" плюс "sectorSize". Это определяет границы сектора.
- Далее вызывается функция "RNDfromCI", которая генерирует случайное значение в пределах от "sectorStart" до "sectorEnd". Это значение представляет собой координату, сгенерированную в пределах указанного сектора.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_TSm::GenerateCoordInSector (int sectorIndex, int dimension) { double sectorSize = (rangeMax [dimension] - rangeMin [dimension]) / sectorsPerCoord; double sectorStart = rangeMin [dimension] + sectorIndex * sectorSize; double sectorEnd = sectorStart + sectorSize; double newCoord = u.RNDfromCI (sectorStart, sectorEnd); return newCoord; } //——————————————————————————————————————————————————————————————————————————————
В завершении разберем метод "IsInBlackList", который проверяет, находится ли агент в "черном списке" для заданного сектора и измерения. Параметры:
- agentIndex - индекс агента, для которого выполняется проверка.
- dimension - индекс измерения.
- sectorIndex - индекс сектора, который проверяется.
Метод возвращает "true", если агент находится в черном списке и выполнена вероятность на смену сектора с учётом "достижений" сектора согласно белого списка.
- "blackCount" и "whiteCount" получают количество записей в черном и белом списках соответственно для указанного агента, измерения и сектора.
- Общее количество записей "totalCount" вычисляется как сумма черных и белых записей.
- Если общее количество записей равно нулю, метод сразу возвращает "false", что означает, что агент не может находиться в черном списке, так как нет ни черных, ни белых записей.
- Далее вычисляется вероятность того, что данный сектор нужно учесть к находящийся в черном списке. Это делается путем деления количества черных записей на общее количество записей.
- Метод "RNDprobab ()" генерирует случайное число от 0 до 1. Если это случайное число меньше вычисленной вероятности черного списка "blackProbability", то метод возвращает "true".
Метод "IsInBlackList" учитывает как черные, так и белые записи для определения вероятности, что сектор находится в черном списке и его нужно изменить. Чем больше количество записей в черном списке по сравнению с записями белого списка, тем выше вероятность смены сектора в дальнейшем на другой случайный.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_TSm::IsInBlackList (int agentIndex, int dimension, int sectorIndex) { int blackCount = agents [agentIndex].blacklist [dimension].sector [sectorIndex]; int whiteCount = agents [agentIndex].whitelist [dimension].sector [sectorIndex]; int totalCount = blackCount + whiteCount; if (totalCount == 0) return false; double blackProbability = (double)blackCount / totalCount; return u.RNDprobab () < blackProbability; } //——————————————————————————————————————————————————————————————————————————————
Результаты тестов
Распечатка работы алгоритма TSm на тестовых функциях:
TSm|Tabu Search M|50.0|100.0|0.8|
=============================
5 Hilly's; Func runs: 10000; result: 0.8779456463913048
25 Hilly's; Func runs: 10000; result: 0.6143121517195806
500 Hilly's; Func runs: 10000; result: 0.2910412462428753
=============================
5 Forest's; Func runs: 10000; result: 0.9288481105123887
25 Forest's; Func runs: 10000; result: 0.5184350456698835
500 Forest's; Func runs: 10000; result: 0.19054478009120634
=============================
5 Megacity's; Func runs: 10000; result: 0.6107692307692308
25 Megacity's; Func runs: 10000; result: 0.3821538461538462
500 Megacity's; Func runs: 10000; result: 0.1215692307692319
=============================
All score: 4.53562 (50.40%)
Можно заметить, что алгоритм TSm работает достаточно хорошо, достойные показатели результатов как на распечатке работы на тестовых функциях, так и на визуализации, конечно, есть разброс на функциях с малой размерностью, но как вы успели заметить, очень много алгоритмов подвержены этому явлению. Отметим хорошую способность алгоритма выделять большинство значимых областей поверхности исследуемой функции.
TSm на тестовой функции Hilly
TSm на тестовой функции Forest
TSm на тестовой функции Megacity
По результатам тестирования, алгоритм TSm занимает 18 место в рейтинговой таблице алгоритмов оптимизации, что является результатом выше среднего.
№ | AO | Description | Hilly | Hilly final | Forest | Forest final | Megacity (discrete) | Megacity final | Final result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | ANS | across neighbourhood search | 0,94948 | 0,84776 | 0,43857 | 2,23581 | 1,00000 | 0,92334 | 0,39988 | 2,32323 | 0,70923 | 0,63477 | 0,23091 | 1,57491 | 6,134 | 68,15 |
| 2 | CLA | code lock algorithm | 0,95345 | 0,87107 | 0,37590 | 2,20042 | 0,98942 | 0,91709 | 0,31642 | 2,22294 | 0,79692 | 0,69385 | 0,19303 | 1,68380 | 6,107 | 67,86 |
| 3 | AMOm | animal migration ptimization M | 0,90358 | 0,84317 | 0,46284 | 2,20959 | 0,99001 | 0,92436 | 0,46598 | 2,38034 | 0,56769 | 0,59132 | 0,23773 | 1,39675 | 5,987 | 66,52 |
| 4 | (P+O)ES | (P+O) evolution strategies | 0,92256 | 0,88101 | 0,40021 | 2,20379 | 0,97750 | 0,87490 | 0,31945 | 2,17185 | 0,67385 | 0,62985 | 0,18634 | 1,49003 | 5,866 | 65,17 |
| 5 | CTA | comet tail algorithm | 0,95346 | 0,86319 | 0,27770 | 2,09435 | 0,99794 | 0,85740 | 0,33949 | 2,19484 | 0,88769 | 0,56431 | 0,10512 | 1,55712 | 5,846 | 64,96 |
| 6 | SDSm | stochastic diffusion search M | 0,93066 | 0,85445 | 0,39476 | 2,17988 | 0,99983 | 0,89244 | 0,19619 | 2,08846 | 0,72333 | 0,61100 | 0,10670 | 1,44103 | 5,709 | 63,44 |
| 7 | ESG | evolution of social groups | 0,99906 | 0,79654 | 0,35056 | 2,14616 | 1,00000 | 0,82863 | 0,13102 | 1,95965 | 0,82333 | 0,55300 | 0,04725 | 1,42358 | 5,529 | 61,44 |
| 8 | SIA | simulated isotropic annealing | 0,95784 | 0,84264 | 0,41465 | 2,21513 | 0,98239 | 0,79586 | 0,20507 | 1,98332 | 0,68667 | 0,49300 | 0,09053 | 1,27020 | 5,469 | 60,76 |
| 9 | ACS | artificial cooperative search | 0,75547 | 0,74744 | 0,30407 | 1,80698 | 1,00000 | 0,88861 | 0,22413 | 2,11274 | 0,69077 | 0,48185 | 0,13322 | 1,30583 | 5,226 | 58,06 |
| 10 | ASO | anarchy society optimization | 0,84872 | 0,74646 | 0,31465 | 1,90983 | 0,96148 | 0,79150 | 0,23803 | 1,99101 | 0,57077 | 0,54062 | 0,16614 | 1,27752 | 5,178 | 57,54 |
| 11 | TSEA | turtle shell evolution algorithm | 0,96798 | 0,64480 | 0,29672 | 1,90949 | 0,99449 | 0,61981 | 0,22708 | 1,84139 | 0,69077 | 0,42646 | 0,13598 | 1,25322 | 5,004 | 55,60 |
| 12 | DE | differential evolution | 0,95044 | 0,61674 | 0,30308 | 1,87026 | 0,95317 | 0,78896 | 0,16652 | 1,90865 | 0,78667 | 0,36033 | 0,02953 | 1,17653 | 4,955 | 55,06 |
| 13 | CRO | chemical reaction optimisation | 0,94629 | 0,66112 | 0,29853 | 1,90593 | 0,87906 | 0,58422 | 0,21146 | 1,67473 | 0,75846 | 0,42646 | 0,12686 | 1,31178 | 4,892 | 54,36 |
| 14 | BSA | bird swarm algorithm | 0,89306 | 0,64900 | 0,26250 | 1,80455 | 0,92420 | 0,71121 | 0,24939 | 1,88479 | 0,69385 | 0,32615 | 0,10012 | 1,12012 | 4,809 | 53,44 |
| 15 | HS | harmony search | 0,86509 | 0,68782 | 0,32527 | 1,87818 | 0,99999 | 0,68002 | 0,09590 | 1,77592 | 0,62000 | 0,42267 | 0,05458 | 1,09725 | 4,751 | 52,79 |
| 16 | SSG | saplings sowing and growing | 0,77839 | 0,64925 | 0,39543 | 1,82308 | 0,85973 | 0,62467 | 0,17429 | 1,65869 | 0,64667 | 0,44133 | 0,10598 | 1,19398 | 4,676 | 51,95 |
| 17 | (PO)ES | (PO) evolution strategies | 0,79025 | 0,62647 | 0,42935 | 1,84606 | 0,87616 | 0,60943 | 0,19591 | 1,68151 | 0,59000 | 0,37933 | 0,11322 | 1,08255 | 4,610 | 51,22 |
| 18 | TSm | tabu search M | 0,87795 | 0,61431 | 0,29104 | 1,78330 | 0,92885 | 0,51844 | 0,19054 | 1,63783 | 0,61077 | 0,38215 | 0,12157 | 1,11449 | 4,536 | 50,40 |
| 19 | BSO | brain storm optimization | 0,93736 | 0,57616 | 0,29688 | 1,81041 | 0,93131 | 0,55866 | 0,23537 | 1,72534 | 0,55231 | 0,29077 | 0,11914 | 0,96222 | 4,498 | 49,98 |
| 20 | WOAm | wale optimization algorithm M | 0,84521 | 0,56298 | 0,26263 | 1,67081 | 0,93100 | 0,52278 | 0,16365 | 1,61743 | 0,66308 | 0,41138 | 0,11357 | 1,18803 | 4,476 | 49,74 |
| 21 | AEFA | artificial electric field algorithm | 0,87700 | 0,61753 | 0,25235 | 1,74688 | 0,92729 | 0,72698 | 0,18064 | 1,83490 | 0,66615 | 0,11631 | 0,09508 | 0,87754 | 4,459 | 49,55 |
| 22 | ACOm | ant colony optimization M | 0,88190 | 0,66127 | 0,30377 | 1,84693 | 0,85873 | 0,58680 | 0,15051 | 1,59604 | 0,59667 | 0,37333 | 0,02472 | 0,99472 | 4,438 | 49,31 |
| 23 | BFO-GA | bacterial foraging optimization - ga | 0,89150 | 0,55111 | 0,31529 | 1,75790 | 0,96982 | 0,39612 | 0,06305 | 1,42899 | 0,72667 | 0,27500 | 0,03525 | 1,03692 | 4,224 | 46,93 |
| 24 | ABHA | artificial bee hive algorithm | 0,84131 | 0,54227 | 0,26304 | 1,64663 | 0,87858 | 0,47779 | 0,17181 | 1,52818 | 0,50923 | 0,33877 | 0,10397 | 0,95197 | 4,127 | 45,85 |
| 25 | ASBO | adaptive social behavior optimization | 0,76331 | 0,49253 | 0,32619 | 1,58202 | 0,79546 | 0,40035 | 0,26097 | 1,45677 | 0,26462 | 0,17169 | 0,18200 | 0,61831 | 3,657 | 40,63 |
| 26 | MEC | mind evolutionary computation | 0,69533 | 0,53376 | 0,32661 | 1,55569 | 0,72464 | 0,33036 | 0,07198 | 1,12698 | 0,52500 | 0,22000 | 0,04198 | 0,78698 | 3,470 | 38,55 |
| 27 | IWO | invasive weed optimization | 0,72679 | 0,52256 | 0,33123 | 1,58058 | 0,70756 | 0,33955 | 0,07484 | 1,12196 | 0,42333 | 0,23067 | 0,04617 | 0,70017 | 3,403 | 37,81 |
| 28 | Micro-AIS | micro artificial immune system | 0,79547 | 0,51922 | 0,30861 | 1,62330 | 0,72956 | 0,36879 | 0,09398 | 1,19233 | 0,37667 | 0,15867 | 0,02802 | 0,56335 | 3,379 | 37,54 |
| 29 | COAm | cuckoo optimization algorithm M | 0,75820 | 0,48652 | 0,31369 | 1,55841 | 0,74054 | 0,28051 | 0,05599 | 1,07704 | 0,50500 | 0,17467 | 0,03380 | 0,71347 | 3,349 | 37,21 |
| 30 | SDOm | spiral dynamics optimization M | 0,74601 | 0,44623 | 0,29687 | 1,48912 | 0,70204 | 0,34678 | 0,10944 | 1,15826 | 0,42833 | 0,16767 | 0,03663 | 0,63263 | 3,280 | 36,44 |
| 31 | NMm | Nelder-Mead method M | 0,73807 | 0,50598 | 0,31342 | 1,55747 | 0,63674 | 0,28302 | 0,08221 | 1,00197 | 0,44667 | 0,18667 | 0,04028 | 0,67362 | 3,233 | 35,92 |
| 32 | FAm | firefly algorithm M | 0,58634 | 0,47228 | 0,32276 | 1,38138 | 0,68467 | 0,37439 | 0,10908 | 1,16814 | 0,28667 | 0,16467 | 0,04722 | 0,49855 | 3,048 | 33,87 |
| 33 | GSA | gravitational search algorithm | 0,64757 | 0,49197 | 0,30062 | 1,44016 | 0,53962 | 0,36353 | 0,09945 | 1,00260 | 0,32667 | 0,12200 | 0,01917 | 0,46783 | 2,911 | 32,34 |
| 34 | BFO | bacterial foraging optimization | 0,61171 | 0,43270 | 0,31318 | 1,35759 | 0,54410 | 0,21511 | 0,05676 | 0,81597 | 0,42167 | 0,13800 | 0,03195 | 0,59162 | 2,765 | 30,72 |
| 35 | ABC | artificial bee colony | 0,63377 | 0,42402 | 0,30892 | 1,36671 | 0,55103 | 0,21874 | 0,05623 | 0,82600 | 0,34000 | 0,14200 | 0,03102 | 0,51302 | 2,706 | 30,06 |
| 36 | BA | bat algorithm | 0,59761 | 0,45911 | 0,35242 | 1,40915 | 0,40321 | 0,19313 | 0,07175 | 0,66810 | 0,21000 | 0,10100 | 0,03517 | 0,34617 | 2,423 | 26,93 |
| 37 | AAA | algae adaptive algorithm | 0,50007 | 0,32040 | 0,25525 | 1,07572 | 0,37021 | 0,22284 | 0,16785 | 0,76089 | 0,27846 | 0,14800 | 0,09755 | 0,52402 | 2,361 | 26,23 |
| 38 | SA | simulated annealing | 0,55787 | 0,42177 | 0,31549 | 1,29513 | 0,34998 | 0,15259 | 0,05023 | 0,55280 | 0,31167 | 0,10033 | 0,02883 | 0,44083 | 2,289 | 25,43 |
| 39 | IWDm | intelligent water drops M | 0,54501 | 0,37897 | 0,30124 | 1,22522 | 0,46104 | 0,14704 | 0,04369 | 0,65177 | 0,25833 | 0,09700 | 0,02308 | 0,37842 | 2,255 | 25,06 |
| 40 | PSO | particle swarm optimisation | 0,59726 | 0,36923 | 0,29928 | 1,26577 | 0,37237 | 0,16324 | 0,07010 | 0,60572 | 0,25667 | 0,08000 | 0,02157 | 0,35823 | 2,230 | 24,77 |
| 41 | Boids | boids algorithm | 0,43340 | 0,30581 | 0,25425 | 0,99346 | 0,35718 | 0,20160 | 0,15708 | 0,71586 | 0,27846 | 0,14277 | 0,09834 | 0,51957 | 2,229 | 24,77 |
| 42 | MA | monkey algorithm | 0,59107 | 0,42681 | 0,31816 | 1,33604 | 0,31138 | 0,14069 | 0,06612 | 0,51819 | 0,22833 | 0,08567 | 0,02790 | 0,34190 | 2,196 | 24,40 |
| 43 | SFL | shuffled frog-leaping | 0,53925 | 0,35816 | 0,29809 | 1,19551 | 0,37141 | 0,11427 | 0,04051 | 0,52618 | 0,27167 | 0,08667 | 0,02402 | 0,38235 | 2,104 | 23,38 |
| 44 | FSS | fish school search | 0,55669 | 0,39992 | 0,31172 | 1,26833 | 0,31009 | 0,11889 | 0,04569 | 0,47467 | 0,21167 | 0,07633 | 0,02488 | 0,31288 | 2,056 | 22,84 |
| 45 | RND | random | 0,52033 | 0,36068 | 0,30133 | 1,18234 | 0,31335 | 0,11787 | 0,04354 | 0,47476 | 0,25333 | 0,07933 | 0,02382 | 0,35648 | 2,014 | 22,37 |
Выводы
Рассматривая результаты работы алгоритма на тестовых функциях различной размерности можно заметить, что алгоритм труднее справляется с задачами большой размерности на гладкой функции "Hilly". В остальных тестах алгоритм демонстрирует стабильные хорошие результаты.
Данная предложенная модификация известного алгоритма Tabu Search, в отличие от оригинальной версии, может быть использована в любых задачах оптимизации общего вида в непрерывных пространствах поиска, включая как гладкие, так и дискретные задачи. Алгоритм может служить мощной основой для использования идейной базы в других алгоритмах. Для повышения точности сходимости можно использовать приёмы, используемые в ранее рассмотренных алгоритмах, но на данном этапе представляю модификацию "как есть".
Рисунок 1. Цветовая градация алгоритмов по соответствующим тестам. Белым цветом подсвечены результаты больше или равные 0.99
Рисунок 2. Гистограмма результатов тестирования алгоритмов (по шкале от 0 до 100, чем больше, тем лучше,
где 100 - максимально возможный теоретический результат, в архиве скрипт для расчета рейтинговой таблицы)
Плюсы и минусы алгоритма TSm:
Плюсы:
- Перспективная идея для дальнейшего усовершенствования и использование как базы в новых алгоритмах.
- Хорошая масштабируемость.
- Небольшое количество интуитивно понятных параметров (всего два без учета выбора размера популяции).
Минусы:
- Точность сходимости хотелось бы выше.
К статье прикреплён архив с актуальными версиями кодов алгоритмов. Автор статьи не несёт ответственности за абсолютную точность в описании канонических алгоритмов, во многие из них были внесены изменения для улучшения поисковых возможностей. Выводы и суждения, представленные в статьях, основываются на результатах проведённых экспериментов.
Изучение MQL5 — от новичка до профи (Часть V): Основные операторы перенаправления потока команд
Разработка системы репликации (Часть 45): Проект Chart Trade (IV)
Нейросети в трейдинге: Иерархический векторный Transformer (Окончание)
Разработка MQTT-клиента для MetaTrader 5: методология TDD (финал)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования