Математичні моделі в задачах організації та планування вантажних перевезень

Размещено на http://www.allbest.ru/

Вступ

В останні роки в багатьох галузях народного господарства для раціональної організації виробництва і виконання виробничих завдань широко застосовується системний підхід. При такому підході організація окремих етапів виробництва повинна розглядатися з точки зору їх впливу на ефективність усього виробництва в цілому. Організація автомобільних перевезень вантажів(задача комівояжера, задача про розподіл транспортних засобів за грошовими витратами) не є виключенням: комплексний характер сучасних досліджень з організації даних процесів істотно відрізняє їх від концепції досліджень минулого століття.

Тільки оптимальний розподіл матеріальних, трудових і фінансових ресурсів між усіма складовими може гарантувати найвищу ефективність процесу в цілому. Оптимальна організація окремих етапів не є умовою оптимальності всього процесу. Однак уміння визначати оптимально можливі результати на будь-якому етапі дозволяє забезпечити дослідників і виробників важливим критерієм для оцінки впливу цього етапу на ефективність усього процесу. Тому проблема оптимізації кожного етапу управлінського процесу завжди буде залишатись актуальною, але не завжди визначальною.

Для підвищення ефективності процесу транспортних перевезень у тому числі і автомобільних, процесу призначення робіт між працівниками застосовують формальний(науково-обгрунтований) або евристичний підхід. Такий підхід не гарантує найбільш вдалого використання транспортних, трудових ресурсів або отримання максимального економічного ефекту від процесу взагалі.

Зовсім інші результати забезпечує науковий підхід. Саме він використовує математичні моделі та методи пошуку оптимальних параметрів процесу управління, що гарантують максимальний економічний ефект. Крім наукового та евристичного підходу, може бути застосований змішаний підхід, коли організація деяких етапів будуються на евристичному підході, деякі - на формальному. Кожний із цих підходів може бути визначальним при організації транспортного процесу та процесу призначення або бути присутнім поряд з іншими. Математичні моделі багатьох задач управління (зокрема і вищеприведені) описуються задачами з бульовими змінними. З іншого боку реальні задачі управління є складними і вимагають одночасного розгляду багатьох критеріїв, що приводить для їх розв'язання методів багатокритеріальної оптимізації.

Актуальність роботи. Транспорт - одна із найважливіших галузей народного господарства будь-якої країни. Він забезпечує розвиток всіх видів виробництва, просування товарів до споживачів, задовольняє потреби населення в перевезеннях. Реалізуючи основну частину зовнішньо-економічних зв'язків, транспорт сприяє міжнародному розподілу праці.

Розв'язання цих та інших науково-прикладних задач вимагає формування відповідних організаційних і функціональних структур на регіональному та державному рівнях, які повинні взяти на себе виконання функцій, пов'язаних із організацією роботи різних видів транспорту як по горизонталі (різні види транспорту), так і по вертикалі (виробничий, регіональний та державний рівні).

Метою роботи є розглянути математичні моделі задач організації та планування вантажних перевезень, розробити програмну реалізацію методу потенціалів для їх розв'язання , та проаналізувати отримані результати.

Дана робота складається із вступу, теоретичної, практичної частин та висновків.

В теоретичні частині розглянуто змістовні і математичні постановки задач: про вибір маршруту, про розподіл транспортних засобів за грошовими витратами з булевими змінними та метод потенціалів.



1. ТЕОРЕТИЧНА ЧАСТИНА

1.1 Математичні моделі в задачах організації та планування вантажних перевезень

Серед усіх етапів планування транспортних перевезень етапи «моделювання процесу перевезень» і «розв'язання транспортної задачі» залишаються центральними. Пояснюється це тим, що моделювання процесу перевезення з наступним визначенням оптимального розподілу наявних об'ємів вантажу у постачальників між одержувачами дозволяє не тільки повною мірою забезпечити вимоги останніх, але і зробити це з мінімальними витратами. Іншими словами, такий підхід дозволяє «на папері»

