Во-первых, я должен сказать, что это кажется довольно небольшим пространством для решения: вы уверены, что грубая сила — не самый простой способ продвижения вперед?
Во-вторых, вы хотите сказать, что вам нужен «довольно хороший» результат за какое-то постоянное время или что вам нужен алгоритм, равный O(1)? Я не скажу, что это невозможно, но... ну, я почти уверен, что это невозможно.
В частности, основное различие между ГА и СА заключается в том, что СА по сути представляет собой алгоритм восхождения на холм, который ищет «вовне» от последней точки в пространстве решений, в то время как ГА являются вероятностными и ищут гиперплоскости в пространстве решений.
Вы говорите две вещи, которые заставляют меня думать, что SA лучше подходит для вашей проблемы: «итеративное построение» и «невозможные состояния». Поскольку ГА рекомбинируют «довольно хорошие» решения по гиперплоскостям в пространстве решений, они имеют тенденцию «повторно обнаруживать» мертвые зоны в пространстве решений. Если вы убеждены, что лучшее решение может быть итеративно построено из довольно хорошего решения, вы находитесь на труднодоступной территории, и SA может подойти лучше.
В общем, относительное преимущество ГА состоит в том, что они быстро обрабатывают очень большие объемы пространства решений, но полагаются на то, что в этом пространстве решений кратко закодированы «хорошие идеи». Относительное преимущество SA заключается в том, что он ищет локальное пространство решений «вокруг» своего исходного решения, что позволяет эффективно находить локальные улучшения. Недостатком является то, что SA заполняется случайным образом и поэтому неэффективен при исследовании больших пространств решений.
person
Larry OBrien
schedule
30.12.2011
