2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 софт для глобальной оптимизации
Сообщение28.06.2010, 10:10 
Аватара пользователя
Хочу протестировать свой велосипед на тему глобальной оптимизации (роевые модели) на задачах большой размерности.

Допустим, есть такая тестовая задача:

оптимизируемая функция:
$f(\vec{x})=\sum\limits_{i=0}^n(x_i-1)^2 - \sum\limits_{i=1}^n(x_ix_{i-1})$,
n - размерность вектора x (число аргументов), путь равно 100.
стартовое значение $\forall x_i = 0$, поиск в диапазоне $n^2=10000$

Хочется узнать, насколько хорошо такую задачу решит качественный софт (интересует что-нибудь большее, чем отжиг, например, ГА).

Поэтому вопрос. Чем стоит воспользоваться, чтобы не особо мучиться с компилянием, чтением манов и т.д. Да, что-нибудь открытое/свободное хотелось бы, матлабом не владею.

Нашел в сети кучу поделий на эту тему, в виде Си-кода или скриптов для matlab (=> scilab), R и проч., но все они либо не работают, либо тестовая функция прибита в коде множеством гвоздей.

Хотелось бы что-нибудь такое, где можно просто вбить функцию и насладиться результатом. :)

 
 
 
 Re: софт для глобальной оптимизации
Сообщение28.06.2010, 17:33 
allchemist в сообщении #335831 писал(а):
оптимизируемая функция:
$f(\vec{x})=\sum\limits_{i=0}^n(x_i-1)^2 - \sum\limits_{i=1}^n(x_ix_{i-1})$,

min, max, minimax, maximin?

allchemist в сообщении #335831 писал(а):
стартовое значение $\forall x_i = 0$, поиск в диапазоне $n^2=10000$

$\forall i ~ x_i \in [0,10000]$?

 
 
 
 Re: софт для глобальной оптимизации
Сообщение28.06.2010, 18:20 
"MOPSO-CD" - такое было среди находок?

 
 
 
 Re: софт для глобальной оптимизации
Сообщение28.06.2010, 20:45 
В mathematica встроен очень хороший глобальный оптимизатор Minimize[]

 
 
 
 Re: софт для глобальной оптимизации
Сообщение28.06.2010, 21:18 
Аватара пользователя
dmd
минимизация. да, можно для примера ограничиться положительными числами, т.к. решений с отрицательными там не будет.

yk2ru
ух, он скомпилировался с первого раза, да еще и PSO :)
там надо вставлять свою функцию в заголовочный файл и добавлять ее в switch функции evaluate, так?

Андрей1
мои промытые и поgnuтые мозги отказываются воспринимать проприетарный софт, даже и доступный с торрентов :)
кстати, какой там метод используется?

 
 
 
 Re: софт для глобальной оптимизации
Сообщение29.06.2010, 12:06 
allchemist в сообщении #335831 писал(а):
$f(\vec{x})=\sum\limits_{i=0}^n(x_i-1)^2 - \sum\limits_{i=1}^n(x_ix_{i-1})$,
n - размерность вектора x (число аргументов), путь равно 100.

Заметьте, согласно формуле размерность задачи не $100$, а $101$.


allchemist в сообщении #335831 писал(а):
Хотелось бы что-нибудь такое, где можно просто вбить функцию и насладиться результатом. :)

Мат-ка
Код:
S={Sum[(x_i-1)^2,{i,0,100}]-Sum[x_i x_{i-1},{i,1,100}]};X={};
For[i=0,i<=100,i++,S=Join[S,{0<=x_i<=10000}];X=Join[X,{x_i}]];
NMinimize[S,X]