дістати прибуток, що втрачається при евристичному або інтуїтивному плануванні перевезень. При цьому аналітичні методи пошуку раціональних варіантів дозволяють уникнути процесу прямого перебору варіантів.

Як бачимо, всі задачі за співвідношенням кількості постачальників (пунктів відправлення) та кількості замовників (пунктів призначення) підрозділяються на чотири типи:

«один-до-одного»;

«один-до-багатьох»;

«багато-до-одного»;

«багато-до-багатьох».

Всі задачі організації перевезень можна розподілити також за їх призначенням. Так, для задач типу «один-до-одного» це:

вибір транспортних засобів та розподіл вантажу;

формування парку машин та їх розподіл.

Задачі типу «один-до-багатьох» складаються з класів:

розподіл транспортних засобів за витратами часу;

розподіл транспортних засобів за обсягом перевезень;

розподіл транспортних засобів за витратами коштів;

розподіл транспортних засобів із фіксованими доплатами;

формування парку машин та їх розподіл;

розвезення вантажу;

вибір маршруту.

Тип задач «багато-до-одного» має майже такі ж самі класи, що й тип «один-до-багатьох»:

планування випуску продукції;

розподіл транспортних засобів за витратами часу;

розподіл транспортних засобів за обсягом перевезень;

розподіл транспортних засобів за витратами коштів;

розподіл транспортних засобів із фіксованими доплата-ми;

формування парку машин та їх розподіл;

звезення вантажу;

вибір маршруту.

Найбільш поширеним типом задач організації перевезень є останній тип «багато-до-багатьох». Саме до цього типу належить класична транспортна задача та її різновиди. Він об'єднує такі класи задач:

класична транспортна задача;

транспортна задача з неперервною відкритою математичною моделлю;

транспортна задача з дискретною математичною моделлю;

перевезення вантажу за два етапи;

перевезення вантажу декількох видів за два етапи;

перевезення вантажу декількох видів за два етапи за замовленнями споживачів;

закриття заводу;

розіграш кубку;

розбиття транспортної мережі на райони.

Перелік класів за призначенням налічує 25 найменувань.

Тут треба зауважити, що цей перелік не претендує на вичерпаність. Він містить тільки найбільш відомі класи. Головне інше, що кожний клас можна розподілити ще на підкласи за видом математичної моделі задачі. Кожний клас задач має декілька різновидів, що відрізняються однин від одного або виглядом цільової функції, або виглядом обмежень на змінні або тим та іншим одночасно. Загальну кількість підкласів важко визначити. Практика перевезень постійно пропонує нові математичні моделі, тому зосереджувати увагу на кожній моделі нема сенсу. Проте надалі принаймні одна з математичних моделей для кожного класу задач буде докладно розглянута.

Проблема вимірності стосується всіх класів задач з організації перевезень. В подальшому при розгляді різних класів задач увага на проблемі вимірності зосереджуватися не буде. Виключення складають тільки задачі розподілу транспортної мережі на райони та задача маршрутизації (комівояжера).

1.2 Транспортна задача. Види моделей. Приклади математичних моделей

Під назвою “транспортна задача” об'єднується широке коло завдань(задач) з єдиною математичною моделлю. Дані задачі відносяться до завдань лінійного програмування і можуть бути вирішені симплексним методом потенціалів. Проте система обмежень настільки своєрідна, що для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, покращуючи його, отримати оптимальне рішення.

У загальній постановці транспортна задача полягає у відшуканні опти-мального плану перевезень деякого однорідного вантажу з баз споживачам .

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

(1)

замовлення кожного із споживачів (потреби) позначимо

(2)

(3)

(4)

