Comments | dobroslav: Алгоритмы глобальной оптимизации

dobroslav

Алгоритмы глобальной оптимизации

Feb 06, 2015 11:54

По работе (в области оптимального управления квантовыми системами) потребовалось написать коды алгоритмов глобальной оптимизации: имитации отжига и дифференциальной эволюции (разновидность генетического алгоритма), т.к. средства, предоставляемые системой Wolfram Mathematica, меня устраивали неполностью. Пришлось тряхнуть стариной и вспомнить, что ( Read more... )

наука

Comments 9

mns2012 February 6 2015, 10:09:32 UTC

А этот симплекс-метод точечный? Может, он просматривает не одну, а более окрестностей параллельно. Я встречался с такими роевыми алгоритмами. Есть еще методы больших окрестностей: когда модифицируются большие области решений за один шаг поиска. Например, обычный алгоритм оптимизации расписания переставляет одну операцию за один шаг, а алгоритм просмотра большой окрестности, манипулирует сразу несколькими операциями. Выгода в том, что намного дальше можно просмотреть, в сильно упакованных расписаниях вообще может быть невозможно вытащить одну операцию и переставить ее в другое место, тогда как манипуляции с бОльшим числом операций создают больше возможностей модификации имеющегося решения. Но минус в том, что бОльше требуется вычислительных ресурсов.

dobroslav February 6 2015, 11:42:30 UTC

Если симплекс маленький, то практически да точечный. Если большой, то, соответственно, нет. Справочная система "Математики" сообщает, что несмотря на то, что это метод поиска локального экстремума, при определённых настройках (например, если симплекс сделать большим, чтоб перешагивал через локальные экстремумы, разрешить растягиваться), он может найти и глобальный экстремум. Но мне-то как раз нужен ближайший локальный. Поэтому я сам задаю начальный симплекс, делаю его очень маленьким (много меньше размера склона, на котором он находится), запрещаю растягиваться. По логике алгоритма он должен взобраться по склону и остановиться. Но решение он выдаёт в другом месте (в одномерном случае я могу нарисовать график и посмотреть весь ландшафт ( ... )

mns2012 February 6 2015, 11:51:40 UTC

А Вы не пробовали протестировать на сравнительно маленьких тестовых примерчиках? Конечно, неприятно, когда приходится пользоваться черным ящиком.

mns2012 February 6 2015, 11:57:28 UTC

Кстати, можно было бы еще посмотреть, какие данные доступны оператору шага поиска. Если есть что-то типа памяти нескольких предыдущих шагов вроде табу-списка, то можно попытаться как-то настроить ее, обнулить если она не нужна, то есть если не нужно искать лучший из нескольких оптимумов, а остановиться на первом подвернувшемся. Я бы поискал в мануале что-нибудь типа жадного режима. Наверняка это можно, если алгоритм такой умный.

Thread 6

mns2012 February 6 2015, 10:13:33 UTC

Еще можно посмотреть, footprint Вашей программы и стандартной. Стандартная, вероятно, много более эффективна. Очень сильно это может зависеть от используемых структур данных и прочих наворотов.

dobroslav February 6 2015, 11:44:41 UTC

А что такое footprint? Шаги выполнения алгоритма? Тут у меня не хватает знаний системы Mathematica, чтобы их выудить. Справочная система у них неплохая для ознакомления, но обо всех возможностях она не сообщает.

mns2012 February 6 2015, 11:49:31 UTC

Это сколько памяти жрет программа. Есть стандартные средства профайлинга. Например, я, программируя на яве, пользовался средствами IDE NetBeans. Есть еще IDE Eclipse, там тоже можно это делать. Виндоузовый Task Manager показывает то же, только не детально, а интегрально по всему приложению. Наверняка есть средства профайлинга, применимые в Вашем случае. Правда, я не знаю, как это будет выглядеть без доступа к исходнику, в случае стандартной программы.