Устойчивая конфигурация N частиц

[poisonous]

Помогите пожалуйста. У меня есть некий набор из N точек с координатами (x,y). Задан парный потенциал взаимодействия. Нужно определить таку конфигурацию точек, чтобы энергия была минимальной. Я пробовала сделать это методом локальных вариаций, т.е. немного меняла координаты x и y и смотрела, где энергия меньше, заменяла координаты. Но, похоже, этим методом можно найти только локальный минимум, а нужен - глобальный. Что же делать?(

[paha]

Минимизируя $E=\sum U_{ij}$ получим $2N$ уравнений на $2N$ координат. В общем положении имеется конечное множество решений.

Может быть в Вашей задаче можно сразу дать оценку $E\ge E_0$ и указать экстремальную конфигурацию.

[мат-ламер]

В статье Википедии про метод Нелдера-Мида говорится "Более развитый подход к исключению локальных экстремумов предлагается в алгоритмах, основанных на методе Монте-Карло, а также в эволюционных алгоритмах." А про алгоритм имитации отжига - "Алгоритм имитации отжига похож на градиентный спуск, но за счёт случайности выбора промежуточной точки должен будет попадать в локальные минимумы реже, чем градиентный спуск." Вероятно, для Вашей задачи есть специальные методы, лучше приспособленные для многоэкстремальности. Но в общем случае это задача сложная. Попробуйте поэкспериментировать с методом имитации отжига (Метрополиса). Я его не знаю. Подробности Вам выдаст Гугл.

[ИСН]

Сколько атомов тянет алгоритм? Получаются ли канонические конфигурации для N=3 и 4?

А потом, если с этим всё уже хорошо, то понимаете... Вот человек решает диффур. Ракета у него там летит или что-нибудь. Трудности могут быть такие и сякие, но есть один неубиваемый аргумент - "ведь природа же как-то это решает". То есть в природе ракета как-то летит. Вряд ли она зависнет в воздухе (в реале) от вычислительных трудностей
Так вот, Ваша задача другая - её природа не решает. Она тоже заезжает в локальный минимум и не парится.

[poisonous]

Нет, он не хочет работать для 3 частиц, т.е. Получается равнобедренный треугольник, а не равносторонний. Я вот подумала, может можно как-то резко потом увеличить шаг и тем самым выпрыгнуть из локального минимума? Но критерий сходимости я тогда не могу придумать(

[ИСН]

Блин. Я же говорил: это не минимум вообще. Проверьте руками, если не верите на слово. (Написать функцию, взять производную, сравнить с нулём.) У Вас нет метода поиска минимума. Надо написать такой метод. Сначала. А потом всё остальное.

[poisonous]

Метод градиентного спуска подойдет?

[ИСН]

Можно и такой. Да неважно какой. Лишь бы работало.

[Circiter]

2poisonous
А я бы соединил бы точки пружинками с жесткостью зависящей от потенциала... :) Точки можно зарядить, а саму систему положить в вязкую среду... Иногда это дает неплохие результаты. Например, надо мне было как-то равномерно распределить точки по сфере, ну я недолго думая построил пружинную систему... и остался доволен. :)

[мат-ламер]

Цитата:

А я бы соединил бы точки пружинками с жесткостью зависящей от потенциала... :)

Очень правильно. Это примерно эквивалентно методу тяжёлого шарика.

Цитата:

У Вас нет метода поиска минимума. Надо написать такой метод. Сначала.

Ну, можно и не писать, а взять готовый метод, например, в МатЛабе. Там как раз есть демо-пример с атомами. Градиентный метод сходится медленно. Если будете сами программировать, то уж лучше метод Ньютона. Причём запускайте его многократно с разных начальных точек, чтобы найти побольше локальных минимумов.

[poisonous]

Но ведь метод Ньютона может не сойтись.

[Circiter]

2poisonous

Цитата:

Но ведь метод Ньютона может не сойтись.

Может быть именно поэтому мат-ламер говорил о многократном запуске такой оптимизации из различных начальных точек... :)

[poisonous]

Может я что-то не так понимаю? Для реализации метода градиентного спуска для 3 частиц я в качестве координат беру расстояния между частицами и потенциальная энергия записывается в виде $U=\frac{1}{x^{12}}-\frac{1}{x^6}+\frac{1}{y^{12}}-\frac{1}{y^6}+\frac{1}{z^{12}}-\frac{1}{z^6}$, используя потенциал Леннарда-Джонса. И ищу минимум. Но он не работает. $\lambda$ из метода я беру изначально маленькой, а потом делю пополам. Может я саму функцию не ту беру? Не понимаю...

[мат-ламер]

В качестве независимых переменных можно выбрать координаты трёх частиц - всего 9 координат. Потенциальная энергия - сумма трёх членов - описывает взаимодействие каждой из частиц с каждой. В знаменателях дробей - расстояния между частицами в соответствующих степенях. Может Вы попробуете выписать тут формулу для потенциальной энергии? Применение градиентного метода даже для трёх частиц выглядит сомнительным, ну попробуйте.

[ИСН]

Функция правильная. Плохой либо метод, либо конкретная реализация.