IX Международная студенческая научная конференция Студенческий научный форум - 2017

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

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

Современные стохастические эвристические методы оптимизации, основанные на поведении различных живых существ, не гарантируют получение точного результата, но они, как правило, позволяют максимально приблизиться к этому значению для практического использования за приемлемое время.

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

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

Использование цепей Маркова позволяет доказать сходимость рассматриваемых алгоритмов к глобальному оптимуму только теоретически, при устремлении времени работы к бесконечности, однако, такой подход не объясняет показанную в многочисленных экспериментах высокую эффективность рассматриваемых стохастических алгоритмов оптимизации для решения задач с ограничением по времени. Рассматриваемые алгоритмы называют алгоритмами дискретной оптимизации, поскольку они работают пошагово, по итерациям, а не непрерывно.

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

Алгоритм имитации отжига возник в середине 1980-х годов, его основатели: Скотт Киркпатрик, Даниель Желатт, Марио Вечи и Владо Церни [1]. Алгоритм основан на аналогии с процессом кристаллизации вещества, например, при отжиге металла. В ходе этого процесса температура вещества понижается, оно отвердевает, при этом замедляется скорость движения частиц вещества.

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

Алгоритм имитации отжига прост в реализации и показывает высокую эффективность в решении самых разных задач оптимизации [1]. Однако для получения высокой эффективности может потребоваться тщательная настройка формулы понижения температуры как численных параметров, так и самого вида зависимости, кроме того, часто температуру меняют не на каждой итерации алгоритма, а через определенное число итераций.

Генетический алгоритм. Впервые компьютерным моделированием эволюционного отбора занялся Нильс Баричелли в 1954 году. Признание генетического алгоритма как метода решения оптимизационных задача произошло в 1960–70 годах в результате работ Инго Рехенберга и Джона Голланда[2]. Генетический алгоритм (ГА) относится к стохастическим методам и основан на принципе естественного эволюционного отбора. Идея

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

Основной идеей ГА является борьба за существование между решениями задачи [2]. Каждое решение записывается в виде некоторого вектора значений (аллелей), который называется хромосомой, или особью. Совокупность решений называют популяцией. Каждая особь в популяции оценивается значением целевой функции, рассчитанной на основе значений из хромосомы. Более перспективные решения проходят в следующую стадию и оказывают влияние на «потомство», т. е. на вновь генерируемые решения.

Алгоритм роя частиц. Специалист в области компьютерной графики Крейг Рейнольдс создал в 1986 году компьютерную модель для визуальной имитации поведения стаи птиц, основанную на том, что движение каждой птицы описывается рядом простых правил, связанных с ориентацией на

остальных птиц стаи. Модель заинтересовала ученых и в 1995 году Джеймс Кеннеди и Рассел Эберхарт предложили метод для оптимизации непрерывных функций, названный ими алгоритмом роя частиц [3].

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

Основная идея метода заключается в перемещении частиц в пространстве решений. Пусть решается задача нахождения минимума (максимума) функции вида f(X), где X – вектор варьируемых параметров, которые могут принимать значения из некоторой области D. Тогда каждая частица в каждый момент времени характеризуется значением параметров X из области D (координатами точки в пространстве решений) и значением оптимизируемой функции f(X) (привлекательностью данной точки). При этом частица «помнит» наилучшую точку в пространстве решений, в которой была, и стремится в нее вернуться, но подчиняется также закону инерции и имеет склонность к небольшому стохастическому изменению направления движения. Однако этих правил недостаточно для перехода к системе, так как не заданы связи между элементами. В качестве связи используется так называемая общая память, благодаря которой каждая частица знает координаты наилучшей точки среди всех, в которых была любая частица роя.

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

Алгоритм колонии муравьев основан на модели, симулирующей процесс поиска муравьями кратчайших путей от муравейника до источников пищи, и разработан М. Дорино в 1990-е годы [4,5]. Муравьи решают задач поиска путей с помощью химической регуляции. Каждый муравей оставляет за собой на земле дорожку особых веществ – феромонов. Другой муравей, почуяв след на земле, устремляется по нему. Чем больше по одному пути прошло муравьев, тем заметнее для них след, а чем более заметен след, тем большее желание пойти в ту же сторону возникает у муравьев. Поскольку муравьи, нашедшие самый короткий путь к «кормушке», тратят меньше времени на путь туда и обратно, их след быстро становится самым заметным. Он привлекает большее число муравьев, таким образом, процесс поиска более короткого пути быстро завершается. Остальные пути – менее используемые – постепенно пропадают. Можно сформулировать основные принципы взаимодействия муравьев: случайность, многократность, положительная обратная связь. Так как каждый муравей выполняет примитивные действия, то и алгоритм получается очень простым и сводится к многократному обходу некоторого графа, дуги которого имеют не только вес, но и дополнительную динамически меняющуюся количественную характеристику, называемую количеством феромона или просто феромоном.

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

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

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

Список используемой литературы:

1) Карпенко А.П. Популяционные алгоритмы глобальной оптимизации.

Обзор новых и малоизвестных алгоритмов // Приложение к журналу «Информационные технологии». – 2012. – № 7. – С. 1–32.

2) Матренин П.В. Секаев В.Г. Системное описание алгоритмов роевого интеллекта // Программная инженерия. – 2013. – № 12. – С. 39–45.

3) Курейчик В.М. Использование роевого интеллекта в решении NP-трудных задач/ В.М. Курейчик, А.А. Кажаров // Известия ЮФУ. Технические

науки. – 2011. – № 7 (120). – С. 30–37.

4) Матренин П.В., Секаев В.Г. Оптимизация адаптивного алгоритма муравьиной колонии на примере задачи календарного планирования // Программная инженерия. – 2013. – № 4. – С. 34–40.

5) Карпов В.Э. Методологические проблемы эволюционных вычислений //Искусственный интеллект и принятие решений. – № 4. – 2012. – C. 95–102.

6) Матренин П.В. Описание и реализация алгоритмов роевого интеллекта с использованием системного подхода // Программная инженерия. – 2015. –№ 3. – С. 27–34.

Код для цитирования: Скопировать