Вопрос 32. Алгоритм капель воды

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

В IWD алгоритме, несколько искусственных капель воды, которые зависят друг от друга, способны менять свое окружение таким образом, что находят оптимальный путь по пути наименьшего сопротивления. IWD алгоритм – это конструктивный популяционно- ориентированный алгоритм оптимизации.

В природе капли воды наблюдаются в основном в реках, где они образуют огромные массы (рои капель воды). Пути, которыми текут природные реки, были созданы роями из капель воды. Для роя капель воды, реки, в которых они протекают, являются частью окружающей среды, которая была значительно изменена роем, а также будет изменена в будущем. Более того, сама среда оказывает существенное влияние на пути следования капель воды. Им оказывают сопротивление берега реки. Например, рою капель воды сопротивляются больше те части окружающей среды, из которых состоит жесткий грунт, чем части из мягкого грунта. Естественное русло реки является результатом конкуренции между каплями воды и окружающей средой, которая оказывает сопротивление движению капель воды.

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

Три очевидных изменения произойдет в течение этого переходного периода: – скорость капли воды увеличивается; – насыщенность грунтом капли воды увеличивается; – между этими двумя точками, количество грунта в русле уменьшается.

Почва русла удаляется каплями воды, добавляясь в почву, которую переносит эта капля. Кроме того, скорость капли воды увеличивается в переходный период. Выше было отмечено, что каждая капля воды имеет свою скорость. Эта скорость играет важную роль в сборе почвы от русла реки.

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

Скорость капли воды возрастает на пути с низким уровнем почвы больше, чем на пути с высоким уровнем почвы. Таким образом, путь с небольшим количеством почвы позволяет текущей капле воды собрать больше почвы и получить большую скорость, в то время как путь с большими уровнями грунта приводит к уменьшению скорости. Ещё одно свойство природных капель воды – выбор лёгкого пути.

Основные принципы: – капля воды предпочитает путь с меньшим количеством почвы, чем пути с большим количеством почвы; – капля воды предпочитает более лёгкий путь, когда приходится выбирать между несколькими маршрутами, которые существуют на пути от источника к месту назначения; – лёгкость или твёрдость пути определяется количеством почвы на этом пути. Путь с большим уровнем почвы считается трудным путем, тогда как путь с меньшим уровнем почвы считается лёгкий путем. Алгоритм интеллектуального движения капель воды, формируется следующим образом. Каждая капля воды (IWD) обладает двумя важными свойствами: – находящийся в ней грунт обозначают уровнем грунта (МЗ); – скорость, которой она обладает, называется скоростью (МЗ).

Для каждого IWD, значение и свойства почвы и скорости может смениться другими IWD в его окружении. С инженерной точки зрения, среда представляет собой проблему, которая должна быть решена. Река с потоком (роем) IWDs ищет оптимальный путь для данной проблемы.

Каждый IWD предполагает движение от источника к месту назначения. В окружающей среде существует множество путей от данного источника к месту назначения. Место назначения может быть неизвестно. Если местонахождение искомого назначения известно, то для решения проблемы необходимо найти лучшие (часто кратчайшие) пути каждой капли от источника к месту назначения.

IWD алгоритм использует ряд IWDs, чтобы найти оптимальное решение данной проблемы, представляющей собой граф (N, E) с набором узлов N и множеством рёбер E. Этот граф является средой для IWDs и их потока по рёбрам графа.

Каждый IWD начинает строительство своего решения постепенно, путешествуя между узлами графа пока, наконец, не завершает её решения. Одна итерация IWD алгоритма завершается, когда все IWDs завершили свой проход по рёбрам графа. После каждой итерации, находится лучшее решение T – это лучшее решение на основе функции качества среди всех решений, полученных IWDs в текущей итерации. T используется для выполнения следующих итераций. Лучшее решение Т – это лучшее решение с начала работы IWD алгоритма, которое было найдено во всех итерациях.

IWD алгоритм можно применить для решения 4х задач: – TSP (Задача коммивояжера); – задача Н ферзей; – MKP (многомерная задача о ранце); – AMT (автоматический многоуровневый порог).