Диссертация (1137145), страница 15
Текст из файла (страница 15)
46. Алгоритм Табу-поиска решений предложенной моделиАлгоритмnumber _ of _ stepsTaboo.имеетдвапараметра:number _ of _ failsиПервый параметр используется в условии остановки.Подсчитывается сколько шагов подряд не может улучшить текущеерешение. Алгоритм останавливается, если число подряд шагов безулучшения решения превышает этот параметр number _ of _ fails . Второйпараметр соответствует числу разрешённых циклов, при добавлении рёбериз запрещённого списка (табу списка).На каждой итерации алгоритм пытается найти такое ребро, удаление илидобавление которого, позволяет улучшить текущее решение. МножествоE ' содержит все такие рёбра.
В момент формирования множества E ' ,исключается использование рёбер, которые находятся в табу-списке, тогдаи только, когда из использование не приводят к улучшению решения.Когда алгоритм обнаруживает локальный минимум, то он сравниваетсяс глобальным, если текущее решение лучше найденного глобального100минимума, то глобальным минимум обновляется, в другом случаеалгоритм начинает подсчитывать количество шагов без улучшениярешений, увеличивая переменную fails.
Если выполняется условиеостановки, алгоритм завершает свою работу, в другом случае алгоритмначинает новую итерацию, добавляя ребро в табу список, которое будетхранитсятамвтеченииколичествошаговравнымпараметруnumber _ of _ steps .4.4 Результаты вычислительных экспериментовНиже на рисунках 47, 48, 49 приведены результаты найденныхэвристическималгоритмомTabooдляслучая,когдаэлементырасполагаются на прямой. Соответственно, на рисунках 50-53 приведенырешения для случая когда элементы располагаются в два столбца. Вкачестве функции расстояния в обоих случая использовалась метрика L2 .Точные решения для точек регулярной решётки размером 4x4 дляфункций расстояния L2 , L1 , L∞ приведены на рисунке 54. Эвристическиерешения приведены на рисунках 55, 56. Во всех случаях на рисункахзначение целевой функции обозначалось символом f10111222222222222222211221x4 f=2,6251x5 f=3.081x6 f=3.44421x7 f=3.775222222222222222222222222221x8 f=4.1251x9 f=4.4571x10 f=4.8332223232323332223332231x11 f=5.0831x12 f=5.3193322222333322222333322222331x13 f=5.5681x14 f=5.821Рис.
47. Решения и значения целевой функции f найденный алгоритмом Табу-поискадля целочисленной решётки 1x4,5,…141023222332223322231x15 f=6.05832223322223322231x16 f=6.316132223222223222311x17 f=6.64Рис. 48. Решения и значения целевой функции f найденный алгоритмом Табу-поискадля целочисленной решётки 1x15,16,17103332233322232233222232322223322322233322331x41 f=10.1874223322243223332224322342223332234222332241x42 f=10.07Рис. 49. Решения и значения целевой функции f найденный алгоритмом Табу-поискадля целочисленной решётки 1x41,1x4210422223222333333333333333222222x2 f=2.752x3 f=3.722333333333332z4 f=4,656333344334433332x5 f=5.34333344333344333332x6 f=5.9722x7 f=6.5612x8 f =7.031444433334444444433334433444433444433442x9 f=7.4382x10 f=7.8544553344333344443344553355443344443333334444552x11 f=8.332x12 f=8.753Рис.
50. Решения и значения целевой функции f найденный алгоритмом Табу-поискадля целочисленной решётки 2x2,3,…,121055533444433333344443333335555553333334444333333444433552x13 f=9.1712x14 f=9.591554444443333333344443333334455555544333333444433333344553344442x15 f=9.9442x16 f=10,37555554433444433445544334444334455552x17 f=10.727Рис. 51. Решения и значения целевой функции f найденный алгоритмом Табу-поискадля целочисленной решётки 2x13,15,…,171065555443344443333555533334444334455552x18 f=11.145556644444433444444334444443344444466552x19 f=11.42544553333443344444433334444443344333355442x20 f=11.814Рис. 52.
Решения и значения целевой функции f найденный алгоритмом Табу-поискадля целочисленной решётки 2x18,19,201075555334444334444443333334444443344443355552x21 f=12.078335533443333443344333333334433443333443355332x22 f=12.710Рис 53. Решения и значения целевой функции f найденный алгоритмом Табу-поискадля целочисленной решётки 2x21,22108(a)L2 ,f ≈ 7.093(b)L1 , f ≈ 7.039(c)L∞ ,f ≈ 7.203Рис. 54. Точные решения полученные с помощью метода ветвей и границ длярегулярной решётки 4x4(a)L2 ,f ≈ 8.974(b)L1 , f = 8.784(c)L∞ ,f ≈ 9.036Рис. 55. Решения найденные с помощью эвристического алгоритма для узловрегулярной решётки 5x5(a)L2 ,f ≈ 10.509(b)L1 , f ≈ 10.485(c)L∞ ,f ≈ 10.756Рис. 56.
Решения найденные с помощью эвристического алгоритма для узловрегулярной решётки 6x61094.5 ВыводыПриведенные решения модели для некоторых частных случаев являютсятолько первым шагом в исследовании свойств оптимальных структур.Предложенная модель не претендует на эффективный способ построениясетевых структур пригодных для быстрого поиска децентрализованнымалгоритмом, но она главным образом демонстрируют идею существованиядля фиксированного алгоритма поиска и для фиксированного множестваобъектов с функцией расстояния оптимальной конфигурации рёберграфа с точки зрения вычислительной сложности алгоритма поиска .Главный вклад предложенной модели заключается в том, что онапозволяет рассматривать алгоритмы построения структур для поиска,затронутые в предыдущих главах, в качестве эвристик, предлагаетинструмент для оценки того, насколько эвристические решения далеки отоптимальных, открывает возможность для исследования и создания болееэффективных алгоритмов построения сетевых структур ориентированныхна поиск.110Глава 5.
Архитектура программной платформы дляисследования свойств распределённых алгоритмов дляпоиска в метрическом пространствеIt is better to have 100 functions operate onone data structure than 10 functions on 10 datastructures.(Alan J. Perlis, Yale UniversitySIGPLAN Notices Vol. 17, No. 9, September 1982, pages 7 - 13)Чтобы исследовать свойства алгоритмов предложенных во второй главе,была создана программная платформа для проведения численныхэкспериментов со структурами данных предназначенных для поиска вметрических пространствах на языке программирования java версии1.8.0_74.
Код платформы находится в Интернете в открытом доступе поадресуhttp://aponom84.github.io/MetrizedSmallWorld/алгоритмы.ПредложенныеMSWConstruction, K-NNSearch, СonstuctionByReparing былиреализованы в рамках данной программной платформы.C моделировать для алгоритмов условия распределенного оборудованиябыло одним из требований, которое учитывалось, при проектированиеархитектуры классов данной программной платформы. Испытываемымалгоритмам создавались такие условия, при которых они не имели доступкинформацииопроизвольныхчастяхсети.Алгоритмымоглииспользовать только локальную информацию о структуре известной имсети, т.е.
только такого множества узлов, чьи идентификаторы сталиизвестны в течении одногосеанса работы испытуемого алгоритма,например, алгоритма поиска или добавления. Далее в этой главеобсуждаются детали и архитектура этой программной платформы.1115.1 Базовый абстрактный класс MetricElementБазовой логической единицей данной программной платформы являетсяабстрактный класс MetricElement. Он занимает центральное место виерархии классов. Класс воплощает в себе две идеи. Во-первых онреализует идею некоторого элемента пространства , снабженногонекоторой функцией расстояния : × → ! . Во-вторых,MetricElementклассвоплощает идею автономного узла сети, который посредством нижележащего транспортного протокола, например tcp/ip, знаяидентификатор другого узла, имеет возможность коммуницировать с ним.Вторая идея выражена в программном коде за счёт того, что классMetricElement хранит список ссылок на объекты этого же класса.private final List<MetricElement> friends;Чтобы иметь возможность параллельной работы с графом этот списокинициализируется как покобезопасный двусвязный список (список«друзей»)public MetricElement() {friends = Collections.synchronizedList(new ArrayList());}Первая идея реализуется за счёт того, что в классе MetricElement естьпубличный метод calcDistance, который на вход принимает объект этогоже класса и возвращает вещественное числоabstract double calcDistance(MetricElement gme)Кроме того, данный класс содержит вспомогательные методы:public synchronized List<MetricElement> getAllFriends()возвращает список элементов окрестности (список смежных вершин);public MetricElement getClosestElemet(MetricElement q)возвращает из окрестности ближайший элемент к элементу q;public synchronized void addFriend(MetricElement e)позволяет добавлять в окрестность новый элемент;public synchronized void removeFriend(MetricElement e)удаляет элемент e из окрестности;112public synchronized void removeAllFriends()удаляет все элементы из окрестности.5.2 Интерфейс MetricElementFactoryДругойважнойабстракциейкотораяпозволяетсделатькоднезависимым от конкретного вида метрического пространства т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
