Важнейшим параметром нашего алгоритма является длина списка исключений, и она, как мы уже отмечали выше, по ходу выполнения варьируется. Остановимся на этом более подробно.
Начнём с того, почему длину списка исключений в нашем случае вообще целесообразно варьировать. Во-первых, потому, что выбор конкретного фиксированного значения в нашей крайне сложной задаче было бы очень трудно обосновать .
Поскольку при этом важна не только размерность задачи (число линий, заявок и т.д.), но и жёсткость ограничений, зависящая от производительности печей, количества имеющихся формокомплектов и условий выполнения переводов. А если трудно выбрать конкретное значение параметра – значит, надо его варьировать! Но есть и другая причина. Варьирование длины списка исключений позволяет более надёжно застраховаться от зацикливания алгоритма, поскольку если даже на каком-то шаге итерационного процесса поиска мы вернёмся к ранее пройденному решению, то при изменившейся длине списка исключений мы, вполне вероятно, дальше (на следующем же шаге или чуть позже) пойдём другим путём.
Варьирование длины списка исключений производится случайным образом (с помощью генератора случайных чисел), но не «абы как», а из определённых соображений. Логика здесь такая. Если на каком-то шаге итерационного процесса поиска было получено наилучшее к этому моменту (рекордное по маржинальности) решение, то можно надеяться где-то «поблизости» (за несколько шагов) найти ещё более удачное решение. Но для этого надо, не удаляясь далеко от найденного решения, более тщательно поискать в его окрестности, что обеспечивается уменьшением длины списка исключений (вплоть до 1). Если же, наоборот, после отыскания последнего рекордного решения минуло большое число шагов итерационного процесса (что может даже свидетельствовать о зацикливании процесса), то надо попытаться как можно быстрее уйти подальше (в другую область множества решений), а для этого длина списка исключений должна быть большой. Большая длина списка исключений позволяет сдвинуть с места заявки, которые долгое время оставались на одном месте – в частности, самую маржинальную заявку, которая, попав в план первой, могла после этого никуда не перемещаться, или те заявки, которые до этого вообще ни разу не попадали в план.
На самом деле по ходу работы алгоритма варьируется не только сама длина списка исключений, но и (через определённое число итераций) пределы её изменения, есть и другие варьируемые параметры. Более того, в нашем алгоритме варьируются не только параметры, но (и также случайным образом) даже сама логика поиска: а именно, правило запретов и элементарные преобразования.
Резюмируя этот раздел, можно констатировать следующее: наш опыт показал, что в алгоритмах направленного поиска, подобных рассмотренному в данной статье, должно быть как можно больше варьируемых составляющих, что не только позволяет избежать зацикливания, но и повышает эффективность поиска.
Но есть возможность сделать алгоритм ещё более «интеллектуальным»: не просто адаптирующимся по ходу поиска, а самообучающимся! Для этого предполагается предусмотреть специальный тестовый режим его работы, в котором, в частности, подбирались бы оптимальные пределы варьирования длины списка исключений и других варьируемых параметров, а также значения параметров, не подлежащих варьированию – с тем, чтобы потом в основном режиме (при составлении реальных планов производства) алгоритм работал максимально эффективно. Но уже тема для отдельной статьи.