Очевидно, у разі закритої моделі що весь є в наявності вантаж розвозиться повністю, і всі потреби замовників цілком задоволені; у разі ж відкритої моделі або всі замовники задоволені і при цьому на деяких базах залишаються надлишки вантажу (), або весь вантаж виявляється витраченим, хоча потреби повністю не задоволені (). Так само існують одноетапні моделі завдань, де перевезення здійснюється безпосередньо від, наприклад, бази або заводу виробника до споживача, і двоетапні, де між ними є “перевалочний пункт”, наприклад - склад. План перевезень з вказівкою запасів і потреб зручно записувати у вигляді наступної таблиці, названою таблицею перевезень:

Пункти Відправлення	Пункти призначення	Запаси
			.
Потреби					Або



Умова або означає, з яким завданням ми маємо справу, із закритою моделлю або відкритою моделлю транспортної задачі. Змінна означає кількість вантажу, що перевозиться з бази споживачеві : сукупність цих величин утворює матрицю (матрицю перевезень).

Очевидно, змінні повинні задовольняти умовам:

(5)

(6)

Система (5) містить рівнянь з невідомими. Її особливість полягає в тому, що коефіцієнти при невідомих усюди дорівнюють одиниці. Крім того, всі рівняння системи (5) можуть бути розділені на дві групи: перша група з перших рівнянь (“горизонтальні” рівняння) і другої групи з решти рівнянь (“вертикальні” рівняння). У кожному з горизонтальних рівнянь містяться невідомі з одним і тим же першим індексом (вони утворюють один рядок матриці перевезень), в кожному з вертикальних рівнянь містяться невідомі з одним і тим же другим індексом (вони утворюють один стовпець матриці перевезень). Таким чином, кожна невідома зустрічається в системі (5) двічі: у одному і лише одному горизонтальному і в одному і лише одному вертикальному рівняннях.

Така структура системи (5) дозволяє легко встановити її ранг. Дійсно, покажемо, що сукупність невідомих, котрі утворюють перший рядок і перший стовпець матриці перевезень, можна прийняти як базис. При такому виборі базису, принаймні, один з двох їх індексів дорівнює одиниці, а, відповідно, вільні невідомі визначаються умовою . Перепишемo систему (5) у вигляді:

(7)

де символи означають підсумовування по відповідному індексу.

Так, наприклад

При цьому легко відмітити, що під символами такого сумування об'єднуються тільки вільні невідомі (тут ).

У розглядуваній нами системі, тільки два рівняння, а саме перше горизонтальне і перше вертикальне, містять більш одного невідомого з числа вибраних нами для побудови базису. Виключивши з першого горизонтального рівняння базисні невідомі за допомогою вертикальних рівнянь, ми отримуємо|одержуємо| рівняння

або коротше



де символ

означає суму всіх вільних невідомих. Аналогічно, виключивши з першого вертикального рівняння базисні невідомі за допомогою горизонтальних рівнянь, ми отримуємо|одержуємо| рівняння

Оскільки для закритої моделі транспортної задачі то отримані нами рівняння (8) і (9) однакові і, виключивши з одного з них невідоме ми отримаємо рівняння-тотожність , яке з системи викреслюється.

Отже, перетворення системи (5) звелося до заміни двох рівнянь| (першого горизонтального і першого вертикального) рівнянням| (8). Решта рівнянь залишається незмінними. Система набрала вигляду:

(10)

У системі (10) виділений вказаний вище базис: базисні невідомі з перших рівнянь утворюють перший стовпець матриці перевезень, а базисні невідомі решти рівнянь утворюють перший рядок матриці перевезень без першого невідомого [вона входить в перше рівняння системи (10)]. У системі (10) є рівнянь, виділений базис містить невідомих, а, отже, і ранг системи (5)

.

Для вирішення транспортної задачі необхідно крім запасів і потреб знати також і тарифи , тобто вартість перевезення одиниці вантажу з бази споживачеві.

Сукупність тарифів , також утворює матрицю, яку можна об'єднати з матрицею перевезень і даними про запаси і потреби в одну таблицю:

Пункти Відправлення	Пункти призначення	Запаси
			.
					.
					.
