Восток Маркетинг


Статьи

НОУ ІНТУЇТ | лекція | Генетичні алгоритми для задач комбінаторної оптимізації

  1. 2.2. Завдання про покриття Задано безліч елементів і безліч підмножин цієї множини . Необхідно...
  2. 2.3.1. Упорядковане представлення.

2.2. Завдання про покриття

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

Очевидно, тут рішення можна також представити двійковим вектором

, де , де

, Якщо підмножина   входить в покриття; , Якщо підмножина входить в покриття;

, якщо   не входить в покриття; , якщо не входить в покриття;

і при цьому

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

2.3. завдання комівояжера

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

Відстані між містами відомі. У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?


Мал.2.1.

завдання комівояжера

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

Тур комівояжера може бути описаний циклічною перестановкою Тур комівояжера може бути описаний циклічною перестановкою   , Причому всі   - попарно різні;  повторюваний на початку і в кінці номер міста   , Показує, що перестановка циклічна , Причому всі - попарно різні; повторюваний на початку і в кінці номер міста , Показує, що перестановка циклічна. Простором пошуку рішень цього завдання є безліч перестановок міст. Будь-яка проста (одиночна) перестановка міст дає рішення, яке є повним туром з міст. Оптимальним рішенням є перестановка, яка дає мінімальну вартість туру. Очевидно, розмірність простору пошуку для несиметричною завдання дорівнює . Відомо, що ця задача є NP - повної, тобто переборного. Вона має численні практичні додатки, в яких число "міст" може бути досить великим. Наприклад, при виробництві складних деталей завдання свердління отворів може мати сотні і тисячі "міст". При виробництві НВІС виникають завдання (наприклад, щодо внесення домішок в напівпровідник) з числом "міст" близько мільйона. За останні десятиліття розроблено досить багато алгоритмів вирішення цього завдання, що дають субоптимальное рішення. В останнє десятиліття ця задача є базовою для дослідження ГА в області комбінаторної оптимізації.

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

Для вирішення ЗК за допомогою генетичних алгоритмів розроблені спеціальні методи представлення (кодування) рішень і відповідні проблемно-орієнтовані генетичні оператори [ 2 , 3 , 4 ]. В основному використовуються три способи подання туру при вирішенні ЗК з використанням ГА: 1) уявлення порядку; 2) уявлення сусідства; 3) уявлення шляхів. Для кожного з цих уявлень розроблені свої "генетичні" оператори. Оператор мутації відносно легко визначити на цих уявленнях у вигляді одиночної перестановки сусідніх міст в турі. Тому в подальшому ми, в основному, розглянемо оператори кросинговеру.

2.3.1. Упорядковане представлення.

В цьому випадку тур представляється списком з n міст, де В цьому випадку тур представляється списком з n міст, де   -й елемент списку має номер від 1 до -й елемент списку має номер від 1 до . При цьому використовується базовий упорядкований список міст , Який служить для посилань упорядкованого уявлення. Фактично ми розглядали цей метод кодування рішення при вирішенні задачі про укладання рюкзака.

Розглянемо його на конкретному прикладі туру Розглянемо його на конкретному прикладі туру   = (1-2-4-3-8-5-9-6-7), для якого впорядкований список   = (1 2 3 4 5 6 7 8 9) = (1-2-4-3-8-5-9-6-7), для якого впорядкований список = (1 2 3 4 5 6 7 8 9). Тоді даний тур при цьому упорядкованому списку представляється наступним списком посилань = (1 + 1 2 1 4 1 3 1 1), який інтерпретується наступним чином. Тут жирним курсивом виділено поточний покажчик в списку .

Перший номер зі списку Перший номер зі списку   дорівнює 1, тому поміщаємо в тур 1-й місто з базового списку   , Видаляємо його з   і зрушуємо покажчик по дорівнює 1, тому поміщаємо в тур 1-й місто з базового списку , Видаляємо його з і зрушуємо покажчик по . Тоді отримуємо:

тур тур   = (1), базовий список   = (2 3 4 5 6 7 8 9), покажчик   = (1 + 1 2 1 4 1 3 1 1) = (1), базовий список = (2 3 4 5 6 7 8 9), покажчик = (1 + 1 2 1 4 1 3 1 1).

Наступний номер за вказівником Наступний номер за вказівником   також дорівнює 1, тому знову поміщаємо в тур 1-й місто з базового списку   , Видаляємо його з   і зрушуємо покажчик по також дорівнює 1, тому знову поміщаємо в тур 1-й місто з базового списку , Видаляємо його з і зрушуємо покажчик по .

В результаті отримуємо:

поточний тур поточний тур   = (1-2),   = (3 4 5 6 7 8 9) і покажчик в e зсувається на третю позицію   = (1 + 1 2 1 4 1 3 1 1) = (1-2), = (3 4 5 6 7 8 9) і покажчик в e зсувається на третю позицію = (1 + 1 2 1 4 1 3 1 1). Наступний номер списку е дорівнює 2, тому ми беремо і видаляємо 2-й місто з поточного базового списку і додаємо його в тур і пересуваємо покажчик по . маємо:

поточний тур поточний тур   = (1-2-4),   = (3 5 6 7 8 9),   = (1 + 1 2 1 4 1 3 1 1) = (1-2-4), = (3 5 6 7 8 9), = (1 + 1 2 1 4 1 3 1 1).

Продовжуючи цей процес, в результаті декодування по даному коду Продовжуючи цей процес, в результаті декодування по даному коду   = (1 + 1 2 1 4 1 3 1 1), базового списку   = (1 2 3 4 5 6 7 8 9) буде побудований тур   = (1-2-4-3-8-5-9-6-7) = (1 + 1 2 1 4 1 3 1 1), базового списку = (1 2 3 4 5 6 7 8 9) буде побудований тур = (1-2-4-3-8-5-9-6-7).

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

Наприклад, для батьків

= (1 1 2 1 | 4 1 3 1 1) і   = (5 1 5 5 | 5 3 3 2 1), = (1 1 2 1 | 4 1 3 1 1) і = (5 1 5 5 | 5 3 3 2 1),

які відповідають турам

= (1-2-4-3-8-5-9-6-7) і   = (5-1-7-8-9-4-6-3-2), = (1-2-4-3-8-5-9-6-7) і = (5-1-7-8-9-4-6-3-2),

маємо наступних нащадків при схрещуванні

= (1 1 2 1 5 3 3 2 1) і   = (5 1 5 5 4 1 3 1 1), = (1 1 2 1 5 3 3 2 1) і = (5 1 5 5 4 1 3 1 1),

які представляють тури

= (1-2-4-3-9-7-8-6-5) і   = (5-1-7-8-6-2-9-3-4) = (1-2-4-3-9-7-8-6-5) і = (5-1-7-8-6-2-9-3-4).

Очевидно, що часткові тури зліва від точки кросинговеру не змінюються, в той же час часткові тури праворуч від неї розриваються випадковим чином (зберігаючи коректність рішення). На жаль, машинні експерименти за рішенням ЗК на основі цього подання рішень з використанням класичного кросинговеру показують посередні результати [ 4 ].

У якому порядку слід обходити міста, щоб замкнутий шлях (тур) комівояжера був найкоротшим?

Новости

также можем предложить:
печать бланков и прайс-листов | печать визитных карточек (визиток)
изготовление папок и меню | изготовление блокнотов
печать листовок

Связаться с менеджером для оформления заказа:
тел.: +38 (062) 349-56-15, 348-62-20
моб.: +38 (095) 811-22-62, +38 (093) 665-38-06,
+38 (067) 17 44 103
факс: +38 (062) 332-28-98
e-mail: [email protected]
г. Донецк, ул. Артема, 41

   2010 © Восток Маркетинг Яндекс.Метрика