моделирование неопределенного поведения программ
может fuzzy logic?
нечеткая логика - возможный вариант, но вот в данном случае с подстройкой будет непросто
вот в данном случае с подстройкой будет непростоПочему? Flexible neuro-fuzzy system разве не прокатит?
Может я ошибаюсь, но IMHO подобные методы помогают моделировать поведение сложных систем на компьютере. Максимум, чего я тут могу добиться --- запустить такую модель с одним алгоритмом кэширования диска, потом с другим алгоритмом, и придти к выводу: в данных случаях алгоритм1 лучше алгоритма2. С конкретными случаями тут как раз проблем нет --- взял какую-нибудь первую попавшуюся большую программу и с помощью разных отладочных средств смотришь, что она делает. Нужна как раз возможность обобщения: с помощью каких-то аналитических оценок (формул) получить, что сразу для большого класса случаев алгоритм1 лучше алгоритм2. Позволяют ли fuzzy system аналитически выводить их характеристики?
для обучения neuro-fuzzy системы необходим эталон
может, конечно, есть адаптивные алгоритмы подстройки neuro-fuzzy, но я о таком не слышал
может, конечно, есть адаптивные алгоритмы подстройки neuro-fuzzy, но я о таком не слышал
может, конечно, есть адаптивные алгоритмы подстройкиЯ не очень хорошо понимаю, что у тебя означает эталон и адаптивные алгоритмы, но есть, например, генетические алгоритмы обучения нейро-нечётких систем. Насколько я понимаю, они входят в твоё определение адаптивных.
Автору темы - я с трудом представляю формализацию этой задачи, вряд ли чем-то смогу помочь.
я так понял, что автор хочет, чтобы была возможность на основании характеристик алгоритма, полученных на нескольких разных классах задач, прикинуть характеристики, которые будут выдаваться для любях других классов задач.
То есть. Есть алгоритм M(a который для задач типа A={a1, a2, a3, ..} оказывается оптимальным, а для задач типа B={b1, b2, ..} лучше оказывается алгоритм N(a). На задачах класса A качество алгоритма N Q(N) ниже качества Q(M) алгоритма M.
Если я правильно понял, то автор хочет, основываясь на данных, полученных для классов A, B и С задач, найти алгоритм M, дающий наилучшее качество на любых задачах, в том числе ранее не проверенного класса D.
С моей точки зрения, такая проблема решения не имеет.
С другой стороны, подобное решение, мне кажется, искать и не нужно. Потому что хотя классов программ можно придумать сколько угодно, но на практике их число весьма мало. И легче подогнать алгоритм под наиболее вероятные классы и пренебречь вероятностью остальных.
Это, конечно, если я правильно понял постановку задачи.
То есть. Есть алгоритм M(a который для задач типа A={a1, a2, a3, ..} оказывается оптимальным, а для задач типа B={b1, b2, ..} лучше оказывается алгоритм N(a). На задачах класса A качество алгоритма N Q(N) ниже качества Q(M) алгоритма M.
Если я правильно понял, то автор хочет, основываясь на данных, полученных для классов A, B и С задач, найти алгоритм M, дающий наилучшее качество на любых задачах, в том числе ранее не проверенного класса D.
С моей точки зрения, такая проблема решения не имеет.
С другой стороны, подобное решение, мне кажется, искать и не нужно. Потому что хотя классов программ можно придумать сколько угодно, но на практике их число весьма мало. И легче подогнать алгоритм под наиболее вероятные классы и пренебречь вероятностью остальных.
Это, конечно, если я правильно понял постановку задачи.
Оптимизировать под данные классы нагрузок сейчас и так очень модно, вот и получаются всякие винды и линуксы, в которых чуть запустишь что нестандартное, сразу проблемы.
ИМХО лучше рассматривать поведение в наихудшем случае, чтоб получить предсказуемую систему.
ИМХО лучше рассматривать поведение в наихудшем случае, чтоб получить предсказуемую систему.
> ИМХО лучше рассматривать поведение в наихудшем случае, чтоб получить предсказуемую систему.
большинство текущих задач не имеют решения для наихудшего случая.
большинство текущих задач не имеют решения для наихудшего случая.
> ИМХО лучше рассматривать поведение в наихудшем случае, чтоб получить предсказуемую систему.
Интересная мысль! В каких терминах эта предсказуемость выражается? Например, если мы пишем какой-нибудь алгоритм вытеснения страниц, то гарантируется, что "будет вытесняться не более X% страниц каждой программы?"
Интересная мысль! В каких терминах эта предсказуемость выражается? Например, если мы пишем какой-нибудь алгоритм вытеснения страниц, то гарантируется, что "будет вытесняться не более X% страниц каждой программы?"
Не совсем так. Возможно, я плохо объяснил постановку задачи. Суть такая:
Понятно, что лучшего алгоритма нет. Но с другой стороны, какой-то алгоритм в системе должен быть, как-то же нужно памятью управлять. Речь идет как раз об этом, дефолтном алгоритме, который устанавливается в систему по умолчанию. А потом, если у пользователя возникают какие-то специфические задачи, на которых этот алгоритм явно лажает, то он устанавливает другой (как например, в Linux можно выбирать disk elevator).
Далее, есть несколько алгоритмов (заранее известных и определенных). Есть чисто интуитивное ощущение, что алгоритм1 лучше (при использовании именно в качестве такого дефолтного чем алгоритм2. Запуск на некоторых простых имеющихся примерах подтверждает это интуитивное предположение. По этой причине возникает желание использовать алгоритм1. Однако появляются сомнения, что вдруг на других задачах будет все наоборот. Хочется эту ситуацию исследовать как-нибудь математически, чтобы обосновать выбор алгоритма более строго, чем просто "вот этот алгоритм нам больше по душе пришелся, мы его и реализовали".
Понятно, что лучшего алгоритма нет. Но с другой стороны, какой-то алгоритм в системе должен быть, как-то же нужно памятью управлять. Речь идет как раз об этом, дефолтном алгоритме, который устанавливается в систему по умолчанию. А потом, если у пользователя возникают какие-то специфические задачи, на которых этот алгоритм явно лажает, то он устанавливает другой (как например, в Linux можно выбирать disk elevator).
Далее, есть несколько алгоритмов (заранее известных и определенных). Есть чисто интуитивное ощущение, что алгоритм1 лучше (при использовании именно в качестве такого дефолтного чем алгоритм2. Запуск на некоторых простых имеющихся примерах подтверждает это интуитивное предположение. По этой причине возникает желание использовать алгоритм1. Однако появляются сомнения, что вдруг на других задачах будет все наоборот. Хочется эту ситуацию исследовать как-нибудь математически, чтобы обосновать выбор алгоритма более строго, чем просто "вот этот алгоритм нам больше по душе пришелся, мы его и реализовали".
тогда не надо генетики или нечеткой логики
пишешь тесты и смотришь. или используешь существующие программы, которые активно могут юзать твой алгоритм (про случай с памятью - часто и постоянно перевыделяют память). это наименее геморройный и приемлимый по качеству метод исследования
пишешь тесты и смотришь. или используешь существующие программы, которые активно могут юзать твой алгоритм (про случай с памятью - часто и постоянно перевыделяют память). это наименее геморройный и приемлимый по качеству метод исследования
Ну например, если одновременно активно (в определённом смысле) N задач, каждая из которых использует (в определённом смысле) M страниц, то каждая операция (в определённом смысле) каждой задачи будет выполнятся за время не более T(N, M).
Хотя это тоже, наверное, слишком сложно.
Хотелось бы систему, чтобы, произведя тестовый запуск задачи для одного пользователя, предсказать, например, какого размера сервер понадобится для одновременного выполнения запросов N пользователей с гарантированным (в предположениях модели) временем отклика.
Хотя это тоже, наверное, слишком сложно.
Хотелось бы систему, чтобы, произведя тестовый запуск задачи для одного пользователя, предсказать, например, какого размера сервер понадобится для одновременного выполнения запросов N пользователей с гарантированным (в предположениях модели) временем отклика.
Оставить комментарий
Landstreicher
Предположим, я пишу какой-то общий компонент операционной системы. Например, подсистему управления памятью, диском итп. Необходимо принимать решения по типу таких: у какого процесса отбирать страницы и помещать их в своп, когда не хватает памяти? какой из файлов выкидывать из кэша при его переполнении? итп.Для каждого конкретного случая, понятно, что есть наилучшее поведение. Однако нам недоступна информация о том, что будет происходить дальше. Процесс может считать, а может продолжить чтение с диска, а может начать писать что-то в сеть. Мы заранее не знаем поведение процесса.
В таких ситуация обычно строят системы на основании некоторых эвристик по типу: выкидывать из кэша те файлы, которые дольше всего не читали. Или: выкидывать из кэша те файлы, которы реже всего читают. Для каждой из эвристик есть случаи, где она ведет себя хорошо, и где она ведет себя плохо.
Хочется описать эту ситуация формально, математически. Например, набором каких-то формул задаем поведение одной эвристики, набором других формул --- другой. По формулам что-то считаем (аналитически) и говорим: в таком-то классе задач эвристика "дольше всего не использованный" лучше, чем "наиболее редко используемый".
Я знаю один такой метод описания --- статистический. Грубо говоря, мы говорим, что с вероятностью 1/3 программа пишет в файл, с вероятностью 1/3 читает из файла, с вероятностью 1/3 грузит процессор. Но у этой модели есть такой недостаток: если шаги выполения одной программы брать независимыми, то моделируемое поведение получается неправдоподобным, и результаты не соответствуют реальным программам. Можно попытаться вводить некоторую зависимость между тем, что программа делала раньше и тем, что она будет делать потом. Тут, во-первых, непонятно, как эту зависимость описывать и моделировать, чтобы она была как-то похоже на реальные прогаммы. Во-вторых, от этой зависимости все формулы дико усложняются и ничего посчитать аналитически не удается
Подскажите хотя бы в какую-то сторону копать.
PS. Насколько я понимаю, проблема общая. Она возникает не только при моделировании работы программ, но и при моделировании поведения людей в городе, животных в природе, автомашин в транспортном потоке.