.	.	.	.	.	.
					.
Потреби			.		або

Сума всіх витрат, тобто вартість реалізації даного плану перевезень, є лінійною функцією змінних :

Потрібно в області допустимих вирішень системи рівнянь (5) і (6) знайти рішення, яке зводить до мінімуму лінійну функцію (11). Таким чином, ми бачимо, що транспортна задача є завданням лінійного програмування. Для її вирішення застосовують також симплексний метод, але через специфіку завдання тут можна обійтися без симплекс-таблиць. Рішення можна отримати шляхом деяких перетворень таблиці перевезень. Ці перетворення відповідають переходу від одного плану перевезень до іншого. Але, як і в загальному випадку, оптимальне рішення шукається серед базисних рішень. Отже, ми матимемо справу тільки з базисними (або опорними) планами. Оскільки в даному випадку ранг системи рівний , то серед всіх невідомих виділяється базисних невідомих, а решта (m-1)•(n-1) виявляться вільними. У базис-ному розв'язанні вільні невідомі дорівнюють нуль-індикатору. Зазвичай ці нулі в таблицю не вписують, залишаючи відповідні клітки порожніми. Таким чином, в таблиці перевезень, що представляє опорний план, ми маємо заповнених і (m-1)•(n-1) порожніх кліток.

Для контролю треба перевіряти, чи рівна сума чисел в заповнених клітинах кожного рядка таблиці перевезень запасу вантажу|тягаря| на відповідній базі, а в кожному стовпці -- потребі замовника [цим підтверджується, що даний план є вирішенням системи (5)].

Зауваження 1. Не виключаються тут і вироджені випадки, тобто можливість перетворення на нуль однієї або декількох базисних невідомих. Але ці нулі на відміну від нулів вільних невідомих вписуються у відповідну клітку, і ця клітка вважається за заповнену.

Зауваження 2. Під величинами очевидно, не обов'язково мати на увазі тільки тарифи. Можна також вважати їх за величини, пропорційні тарифам, наприклад, відстанями від баз до споживачів. Якщо, наприклад виражені в тоннах, а у кілометрах, то величина визначувана формулою (11), є кількістю тонно-километрів, які складають об'єм даного плану перевезень. Очевидно, що витрати на перевезення пропорційні кількості тонно-километрів і, отже, будуть мінімальними при мінімумі . В цьому випадку замість матриці тарифів ми маємо матрицю відстаней.

Змістовна і математична постановка задачі про розподіл транспортних засобів за грошовими витратами.

Нехай є транспортних ліній, за якими щоденно розвозять будматеріали з будмаркету «ДОБРОБУТ» . На -й лінії необхідно виконати рейсів, . У наявності є транспортні одиниці типів. Резерви корисного часу транспортних одиниць типу становлять

.

На виконання транспортною одиницею типу рейсу на лінії потрібен час , а грошові витрати на один рейс становлять . Потрібно визначити найбільш економічне розміщення транспортних одиниць за всіма лініями, тобто розміщення з мінімальними грошовими витратами на виконання всіх рейсів. Позначимо через кількість рейсів, що транспортна одиниця повинна виконати на лінії . Тоді математична модель задачі про розподіл транспортних засобів за витратами коштів набуває вигляду:

Тут цільова функція (12) відповідає сумарним витратам на виконання всіх рейсів за всіма лініями. Система нерівностей (13) обмежує сумарні витрати часу транспортними одиницями кожного типу. Система нерівностей (14) вимагає виконання потрібної за умови задачі кількості рейсів на кожній лінії. Вирази (15) і (16) обмежують простір припустимих рішень відповідно до суті зінних.

Змістовна і математична постановка задачі про вибір маршруту.

Транспортна мережа налічує пункт. Відомо відстані між пунктами Виїжджаючи з початкового пункту (йому приписується номер 0), комівояжер повинний побувати у всіх інших пунктах тільки один раз і повернутися в пункт 0. В якому порядку треба об'їжджати пункти ,щоб пройдена сумарна відстань була мінімальною?

