Есть ли предварительно определенное имя для следующего алгоритма поиска/оптимизации решения?

Рассмотрим задачу, решение которой максимизирует целевую функцию.
Проблема: из 500 элементов необходимо выбрать 15 (решение-кандидат). Значение целевой функции зависит от попарных отношений между элементами в решении-кандидате и еще от некоторых других.
Шаги решения такой проблемы описаны здесь:

    1. Generate a set of candidate solutions in guided random manner(population) //not purely random the direction is given to generate the population 
    2. Evaluating the objective function for current population
    3. If the current_best_solution exceeds the global_best_solution, then replace the global_best with current_best
    4. Repeat steps 1,2,3 for N (arbitrary number) times


где размер совокупности и N меньше (около 50)
После N итераций он возвращает решение-кандидат, хранящееся в global_best_solution

  • Это описание известного алгоритма?

  • Если да, то как называется этот алгоритм, а если нет, то к какой категории относятся алгоритмы этого типа?


optimization iteration mathematical-optimization evolutionary-algorithm
person Prem Jith    schedule 21.08.2015    source источник
comment
Создаются ли решения-кандидаты на основе текущего лучшего решения (т. е. какой-либо формы мутации) или они создаются с нуля? В первом случае это своего рода восхождение на холм; в последнем случае это то же самое, что генерировать сразу всех кандидатов из всех поколений и выбирать лучшее из них.   -  person tobias_k    schedule 21.08.2015
comment
Что ж, необычно (и, вероятно, менее эффективно) не выполнять какой-либо локальный поиск, но я думаю, что это можно считать случайный поиск с бесконечным поисковым окружением.   -  person josliber♦    schedule 21.08.2015
comment
@tobias_k это не с нуля, пространство поиска (которое представляет собой набор элементов) находится на каждой итерации, а затем генерируются некоторые случайные комбинации для формирования возможных решений. Поиск пространства поиска — это управляемый процесс, в результате которого выявляется пространство, в котором высока вероятность нахождения оптимальных решений.   -  person Prem Jith    schedule 22.08.2015

Ответы (2)


arrow_upward
3
arrow_downward

То, что у вас есть, звучит так, будто вы просто ловите рыбу. Обратите внимание, что вы могли бы также избавиться от шагов 3 и 4, так как запуск цикла 100 раз будет таким же, как выполнение его один раз с начальной популяцией в 100 раз большей.

Если вы думаете о целевой функции как о случайной величине, которая является функцией случайных переменных решения, то то, что вы делаете, например. дать вам что-то в 99,9-м процентиле с очень высокой вероятностью, но нет предела тому, насколько оптимум может быть далеко от 99,9-го процентиля.

Чтобы проиллюстрировать эту трудность, рассмотрим следующую задачу коммивояжера. Представьте себе два кластера точек A и B, в каждом из которых по 100 точек. Внутри кластеров каждая точка произвольно близка к любой другой точке (например, 0,0000001). Но -- между кластерами расстояние, скажем, 1 000 000. Оптимальный тур явно будет иметь длину 2 000 000 (+ незначительная сумма). Случайный тур — это просто случайная перестановка этих 200 точек принятия решений. Получение оптимального или близкого к оптимальному тура было бы похоже на перетасовку колоды из 200 карт со 100 прочитанными и 100 черными и наличием всех красных карт в колоде в блоке (считая блоки, которые «обертываются») — исчезающе маловероятно ( Его можно рассчитать как 99 * 100! * 100! / 200! = 1,09 x 10^-57). Даже если вы сгенерируете квадриллионы туров, весьма вероятно, что каждый из этих туров будет отличаться на миллионы. Это минимальная проблема, но также легко придумать максимальные задачи, где исчезающе маловероятно, что вы получите решение, близкое к оптимальному, путем чисто случайных настроек переменных решения.

Это крайний пример, но его достаточно, чтобы показать, что чисто случайный поиск решения не очень надежен. Было бы разумнее использовать эволюционные алгоритмы или другие эвристики, такие как симуляция отжига или поиск табу.

person John Coleman    schedule 21.08.2015
comment
Отличный ответ. Одно уточнение: 100 TSP — это не то же самое, что 200 раз перевернуть и получить 100 орлов, а затем 100 решек. В туре по 100 местам пространство поиска составляет 100! , что составляет 10^157. Так что это, вероятно, похоже на выигрыш в лотерею 15 раз подряд. См. также . - person Geoffrey De Smet; 21.08.2015
comment
Дело в том, что имеется 100 + 100 = 200 городов, из которых из А и половина из В. Близкие к оптимальным решения соответствуют перестановкам, в которых все 100 А-городов перечислены перед всеми 100 В-городами или наоборот (при этом порядок внутри каждого кластера практически не имеет значения). Это не совсем то же самое, что подбросить монету 200 раз (из-за отсутствия независимости), но это было достаточно похоже на интуицию. Лучшее описание может быть таким: иметь колоду из 200 карт, 100 красных и 100 черных, перетасовать их, а затем поставить все красные карты выше всех черных карт. - person John Coleman; 21.08.2015
comment
@GeoffreyDeSmet Я отредактировал ответ, включив в него расчет вероятности, который я считаю правильным. - person John Coleman; 21.08.2015
comment
@ John Coleman Проблема похожа на 500 элементов, из которых нужно выбрать 15 (кандидатное решение). Значение целевой функции зависит от попарной связи между элементами и еще от чего-то. Поэтому я выбрал этот метод, и он дал лучшее решение, чем эволюционный алгоритм. Отредактировал мой вопрос: стратегия выбора кандидата-кандидата не является чисто случайной, это управляемый случайный метод. - person Prem Jith; 22.08.2015
comment
@PremJith Неудивительно, что есть проблемы, для которых это нормально. Теоремы об отсутствии бесплатных обедов в некотором смысле предсказывают существование таких проблем. Возвращаясь к тому, что я сказал о 99,9-м процентиле - если распределение возможных оценок имеет короткий хвост, то это приблизит вас к максимуму. Тем не менее, я подозреваю, что должен быть какой-то оператор мутации, для которого эволюционный подход работает лучше. - person John Coleman; 22.08.2015

arrow_upward
0
arrow_downward

почему вы работаете с населением, если члены этого населения не взаимодействуют?

то, что у вас есть, это случайный поиск.

если вы добавите мутацию, это будет выглядеть как стратегия эволюции: https://en.wikipedia.org/wiki/Evolution_strategy< /а>

person Mihai Oltean    schedule 21.08.2015