2014 dxdy logo

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

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





Начать новую тему Ответить на тему
 
 Выражение для оценки равномерности расстановки 2 видов точек
Сообщение17.07.2016, 12:48 


17/07/16
1
Есть два вида точек на плоскости: добывающие скважины и нагнетательные скважины.
Т.е. у каждой точки есть три свойства: координата Х, координата Y и тип (принимающий два значения).

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

В идеале максимум целевой функции (при заданном количестве точек в соотношении типов 3 к 1) должна давать при расположении как на картинке:

Изображение

Искомое выражение будет использоваться как целевая функция в генетическом алгоритме, который будет расставлять скважины в области. Помимо равномерности, есть и другие условия (свойства пласта), с которыми то всё более менее ясно, но первая часть задачи состоит в том, чтобы предполагая полностью однородный пласт получать равномерную расстановку.

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

Изображение

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

Изображение

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

$Value=R/(R+b)$
где R - расстояние до ближайшей скважины, а b - положительная постоянная.

Такой подход также приводит к неверным решениям (по всей видимости из-за неустойчивости):

Изображение

 Профиль  
                  
 
 Re: Выражение для оценки равномерности расстановки 2 видов точек
Сообщение17.07.2016, 20:30 
Заслуженный участник


10/01/16
1256
Gomez в сообщении #1138399 писал(а):
В идеале

Ну и прекрасно! Возьмите прямо эту картинку (гексагональная решетка, да?), отмасштабируйте - чтоб заданное число черно-белых точек было - и всуньте в свою область...
Gomez в сообщении #1138399 писал(а):
все точки стремятся к краям области,

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

 Профиль  
                  
 
 Re: Выражение для оценки равномерности расстановки 2 видов точек
Сообщение17.07.2016, 20:44 
Модератор
Аватара пользователя


09/05/12
10507
Кронштадт
DeBill в сообщении #1138507 писал(а):
Добавьте в целевую функцию штраф (обратный квадрат расстояния до каждой из границ - верт. и гориз. - с коэф-том. Его надо подбирать, но, думаю, надо 2. Или полтора? )
Возможно, проще будет рассматривать расстановку на торе: "склеив" у области верх с низом, а правый край - с левым.

 Профиль  
                  
 
 Re: Выражение для оценки равномерности расстановки 2 видов точек
Сообщение18.07.2016, 22:19 


25/03/11
66
Задача очень близка к технологии печати серого фона из черных точек: blue noise pattern
Там масса всего опробовано в этой области. Например:
http://www.hpl.hp.com/research/isl/halftoning/publications/DitheringWithBlue.pdf

Т.е. задача сводится к генерации двумерного массива точек со свойствами синего шума. Общее количество точек равно требуемому общему количеству скважин. Затем поверх накладывается другой массив с общим количеством точек равного только одному типу скважин. Далее для каждой точки из второго массива находится ближайшая точка из первого. Таким образом первый массив разбивается на совокупность двух видов точек.

 Профиль  
                  
 
 Re: Выражение для оценки равномерности расстановки 2 видов точек
Сообщение11.12.2016, 01:05 
Аватара пользователя


01/06/12
755
Adelaide, Australia
Перепробовал несколько функций. Вроде что то подходящее нашел но она не очень красивая. Для каждой точки я нахожу расстояние до ближайшей точки такого же типа (А) и расстояние до ближайшей точки другого типа (B). Для функции беру $10A+B$ с каждой точки. Расстояние считаю через manhattan: $d(a,b)=|a.x-b.x|+|a.y-b.y|$. Вот пример решения:

Изображение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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