Примітка [1]. Ця задача добре відома як задача про комівояжера.

Впровадимо двійкові змінні що мають наступний зміст:

Впровадимо також додаткові змінні , що приймають довільні дійсні значення(не применшуючи спільності, їх можна вважати цілими). Дані змінні дозволять сформувати умову зв'язності маршруту комівояжера: виключити розпадання маршруту на підцикли. Тоді математична модель задачі набуває вигляду:

(20)

(21)

(22)

Тут (17) визначає цільову функцію, як сумарну довжину маршруту комівояжера. Умова (18) говорить про те, що комівояжер в'іжджає в кожний пункт рівно один раз. Умова (19) говорить про те, що комівояжер виїжджає з кожного пункту рівно один раз. Обмеження (20) вимагає, щоб будь-який маршрут комівояжера складався з одного циклу. Система рівностей (21) обмежує область припустимих значень додаткових змінних цілими числами (позитивними чи негативними). Останнє обмеження (22) виключає повернення комівояжера до пункту, в якому він вже побував.

Метод мінімального (максимального) елемента

Суть методу полягає в тому , що з усієї таблиці вартостей вибирають найменшу і в клітку, яка їй відповідає, поміщають менше з чисел і . Потім з розгляду виключають або рядок, відповідну постачальнику , запаси якого повністю витрачені, або стовпець, відповідний споживачеві, потреби якого повністю задоволені, або і рядок і стовпець, якщо витрачені запаси постачальника і задоволені потреби споживача. З решти таблиці вартостей знову вибирають найменшу вартість, і процес розподілу запасів продовжують , поки всі запаси не будуть розподілені, а потреби задоволені.

1.3 Задача про вибір маршруту, як задача цілочислового лінійного програмування

Змістовна і математична постановка задачі про вибір маршруту.

Транспортна мережа налічує пункт. Відомо відстані між пунктами Виїжджаючи з початкового пункту (йому приписується номер 0), комівояжер повинний побувати у всіх інших пунктах тільки один раз і повернутися в пункт 0. В якому порядку треба об'їжджати пункти ,щоб пройдена сумарна відстань була мінімальною?

Примітка [1]. Ця задача добре відома як задача про комівояжера.

Впровадимо двійкові змінні що мають наступний зміст:



Впровадимо також додаткові змінні , що приймають довільні дійсні значення(не применшуючи спільності, їх можна вважати цілими). Дані змінні дозволять сформувати умову зв'язності маршруту комівояжера: виключити розпадання маршруту на підцикли. Тоді математична модель задачі набуває вигляду:

(1.3)

(1.4)

(1.5)

(1.6)

Тут (1.1) визначає цільову функцію, як сумарну довжину маршруту комівояжера. Умова (1.2) говорить про те, що комівояжер в'іжджає в кожний пункт рівно один раз. Умова (1.3) говорить про те, що комівояжер виїжджає з кожного пункту рівно один раз. Обмеження (1.4) вимагає, щоб будь-який маршрут комівояжера складався з одного циклу. Система рівностей (1.5) обмежує область припустимих значень додаткових змінних цілими числами (позитивними чи негативними). Останнє обмеження (1.6) виключає повернення комівояжера до пункту, в якому він вже побував.

1.4 Метод Монте-Карло

Метод Монте-Карло (за назвою міста Монте-Карло, Монако, яке відоме своїми казино) -- загальна назва групи числових методів, основаних на одержанні великої кількості реалізацій стохастичного (випадкового) процесу, який формується у той спосіб, щоб його ймовірнісні характеристики збігалися з аналогічними величинами задачі, яку потрібно розв'язати. Використовується для розв'язування задач у фізиці, математиці, економіці, оптимізації, теорії управління тощо.

