различные вопросы и ответы АОМПО (1121266), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Кодирование: вектор из 0 и 1, 0 - если вещь не взята в рюкзак, 1 - если взята. Вектор памяти: создадим вектор вероятностей выбора каждой вещи для добавления ее в рюкзак на новом шаге. Сначала присвоим всем равные вероятности. Модификация решения: выберем случайно вещь, которая не лежит в рюкзаке, причем используем наш вектор памяти (вектор вероятностей): чем выше значение соответствующей переменной, тем выше вероятность взять ее. После того, как вещь выбрали, будем складывать ее в рюкзак - может понадобиться вынуть несколько вещей перед этим - вынем самые малоценные. Самообучение: если новое решение (после добавления вещи k) стало хуже, уменьшим вероятность в k-ой позиции вектора памяти - оштрафуем плохое решение.

Штраф можно выбрать пропорционально тому, как ухудшилось решение. Направленный поиск использует свойства функции (в пределе стремится к направлению, противоположному градиенту). Метод случайного поиска с самообучением никакой информации не использует - это тот же метод Монте-Карло, но еще мы пытаемся уменьшить рандом путем выкидывания плохих претендентов. Ответ "Тем, что один генетический, а другой нет" не прокатил.

Прокатило то, что в методе имитации отжига всегда рассматривается одно случайное решение, которое после нескольких модификаций пойдет в ответ. В генетическом алгоритме имеется некая выборка, и мы можем взять одно из нескольких хороших решений - это ответ, почему генетика быстрее сходится. Мутный вопрос. Недостатки (точно) - не факт, что сойдется к оптимальному решению (приближенный метод). Также к недостаткам я отнес то, что это эвристика, непонятно, почему вообще работает.

Не ко всем задачам подходит, может на одной задаче дать офигенный результат, а на другой стабильно выдавать фигню. Достоинства - ну, он все-таки сходится. Иногда быстрее других. Опять же, непонятно, почему. И не ходите к Волканову, если он будет. Не халява. Пытался спросить 15 билет и теорему схем. .

Характеристики

Список файлов ответов (шпаргалок)