Optaplanner; Застрял в локальных оптимумах в соответствии с сортировкой входных данных

Использование Optaplanner версии 6.2.0

Мои правила DROOLS:

rule "Transition Time Constraint"
  when
      $leftImageStrip:ImageStrip($selected : selected,
        $satellite : satellite,
        selected != null,
        $timeslot : timeslot,
        leftId : id,
        lGain : gain,
        lRollAngle : rollAngle,
        $duration : duration)

      $rightImageStrip : ImageStrip(selected == $selected,
        satellite == $satellite,
        Math.abs(timeslot.getTime() - $timeslot.getTime()) <= 460000,
        this != $leftImageStrip,
        rGain : gain,
        rRollAngle : rollAngle)
  then
      x = new SimpleDateFormat("dd-MM-yyyy HH:mm:ss.SSS");
      scoreHolder.addHardConstraintMatch(kcontext, -1);
end

rule "Shoot Strip once"
   when
      $leftImageStrip: ImageStrip($selected : selected, $stripList : stripList,
                                leftId : id, selected != null)
      $rightImageStrip: ImageStrip(selected == $selected, stripList == $stripList,
                                this != $leftImageStrip)
   then
      scoreHolder.addMediumConstraintMatch(kcontext, -1);
end

rule "Maximization of Selected Parameters"
   when     
      $imageStrip: ImageStrip(selected != null)
   then
      scoreHolder.addSoftConstraintMatch(kcontext, $imageStrip.gain);
end

Я придерживался локального оптимума, который различается в зависимости от сортировки входных данных.

Как я могу преодолеть эту проблему, чтобы получить такое же оптимальное решение, как и при сортировке входных данных? И, конечно, это должно быть глобально оптимальное решение.

Можно ли гарантировать, что полученный результат с помощью Optaplanner является глобальным оптимумом? независимо от сортировки входных данных?


optaplanner
person Amr Qamar    schedule 02.11.2015    source источник
comment
Кто-нибудь может помочь мне ответить на этот вопрос?   -  person Amr Qamar    schedule 04.11.2015

Ответы (1)


arrow_upward
0
arrow_downward

Похоже, у вас есть ловушка для оценки в правиле «Ограничение времени перехода». См. Документацию по ключевому слову "Score Trap". Исправление этого может иметь очень большое значение, чтобы избежать локальных оптимумов и получить хорошие результаты. Что-то вроде этого исправило бы это (возможно, перевернутое с макушки):

scoreHolder.addHardConstraintMatch(kcontext, ... 460000 - Math.abs(timeslot.getTime() - $timeslot.getTime()) ...);

Как только это будет исправлено, посмотрите на свое среднее количество баллов в секунду (последняя строка журнала или отчет тестера).

При этом метаэвристика (например, локальный поиск) не связана с поиском глобального оптимального решения. Они стремятся найти наилучшее возможное решение при масштабировании в разумные сроки, лучше, чем любая другая технология может дать вам за то время, которое у вас есть при масштабировании (см. Исследования, такие как ROADEF, ITT и INRC для доказательства - все технологии, претендующие на достижение глобального оптимума, не масштабируются). Обратной стороной этого является то, что метаэвристика не всегда хорошо масштабируется вниз (только вверх).

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

person Geoffrey De Smet    schedule 04.11.2015
comment
Версия 6.3.0 решает эту проблему? Если так, я могу изменить его использование. - person Amr Qamar; 04.11.2015
comment
Из документов я понял, что это происходит, когда уровень оценки одинаков, но у моей проблемы только один жесткий, один мягкий и один средний. Если бы я понял, Райт ...! Таким образом, использование (... -1 ...) для штрафа за ограничение не повлияет на результат. Я прекрасно понимаю это дело ??? - person Amr Qamar; 04.11.2015
comment
Мистер Джеффри Де Смет, не могли бы вы помочь мне решить эту проблему? скажите, понимаю ли я ваш ответ и что написано в документации. - person Amr Qamar; 05.11.2015