PDA

View Full Version : Парето-оптимальные стратегии.



Anonymous
08-12-2004, 07:26 PM
Новый шаг в области поиска оптимальных решений: реализация численного метода для решения многокритериальных задач оптимизации, на основе Генетического Алгоритма.

http://www.whiteline.front.ru/

Olezhik
08-13-2004, 04:13 AM
Новый шаг в области поиска оптимальных решений: реализация численного метода для решения многокритериальных задач оптимизации, на основе Генетического Алгоритма.

http://www.whiteline.front.ru/

Ты сам-то понял чё сказал?

Anonymous
08-13-2004, 09:26 AM
Ну да, а какие сомнения? Вроде не по-армянски написано.

Krakadil
08-13-2004, 09:35 AM
Что такое Генетический Алгоритм?

Baba_Yaga
08-13-2004, 10:10 AM
Что такое Генетический Алгоритм?

Генетический алгоритм - это глобальный оптимизатор. И как некоторые другие удачные алгоритмы типа Neural Networks спёрт у матушки-природы. Все свойства обьекта которые исследователь хочет оптимизировать кодируются в гены и из генов собирается "хромосома" - с настоящими биологическими хромосомами у них, конечно, мало общего. Для затравки берётся набор обьектов сильно отличающихся друг от друга по свойствам и для каждого обьекта кодируется хромосома. Далее из этих хромосом составляется "поколение". Хромосомы из данного поколения могут скрещиваться друг с другом, обмениваясь генами и мутировать. Результаты мутации и скрещивания составляют так называемый селекционный набор. Из этого набора выбирают лучших представителей, которые образуют второе поколение и так далее. В результате после многих поколений - вы получаете набор обьектов обладающих нужными для вас свойствами.
Но здесь есть одна тонкость: выбрать лучших из селекционного набора часто бывает сложно. Обычно для этого использовалась т.н. "scoring function", которая для каждого обьекта подсчитывала число "score". Чем выше score - тем лучше обьект. Делалось это путём сложения различных цифровых параметров, присущих обьекту с определёнными множителями (весом). Вес соответствовал вкладу данного параметра в качество обьекта. Вот именно выбор веса и составлял проблему для многопараметрических задач. Pareto scoring имеет дело с рангом параметра (больше, меньше), а не с абсолютным его значением - поэтому позволяет более адекватно оценивать качество обьекта.

Nabludatel'
08-13-2004, 02:41 PM
Что такое Генетический Алгоритм?

Генетический алгоритм - это глобальный оптимизатор. И как.. .

Панятна... а я ета...вчера тоже масла поменял. Ничо, едет пока

Krakadil
08-13-2004, 02:52 PM
Вопрос об использовании оптимизации для стратегий является спорным (c)

Использование ГА, оправдывает себя тех случаях, где требуются действительно, колоссальные вычислительные емкости (c)

Nabludatel'
08-13-2004, 02:55 PM
Вопрос об использовании оптимизации для стратегий является спорным (c)

да, вот Чапаев был стратег, и ничего. Никакими там оптимизаторами не пользовался. Только конь и шашка удалая.

Krakadil
08-13-2004, 03:05 PM
Наверное, тоже пойду масло поменяю

Baba_Yaga
08-13-2004, 03:11 PM
Использование ГА, оправдывает себя тех случаях, где требуются действительно, колоссальные вычислительные емкости (c)

Ну, собственно, так и обстоит дело когда задача многопараметрическая. Т.е. фактически есть 2 пути:
1) подумать и исключить параметры, которые не оказывают существенного влияния на конечную модель, т.е. уменьшить количество параметров в модели и решить её аналитически;
2) накидать в кучу все параметры о которых только можешь подумать и искать глобальный минимум/максимум с помощью какого-нибудь глобального оптимизатора, например ГА.

В первом пути есть опасность выплеснуть ребёнка вместе с водой, а во втором - утонуть в море параметров и так и не найти ответа, поскольку нет идеальных оптимизаторов.

Baba_Yaga
08-13-2004, 03:14 PM
да, вот Чапаев был стратег, и ничего. Никакими там оптимизаторами не пользовался. Только конь и шашка удалая.

Ты Чапаева не трожь - великий философ был. Эето Фурманов про него всё наврал. Возьми хотя бы "Чапаев и Пустота" Пелевина. :lol:

