Зміст:
Введення
Глава 1. Генетичні алгоритми
1.1 Природний відбір в природі
1.2 Представлення об'єктів. Кодування ознак
1.3 Основні генетичні оператори
1.4 Схема функціонування генетичного алгоритму
Висновок
Глава 2. Завдання оптимізації
2.1 Завдання, які вирішуються за допомогою генетичних алгоритмів
2.2 Математична постановка задачі оптимізації
2.3 Рішення діофантових рівнянь
2.4 Шляхи вирішення завдань оптимізації
2.5 Завдання комівояжера
Висновок
Глава 3. Програмна реалізація. Створення посібника з генетичним алгоритмам
3.1 Обгрунтування вибору програмного забезпечення
3.2 Опис програмної реалізації
Висновок
Бібліографія
ВСТУП
Природа вражає своєю складністю і багатством проявів. Серед прикладів можна назвати складні соціальні системи, імунні і нейронні системи, складні взаємозв'язки між видами. Вони - всього лише деякі з чудес, що стали очевидними при глибокому дослідженні природи навколо нас. Наука - це одна із систем, яка пояснює навколишнє і допомагає пристосуватися до нової інформації, одержуваної з зовнішнього середовища. Багато чого з того, що ми бачимо і спостерігаємо, можна пояснити теорією еволюції через спадковість, зміна і відбір.
На світогляд людей сильно вплинула теорія еволюції Чарльза Дарвіна, представлена в роботі "Походження Видів", в 1859 році. Безліч областей наукового знання багатьом зобов'язана революції, викликаної теорією еволюції і розвитку. Але Дарвін, подібно багатьом сучасникам, що передбачає, що в основі розвитку лежить природний відбір, не міг не помилятися. Наприклад, він не зміг показати механізм успадкування, при якому підтримується мінливість. Однак Дарвін виявив головний механізм розвитку: відбір у поєднанні з мінливістю. У багатьох випадках, специфічні особливості розвитку через мінливість і відбір все ще не безперечні, однак, основні механізми пояснюють неймовірно широкий спектр явищ, що спостерігаються в Природі. Тому не дивно, що вчені, які займаються комп'ютерними дослідженнями, у пошуках натхнення звернулися до теорії еволюції. Можливість того, що обчислювальна система, наділена простими механізмами мінливості і відбору, могла б функціонувати за аналогією з законами еволюції в природних системах, була дуже привабливою. Ця надія є причиною появи ряду обчислювальних систем, побудованих на принципах природного відбору.
Отже, в природі постійно відбувається процес вирішення завдань оптимізації. Завдання оптимізації - найбільш поширений і важливий для практики клас задач. Їх доводиться вирішувати кожному з нас або в побуті, розподіляючи свій час між різними справами, або на роботі, домагаючись максимальної швидкості роботи програми чи максимальної прибутковості компанії - залежно від посади.
Завдяки відкриттям останніх ста років сучасній науці відомі всі основні механізми еволюції, пов'язані з генетичним успадкуванням. Ці механізми досить прості за своєю ідеєю, але дотепні (якщо до природи застосовно це слово) і ефективні. Дивно, але просте моделювання еволюційного процесу на комп'ютері дозволяє отримати рішення багатьох практичних завдань. Такі моделі отримали назву "генетичні алгоритми" і вже широко застосовуються в різних областях.
У процесі вивчення різних підходів до вирішення завдань оптимізації нами висувається гіпотеза що, рішення задач оптимізації можливо за допомогою генетичних алгоритмів.
Об'єктом вивчення даної курсової роботи є генетичні алгоритми.
Предмет вивчення - застосування генетичних алгоритмів для знаходження рішення оптимізаційної задачі.
Методи дослідження:
o збір і аналіз літературних джерел з даної теми;
o вивчення особливостей створення і використання генетичних алгоритмів;
o моделювання роботи генетичного алгоритму на комп'ютері застосовно до знаходження рішення задачі оптимізації.
Метою даної курсової роботи є розробка електронного посібника, в якому поетапно описується рішення задачі про знаходження найкоротшого маршруту в існуючій системі доріг.
Завдання:
1. проаналізувати можливості генетичних алгоритмів;
2. вивчити особливості генетичних алгоритмів;
3. створення електронного посібника з основ генетичних алгоритмів;
РОЗДІЛ 1: ГЕНЕТИЧНІ АЛГОРИТМИ
1.1. Природний відбір в природі
"XIX столітті Чарльз Дарвін здійснив кругосвітнє плавання, збираючи інформацію для теорії еволюції на основі природного відбору, при якому виживає найсильніший. Чи міг він припускати, що сто років по тому математики будуть використовувати цю теорію для вирішення задачі про оптимальний маршрут навколосвітньої подорожі із зупинками на багатьох маленьких островах? .. "
Автор: РОСС Клемент
Опубліковано в журналі "Компьютерра" № 11 від 16 березня 1999
Ключову роль в еволюційній теорії грає природний відбір. Його суть полягає в тому, що найбільш пристосовані особини краще виживають і приносять більше нащадків, ніж менш пристосовані. Зауважимо, що сам по собі природний відбір ще не забезпечує розвиток біологічного виду. Тому дуже важливо зрозуміти, яким чином відбувається спадкування, тобто як властивості нащадка залежать від властивостей батьків.
Основний закон спадкування інтуїтивно зрозумілий кожному - він полягає в тому, що нащадки схожі на батьків. Зокрема, нащадки більш пристосованих батьків будуть, швидше за все, одними з найбільш пристосованих у своєму поколінні. Щоб зрозуміти, на чому грунтується це схожість, потрібно трохи заглибитися в побудову природної клітини - у світ генів і хромосом [4].
Майже в кожній клітині будь-якої особини є набір хромосом, що несуть інформацію про цю особини. Основна частина хромосоми - нитка ДНК, що визначає, які хімічні реакції будуть відбуватися в даній клітині, як вона буде розвиватися і які функції виконувати. Ген - це відрізок ланцюга ДНК, відповідальний за певну властивість особини, наприклад за колір очей, тип волосся, колір шкіри і т.д. При розмноженні тварин відбувається злиття двох батьківських статевих клітин та їх ДНК взаємодіють, створюючи ДНК нащадка. Основний спосіб взаємодії - кросовер (cross-over, схрещування). При кросовері ДНК предків діляться на дві частини, а потім обмінюються своїми половинками.
При успадкування можливі мутації через радіоактивності або інших впливів, у результаті яких можуть змінитися деякі гени в статевих клітинах одного з батьків. Змінені гени передаються нащадку і надають йому нових властивостей. Якщо ці нові властивості корисні, вони, швидше за все, збережуться в даному виді - при цьому відбудеться стрибкоподібне підвищення пристосованості виду. Вперше подібний алгоритм був запропонований у 1975 році Джоном Холландом (John Holland) в Мічиганському університеті. Він отримав назву «репродуктивний план Холланда» і ліг в основу практично всіх варіантів генетичних алгоритмів [8]. Однак, перед тим як ми його розглянемо докладніше, необхідно зупиниться на тому, яким чином об'єкти реального світу можуть бути закодовані для використання в генетичних алгоритмах.
1.2. Подання об'єктів. Кодування ознак
З біології ми знаємо, що будь-який організм може бути представлений своїм фенотипом, який фактично визначає, чим є об'єкт у реальному світі, і генотипом, який містить всю інформацію про об'єкт на рівні хромосомного набору. При цьому кожен ген, тобто елемент інформації генотипу, має своє відображення у фенотипі [9]. Таким чином, для вирішення завдань нам необхідно представити кожну ознаку об'єкта у формі, що підходить для використання в генетичному алгоритмі. Всі подальше функціонування механізмів генетичного алгоритму виробляється на рівні генотипу, дозволяючи обійтися без інформації про внутрішню структуру об'єкта, що й обумовлює його широке застосування в самих різних задачах.
У найбільш часто зустрічається різновиди генетичного алгоритму для подання генотипу об'єкту застосовуються бітові рядки. При цьому кожному атрибуту об'єкту у фенотипі відповідає один ген в генотипі об'єкта. Ген є бітову рядок, найчастіше фіксованої довжини, яка представляє собою значення цієї ознаки.
Для кодування таких ознак можна використовувати найпростіший варіант - бітове значення цієї ознаки. Тоді нам буде дуже просто використовувати ген певної довжини, достатньої для представлення всіх можливих значень такої ознаки. Таким кодом є код Грея, який доцільно використовувати в реалізації генетичного алгоритму [9]. Значення кодів Грея розглянуті в таблиці нижче:
Таким чином, для того, щоб визначити фенотип об'єкта (тобто значення ознак, що описують об'єкт) нам необхідно лише знати значення генів, відповідним цими ознаками, тобто генотип об'єкта. При цьому сукупність генів, що описують генотип об'єкта, являє собою хромосому. У деяких реалізаціях її також називають особиною. Таким чином, у реалізації генетичного алгоритму хромосома є бітову рядок фіксованої довжини. При цьому кожній ділянці рядка відповідає ген. Довжина генів усередині хромосоми може бути однаковою або різною. Найчастіше застосовують гени однакової довжини [10]. Розглянемо приклад хромосоми та інтерпретації її значення. Припустимо, що в об'єкта є 5 ознак, кожен закодований геном довжиною в 4 елементи. Тоді довжина хромосоми буде 5 * 4 = 20 біт
тепер ми можемо визначити значення ознак
1.3 Основні генетичні оператори
Як відомо в теорії еволюції важливу роль відіграє те, яким чином ознаки батьків передаються нащадкам. У генетичних алгоритмах за передачу ознак батьків нащадкам відповідає оператор, який називається схрещування (його також називають кросовер або кросинговер). Цей оператор визначає передачу ознак батьків нащадкам. Діє він у такий спосіб:
o з популяції обираються дві особини, які будуть батьками;
o визначається (зазвичай випадковим чином) точка розриву;
o нащадок визначається як конкатенація частини першого і другого батька.
Розглянемо функціонування цього оператора
Припустимо, розрив відбувається після 3-го біта хромосоми, тоді отримуємо.
Отже, розглянемо всі ж оператори по порядку:
1) кросинговер - створення структури, заснованої на двох структурах - заміною однієї частини першої структури на ту ж область у другій.
Приклад: з (A, B, C, D, E) і (a, b, c, d, e) вийде (A, B, c, d, E).
Потім з ймовірністю 0,5 визначається одна з результуючих хромосом в якості нащадка.
Наступний генетичний оператор призначений для того, щоб підтримувати різноманітність особин з популяції. Він називається оператором мутації. При використанні цього оператора кожен біт в хромосомі з певною ймовірністю інвертується. Крім того, використовується ще й так званий оператор інверсії, який полягає в тому, що хромосома ділиться на дві частини, і потім вони міняються місцями. Схематично це можна представити таким чином:
2) інверсія - перестановка в структурі деякої її частини навпаки
Приклад: з (1, 1, 0, 1, 0, 0, 1, 0) вийде (1, 1, 0, 0, 1, 0, 1, 0).
3) мутація - заміна в структурі одного з значень випадково вибраних компонентів
Приклад: з (1, 1, 0, 1, 0, 0, 1, 0) вийде (1, 1, 0, 1, 1, 0, 1, 0).
У принципі для функціонування генетичного алгоритму досить цих двох генетичних операторів, але на практиці застосовують ще й деякі додаткові оператори або модифікації цих двох операторів. Наприклад, кроссовер може бути не одноточечне (як було описано вище), а багатоточковий, коли формується кілька точок розриву (частіше всього дві). Крім того, в деяких реалізаціях алгоритму оператор мутації є інверсію тільки одного випадково обраного біта хромосоми.
1.4. Схема функціонування генетичного алгоритму
Тепер, знаючи як інтерпретувати значення генів, перейдемо до опису функціонування генетичного алгоритму. Розглянемо схему функціонування генетичного алгоритму в його класичному варіанті.
Ініціювати початковий момент часу t = 0. Випадковим чином сформувати початкову популяцію, що складається з k особин.
Обчислити пристосованість кожної особини і популяції в цілому (також іноді звану терміном фіттнес). Значення цієї функції визначає наскільки добре підходить особина, описана даної хромосомою, для вирішення завдання.
1. Вибрати особина з популяції.
2. З певною вірогідністю (ймовірністю кроссовера) вибрати другу особина з популяції і провести оператор кросовера.
3. З певною вірогідністю (ймовірністю мутації) виконати оператор мутації.
4. З певною вірогідністю (ймовірністю інверсії) виконати оператор інверсії.
5. Помістити отриману хромосому в нову популяцію
6. Виконати операції, починаючи з пункту 3, k разів.
7. Збільшити номер поточної епохи t = t +1.
8. Якщо виповнилося умова зупинки, то завершити роботу, інакше перехід на крок 2 [13].
Розпишемо більш докладно наступні етапи:
1. Вибір батьківської пари.
Перший підхід самий простий - це випадковий вибір батьківської пари ("панміксія"), коли обидві особини, які складуть батьківську пару, випадковим чином вибираються з усієї популяції, причому будь-яка особина може стати членом кількох пар. Незважаючи на простоту, такий підхід універсальний для вирішення різних класів задач. Але він досить критичний до чисельності популяції, оскільки ефективність алгоритму, що реалізує такий підхід, знижується зі зростанням чисельності популяції.
Другий спосіб вибору особин в батьківську пару - так званий селективний. Його суть полягає в тому, що "батьками" можуть стати тільки ті особини, значення пристосованості яких не менше середнього значення пристосованості по популяції, при рівній ймовірності таких кандидатів скласти шлюбну пару. Такий підхід забезпечує більш швидку збіжність алгоритму. Проте через швидку збіжність селективний вибір батьківської пари не підходить тоді, коли ставиться завдання визначення декількох екстремумів, оскільки для таких завдань алгоритм, як правило, швидко сходиться до одного з рішень. Крім того, для деякого класу задач зі складним ландшафтом пристосованості швидка відповідність може перетворитися на передчасну збіжність до квазіоптимальних рішень. Цей недолік може бути частково компенсований використанням відповідного механізму відбору (про що буде сказано нижче), який би "гальмував" занадто швидку збіжність алгоритму. Введення
Глава 1. Генетичні алгоритми
1.1 Природний відбір в природі
1.2 Представлення об'єктів. Кодування ознак
1.3 Основні генетичні оператори
1.4 Схема функціонування генетичного алгоритму
Висновок
Глава 2. Завдання оптимізації
2.1 Завдання, які вирішуються за допомогою генетичних алгоритмів
2.2 Математична постановка задачі оптимізації
2.3 Рішення діофантових рівнянь
2.4 Шляхи вирішення завдань оптимізації
2.5 Завдання комівояжера
Висновок
Глава 3. Програмна реалізація. Створення посібника з генетичним алгоритмам
3.1 Обгрунтування вибору програмного забезпечення
3.2 Опис програмної реалізації
Висновок
Бібліографія
ВСТУП
Природа вражає своєю складністю і багатством проявів. Серед прикладів можна назвати складні соціальні системи, імунні і нейронні системи, складні взаємозв'язки між видами. Вони - всього лише деякі з чудес, що стали очевидними при глибокому дослідженні природи навколо нас. Наука - це одна із систем, яка пояснює навколишнє і допомагає пристосуватися до нової інформації, одержуваної з зовнішнього середовища. Багато чого з того, що ми бачимо і спостерігаємо, можна пояснити теорією еволюції через спадковість, зміна і відбір.
На світогляд людей сильно вплинула теорія еволюції Чарльза Дарвіна, представлена в роботі "Походження Видів", в 1859 році. Безліч областей наукового знання багатьом зобов'язана революції, викликаної теорією еволюції і розвитку. Але Дарвін, подібно багатьом сучасникам, що передбачає, що в основі розвитку лежить природний відбір, не міг не помилятися. Наприклад, він не зміг показати механізм успадкування, при якому підтримується мінливість. Однак Дарвін виявив головний механізм розвитку: відбір у поєднанні з мінливістю. У багатьох випадках, специфічні особливості розвитку через мінливість і відбір все ще не безперечні, однак, основні механізми пояснюють неймовірно широкий спектр явищ, що спостерігаються в Природі. Тому не дивно, що вчені, які займаються комп'ютерними дослідженнями, у пошуках натхнення звернулися до теорії еволюції. Можливість того, що обчислювальна система, наділена простими механізмами мінливості і відбору, могла б функціонувати за аналогією з законами еволюції в природних системах, була дуже привабливою. Ця надія є причиною появи ряду обчислювальних систем, побудованих на принципах природного відбору.
Отже, в природі постійно відбувається процес вирішення завдань оптимізації. Завдання оптимізації - найбільш поширений і важливий для практики клас задач. Їх доводиться вирішувати кожному з нас або в побуті, розподіляючи свій час між різними справами, або на роботі, домагаючись максимальної швидкості роботи програми чи максимальної прибутковості компанії - залежно від посади.
Завдяки відкриттям останніх ста років сучасній науці відомі всі основні механізми еволюції, пов'язані з генетичним успадкуванням. Ці механізми досить прості за своєю ідеєю, але дотепні (якщо до природи застосовно це слово) і ефективні. Дивно, але просте моделювання еволюційного процесу на комп'ютері дозволяє отримати рішення багатьох практичних завдань. Такі моделі отримали назву "генетичні алгоритми" і вже широко застосовуються в різних областях.
У процесі вивчення різних підходів до вирішення завдань оптимізації нами висувається гіпотеза що, рішення задач оптимізації можливо за допомогою генетичних алгоритмів.
Об'єктом вивчення даної курсової роботи є генетичні алгоритми.
Предмет вивчення - застосування генетичних алгоритмів для знаходження рішення оптимізаційної задачі.
Методи дослідження:
o збір і аналіз літературних джерел з даної теми;
o вивчення особливостей створення і використання генетичних алгоритмів;
o моделювання роботи генетичного алгоритму на комп'ютері застосовно до знаходження рішення задачі оптимізації.
Метою даної курсової роботи є розробка електронного посібника, в якому поетапно описується рішення задачі про знаходження найкоротшого маршруту в існуючій системі доріг.
Завдання:
1. проаналізувати можливості генетичних алгоритмів;
2. вивчити особливості генетичних алгоритмів;
3. створення електронного посібника з основ генетичних алгоритмів;
РОЗДІЛ 1: ГЕНЕТИЧНІ АЛГОРИТМИ
1.1. Природний відбір в природі
"XIX столітті Чарльз Дарвін здійснив кругосвітнє плавання, збираючи інформацію для теорії еволюції на основі природного відбору, при якому виживає найсильніший. Чи міг він припускати, що сто років по тому математики будуть використовувати цю теорію для вирішення задачі про оптимальний маршрут навколосвітньої подорожі із зупинками на багатьох маленьких островах? .. "
Автор: РОСС Клемент
Опубліковано в журналі "Компьютерра" № 11 від 16 березня 1999
Ключову роль в еволюційній теорії грає природний відбір. Його суть полягає в тому, що найбільш пристосовані особини краще виживають і приносять більше нащадків, ніж менш пристосовані. Зауважимо, що сам по собі природний відбір ще не забезпечує розвиток біологічного виду. Тому дуже важливо зрозуміти, яким чином відбувається спадкування, тобто як властивості нащадка залежать від властивостей батьків.
Основний закон спадкування інтуїтивно зрозумілий кожному - він полягає в тому, що нащадки схожі на батьків. Зокрема, нащадки більш пристосованих батьків будуть, швидше за все, одними з найбільш пристосованих у своєму поколінні. Щоб зрозуміти, на чому грунтується це схожість, потрібно трохи заглибитися в побудову природної клітини - у світ генів і хромосом [4].
Майже в кожній клітині будь-якої особини є набір хромосом, що несуть інформацію про цю особини. Основна частина хромосоми - нитка ДНК, що визначає, які хімічні реакції будуть відбуватися в даній клітині, як вона буде розвиватися і які функції виконувати. Ген - це відрізок ланцюга ДНК, відповідальний за певну властивість особини, наприклад за колір очей, тип волосся, колір шкіри і т.д. При розмноженні тварин відбувається злиття двох батьківських статевих клітин та їх ДНК взаємодіють, створюючи ДНК нащадка. Основний спосіб взаємодії - кросовер (cross-over, схрещування). При кросовері ДНК предків діляться на дві частини, а потім обмінюються своїми половинками.
При успадкування можливі мутації через радіоактивності або інших впливів, у результаті яких можуть змінитися деякі гени в статевих клітинах одного з батьків. Змінені гени передаються нащадку і надають йому нових властивостей. Якщо ці нові властивості корисні, вони, швидше за все, збережуться в даному виді - при цьому відбудеться стрибкоподібне підвищення пристосованості виду. Вперше подібний алгоритм був запропонований у 1975 році Джоном Холландом (John Holland) в Мічиганському університеті. Він отримав назву «репродуктивний план Холланда» і ліг в основу практично всіх варіантів генетичних алгоритмів [8]. Однак, перед тим як ми його розглянемо докладніше, необхідно зупиниться на тому, яким чином об'єкти реального світу можуть бути закодовані для використання в генетичних алгоритмах.
1.2. Подання об'єктів. Кодування ознак
З біології ми знаємо, що будь-який організм може бути представлений своїм фенотипом, який фактично визначає, чим є об'єкт у реальному світі, і генотипом, який містить всю інформацію про об'єкт на рівні хромосомного набору. При цьому кожен ген, тобто елемент інформації генотипу, має своє відображення у фенотипі [9]. Таким чином, для вирішення завдань нам необхідно представити кожну ознаку об'єкта у формі, що підходить для використання в генетичному алгоритмі. Всі подальше функціонування механізмів генетичного алгоритму виробляється на рівні генотипу, дозволяючи обійтися без інформації про внутрішню структуру об'єкта, що й обумовлює його широке застосування в самих різних задачах.
У найбільш часто зустрічається різновиди генетичного алгоритму для подання генотипу об'єкту застосовуються бітові рядки. При цьому кожному атрибуту об'єкту у фенотипі відповідає один ген в генотипі об'єкта. Ген є бітову рядок, найчастіше фіксованої довжини, яка представляє собою значення цієї ознаки.
Для кодування таких ознак можна використовувати найпростіший варіант - бітове значення цієї ознаки. Тоді нам буде дуже просто використовувати ген певної довжини, достатньої для представлення всіх можливих значень такої ознаки. Таким кодом є код Грея, який доцільно використовувати в реалізації генетичного алгоритму [9]. Значення кодів Грея розглянуті в таблиці нижче:
| Двійкове кодування | Кодування за кодом Грея | ||||
| десяткове | двійкове | шестнадца- терічное | десяткове | двійкове | шестнадца- терічное |
| 0 | 000 | 0h | 0 | 0000 | 0h |
| 1 | 0001 | 1h | 1 | 0001 | 1h |
| 2 | 0010 | 2h | 3 | 0011 | 3h |
| 3 | 0011 | 3h | 2 | 0010 | 2h |
| 4 | 0100 | 4h | 6 | 0110 | 6h |
| 5 | 0101 | 5h | 7 | 0111 | 7h |
| 6 | 0110 | 6h | 5 | 0101 | 5h |
| 7 | 0111 | 7h | 4 | 0100 | 4h |
| 8 | 1000 | 8h | 12 | 1100 | Ch |
| 9 | 1001 | 9h | 13 | 1101 | Dh |
| 10 | 1010 | Ah | 15 | 1111 | Fh |
| 11 | 1011 | Bh | 14 | 1110 | Eh |
| 12 | 1100 | Ch | 10 | 1010 | Ah |
| 13 | 1101 | Dh | 11 | 1011 | Bh |
| 14 | 1110 | Eh | 9 | 1001 | 9h |
| 15 | 1111 | Fh | 8 | 1000 | 8h |
| 0010 | 1010 | 1001 | 0100 | 1101 |
| Ознака | Значення гена | Двійкове значення ознаки | Десяткове значення ознаки | ||||
| Ознака 1 | 0010 | 0011 | 3 | ||||
| Ознака 2 | 1010 | 1100 | 12 | ||||
| Ознака 3 | 1001 | 1110 | 14 | ||||
| Ознака 4 | 0100 | 0111 | 7 | ||||
| Ознака 5 | 1101 | 1001 | 9 | ||||
Як відомо в теорії еволюції важливу роль відіграє те, яким чином ознаки батьків передаються нащадкам. У генетичних алгоритмах за передачу ознак батьків нащадкам відповідає оператор, який називається схрещування (його також називають кросовер або кросинговер). Цей оператор визначає передачу ознак батьків нащадкам. Діє він у такий спосіб:
o з популяції обираються дві особини, які будуть батьками;
o визначається (зазвичай випадковим чином) точка розриву;
o нащадок визначається як конкатенація частини першого і другого батька.
Розглянемо функціонування цього оператора
| Хромосома_1: | 0000000000 |
| Хромосома_2: | 1111111111 |
| Хромосома_1: | 0000000000 | >> | 000 | 1111111 | Результуюча хромосома 1 |
| Хромосома_2: | 1111111111 | >> | 111 | 0000000 | Результуюча хромосома 2 |
1) кросинговер - створення структури, заснованої на двох структурах - заміною однієї частини першої структури на ту ж область у другій.
Приклад: з (A, B, C, D, E) і (a, b, c, d, e) вийде (A, B, c, d, E).
Потім з ймовірністю 0,5 визначається одна з результуючих хромосом в якості нащадка.
Наступний генетичний оператор призначений для того, щоб підтримувати різноманітність особин з популяції. Він називається оператором мутації. При використанні цього оператора кожен біт в хромосомі з певною ймовірністю інвертується. Крім того, використовується ще й так званий оператор інверсії, який полягає в тому, що хромосома ділиться на дві частини, і потім вони міняються місцями. Схематично це можна представити таким чином:
| 000 | 1111111 | >> | 1111111 | 000 |
Приклад: з (1, 1, 0, 1, 0, 0, 1, 0) вийде (1, 1, 0, 0, 1, 0, 1, 0).
3) мутація - заміна в структурі одного з значень випадково вибраних компонентів
Приклад: з (1, 1, 0, 1, 0, 0, 1, 0) вийде (1, 1, 0, 1, 1, 0, 1, 0).
У принципі для функціонування генетичного алгоритму досить цих двох генетичних операторів, але на практиці застосовують ще й деякі додаткові оператори або модифікації цих двох операторів. Наприклад, кроссовер може бути не одноточечне (як було описано вище), а багатоточковий, коли формується кілька точок розриву (частіше всього дві). Крім того, в деяких реалізаціях алгоритму оператор мутації є інверсію тільки одного випадково обраного біта хромосоми.
1.4. Схема функціонування генетичного алгоритму
Тепер, знаючи як інтерпретувати значення генів, перейдемо до опису функціонування генетичного алгоритму. Розглянемо схему функціонування генетичного алгоритму в його класичному варіанті.
Ініціювати початковий момент часу t = 0. Випадковим чином сформувати початкову популяцію, що складається з k особин.
Обчислити пристосованість кожної особини і популяції в цілому (також іноді звану терміном фіттнес). Значення цієї функції визначає наскільки добре підходить особина, описана даної хромосомою, для вирішення завдання.
1. Вибрати особина з популяції.
2. З певною вірогідністю (ймовірністю кроссовера) вибрати другу особина з популяції і провести оператор кросовера.
3. З певною вірогідністю (ймовірністю мутації) виконати оператор мутації.
4. З певною вірогідністю (ймовірністю інверсії) виконати оператор інверсії.
5. Помістити отриману хромосому в нову популяцію
6. Виконати операції, починаючи з пункту 3, k разів.
7. Збільшити номер поточної епохи t = t +1.
8. Якщо виповнилося умова зупинки, то завершити роботу, інакше перехід на крок 2 [13].
Розпишемо більш докладно наступні етапи:
1. Вибір батьківської пари.
Перший підхід самий простий - це випадковий вибір батьківської пари ("панміксія"), коли обидві особини, які складуть батьківську пару, випадковим чином вибираються з усієї популяції, причому будь-яка особина може стати членом кількох пар. Незважаючи на простоту, такий підхід універсальний для вирішення різних класів задач. Але він досить критичний до чисельності популяції, оскільки ефективність алгоритму, що реалізує такий підхід, знижується зі зростанням чисельності популяції.
Інші два способи формування батьківської пари, на які хотілося б звернути увагу, це інбридинг і аутбридинг. Обидва ці методу побудовані на формуванні пари на основі близького і далекого "спорідненості" відповідно. Під "спорідненням" тут розуміється відстань між членами популяції як в сенсі геометричного відстані особин у просторі параметрів. У зв'язку з цим будемо розрізняти генотипний і фенотипно (або географічний) інбридинг і аутбридинг. Під інбридингом розуміється такий метод, коли перший член пари вибирається випадково, а другим з більшою ймовірністю буде максимально близька до нього особина. Аутбридинг ж, навпаки, формує шлюбні пари з максимально далеких особин. Використання генетичних інбридингу і аутбридинга виявилося більш ефективним у порівнянні з географічним для всіх тестових функцій при різних параметрах алгоритму. Найбільш корисне застосування обох представлених методів для багатоекстремального завдань [14]. Проте два цих способу по-різному впливають на поведінку генетичного алгоритму. Так інбридинг можна охарактеризувати властивістю концентрації пошуку в локальних вузлах, що фактично призводить до розбиття популяції на окремі локальні групи навколо підозрілих на екстремум ділянок ландшафту, навпаки аутбридинг якраз спрямований на попередження збіжності алгоритму до вже знайденим рішенням, змушуючи алгоритм переглядати нові, недосліджені області.
2. Механізм відбору
Обговорення питання про вплив методу створення батьківських пар на поведінку генетичного алгоритму неможливо вести у відриві від реалізованого механізму відбору при формуванні нового покоління. Найбільш ефективні два механізми відбору елітний і відбір з витісненням.
Ідея елітного відбору, загалом, не нова, цей метод заснований на побудові нової популяції тільки з кращих особин репродукційної групи, що об'єднує в собі батьків, їх нащадків і мутантів. В основному це пояснюють потенційною небезпекою передчасної збіжності, віддаючи перевагу пропорційному відбору. Швидка відповідність, забезпечувана елітним відбором, може бути, коли це необхідно, з успіхом компенсували підходящим методом вибору батьківських пар, наприклад аутбридинг. Саме така комбінація "аутбридинг - елітний відбір" є однією з найбільш ефективною. Другий метод, на якому хотілося б зупинитися, це відбір витісненням. Чи буде особина з репродукційної групи заноситися в популяцію нового покоління, визначається не тільки величиною її пристосованості, а й тим, чи є вже в формованої популяції наступного покоління особина з аналогічним хромосомним набором. З усіх особин з однаковими генотипами перевагу спочатку, звичайно ж, віддається тим, чия пристосованість вище. Таким чином, досягається дві мети: по-перше, не губляться кращі знайдені рішення, які мають різними хромосомними наборами, а по-друге, в популяції постійно підтримується достатня генетичну різноманітність. Витіснення в даному випадку формує нову популяцію скоріше з далеко розташованих особин, замість особин, що групуються близько поточного знайденого рішення. Цей метод особливо добре себе показав при вирішенні багатоекстремального завдань, при цьому крім визначення глобальних екстремумів з'являється можливість виділити і ті локальні максимуми, значення яких близькі до глобальних.
Висновок
Отже, викладений підхід до вивчення генетичних алгоритмів є евристичним, тобто показує хороші результати на практиці, але погано піддається теоретичному дослідженню та обгрунтуванню. Природно поставити питання - чи слід користуватися такими алгоритмами, що не мають строгого математичного обгрунтування?
Як і в питанні про нейронні мережі, тут не можна відповісти однозначно. З одного боку, в математиці існує досить великий клас абсолютно надійних (в сенсі гарантії отримання точного рішення) методів вирішення різних завдань. З іншого боку, мова йде про дійсно складних практичних завданнях, в яких ці надійні методи часто непридатні. Нерідко ці завдання виглядають настільки неозорими, що не робиться навіть спроб їх осмисленого рішення. [15]
Наприклад, фірма, що займається транспортними перевезеннями, в сучасних умовах російського бізнесу швидше віддасть перевагу найняти зайвих водіїв та підвищити ціни на свої послуги, ніж оптимізувати маршрути і розкладу поїздок. На західному ринку, де вже давно діють закони більш-менш чесної конкуренції, оптимальність діяльності компанії значно впливає на її доходи і навіть може стати вирішальним чинником для її виживання. Тому будь-які ідеї, що дозволяють компанії стати "розумнішими" своїх конкурентів, знаходять там широке застосування.
Генетичні алгоритми - реалізація однієї з найбільш популярних ідей такого роду. Ця популярність викликана, мабуть, винятковою красою підходу і його близькістю до природного механізму. Подібним чином популярність нейромережевої технології підігрівається багато в чому її схожістю з роботою мозку. По-справжньому активний розвиток евристичних підходів безпосередньо пов'язано з розвитком вільного ринку та економіки в цілому.
Таким чином, задавши умови життя в деякому віртуальному світі і заселивши його представниками з певними властивостями, після процесів схрещування, мутації і природного відбору, аналоги яких відбуваються і в реальному світі, ми стабільно отримуємо особина, властивості якої відповідають раніше заданим вимогам. Успішне вирішення завдання змушує захоплюватися мудрістю природи, що реалізувала такий дивно нескладний і приголомшливо ефективний механізм. Цей факт наводить на думку про те, що розуміння перевірених століттями законів природи дозволяє використовувати їх при вирішенні, здавалося б, і далеких від неї завдань, окремим випадком яких є розглянуті далі задачі оптимізації.
РОЗДІЛ 2. ЗАВДАННЯ ОПТИМІЗАЦІЇ.
2.1 Завдання, які вирішуються за допомогою генетичних алгоритмів
Тепер ми з вами розуміємо, на чому грунтуються принципи роботи генетичних алгоритмів. Але для вирішення яких завдань реалізуються ці алгоритми? Отже, в цьому розділі нами будуть розглянуті задачі оптимізації, їх математична постановка та шляхи вирішення. Так само нами будуть розглянуті рішення діофантових рівнянь і задачі комівояжера.
Завдання оптимізації - найбільш поширений і важливий для практики клас задач. Їх доводиться вирішувати кожному з нас або в побуті, розподіляючи свій час між різними справами, або на роботі, домагаючись максимальної швидкості роботи програми чи максимальної прибутковості компанії - залежно від посади.
2.2 Математична постановка задачі оптимізації
Постановка задачі оптимізації включає в себе безліч допустимих рішень
Не можна ототожнювати критерій (критерії) оптимальності та цільову функцію.
Цільова функція - це аналітична залежність між критерієм (критеріями) оптимальності і підлягають оптимізації параметрами з вказівкою напрямку екстремуму.
Відмінність понять «критерій» і «цільова функція» полягає в наступному:
1. Цільова функція може включати в себе більше одного критерію.
2. Для цільової функції завжди і обов'язково вказується вид екстремуму:
Розрізняють два види завдань оптимізації:
o Завдання мінімізації.
o Завдання максимізації.
Щоб вирішити задачу мінімізації функції
Щоб вирішити завдання максимізації функції на множині, необхідно знайти такий вектор (а також відповідне значення цільової функції), щоб нерівність: виконувалося для всіх. При цьому називають оптимальним (максимальним) рішенням, а-оптимумом (максимумом).
У загальному вигляді знаходиться саме вектор
2.3 Рішення діофантових рівнянь
Розглянемо Діофантові (тільки цілі рішення) рівняння: a +2 b +3 c +4 d = 30, де a, b, c і d - деякі позитивні цілі. Застосування ГА за дуже короткий час знаходить шукане рішення (a, b, c, d).
Звичайно, Ви можете запитати: чому б не використати метод грубої сили: просто не підставити всі можливі значення a, b, c, d (очевидно, 1 <= a, b, c, d <= 30)?
Архітектура ГА-систем дозволяє знайти рішення швидше за рахунок більш 'осмисленого' перебору. Ми не перебираємо всі підряд, але наближаємося від випадково вибраних рішень до кращих.
Для початку виберемо 5 випадкових рішень: 1 = <a, b, c, d = <30. Взагалі кажучи, ми можемо використовувати меншу обмеження для b, c, d, але для спрощення нехай буде 30.
| Хромосома | (A, b, c, d) |
| 1 | (1,28,15,3) |
| 2 | (14,9,2,4) |
| 3 | (13,5,7,3) |
| 4 | (23,8,16,19) |
| 5 | (9,13,5,2) |
Щоб обчислити коефіцієнти виживання (fitness), підставимо кожне рішення у вираз a +2 b +3 c +4 d. Відстань від отриманого значення до 30 і буде потрібним значенням.
| Хромосома | Коефіцієнт виживаності |
| 1 | | 114-30 | = 84 |
| 2 | | 54-30 | = 24 |
| 3 | | 56-30 | = 26 |
| 4 | | 163-30 | = 133 |
| 5 | | 58-30 | = 28 |
Так як менші значення ближче до 30, то вони більш бажані. У нашому випадку великі чисельні значення коефіцієнтів виживаності підходять, на жаль, менше. Щоб створити систему, де хромосоми з більш підходящими значеннями мають великі шанси опинитися батьками, ми повинні обчислити, з якою ймовірністю (у%) може бути обрана кожна. Одне рішення полягає в тому, щоб взяти суму зворотних значень коефіцієнтів, і виходячи з цього обчислювати проценти. (Зауважимо, що всі рішення були згенеровані Генератором Випадкових Чисел - ГВЧ)
| Хромосома | Подходімость |
| 1 | (1 / 84) / 0.135266 = 8.80% |
| 2 | (1 / 24) / 0.135266 = 30.8% |
| 3 | (1 / 26) / 0.135266 = 28.4% |
| 4 | (1 / 133) / 0.135266 = 5.56% |
| 5 | (1 / 28) / 0.135266 = 26.4% |
Для вибору 5-и пар батьків (кожна з яких матиме 1 нащадка, всього - 5 нових рішень), уявімо, що у нас є 10000-стоная гральна кістка, на 880 сторонах відзначена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 і на 2640 сторонах відзначена хромосома 5. Щоб вибрати першу пару, кидаємо кістка два рази і вибираємо випали хромосоми. Таким же чином вибираючи інших, отримуємо:
| Хромосома батька | Хромосома матері |
| 3 | 1 |
| 5 | 2 |
| 3 | 5 |
| 2 | 5 |
| 5 | 3 |
Кожен нащадок містить інформацію про гени і батька і від матері. Взагалі кажучи, це можна забезпечити різними способами, однак у нашому випадку можна використовувати т.зв. "Кроссовер" (cross-over). Нехай мати містить наступний набір рішень: a1, b1, c1, d1, а батько - a2, b2, c2, d2, тоді можливо 6 різних крос-оверов (| = розділова лінія):
| Хромосома-батько | Хромосома-мати | Хромосома-нащадок |
| a1 | b1, c1, d1 | a2 | b2, c2, d2 | a1, b2, c2, d2 or a2, b1, c1, d1 |
| a1, b1 | c1, d1 | a2, b2 | c2, d2 | a1, b1, c2, d2 or a2, b2, c1, d1 |
| a1, b1, c1 | d1 | a2, b2, c2 | d2 | a1, b1, c1, d2 or a2, b2, c2, d1 |
Є досить багато шляхів передачі інформації нащадкові, і крос-овер - тільки один з них. Розташування роздільник може бути абсолютно довільним, як і те, батько чи мати будуть зліва від межі.
А тепер спробуємо зробити це з нашими нащадками
| Хромосома-батько | Хромосома-мати | Хромосома-нащадок |
| (13 | 5,7,3) | (1 | 28,15,3) | (13,28,15,3) |
| (9,13 | 5,2) | (14,9 | 2,4) | (9,13,2,4) |
| (13,5,7 | 3) | (9,13,5 | 2) | (13,5,7,2) |
| (14 | 9,2,4) | (9 | 13,5,2) | (14,13,5,2) |
| (13,5 | 7, 3) | (9,13 | 5, 2) | (13,5,5,2) |
Тепер ми можемо обчислити коефіцієнти виживання (fitness) нащадків.
| Хромосома-нащадок | Коефіцієнт виживаності |
| (13,28,15,3) | | 126-30 | = 96 |
| (9,13,2,4) | | 57-30 | = 27 |
| (13,5,7,2) | | 57-30 | = 22 |
| (14,13,5,2) | | 63-30 | = 33 |
| (13,5,5,2) | | 46-30 | = 16 |
Середня пристосованість (fitness) нащадків виявилася 38.8, в той час як у батьків цей коефіцієнт дорівнював 59.4. Наступне покоління може мутувати. Наприклад, ми можемо замінити одне з значень будь-небудь хромосоми на випадкове ціле від 1 до 30. Продовжуючи, таким чином, одна хромосома, в кінці кінців, досягне коефіцієнта виживання 0, тобто стане рішенням. Системи з більшою популяцією (наприклад, 50 замість 5-та) сходяться до бажаного рівня (0) більш швидко і стабільно.
2.4. Шляхи вирішення завдань оптимізації
Генетичний алгоритм - новітній, але не єдино можливий спосіб рішення задач оптимізації. З давніх-давен відомі два основні шляхи вирішення таких завдань - переборними та локально-градієнтний. У цих методів свої достоїнства і недоліки, і в кожному конкретному випадку слід подумати, який з них вибрати.
Розглянемо переваги і недоліки стандартних і генетичних методів на прикладі класичної задачі комівояжера (TSP - travelling salesman problem). [20] Суть завдання полягає в тому, щоб знайти найкоротший замкнутий шлях обходу декількох міст, заданих своїми координатами. Виявляється, що вже для 30 міст пошук оптимального шляху являє собою складну задачу, що спонукала розвиток різних нових методів (у тому числі нейромереж та генетичних алгоритмів).
рис. SEQ ріс._ \ * ARABIC 1 Найкоротший шлях
Кожен варіант рішення (для 30 міст) - це числова рядок, де на j-му місці стоїть номер j-ого по порядку обходу міста. Таким чином, в цьому завданні 30 параметрів, причому не всі комбінації значень допустимі. Природно, першою ідеєю є повний перебір всіх варіантів обходу.
рис. SEQ ріс._ \ * ARABIC 2 переборних метод | Переборних метод найбільш простий за своєю суттю і тривіальний в програмуванні. Для пошуку оптимального рішення (точки максимуму цільової функції) потрібно послідовно обчислити значення цільової функції у всіх можливих точках, запам'ятовуючи максимальна з них. |
Недоліком цього методу є велика обчислювальна вартість. Зокрема, в задачі комівояжера потрібно прорахувати довжини понад 1030 варіантів шляхів, що абсолютно нереально. Однак, якщо перебір всіх варіантів за розумний час можливий, то можна бути абсолютно впевненим у тому, що знайдене рішення справді оптимально.
Градієнтні методи працюють дуже швидко, але не гарантують оптимальності знайденого рішення. Вони ідеальні для застосування у так званих унімодальних завданнях, де цільова функція має єдиний локальний максимум (він же - глобальний). Легко бачити, що завдання комівояжера унімодальної не є.
Отже, якщо на деякій множині задана складна функція від декількох змінних, то генетичний алгоритм - це програма, яка за розумний час знаходить точку, де значення функції досить близько до максимально можливого. Вибираючи прийнятний час розрахунку, ми отримаємо одне з кращих рішень, які взагалі можливо отримати за цей час [20].
2.5 Рішення задачі комівояжера.
Завдання комівояжера є класичною оптимізаційної завданням. Суть її полягає в наступному. Дано безліч з п міст і матриця відстаней між ними або вартостей переїзду (залежно від інтерпретації). Мета комівояжера - об'їхати всі ці міста по найкоротшому шляху або з найменшими витратами на поїздку. Причому в кожному місті він повинен побувати один раз і свій шлях закінчити в тому ж місті, звідки почав.
Для вирішення пропонується наступне завдання: є п'ять міст, вартість переїзду між якими представлена наступною матрицею:
Для вирішення завдання застосуємо наступний генетичний алгоритм. Рішення представимо у вигляді перестановки чисел від 1 до 5, що відображає послідовність відвідування міст. А значення цільової функції буде дорівнює вартості всієї поїздки, обчисленої відповідно до вищенаведеної матрицею. Відразу зауважимо, що одним з оптимальних рішень задачі є послідовність 514235 вартістю 25.
Зауважимо, що чим менше значення цільової функції, тим краще. Тобто метою в даному випадку є пошук мінімуму цільової функції.
В якості оператора схрещування виберемо процедуру, схожу на двоточковим оператор схрещування. Пояснимо його роботу на прикладі. Нехай є дві батьківські перестановки (12345) і (34 521). Випадково і равновероятно обираються дві точки розриву. Для прикладу візьмемо ситуацію, коли перша точка розриву знаходиться між першим і другим елементами перестановки, а друга точка - між четвертим і п'ятим: (1 | 2 3 4 | 5), (3 | 4 52 | 1). На першому етапі перестановки обмінюються фрагментами, укладеними між точками розриву: (* | 452 | *), (* | 234 | *). На другому етапі замість зірочок вставляються відповідні числа з вихідної батьківської перестановки, починаючи з другого числа виділеного фрагмента і пропускаючи вже наявні в новій перестановці числа. У даному випадку в першій перестановці (1 | 234 | 5) таким початковим числом є 3, за ним йде 4, яке є в новій перестановці, і ми його пропускаємо, також пропускаємо число 5, переходимо на початок перестановки і вибираємо число 1. У результаті замість (* | 5 квітня 2 | *) отримуємо (34521), аналогічно з (3 | 452 | 1) і (* | 234 | *) отримуємо (52341).
Оператор мутації буде представляти собою випадкову перестановку двох чисел в хромосомі, також вибраних випадково по рівномірному закону. Вірогідність мутації 0,01. Розмір популяції виберемо рівним 4.
Вихідна популяція представлена в таблиці 1.
Таблиця SEQ Таблиця \ * ARABIC 1
Нехай для схрещування були обрані наступні пари: (1, 3) і (2, 4). У результаті були отримані нащадки, представлені в таблиці 2.
Таблиця SEQ Таблиця \ * ARABIC 2
Нехай для нащадка (12354) спрацював оператор мутації, і обмінялися місцями числа 2 і 3. У даному випадку рядок (12354) змінилася і прийняла значення (13254). Популяція першого покоління після відсікання гірших особин в результаті роботи оператора редукції прийняла вигляд, поданий у таблиці 3.
Таблиця SEQ Таблиця \ * ARABIC 3
Нехай для отримання другого покоління були обрані наступні пари рядків: (1,4) і (2, 3). І в результаті були отримані нащадки, показані в таблиці 4.
Таблиця SEQ Таблиця \ * ARABIC 4
Популяція другого покоління після відсікання гірших особин прийняла вигляд, показаний у таблиці 5.
Таблиця SEQ Таблиця \ * ARABIC 5
Таким чином, після двох ітерацій значення цільової функції для кращого вирішення змінилося з 29 на 28, середнє значення змінилося з 30,5 до 28,75, а загальна якість з 122 до 111. Тобто також в наявності незначне, але поліпшення популяції [21].
Висновок
Існує безліч варіантів завдань оптимізації. Особливо важко переоцінити їх значимість в математичній економіці. Ми з вами розглянули їх основні шляхи вирішення і на прикладі рішення діофантових рівнянь і задачі комівояжера переконалися в тому, що генетичний алгоритм є найбільш універсальним методом рішення.
РОЗДІЛ 3. ПРОГРАМНА РЕАЛІЗАЦІЯ. СТВОРЕННЯ Допомога по Генетичні алгоритми.
3.1 Обгрунтування вибору програмного забезпечення
Останнім часом різко зріс інтерес до програмування. Це пов'язано з розвитком і впровадженням в повсякденне життя інформаційно-комунікаційних технологій. Якщо людина має справу з комп'ютером, то рано чи пізно у нього виникає бажання, а іноді і необхідність, програмувати.
Серед користувачів персональних комп'ютерів в даний час найбільш популярне сімейство операційних систем Windows і, природно, що той, хто збирається програмувати, прагне писати програми, які будуть працювати в цих системах.
Інтерактивність - сьогодні найбільш важливе, ми б сказали основне
умова для створюваних додатків. Найбільш повний стандарт, який гарантує дану умову, став усім відомий Action Script для Flash. Порівняно недавно він перетворився з простого мови підготовки сценаріїв у повноцінну об'єктно-орієнтоване середовище програмування.
Як ви пам'ятаєте, нашою метою є створення електронного посібника, яке дозволило б достатньо зрозуміло і просто донести до читача основні поняття і принципи організації генетичного алгоритму. Action Script надає прекрасну можливість, організувати барвистий, доступний інтерфейс і навігацію. І ще один незаперечний плюс при створенні підручника на Action Script: використання готового продукту, як самостійну програму (публікація готового продукту з exe розширенням).
3.2 Опис програмної реалізації
Для початку, ми підготували матеріал, який буде представлений в нашому посібнику. Визначилися зі структурою та дизайном, і тільки після цього почалося безпосередньо створення нашого продукту.
Ми використовували, як було згадано вище, Macromedia Flash MX2004. Алгоритм створення наступний:
1. Створюємо новий Flash документ.
2. Опрацьовуємо дизайн нашого допомоги (встановлення фону, шрифту)
3. Розміщуємо підготовлений нами матеріал на кадрах, попередньо вставивши на кожному з них ключовий кадр.
4. Організація навігації.
5. Перевірка і публікація створеного документа в exe форматі.
Розпишемо докладніше деякі пункти.
Розміщення матеріалу було сформовано на зразок звичайної книги з заголовком, змістом і можливістю перегортання сторінок.
Зміст Навігація (перегортання сторінок)
Що стосується навігації і безпосередньо програмування мовою Action Script, тут теж не виникло жодних проблем. Сама програма пишеться у вікні Action, при виділення об'єкта, але який пишуться дії.
Flash Action Script діє за наступним сценарієм:
o сценарій Action Script налаштовується на виявлення певної події.
o Як тільки подія відбувається, виконується обробляє цю подію набір інструкцій Action Script.
На кожен кадр (сторінку нашого посібника) пишеться певна заготовка:
stop ();
/ / Зупиняє автоматичне програвання кадрів.
- На кожну кнопку пишеться інша заготівля:
on (release) {
gotoAndStop ("Scene 1 " , 2);
}
/ / Отже, пояснимо цю нескладну конструкцію. іншими словами перша рядок буде виглядати так: при (відпуску) {виконати це ...}. Команда gotoAndStop дозволяє нам перейти на другий кадр першої сцени і зупинитися.
Ще одне невеличке зауваження, необхідно перетворити намальовану або вставлену з бібліотеки кнопку на символ. Для цього виділяємо наш об'єкт правою кнопкою, і вибираємо в контекстному меню Convert, у меню, ставимо галочку навпроти Button.
У Flash ми на кожному кроці можемо перевіряти (налагоджувати) нашу розробку, для цього в головному меню вибираємо Control / Test movie.
І, нарешті, на останньому кроці ми публікуємо наш посібник в exe форматі, для того, щоб наша розробка запускалася на комп'ютері будь-якого користувача, в не залежності від того, встановлена на його комп'ютері Flash чи ні.
Висновок
Ми з вами пройшли великий шлях, відкриваючи для себе генетичні алгоритми, їх, здавалося б, тривіальну і одночасно з цим геніальну ідею, взяту з природи. У ході вивчення ми багато разів вказували на достоїнства і недоліки генетичних алгоритмів. Серед найбільш значущих позитивних сторін, можна відзначити:
Перший випадок: коли не відомий спосіб точного рішення задачі. Якщо ми знаємо, як оцінити пристосованість хромосом, то завжди можемо змусити генетичний алгоритм вирішувати цю задачу.
Другий випадок: коли спосіб для точного рішення існує, але він дуже складний у реалізації, вимагає великих витрат часу і грошей, тобто, простіше кажучи, справа того не варто. Приклад - створення програми для складання персонального розкладу на основі техніки покриття множин з використанням лінійного програмування.
Що ж стосується недоліків, то в загальному випадку генетичні алгоритми не знаходять оптимального рішення дуже важких завдань. Якщо оптимальне рішення задачі (наприклад, задача комівояжера з дуже великим числом міст) не може бути знайдено традиційними способами, то й генетичний алгоритм навряд чи знайде оптимум
Поряд з генетичними алгоритмами відомі й інші методи рішення задач оптимізації, засновані на природних механізмах, такі як моделювання відпалу (simulated annealing) і табу-пошук (taboo search). Але ефект випадковості, який безумовно присутній при вирішенні генетичним алгоритмом, дуже надихає.
Незважаючи на невелику кількість завдань, яке ми з вами розглянули: рішення діофантових рівнянь і завдання комівояжера, ми повністю підтверджуємо нашу гіпотезу. Завдання оптимізації (і не тільки) успішно вирішуються за допомогою генетичних алгоритмів.
Б ібліографія
1. Вентцель Є.С. «Дослідження операцій», - М.: 1972 р .
2. Гальцина О.Л., Попов І.І. «Основи алгоритмізації та програмування».
3. Грешілов А.А. «Як взяти найкраще рішення в реальних умовах», - М.: 1991 р Р., стор. 164-170
4. Корнєєв В.В., Гарєєв А.Ф. «Бази даних. Інтелектуальна обробка даних », М.: 2001р., Стор 220
5. Коршунов Ю.М. «Математичні основи кібернетики. Для студентів вузів », - М.: 1987 р Р., стор. 67-89
6. Леонов О.І. «Теорія графів».
7. Майнік Е., «Алгоритми оптимізації на мережах і графах.» - М.: 1981
8. Новіков Ф.А. «Дискретна математика для програмістів».
9. «Генетичні алгоритми: чому вони працюють?» / Компьютерра, № 11, 1999 рік
10. Де Джонг К. А. Введення до другого спеціального випуску по
генетичним алгоритмам. Машинне навчання, № 5 (4), с. 351-353
11. Електронні джерела:
12. «Генетичні алгоритми по-російськи» - http://www.chat.ru/ ~ saisa
13. «Нейропроект. Аналітичні технології XXI століття »- http://www.neuroproject.ru
14. «Наукове видавництво ТВП» - http://www.tvp.ru/mathem3.htm
15. «Факультет обчислювальної математики і кібернетики МГУ (ВМиК)» - http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html
16. «Neural Bench Development» - http://www.neuralbench.ru/rus/theory/genetic.htm
17. «Журнал" Автоматизація Проектування "» - http://www.opensystems.ru/ap/1999/01/08.htm
18. «(EHIPS) Генетичні алгоритми» - http://www.iki.rssi.ru/ehips/genetic.htm
19. «SENN Генетичні Алгоритми» - http://fdmhi.mega.ru/ru/senn_ga.htm
20. Хорева Є.В. Курсова робота. Тема «Застосування генетичних алгоритмів для вирішення задач оптимізації»-КДПУ.: 2007р.
21. «Лекції з нейронних мереж і генетичних алгоритмів» - http://infoart.baku.az/inews/30000007.htm
| Другий популярний спосіб грунтується на методі градієнтного спуску (рис. 7). При цьому спочатку вибираються деякі випадкові значення параметрів, а потім ці значення поступово змінюють, домагаючись найбільшої швидкості зростання цільової функції. Досягнувши локального максимуму, такий алгоритм зупиняється, тому для пошуку глобального оптимуму будуть потрібні додаткові зусилля. | рис. SEQ ріс._ \ * ARABIC 3 Метод градієнтного спуску |
рис. SEQ ріс._ \ * ARABIC 4 | Типова практичне завдання, як правило, мультимодальна і багатовимірна, тобто містить багато параметрів. Для таких завдань не існує жодного універсального методу, який дозволяв би досить швидко знайти абсолютно точне рішення (рис. 8). |
| Проте, комбінуючи переборних і градієнтний методи, можна сподіватися отримати хоча б наближене рішення, точність якого буде зростати при збільшенні часу розрахунку. (Рис. 9) | рис. SEQ ріс._ \ * ARABIC 5 |
| Генетичний алгоритм являє собою саме такий комбінований метод (рис. 10). Механізми схрещування і мутації в якомусь сенсі реалізують переборних частина методу, а відбір кращих рішень - градієнтний спуск. На малюнку показано, що така комбінація дозволяє забезпечити стійко гарну ефективність генетичного пошуку для будь-яких типів завдань. |
2.5 Рішення задачі комівояжера.
Завдання комівояжера є класичною оптимізаційної завданням. Суть її полягає в наступному. Дано безліч з п міст і матриця відстаней між ними або вартостей переїзду (залежно від інтерпретації). Мета комівояжера - об'їхати всі ці міста по найкоротшому шляху або з найменшими витратами на поїздку. Причому в кожному місті він повинен побувати один раз і свій шлях закінчити в тому ж місті, звідки почав.
Для вирішення пропонується наступне завдання: є п'ять міст, вартість переїзду між якими представлена наступною матрицею:
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 4 | 6 | 2 | 9 |
| 2 | 4 | 0 | 3 | 2 | 9 |
| 3 | 6 | 3 | 0 | 5 | 9 |
| 4 | 2 | 2 | 5 | 0 | 8 |
| 5 | 9 | 9 | 9 | 8 | 0 |
Зауважимо, що чим менше значення цільової функції, тим краще. Тобто метою в даному випадку є пошук мінімуму цільової функції.
В якості оператора схрещування виберемо процедуру, схожу на двоточковим оператор схрещування. Пояснимо його роботу на прикладі. Нехай є дві батьківські перестановки (12345) і (34 521). Випадково і равновероятно обираються дві точки розриву. Для прикладу візьмемо ситуацію, коли перша точка розриву знаходиться між першим і другим елементами перестановки, а друга точка - між четвертим і п'ятим: (1 | 2 3 4 | 5), (3 | 4 52 | 1). На першому етапі перестановки обмінюються фрагментами, укладеними між точками розриву: (* | 452 | *), (* | 234 | *). На другому етапі замість зірочок вставляються відповідні числа з вихідної батьківської перестановки, починаючи з другого числа виділеного фрагмента і пропускаючи вже наявні в новій перестановці числа. У даному випадку в першій перестановці (1 | 234 | 5) таким початковим числом є 3, за ним йде 4, яке є в новій перестановці, і ми його пропускаємо, також пропускаємо число 5, переходимо на початок перестановки і вибираємо число 1. У результаті замість (* | 5 квітня 2 | *) отримуємо (34521), аналогічно з (3 | 452 | 1) і (* | 234 | *) отримуємо (52341).
Оператор мутації буде представляти собою випадкову перестановку двох чисел в хромосомі, також вибраних випадково по рівномірному закону. Вірогідність мутації 0,01. Розмір популяції виберемо рівним 4.
Вихідна популяція представлена в таблиці 1.
Таблиця SEQ Таблиця \ * ARABIC 1
| № рядка | Код | Значення цільової функції | Вірогідність участі в процесі розмноження |
| 1 | 12345 | 29 | 32/122 |
| 2 | 21435 | 29 | 32/122 |
| 3 | 54312 | 32 | 29/122 |
| 4 | 43125 | 32 | 29/122 |
Таблиця SEQ Таблиця \ * ARABIC 2
| № рядка | Батьки | Нащадки | Значення цільової функції для нащадків |
| 1 | 1 | 23 | 45 | 5 | 43 | 12 | 32 |
| 3 | 5 | 43 | 12 | 1 | 23 | 54 мутація 13254 | 28 |
| 2 | 2 | 143 | 5 | 4 | 312 | 5 | 32 |
| 4 | 4 | 312 | 5 | 2 | 143 | 5 | 29 |
Таблиця SEQ Таблиця \ * ARABIC 3
| № рядка | Код | Значення цільової функції | Вірогідність участі в процесі розмноження |
| 1 (1) | 12345 | 29 | 28/122 |
| 2 (2) | 21435 | 29 | 28/122 |
| 3 (н) | 13254 | 28 | 29/122 |
| 4 (н) | 21435 | 29 | 28/122 |
Таблиця SEQ Таблиця \ * ARABIC 4
| № рядка | Батьки | Нащадки | Значення цільової функції для нащадків |
| 1 | | 123 | 45 | | 214 | 35 | 29 |
| 4 | | 214 | 35 | | 123 | 45 | 29 |
| 2 | | 21 | 435 | | 13 | 452 | 32 |
| 3 | | 13 | 254 | | 21 | 354 | 29 |
Таблиця SEQ Таблиця \ * ARABIC 5
| № рядка | Код | Значення цільової функції | Вірогідність участі в процесі розмноження |
| 1 (1) | 12345 | 29 | 28/111 |
| 2 (2) | 21435 | 29 | 28/111 |
| 3 (3) | 13254 | 28 | 29/111 |
| 4 (н) | 21354 | 29 | 28/111 |
Висновок
Існує безліч варіантів завдань оптимізації. Особливо важко переоцінити їх значимість в математичній економіці. Ми з вами розглянули їх основні шляхи вирішення і на прикладі рішення діофантових рівнянь і задачі комівояжера переконалися в тому, що генетичний алгоритм є найбільш універсальним методом рішення.
РОЗДІЛ 3. ПРОГРАМНА РЕАЛІЗАЦІЯ. СТВОРЕННЯ Допомога по Генетичні алгоритми.
3.1 Обгрунтування вибору програмного забезпечення
Останнім часом різко зріс інтерес до програмування. Це пов'язано з розвитком і впровадженням в повсякденне життя інформаційно-комунікаційних технологій. Якщо людина має справу з комп'ютером, то рано чи пізно у нього виникає бажання, а іноді і необхідність, програмувати.
Серед користувачів персональних комп'ютерів в даний час найбільш популярне сімейство операційних систем Windows і, природно, що той, хто збирається програмувати, прагне писати програми, які будуть працювати в цих системах.
Інтерактивність - сьогодні найбільш важливе, ми б сказали основне
умова для створюваних додатків. Найбільш повний стандарт, який гарантує дану умову, став усім відомий Action Script для Flash. Порівняно недавно він перетворився з простого мови підготовки сценаріїв у повноцінну об'єктно-орієнтоване середовище програмування.
Як ви пам'ятаєте, нашою метою є створення електронного посібника, яке дозволило б достатньо зрозуміло і просто донести до читача основні поняття і принципи організації генетичного алгоритму. Action Script надає прекрасну можливість, організувати барвистий, доступний інтерфейс і навігацію. І ще один незаперечний плюс при створенні підручника на Action Script: використання готового продукту, як самостійну програму (публікація готового продукту з exe розширенням).
3.2 Опис програмної реалізації
Для початку, ми підготували матеріал, який буде представлений в нашому посібнику. Визначилися зі структурою та дизайном, і тільки після цього почалося безпосередньо створення нашого продукту.
Ми використовували, як було згадано вище, Macromedia Flash MX2004. Алгоритм створення наступний:
1. Створюємо новий Flash документ.
2. Опрацьовуємо дизайн нашого допомоги (встановлення фону, шрифту)
3. Розміщуємо підготовлений нами матеріал на кадрах, попередньо вставивши на кожному з них ключовий кадр.
4. Організація навігації.
5. Перевірка і публікація створеного документа в exe форматі.
Розпишемо докладніше деякі пункти.
Розміщення матеріалу було сформовано на зразок звичайної книги з заголовком, змістом і можливістю перегортання сторінок.
Зміст Навігація (перегортання сторінок)
Що стосується навігації і безпосередньо програмування мовою Action Script, тут теж не виникло жодних проблем. Сама програма пишеться у вікні Action, при виділення об'єкта, але який пишуться дії.
Flash Action Script діє за наступним сценарієм:
o сценарій Action Script налаштовується на виявлення певної події.
o Як тільки подія відбувається, виконується обробляє цю подію набір інструкцій Action Script.
На кожен кадр (сторінку нашого посібника) пишеться певна заготовка:
stop ();
/ / Зупиняє автоматичне програвання кадрів.
- На кожну кнопку пишеться інша заготівля:
on (release) {
gotoAndStop ("Scene
}
/ / Отже, пояснимо цю нескладну конструкцію. іншими словами перша рядок буде виглядати так: при (відпуску) {виконати це ...}. Команда gotoAndStop дозволяє нам перейти на другий кадр першої сцени і зупинитися.
Ще одне невеличке зауваження, необхідно перетворити намальовану або вставлену з бібліотеки кнопку на символ. Для цього виділяємо наш об'єкт правою кнопкою, і вибираємо в контекстному меню Convert, у меню, ставимо галочку навпроти Button.
У Flash ми на кожному кроці можемо перевіряти (налагоджувати) нашу розробку, для цього в головному меню вибираємо Control / Test movie.
І, нарешті, на останньому кроці ми публікуємо наш посібник в exe форматі, для того, щоб наша розробка запускалася на комп'ютері будь-якого користувача, в не залежності від того, встановлена на його комп'ютері Flash чи ні.
Висновок
Ми з вами пройшли великий шлях, відкриваючи для себе генетичні алгоритми, їх, здавалося б, тривіальну і одночасно з цим геніальну ідею, взяту з природи. У ході вивчення ми багато разів вказували на достоїнства і недоліки генетичних алгоритмів. Серед найбільш значущих позитивних сторін, можна відзначити:
Перший випадок: коли не відомий спосіб точного рішення задачі. Якщо ми знаємо, як оцінити пристосованість хромосом, то завжди можемо змусити генетичний алгоритм вирішувати цю задачу.
Другий випадок: коли спосіб для точного рішення існує, але він дуже складний у реалізації, вимагає великих витрат часу і грошей, тобто, простіше кажучи, справа того не варто. Приклад - створення програми для складання персонального розкладу на основі техніки покриття множин з використанням лінійного програмування.
Що ж стосується недоліків, то в загальному випадку генетичні алгоритми не знаходять оптимального рішення дуже важких завдань. Якщо оптимальне рішення задачі (наприклад, задача комівояжера з дуже великим числом міст) не може бути знайдено традиційними способами, то й генетичний алгоритм навряд чи знайде оптимум
Поряд з генетичними алгоритмами відомі й інші методи рішення задач оптимізації, засновані на природних механізмах, такі як моделювання відпалу (simulated annealing) і табу-пошук (taboo search). Але ефект випадковості, який безумовно присутній при вирішенні генетичним алгоритмом, дуже надихає.
Незважаючи на невелику кількість завдань, яке ми з вами розглянули: рішення діофантових рівнянь і завдання комівояжера, ми повністю підтверджуємо нашу гіпотезу. Завдання оптимізації (і не тільки) успішно вирішуються за допомогою генетичних алгоритмів.
Б ібліографія
1. Вентцель Є.С. «Дослідження операцій», - М.:
2. Гальцина О.Л., Попов І.І. «Основи алгоритмізації та програмування».
3. Грешілов А.А. «Як взяти найкраще рішення в реальних умовах», - М.:
4. Корнєєв В.В., Гарєєв А.Ф. «Бази даних. Інтелектуальна обробка даних », М.: 2001р., Стор 220
5. Коршунов Ю.М. «Математичні основи кібернетики. Для студентів вузів », - М.:
6. Леонов О.І. «Теорія графів».
7. Майнік Е., «Алгоритми оптимізації на мережах і графах.» - М.: 1981
8. Новіков Ф.А. «Дискретна математика для програмістів».
9. «Генетичні алгоритми: чому вони працюють?» / Компьютерра, № 11, 1999 рік
10. Де Джонг К. А. Введення до другого спеціального випуску по
генетичним алгоритмам. Машинне навчання, № 5 (4), с. 351-353
11. Електронні джерела:
12. «Генетичні алгоритми по-російськи» - http://www.chat.ru/ ~ saisa
13. «Нейропроект. Аналітичні технології XXI століття »- http://www.neuroproject.ru
14. «Наукове видавництво ТВП» - http://www.tvp.ru/mathem3.htm
15. «Факультет обчислювальної математики і кібернетики МГУ (ВМиК)» - http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html
16. «Neural Bench Development» - http://www.neuralbench.ru/rus/theory/genetic.htm
17. «Журнал" Автоматизація Проектування "» - http://www.opensystems.ru/ap/1999/01/08.htm
18. «(EHIPS) Генетичні алгоритми» - http://www.iki.rssi.ru/ehips/genetic.htm
19. «SENN Генетичні Алгоритми» - http://fdmhi.mega.ru/ru/senn_ga.htm
20. Хорева Є.В. Курсова робота. Тема «Застосування генетичних алгоритмів для вирішення задач оптимізації»-КДПУ.: 2007р.
21. «Лекції з нейронних мереж і генетичних алгоритмів» - http://infoart.baku.az/inews/30000007.htm