Метод Монте-Карло -- це метод імітації для приблизного відтворення реальних явищ. Він об'єднує аналіз чутливості (сприйнятливості) і аналіз розподілу ймовірностей вхідних змінних. Цей метод дає змогу побудувати модель, мінімізуючи дані, а також максимізувати значення даних, які використовуються в моделі. Побудова моделі починається з визначення функціональних залежностей у реальній системі. Після чого можна одержати кількісний розв'язок, використовуючи теорію ймовірності й таблиці випадкових чисел.

Метод Монте-Карло широко використовується у всіх випадках симуляції на ЕОМ.

Не існує єдиного методу Монте-Карло, цей термін описує великий і широко використовуваний клас підходів. Проте ці підходи використовують в своїй основі єдиний шаблон:

Визначити область можливих вхідних даних.

Випадковим чином згенерувати вхідні дані із визначеної вище області за допомогою деякого заданого розподілу ймовірностей.

Виконати детерміновані обчислення над вхідними даними.

Проміжні результати окремих розрахунків звести у кінцевий результат.

Наприклад, значення р можна наблизити використанням методу Монте-Карло:

Намалюйте квадрат на підлозі, а потім вмалюйте коло всередину нього. З геометрії, співвідношення площі вписаною кола до площі зовнішнього квадрата становить р / 4.

Рівномірно розкидати деякі об'єкти однакового розміру по всій площі квадрата. Наприклад, це можуть бути зерна рису.

Оскільки дві області знаходяться в співвідношенні р / 4 , об'єкти повинні потрапити в області приблизно в тій же пропорції. Таким чином, підрахувавши кількість об'єктів в колі і розділити на загальну кількість об'єктів в квадраті, отримаємо наближене значення р / 4.

Помноживши результат на 4 буде отримано наближене значення власне самого р.

Історія

Енріко Фермі в 1930-х і Станіславу Уламу в 1946 році першим прийшла в голову ідея подібного методу. Улам пізніше зв'язався з Джоном фон Нейманом, щоб працювати над ним.

Фізики з Лос-Аламоської наукової лабораторії досліджували радіаційний захист та відстань, яку нейтрони, проходять через різні матеріали. Незважаючи на велику кількість необхідних даних, таких як середня відстань, яку нейтрони проходять в речовині до зіткнення з атомним ядром або скільки енергії нейтрони мають віддати, щоб зіткнутися з ядром, задача не могла бути розв'язана за допомогою аналітичних розрахунків.

Джон фон Нейман і Станіслав Улам запропонували розв'язати її на основі моделювання експерименту на комп'ютері за допомогою випадку. Будучи засекреченою, їхня робота вимагала кодове ім'я. Фон Нейман вибрав назву «Монте-Карло». Назва запозичена від казино Монте-Карло в Монако, для гри в якому дядько Улама позичав гроші. Над методом Монте-Карло працював також Ніколас Костянтин Метрополіс.

1.5 Бджолиний алгоритм

математичний вантажний транспортування алгоритм

Бджолиний алгоритми є доволі молодим алгоритмом для знаходження глобальних екстремумів (максимумів чи мінімумів) складних багатовимірних функцій.

В інформатиці та дослідженні операцій, бджолиний алгоритм на основі алгоритму пошуку вперше розроблений в 2005 році. Він імітує поведінку харчування зграї бджіл. У базовій версії, алгоритм виконує свого роду сусідній пошук в поєднанні з випадковим пошуком і може використовуватися для комбінаторної оптимізації і функціональної оптимізації.

Загальні принципи

Для розгляду принципів роботи бджолиного алгоритму, або методу рою бджіл (МРБ) вдамося до аналогії з реальним роєм бджіл.