Moonlight Traveler
08-13-2004, 03:14 PM
Что такое Генетический Алгоритм?

Генетический алгоритм - это глобальный оптимизатор. И как некоторые другие удачные алгоритмы типа Neural Networks спёрт у матушки-природы.
....

И наверное как у матушки-природы у таких алгоритмов есть относительно большая вероятность забраться на локальный максимум :)

МТ

Nabludatel'
08-13-2004, 03:18 PM
В первом пути есть опасность выплеснуть ребёнка вместе с водой, а во втором - утонуть в море параметров и так и не найти ответа, поскольку нет идеальных оптимизаторов.

А вот детей жалко канешна. Они та не виноваты. Дети же малые.

Baba_Yaga
08-13-2004, 03:18 PM
И наверное как у матушки-природы у таких алгоритмов есть относительно большая вероятность забраться на локальный максимум :)

МТ

Да, они нужны тоже, поскольку создают разнообразие популяции. А то вся популяция выродилась бы в клонов Супермена без отрицательных героев - вот скукотища бы была!

Anonymous
08-13-2004, 03:46 PM
На самом деле, такой подход к решению задач поможет сэкономить вам время, и как следствие деньги. Только за последний месяц мною было решено более десятка многокритериальных задач из области финансовых исследований, каждая из которых эквивалентна перебору 10^110, с учётом того, что на каждую итерацию тратилось более 1.5 сек.

Olezhik
08-13-2004, 03:55 PM
На самом деле, такой подход к решению задач поможет сэкономить вам время, и как следствие деньги. Только за последний месяц мною было решено более десятка многокритериальных задач из области финансовых исследований, каждая из которых эквивалентна перебору 10^110, с учётом того, что на каждую итерацию тратилось более 1.5 сек.
Я смотрю на словах вы Лев Толстой, попрошу докозательства. Название компани и писма с благодарностями от клиентов

Anonymous
08-13-2004, 04:26 PM
Я посмотрю, Вы не равнодушны. Я к Вам тоже. Но в первую очередь меня интересуют те, у кого есть нерешённые вычислительные задачи, ну или ещё нет, но появятся, зная, что они их решат. В доказательство работоспособности своего алгоритма, мне не составит труда для вас решить любую многокритериальную задачу оптимизации, вычислительного характера, заданную каким либо алгоритмом, или языке, можно прямо здесь, в виде: Y = F(X), X \in R^n, F = (F_1, F_2, …, F_m), Y \in R^m., F – произвольная, в том смысле что нет никаких ограничений.

Baba_Yaga
08-13-2004, 04:36 PM
в виде: Y = F(X), X \in R^n, F = (F_1, F_2, …, F_m), Y \in R^m., F – произвольная, в том смысле что нет никаких ограничений.

Ну, понятно, что когда у вас есть аналитическая функция, которую можно использовать для селекции детей, то решить её несложно (например всем известную F6, которую часто используют для калибровки ГА). Самое сложное в реальной задаче - это определиться с набором и формулой для Парето параметров или scoring function. В этом и заключается 99.9% работы.

Anonymous
08-13-2004, 04:41 PM
А кто Вам сказал что, X – не функция, это может быть так же элемент пространства непрерывных функций. Пространства должны быть метрическими, и конечномерными, это единственное ограничение, остальное дело техники и времени.

Baba_Yaga
08-13-2004, 04:48 PM
А кто Вам сказал что, X – не функция, это может быть так же элемент пространства непрерывных функций. Пространства должны быть метрическими, и конечномерными, это единственное ограничение, остальное дело техники и времени.

Я о другом: о выборе этих функций, правильно описывающих какой-то критерий реального природного процесса, а не о сложности аналитического представления математической абстракции.

Anonymous
08-13-2004, 05:05 PM
Да, я понял. В таком случае всё зависит от человека, который поставил задачу, ведь множество Парето, применяется не для того, чтоб компьютерам жизнь мёдом не казалась, а от того мир наш имеет во всех отношениях многогранную структуру, и поэтому не все вещи поддаются сравнениям. Ну, то что огурец с коровой не сравнишь это ещё в первом классе говорили, а вот, например помидоры, разного сорта сравнить уже не так просто. Одни большие, зреют долго и несладкие, другие поменьше, но повкусней, дак какие лучше? Поэтому в первую очередь, всё зависит от человека.