моментально даёт ответ
Код:
{-176750.,{x_0\to 101.,x_1\to 200.,x_2\to 297.,x_3\to 392.,x_4\to 485.,x_5\to 576.,x_6\to 665.,x_7\to 752.,x_8\to 837.,x_9\to 920.,x_{10}\to 1001.,x_{11}\to 1080.,x_{12}\to 1157.,x_{13}\to 1232.,x_{14}\to 1305.,x_{15}\to 1376.,x_{16}\to 1445.,x_{17}\to 1512.,x_{18}\to 1577.,x_{19}\to 1640.,x_{20}\to 1701.,x_{21}\to 1760.,x_{22}\to 1817.,x_{23}\to 1872.,x_{24}\to 1925.,x_{25}\to 1976.,x_{26}\to 2025.,x_{27}\to 2072.,x_{28}\to 2117.,x_{29}\to 2160.,x_{30}\to 2201.,x_{31}\to 2240.,x_{32}\to 2277.,x_{33}\to 2312.,x_{34}\to 2345.,x_{35}\to 2376.,x_{36}\to 2405.,x_{37}\to 2432.,x_{38}\to 2457.,x_{39}\to 2480.,x_{40}\to 2501.,x_{41}\to 2520.,x_{42}\to 2537.,x_{43}\to 2552.,x_{44}\to 2565.,x_{45}\to 2576.,x_{46}\to 2585.,x_{47}\to 2592.,x_{48}\to 2597.,x_{49}\to 2600.,x_{50}\to 2601.,x_{51}\to 2600.,x_{52}\to 2597.,x_{53}\to 2592.,x_{54}\to 2585.,x_{55}\to 2576.,x_{56}\to 2565.,x_{57}\to 2552.,x_{58}\to 2537.,x_{59}\to 2520.,x_{60}\to 2501.,x_{61}\to 2480.,x_{62}\to 2457.,x_{63}\to 2432.,x_{64}\to 2405.,x_{65}\to 2376.,x_{66}\to 2345.,x_{67}\to 2312.,x_{68}\to 2277.,x_{69}\to 2240.,x_{70}\to 2201.,x_{71}\to 2160.,x_{72}\to 2117.,x_{73}\to 2072.,x_{74}\to 2025.,x_{75}\to 1976.,x_{76}\to 1925.,x_{77}\to 1872.,x_{78}\to 1817.,x_{79}\to 1760.,x_{80}\to 1701.,x_{81}\to 1640.,x_{82}\to 1577.,x_{83}\to 1512.,x_{84}\to 1445.,x_{85}\to 1376.,x_{86}\to 1305.,x_{87}\to 1232.,x_{88}\to 1157.,x_{89}\to 1080.,x_{90}\to 1001.,x_{91}\to 920.,x_{92}\to 837.,x_{93}\to 752.,x_{94}\to 665.,x_{95}\to 576.,x_{96}\to 485.,x_{97}\to 392.,x_{98}\to 297.,x_{99}\to 200.,x_{100}\to 101.}}

но не уверен, глобальный ли оптимум она находит.

 
 
 
 Re: софт для глобальной оптимизации
Сообщение29.06.2010, 12:22 
Аватара пользователя
здорово, спасибо.

а расшифровать слегка можете?
что такое x_{}, \to, первая пятизначная цифра, ".,". это целые числа?
кстати, оптимизация проводилась на множестве целых чисел или с плавающей запятой? если с плавающей, то это крутой результат, я так понимаю.

 
 
 
 Re: софт для глобальной оптимизации
Сообщение29.06.2010, 13:36 
Первое число $-176750.$ - найденное значение целевой функции, дальше следуют значения составляющих оптимального вектора $\vec{x}$. На x_{}, \to не обращайте внимания, это специфичная форма ответа. В числах присутствует точка, следовательно они явно не целые.

 
 
 
 Re: софт для глобальной оптимизации
Сообщение29.06.2010, 13:43 
allchemist в сообщении #336024 писал(а):
ух, он скомпилировался с первого раза, да еще и PSO :)там надо вставлять свою функцию в заголовочный файл и добавлять ее в switch функции evaluate, так?

По аналогии вставить своё, и задать номер для переходов в операторах switch, также вроде границы задаются для переменных.

 
 
 
 Re: софт для глобальной оптимизации