Уявімо собі рій бджіл на полі. Їх мета -- знайти на полі область з найвищою щільністю квітів. Без якого-небудь уявлення про поле апріорі, бджоли починають пошук квітів з випадкових позицій з випадковими векторами швидкості. Кожна бджола може пам'ятати позиції, де вона знайшла найбільшу кількість квітів і якимось чином знати області, де інші бджоли виявили найбільшу щільність квітів. Вибираючи між поверненням до місця, де бджола сама виявила найбільшу кількість квітів, або дослідженням місця, визначеного іншими, як місце з найбільшою кількістю квітів, бджола спрямовується в напрямку між двома точками в залежності від того, що надасть більший вплив на її рішення -- персональний спогад або соціальний рефлекс. По дорозі бджола може знайти місце з більш високою концентрацією квітів, ніж було знайдено раніше. Надалі воно може бути позначено як нове місце з найбільшою концентрацією квітів, а також як місце найбільшого скупчення квітів, знайдене всім роєм. Випадково бджола може пролетіти повз місця, з великою кількістю квітів, ніж було знайдено будь-якою іншою бджолою рою. Весь рій потім буде прагнути до цього місця в додаток до власних спостережень кожної бджоли. Таким чином, бджоли досліджують поле: перелітаючи місця з найбільшою концентрацією, вони сповільнюються в їхньому напрямку. Безперервно вони перевіряють місця, які пролетіли, порівнюючи з знайденими раніше місцями з найбільшою концентрацією квітів сподіваючись знайти абсолютну найбільшу концентрацію квітів. В підсумку, бджола закінчує рух на місці поля з найбільшою концентрацією квітів. Незабаром весь рій зосереджується в околицях цієї позиції. Не маючи можливості виявити місця з більшою концентрацією квітів, бджоли безперервно рояться в районі найбільшої щільності квітів. Ця поведінка бджіл і була покладена в основу цього методу оптимізації.

Мова методу

Частинка або Агент -- кожна бджола в рої розглядається як частинка або агент. Всі частинки рою діють індивідуально відповідно до одного керуючого принципу: прискорюватися в напрямку найкращої персональної і найкращої спільної позиції, постійно перевіряючи значення поточної позиції. Позиція -- аналогічно розташування бджоли на полі представлені координатами на площині xy. Однак, в загальному випадку можна розширити цю ідею в будь-який N-мірний простір відповідно до поставленого завдання. Цей N-мірний простір є областю рішень для задачі, що оптимізується, де кожний набір координат представляє рішення. Придатність -- за аналогією з прикладом бджолиного рою функція придатності буде щільність квітіів: чим більша щільність, тим краще позиція. Функція придатності служить засобом зв'язку між фізичною проблемою і алгоритмом оптимізації. Персональна найкраща позиція -- за аналогією з бджолиним роєм, кожна бджола пам'ятає позицію, де вона сама виявила найбільшу кількість квітів. Ця позиція з найбільшим значенням придатності виявлена бджолою відома як персональна найкраща позиція (ПНП). Кожна бджола має власне ПНП, яке визначається шляхом, який вона пролетіла. У кожній точці вздовж шляху руху бджола порівнює значення придатності поточної позиції зі значенням ПНП. Якщо поточна позиція має значення придатності вище, значення ПНП замінюється на значення поточної позиції. Глобальна найкраща позиція -- кожна бджола також якимось чином дізнається область найбільшої концентрації квітів, визначену всім роєм. Ця позиція найбільшої придатності відома як глобальна найкраща позиція (ГНП). Для всього рою це одна ГНП, до якої прагне кожна бджола. У кожній точці протягом всього шляху кожна бджола порівнює придатність її поточної позиції з ГНП. У разі якщо будь-яка бджола виявить позицію з більш високою придатністю, ГНП замінюється поточною позицією цієї бджоли.

Алгоритм

