различные вопросы и ответы АОМПО (Самоделы)

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

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

Билет 7-11. Какие-нибудь свойства для алгоритмов направленного случайного поиска - там не нужно, т.е. просто описать алгоритм? Билет 7-11. Правильно ли: с пересчётом при неудачном шаге - это то, что и в слайдах, тут мы при неудачном шаге отказываемся от него, в остальных, кроме "возврата" мы будем принимать шаг, даже, если он оказался неудачным, хотя увеличивать счётчик мы не забываем, т.е.

счётчик мы увеличиваем всегда в остальных методах с возвратом при неудачном шаге - то же, что и с пересчётом, но только в пересчёте мы при увеличении счётчика учитываем только неудачные попытки, а тут мы учитываем и те и другие. парная проба - там мы смотрим в обе стороны от единичного вектора и !каждый раз! шагаем туда, где меньше, наилучшая проба - это мы вместо одного кси генерим сразу несколько и выбираем лучшее (наименьшее значение), и шагаем туда с линейной экстраполяцией - тут в случае неудачной попытки мы идём в противоположном направлении вычисляя значение функции искосственным линейным образом, а не вычисляя её по честному статического градиента - делаем несколько проб, вычисляем прирост в каждом направлении, производим взвешенное суммирование, в котором в качестве веса берём те самые приросты и тем самым находим наш итоговый шаг, потом шагаем в противоположном направлении (если мы ищем min) Билет 7-11.

тут почти во всех алгоритмах есть такая штука, что мы так или иначе должны куда-то шагнуть на каждом шаге но если то, куда мы хотим шагнуть - выходит за ограничения gi - то что делать? я предлагаю, просто засчитать это за попытку, но никуда так и не шагнуть, так или в алгоритмах нужно делать как-то по другому Билет 12. самообучение методом исключения - как именно мы исключаем? направление и некоторую окрестность (т.е. сектор) ? и сбрасываем ли мы уже исключённое, после того, как сделали успешный шаг Билет 12. как мы изменяем вектор памяти в покоординатном экспоненицальном обучении? Билет 7, 9-11. Где вообще можно найти ответы на них? Кто-нибудь имеет представление о задачах или откуда их взять? Билет 16.

Там сказано "подходы, основанные на декомпозиции пространства решений" - множественное число как бы намекает на то, что там мало просто сказать: а давайте разобьём область на столько частей, сколько у нас процессоров - и будет нам счастье. Ну и что с этим делать? Билет 15. Кто-нибудь нашёл хороший источник для этого билета Билет 17. Там на 41 странице из документа Курс Алгоритмы оптимизации, основанные на методе проб и ошибок есть всякие рассуждения про PI PIN POUT - они вообще зачем? и ещё, PI вообще говоря является подмножеством PIN и POUT, что ставит под вопрос некоторые возможности, рассмотренные в той таблице, что вообще говоря наверно значит, что там имелось ввиду не то, что они написали, а что-то другое, у кого-нибудь есть идеи, что имелось в виду?, или же там всё ок? Билет 26.

А это откуда брать? Билет 25. Откуда брать? В алгоритме имитации отжига мы работаем везде в предположении, что на каждом ярусе есть лишь один рабочий интервал, не ограничивая общности. Типо так? Нужно ли знать операторы мутации и скрещивания для эволюционного алоритма? Ибо на лекциях вроде как не было. Случайный поиск с возвратом при неудачном шаге - правда ли, что: Делаем шаг, если удачный, то принимаем его и пытаемся сделать еще Если неудачный, накапливаем счетчик неудач, и все равно принимаем шаг, пока счетчик позволяет Если счетчик неудач исчерпался, проверяем условие выхода, уменьшаем длину шага, сбрасываем счетчик, и все сначала? Меня смущает то, что здесь написано: http://bigor.bmstu.ru/?cnt/? doc=MO/ch0801.mod/?cou=MO/base.cou Как-то странно уменьшать длину шага после принятия 100500 неудачных шагов, как вернуться к удачному тогда? Если кто-то решил хоть какие-то задачи, выложите, пожалуйста, их в группу АСВК.

Вам все будут очень благодарны! Билет 21. Какие операции мутации и скрещивания нужно приводить? Билеты 12 - 13 - где взять? Муравьиные алгоритмы Сколько у нас NP полных задач, к которым мы можем сводить алгоритмы - 6(7) основных или любая, перечисленная в книге Гэри и Джонсоне? Не знаю, стоит ли это писать, но в качестве дополнительных задач и вопросов давалось следующее: - Построить алгоритм случайного поиска с самообучением для задачи о рюкзаке и показать на примере (сделать 2-3 итерации) - Чем такой метод отличается от направленного поиска? - Чем генетический алгоритм отличается от имитации отжига? Почему генетика быстрее сходится? - В чем достоинство и недостатки генетического алгоритма? В первый столбик пишем вопросы во второй столбик пишем ответы.

С большой вероятностью, в каждой клетке на вопрос может завестить отдельный чат, ну да ладно. Ctrl+Enter - переход на новую строку внутри одной клетки Вопросы наверно лучше не удалять. Ну мы не знаем ни вид функции, ни вид решения, либо на поиск такой информации тратиться много времени/ресурсов -> обычные алгоритмы неприменимы. Ебашим метод проб и ошибок. О великий рандом, найди ответ на наш вопрос.

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

Хм, хотя сейчас почитала в Бублик, Зинько, и там, как раз как здесь написано. Да Да Вроде бы тоже верно Начать лучше с примера в лекции 4 - он может быть своего рода общей схемой Методы оптимизации и алгоритмы. Решения задач оптимизации. И.В.

Бейко, Б.Н. Бублик, П.Н. Зинько эта книга есть на dropbox там на страницах 151 и далее и ещё немного google ещё можно чуть-чуть здесь: http://podelise.ru/docs/46595/index-1794-10.htm Немного вот тут: http://window.edu.ru/resource/650/75650/files/OPTIMISATION.pdf - страницы 45 - 47 И вот тут есть что-то: http://bigor.bmstu.ru/?cnt/?doc=MO/ch0801.mod/?cou=MO/base.cou На NP-трудность есть слайды по имени "Лекция 3", но там "методы" Нас же полнота и замкнутость интересует.

Жизнь-боль и счастья нет. Поэтому на странице 47(+-) из пдфки указан ну очень неочевидный алгоритм разбиения. В папке по имени Лекция 9 - как раз это и описано, кажется И ещё этот чувак, который нам рассказывал, сделал ещё и документ на 6 страниц, в котором всё это по идее должен был по подробнее рассказать, документ лежит в "/материалы/Ассимптотическая сходимость алгоритмов имитации отжига" Один из файлов под именем "Лекция 9" одна из пдфок, либо погугли - это работа костенко плакунова скрещивание - по сути некоторая выходного слово будет от 1ого предка, некоторая от второго. мутация внезапное изменение некоторого бита или битов. думаю, этого хватит.

Мне казалось, что в пересчёте учитываем только неудачные попытки, а в возврате - и те и другие, вроде бы так было в Бублике Денис же вроде создал файлик https://docs.google.com/document/d/1V3K9v4-yUYDPLCxB2t5HkyI4d6Io3btDUVAMNkqeF8w/edit Лекция 4 (ооочень кратко) http://habrahabr.ru/post/105302/ скорее всего, формально нужно свести к рюкзаку или комивояжёру, но у людей получалось загонять и не только это, а ещё например задачу многопроцессорной оптимизации Нужно было полноценно решить задачу: выбрать способ кодирования, вектор памяти, модель обучения.