2014 dxdy logo

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

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




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


20/12/08
236
изниоткуда
Хочу протестировать свой велосипед на тему глобальной оптимизации (роевые модели) на задачах большой размерности.

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

оптимизируемая функция:
$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 


16/08/05
1146
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 


03/10/06
826
"MOPSO-CD" - такое было среди находок?

 Профиль  
                  
 
 Re: софт для глобальной оптимизации
Сообщение28.06.2010, 20:45 


16/05/07
172
Москва
В mathematica встроен очень хороший глобальный оптимизатор Minimize[]

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


20/12/08
236
изниоткуда
dmd
минимизация. да, можно для примера ограничиться положительными числами, т.к. решений с отрицательными там не будет.

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

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

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


16/08/05
1146
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 
Аватара пользователя


20/12/08
236
изниоткуда
здорово, спасибо.

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

 Профиль  
                  
 
 Re: софт для глобальной оптимизации
Сообщение29.06.2010, 13:36 


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

 Профиль  
                  
 
 Re: софт для глобальной оптимизации
Сообщение29.06.2010, 13:43 


03/10/06
826
allchemist в сообщении #336024 писал(а):
ух, он скомпилировался с первого раза, да еще и PSO :)там надо вставлять свою функцию в заголовочный файл и добавлять ее в switch функции evaluate, так?

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

 Профиль  
                  
 
 Re: софт для глобальной оптимизации
Сообщение29.06.2010, 14:30 


17/10/08

1313
У меня такое чуйство, что данная квадратичная форма - положительно определенная и локальный минимум совпадает с глобальным, т.е. оптимум найден.

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


20/12/08
236
изниоткуда
ок, спасибо всем большое.

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

 Профиль  
                  
 
 Re: софт для глобальной оптимизации
Сообщение30.06.2010, 09:12 


17/10/08

1313
Есть библиотека задач globallib - несколько сотен нелинейных задач с непрерывными переменными. Думаю что Вы ее найдете без труда. Часть задач имеют доказанные оптимумы.

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

 Профиль  
                  
 
 Re: софт для глобальной оптимизации
Сообщение30.06.2010, 17:41 


16/08/05
1146
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 


16/08/05
1146
На сервере NEOS можно потестировать разные недогнутые солверы. Если исходную задачу сделать кубической, количество неизвестных увеличить до 10001, добавить 10000 нелинейных ограничений, то с такой задачей справятся только солверы KNITRO и LOQO.

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


20/12/08
236
изниоткуда
спасибо всем большое.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group