Першим кроком в реалізації МРБ є вибір параметрів, які необхідно оптимізувати, і визначення допустимого інтервалу для пошуку оптимальних значень. Потім в допустимої області випадковим чином розташовуються бджоли, а також задаються вектори і швидкості їх руху. Потім кожна частка повинна переміщатися через простір рішень, так якщо б вона була бджолою в рої. Алгоритм діє на кожну частку окремо, переміщаючи її на невелику величину, циклічно рухаючи її через весь рій. Наступні кроки виконуються для кожної частки: Оцінка придатності для частинки, порівняння з ПНП і ГНП. Функція придатності, використовуючи координати частинки в просторі рішень, повертає значення придатності для поточної позиції. Якщо це значення більше, ніж значення ПНП, відповідне цій частці, або ГНП, тоді відповідні позиції замінюються поточної позицією. Коригування швидкості частинки. Маніпуляції зі швидкістю частинки є основним елементом усієї оптимізації. Точне розуміння рівняння, використовуваного для визначення швидкості, є ключем до розуміння всього процесу оптимізації. Швидкість частинки змінюється відповідно до взаємним розташуванням позицій ПНП і ГНП. Вона прагне в напрямку цих позицій найбільшої придатності згідно з наступним рівнянням:



де

- швидкість частинки в -му вимірі на попередньому кроці;

- координати частинки в -му вимірі;

- ПНП;

- ГНП.

Розрахунок проводиться для кожного з N. З цього рівняння видно, що нова швидкість виходить зі старої швидкості шляхом простого масштабування на , і додавання напрямків ГНП і ПНП для цього конкретного напряму. і -- це масштабні коефіцієнти, які визначають відносне взаємне «тяжіння» до ПНП і ГНП. Вони іноді розглядаються як пізнавальний і соціальний фактори. -- це коефіцієнт, що визначає який вплив на частку надає її пам'ять про ПНП, -- коефіцієнт, що визначає який вплив на частку надають інші члени рою. Збільшення передбачає дослідження простору рішень шляхом руху кожної частинки в напрямку свого ПНП; збільшення передбачає дослідження передбачуваного глобального максимуму.

Функція випадкових чисел повертає число в інтервалі між -1 і 1. Загалом випадку два появи функції являє собою два різних виклику функції. Більшість реалізацій використовують дві незалежні випадкові величини для стохастичного зміни відносного тяжіння ГНП і ПНП. Це введення випадкового елемента в оптимізацію призначено для моделювання незначного непередбачуваного компонента реальної поведінки рою. називають «інерційним вагою» і це число (вибране в інтервалі між 0 і 1) відображає в якій мірі частка залишається вірною своєму первісному курсом, не зазнавши впливу ГНП і ПНП.

Граничні умови

Межі ми поставили спочатку, але ніде в формулах і методах про них не згадувалося. Так як же все-таки їх враховувати? Існує декілька варіантів.

Наприклад, можна зробити стіни поглинаючими. Коли частка вдаряється об кордон простору рішень в одному з вимірів, швидкість в цьому вимірі обнуляється, і частка в кінцевому підсумку буде повернена в заданий простір рішень. Це означає, що кордони -- «стіни» поглинають енергію частинок, що намагаються покинути дозволену область. Або ж відображати швидкість частинки, коли та підлітає до «стіни». Але найефективнішим рішенням виявилися «невидимі стіни». Частка може спокійно вилітати за їх межі, але перебуваючи поза дозволеної області, значення, отримані нею значення просто не враховуються, до тих пір, поки вона не повернеться назад.

Метод рою бджіл можна ефективно розподілити на декілька паралельних процесів, за рахунок чого значно збільшиться його швидкість. У порівнянні з генетичним алгоритмом, оператори якого можуть бути реалізовані різним чином, МРБ має лише один оператор -- обчислення швидкості, що робить його простішим у використанні. У методі рою бджіл можна легко визначити досягнення точки глобального мінімуму, в той час як в генетичних алгоритмах це значно ускладнено. Концепція цих методів ґрунтується на двох зовсім різних природних процесах: МРБ ґрунтується на соціальній поведінці рою, а генетичний алгоритм імітує процес еволюції і природного відбору. За рахунок цього є можливість об'єднати два цих методи.

Размещено на Allbest.ru

...