Задача оптимизации.
таким образом что (x+x1+x2+...+xn)/n = Xср(задано) и А минимально. Функции f1...fn отличются только известными коэффицентами. n ориентировачно 58. Какие методы оптимизации и алгоритмы вы можете предложить, дабы решить поставленную задачу??? Начал копать в сторону генетических алгоритмов но пока не очень успешно. Буду очень благодарен если вы подскажите ресурсы где размещены примеры решения подобных программ или подробно описаны алгоритмы и методы.
UPD: кажется понял ... сложность получается в кроссовере, потому что надо соблюсти условие (x+x1+x2+...+xn)/n = Xср.
Верно?
Я правильно понимаю:
найти X = (x, x1, x2, ..., xn), такое что A(X) = f(x) + f1(x1) + f2(x2) + ... +fn(xn) -> min при условии (x+x1+x2+...+xn)/n = Xср, (Xср = const)?
Если так, то для начала надо избавиться от одного из x, используя определяющее соотношение, задающее область ограничения в виде гиперплоскости. Получаем функцию, зависящую уже от n переменных. Для этой функции применяем один из многочисленных методов оптимизации. Если функции f - линейны, то насколько я помню, это задача линейного программирования, решаемая симплекс-методом.
Зачем таблицу? Ты говоришь про метод оптимизации нулевого порядка, в котором никаких таблиц не надо, просто перебираем точки пространства (их выбором и определяется метод) и берем ту, которая дает экстремум целевой функции.
f(x, l...)=A
f1(x1, l1...)=A1
...................
fn(xn, ln...)=An (n=58) где x - оптимизируемый параметр, остальные известны.
условия для оптимизации в таком случае (А1+...+An) - минимальна, а (x1+...+xn) = Xср заданна. Функция давольно массивна содержит возведение в степень, интегрирование и логарифмирование, но упрощена более чем сейчас не может быть.
Можете ли вы подсказать ресурсы где более подробно представлены алгоритмы решения подобных задачь?
Знаю что подобные задачи довольно часто имеют место на транспорте, к примеру при состаленни расписаний поездов, трамваев, в судоходтсве. но к сожалению более подробной информации не смог найти...
З.Ы.
см. еще http://ru.wikipedia.org/wiki/Методы_оптимизации
Я так и не понял толком условие :) Но тем не менее: в тех задачах идеально использовать генетику, и если эта типична то, и в ней тоже!
Правда сложность с реализацией кроссовера остается...
P.S. результат задачи найти X = (x, x1, x2, ..., xn)? А то в последнем посте, снова немного неопределенно с этим.
Правда сложность с реализацией кроссовера остается...
P.S. результат задачи найти X = (x, x1, x2, ..., xn)? А то в последнем посте, снова немного неопределенно с этим.
Попробую сформулировать понятней, а общем есть некоторая функция f(x, l...) где все параметры кроме х известны, данная функция допустим, для проведения аналогии, описывает расход энергии при движении трамвая, пусть х скорость, а остальные параметры описывают длинну пути, сопротивление движения и так далее. Пусть стоит задача минимизировать расход инергии суммарный на маршрут, для чего делят маршрут на отрезки с одинаковым сопротивлением движению, расход на каждом участки описывает выражение вида f(x,l....) где х скорость l и прочие параметры есть характеристики данного участка маршрута. Чем меньше скорость тем меньше расход энергии, однако трамвай должен укладывать в график, а следовательно средняя скорость движения должна оставать постоянно и равной определенному значению Хср. Так же существует нюанс, на каждом участке пути есть минимально и максимально допустимые скорости по правилам безопасности. В таком случае моя задача в данной модели формулируется следующим образом: подобрать такие значения скоростей на каждом из участков пути что бы расход энергии был минимален, соблюдалась средняя скорость движения маршрута, и значение скорости на каждом участке не выходило за пределы допустимых значений. :):):)
задача примет вид в таком случае
f(x1, l1,...)+...+f(xn, ln,...)=A - min
(x1+...+xn)/n=Xcp
Xmin1<x1<Xmax1
.......................
Xminn<xn<Xmaxn
В хромосому можно кодировать либо непосредственно скорости на участках (не забывая, что скорость света для трамвая недостижима), либо отклонения от среднего (тоже в каких-то рамках).
Написать кроссовер, который будет удовлетворять условию (x1+..+xn)/n = Xcp ... думаю чрезвычайно сложно.
Поэтому предлагаю взять любой классический кроссовер - например двухточечный. И к основной функции полезности (минимазация А, расхода электричества) добавить ещё одну (увеличение средней скорости)... И в итоге общая функция полезности , определяющая выживет ли особь - будет определяться комбинацией этих функций...
Ссылками особо поделиться не могу ибо сам хороших ресурсов не знаю :(
Позвольте еще раз уточнить. Зависимость значения функции от х линейная ? Или ето х возведение в степень и т.д. и т.п. ?
Судя по всему: нелинейная, к тому же многопараметрическая - не только от х зависит.