Диплом - Стор 4
Точне рішення
Генетичний алгоритм
Рішення за допомогою мінімального кістяка
Рішення за допомогою мінімального кістяка (оптимізоване k = 3)
Рішення за допомогою мінімального кістяка (оптимізоване k = 5
Згідно з дослідженнями, генетичні алгоритми мають трудомісткість у середньому.
O(nт), деn– довжина хромосоми (тобто кількість міст), m –відображає вплив розміру популяції та ймовірностей генетичних операторів. Вузьким місцем генетичних алгоритмів є багаторазове обчислення значення функції пристосованості.
Кількість обчислень дорівнює:
Спробуємо взяти в якості вихідних даних для вирішення задачі комівояжера генетичним алгоритмом отримані рішення за допомогою мінімального кістяка з і без оптимізації (табл. 2.4.4. та табл. 2.4.5.). При великій кількості міст також доводиться змінювати умову зупинення алгоритму.
Таблиця2.4.4.– Порівняння точності розв'язання задачі комівояжера за допомогою генетичних алгоритмів з ефективними методами розв'язання.
Таблиця 2.4.5. – Порівняння часу розв'язання задачі комівояжера за допомогою генетичних алгоритмів з ефективними методами розв'язання (час у мс). Набір даних – розв'язання задачі, одержане за допомогою ефективних способів.
Очевидно, що рішення має кращу якість, але кількість кроків для оптимізації, взятих для вирішення задачі за допомогою мінімального кістяка, ніяк не впливає на нього. З цього можна дійти невтішного висновку, що генетичні алгоритми можна застосовувати після ефективних способів рішення збільшення точності. Час виконання так само значно скоротився
На основі отриманих результатів можна зробити наступний висновок: нехай є завдання, для якого може бути отримане деякенаближене рішення, тоді щоб поліпшити отримане рішення, його можна подати на вхід генетичному алгоритму. Рішення, отримане у такий спосіб, буде більш точним.
З огляду на особливості своєї реалізації, генетичні алгоритми добре піддаються розпаралелювання, виходячи з цього, досліджуємо їх ефективність у такому разі.
2.5. Розвиток генетичних алгоритмів у бік моделі з кількома
2.5.1. Модель міграції генетичних алгоритмів
Генетичні алгоритми застосовують і при паралельних обчисленнях (parallel implementations).
Першим підходом є розпаралелювання окремих кроків алгоритму:
селекції та реплікації, мутації, обчислення функції пристосованості. У цьому популяція поділяється на блоки, з кожного з яких працює окремий потік.
Однак такий підхід не дуже зручний у програмуванні.
Найчастіше застосовується модель міграції (Migration). Модель міграції є популяцією як безліч підпопуляцій. Кожна підпопуляція обробляється окремим процесором. Ці підпопуляції розвиваються незалежно одна від одної протягом однакової кількості поколіньT(час ізоляції). Після закінчення часу ізоляції відбувається обмін особинами між популяціями (міграція, "крадіжка наречених"). Кількість особин, які зазнали обміну (ймовірність міграції), метод відбору особин для міграції та схема міграції визначає частоту виникнення генетичного різноманіття у підпопуляціях та обмін інформацією між підпопуляціями.
Відбір особин для міграції може відбуватися так:
випадкова одноманітна вибірка з числа особин;
пропорційний відбір: для міграції беруться найпридатніші особини.
Окремі підпопуляції у паралельнихГенетичні алгоритми можна умовно прийняти за вершини деякого графа. У зв'язку із цим можна розглядати топологію графа міграційного генетичного алгоритму. Найбільш поширеною топологією міграції є повний граф (рис. 2.5.1.1.), коли особини з будь-якої підпопуляції можуть мігрувати в будь-яку іншу підпопуляцію. Для кожної підпопуляції повна кількість потенційних іммігрантів будується на основі всіх підпопуляцій. Мігруюча особина випадково вибирається із загального числа.
При використанні в необмежену міграцію пропорційного відбору спочатку формується масив з найбільш придатних особин, відібраних по всіх підпопуляціях. Випадковим чином із цього масиву вибирається особина, і нею замінюють найменш придатну особину в підпопуляції 1. Аналогічні дії проробляємо з іншими підпопуляціями. Але за такого походу можливі колізії: що якась популяція отримає дублікат своєї "хорошої" особини.
Малюнок 2.5.1.1 – Міграція з топологією повної мережі
Інша основна міграційна схема має топологію кільця (рис. 2.5.1.2). Тут особини передаються між сусідніми (у напрямку обходу) популяціями. Таким чином, особини з однієї підпопуляції можуть мігрувати лише одну – сусідню популяцію.
Малюнок 2.5.1.2. - Міграція з топологією кільця
Існує стратегія міграції, що поєднує першу та другу модель, так само вона дозволяє дозволити колізії першої моделі. Як і за топології кільця, міграція здійснюється лише між найближчими сусідами, проте міграція в цій моделі так само можлива між "крайніми" підпопуляціями (тороїдальні крайові міграції). [7]
2.5.2. Острівна модель генетичних алгоритмів
Острівна модель є найпоширенішою моделлюпаралельного генетичного алгоритму Її суть полягає в тому, що популяція, як правило, що складається з дуже великої кількості особин, розбивається на однакові за розміром підпопуляції. кожна підпопуляція обробляється відбільним процесором за допомогою одного з різновидів непаралельного генетичного алгоритму. Зрідка, наприклад, через кожні п'ять поколінь підпопуляції обмінюватимуться кількома особинами.
Такі міграції дозволяють підпопуляції спільно використовувати генетичний матеріал.
Нехай виконуються 16 незалежних генетичних алгоритмів, використовуючи підпопуляції зі 100 особин у кожній. Якщо міграції немає, відбувається 16 незалежних пошуків рішення. Усі пошуки ведуться різних початкових популяціях і сходяться до певним особам. Дослідження підтверджують, що генетичний дрейф схильний наводити підпопуляції до різних домінуючих особин. Це з тим, що, по-перше, кількість островів, приймаючих домінуючих " емігрантів " з острова обмежена (2-5 островів). По-друге, обмін особинами односторонній. Тому у великій популяції з'являтимуться групи островів із різними домінуючими особинами. Якщо населення має невеликий розмір, то можливе швидке мігрування фальшивих домінуючих особин.
Наприклад, справжнє рішення перебуває лише одному острові, а кілька помилкових домінант – інших островах. Тоді при міграції кількість хибних особин на островах зросте (на кожний острів міграції відбуваються не менше двох островів), генетичним алгоритмом вірне рішення буде зруйновано. Тим самим у невеликій популяції при генетичному дрейфі можлива поява помилкових домінуючих особин і сходження алгоритму до помилкового оптимуму.
Введення міграції в острівній моделі дозволяє знаходити різні особини-домінантипідпопуляціях, що сприяє підтримці різноманіття у популяції.
Кожну підпопуляцію можна сприйняти як острів. Під час міграції підпопуляції обмінюються генетичним матеріалом. При частому мігруванні великої кількості особин відбувається перемішування генетичного матеріалу. Тим самим усуваються локальні різницю між островами. Дуже рідкісні міграції не дозволяють запобігти передчасній збіжності алгоритму на маленьких популяціях. У
Розглянутої моделі з кожного острова міграції можуть відбуватися лише на певну відстань: 2-5 кістяків залежно від кількості популяцій. Таким чином, кожен острів виявляється майже ізольованим. Кількість островів, на які можуть мігрувати особини однієї підпопуляції, називаютьвідстанню ізоляції.
Слід зазначити, що у такій моделі взаємоміграції виключені.