Учитывают ли алгоритмы поиска ходы, снижающие сложность

Для моей проблемы оптимизации я позволил OptaPlanner построить начальное решение (FIRST_FIT), а затем выполнить локальный поиск.

<unionMoveSelector>
    <changeMoveSelector/>
    <swapMoveSelector/>
    <pillarChangeMoveSelector>
        <subPillarType>ALL</subPillarType>
    </pillarChangeMoveSelector>
    <pillarSwapMoveSelector>
        <subPillarType>ALL</subPillarType>
    </pillarSwapMoveSelector>
</unionMoveSelector>
<acceptor>
    <entityTabuSize>7</entityTabuSize>
    <lateAcceptanceSize>400</lateAcceptanceSize>
</acceptor>
<forager>
    <acceptedCountLimit>1000</acceptedCountLimit>
</forager>

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

Теперь я проверяю решение и вижу, что могу улучшить его всего за 2 хода изменений, то есть назначить двум объектам планирования другое значение. Но первый ход делает задачу невыполнимой (т.е. снижает жесткий балл на <0). Второй шаг увеличивает сложную оценку до 0 и дает более высокую среднюю оценку. Однако, что бы я ни пробовал (более длительное время расчета, acceptCountLimit = 100000 и т. Д.) OptaPlanner не находит этого решения.

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


optaplanner
person Marc Sol    schedule 28.07.2020    source источник
comment
Так что это не было связано с тяжелым / средним баллом. Шаг 1 не снизил сложную оценку. Но в шагах было что-то особенное, связанное с текущей плановой стоимостью двух задействованных плановых единиц и новой плановой стоимостью, которой они оба были присвоены. Поэтому я создал специальный Move, адаптированный к этой ситуации, с помощью MoveIteratorFactory, следуя примеру CheapTime. Это решило мою проблему.   -  person Marc Sol    schedule 28.07.2020
comment
Теперь мой собственный ход - это всего два последовательных ChangeMoves, но эта последовательность никогда не была найдена во время многих прогонов алгоритма, даже когда я переключился на NON_REPRODUCIBLE. В этом конкретном случае было всего 100 плановых единиц и 400 плановых значений. То есть 40k возможных комбинаций и, следовательно, вероятность (1 / 40k) ^ 2 того, что была найдена именно улучшающая комбинация? Я думаю, постепенные шаги должны стать стандартной частью моих кварталов в будущем?   -  person Marc Sol    schedule 28.07.2020
comment
Можете ли вы опубликовать код для своего CustomMove? Вы используете CompositeMove?   -  person code4dc    schedule 12.08.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

Я не рассматривал конкретные реализации в Optaplanner, но в целом, например, при запрете поиска, ход считается принятым, если он улучшает решение, и этот ход не находится в списке запретов, т.е. ход был применен раньше, когда-то недавно. При поиске нового хода, который улучшит текущее лучшее решение, алгоритм также будет применять недопустимые ходы, обычно в надежде наткнуться на решение, которое улучшает текущее лучшее решение. Однако то, как выполняется это исследование, на самом деле зависит от реализации, в этом разделе объясняется, как Optaplanner перебирает параметры. Надеюсь, это помогло!

person k88    schedule 02.08.2020