Сообщение29.06.2010, 14:30 
У меня такое чуйство, что данная квадратичная форма - положительно определенная и локальный минимум совпадает с глобальным, т.е. оптимум найден.

 
 
 
 Re: софт для глобальной оптимизации
Сообщение29.06.2010, 21:18 
Аватара пользователя
ок, спасибо всем большое.

и такой вот еще вопрос, почти по теме.
есть ли какие-то более-менее стандартизованные модельные задачи для обкатки и тестирования алгоритмов глобальной оптимизации? мое гугл-фу практически не принесло результатов.

 
 
 
 Re: софт для глобальной оптимизации
Сообщение30.06.2010, 09:12 
Есть библиотека задач globallib - несколько сотен нелинейных задач с непрерывными переменными. Думаю что Вы ее найдете без труда. Часть задач имеют доказанные оптимумы.

Хорошо бы, чтобы был ресурс, куда действующие инженеры регистрировали бы свои задачи. Тогда бы разработчики могли ориентироваться на реальную жизнь, а не на выдуманные примеры. Пора бы нам уже организоваться...

 
 
 
 Re: софт для глобальной оптимизации
Сообщение30.06.2010, 17:41 
mserg в сообщении #336180 писал(а):
У меня такое чуйство, что данная квадратичная форма - положительно определенная и локальный минимум совпадает с глобальным, т.е. оптимум найден.

Видимо, да. В ampl + cplex аналогично решилось:
Код:
D:\amplcml>copy allch.mod con
set I := {0..100};
set J := {1..100};

var x {i in I}  >= 0, <= 10000;

minimize f:
         sum {i in I} (x[i]-1)^2 - sum {i in J} x[i]*x[i-1];
Скопировано файлов:         1.

D:\amplcml>ampl
ampl: model allch.mod;
ampl: option solver cplex;
ampl: solve;
CPLEX 11.2.0: optimal solution; objective -176750
9 QP barrier iterations
No basis.
ampl: display x;
x [*] :=
  0  101    15 1376    30 2201    45 2576    60 2501    75 1976    90 1001
  1  200    16 1445    31 2240    46 2585    61 2480    76 1925    91  920
  2  297    17 1512    32 2277    47 2592    62 2457    77 1872    92  837
  3  392    18 1577    33 2312    48 2597    63 2432    78 1817    93  752
  4  485    19 1640    34 2345    49 2600    64 2405    79 1760    94  665
  5  576    20 1701    35 2376    50 2601    65 2376    80 1701    95  576
  6  665    21 1760    36 2405    51 2600    66 2345    81 1640    96  485
  7  752    22 1817    37 2432    52 2597    67 2312    82 1577    97  392
  8  837    23 1872    38 2457    53 2592    68 2277    83 1512    98  297
  9  920    24 1925    39 2480    54 2585    69 2240    84 1445    99  200
10 1001    25 1976    40 2501    55 2576    70 2201    85 1376   100  101
11 1080    26 2025    41 2520    56 2565    71 2160    86 1305
12 1157    27 2072    42 2537    57 2552    72 2117    87 1232
13 1232    28 2117    43 2552    58 2537    73 2072    88 1157
14 1305    29 2160    44 2565    59 2520    74 2025    89 1080
;
ampl: exit;

 
 
 
 Re: софт для глобальной оптимизации
Сообщение01.07.2010, 15:07 
На сервере NEOS можно потестировать разные недогнутые солверы. Если исходную задачу сделать кубической, количество неизвестных увеличить до 10001, добавить 10000 нелинейных ограничений, то с такой задачей справятся только солверы KNITRO и LOQO.

 
 
 
 Re: софт для глобальной оптимизации
Сообщение01.07.2010, 20:06 
Аватара пользователя
спасибо всем большое.

> KNITRO и LOQO
а есть ли какие-нибудь свободные аналоги этих двух пакетов?

 
 
 [ Сообщений: 20 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group