Тепер ми в станізрозуміти, як відбувається цей процес. Природний відбір гарантує, що найбільшпристосовані особини дадуть досить велике потомство, а завдяки генетичномуспадкуванню ми можемо бути впевнені, що частина цього потомства не тільки збережевисоку пристосованість батьків, але буде мати і деякими новими властивостями.Якщо ці нові властивості виявляться корисними, то з великою ймовірністю вони перейдутьі в наступне покоління. Таким чином, відбувається накопичення корисних якостей іпоступове підвищення пристосовності біологічного виду в цілому. Знаючи, як вирішуєтьсязадача оптимізації видів у природі, ми тепер застосуємо схожий метод для вирішеннярізних реальних задач. Задачі оптимізації - найбільш розповсюджений і важливийдля практики клас задач. Їх доводиться вирішувати кожному з нас або в побуті, розподіляючисвій час між різними справами, або на роботі, домагаючись максимальної швидкостіроботи програми чи максимальної прибутковості компанії - у залежності від посади.Серед цих завдань є розв'язувані простим шляхом, але є і такі, точне рішення якихзнайти практично неможливо. Введемо позначення і приведемо кілька класичнихприкладів. Як правило, у задачі оптимізації ми можемо керувати декількома параметрами(Позначимо їх значення через x1, x2, ..., xn, а нашою метою є максимізація(Або мінімізація) деякої функції, f (x1, x2, ..., xn), що залежить від цих параметрів.Функція f називається цільовою функцією. Наприклад, якщо потрібно максимізуватицільову функцію В«дохід компаніїВ», то керованими параметрами будуть число співробітниківкомпанії, обсяг виробництва, витрати на рекламу, ціни на кінцеві продукти і т.д. Важливо відзначити, що ці параметри зв'язані між собою - зокрема, при зменшеннічисла співробітників швидше за все впаде й обсяг виробництва. Звичайно, математикиздавна займалися подібними завданнями і розробили кілька методів їх вирішення.У разі якщо цільова функція достатньо гладка і має тільки один локальний максимум(Унімодального), то оптимальне рішення можна отримати методом градієнтного спуску.Ідея цього методу полягає в т
ому, що оптимальне рішення виходить ітераціями.Береться випадкова початкова точка, а потім у циклі відбувається зрушення цієї точки намалий крок, причому крок робиться в тому напрямі, в якому цільова функція зростаєшвидше за все. Недоліком градієнтного алгоритму є занадто високі вимогидо функції - на практиці унімодального зустрічається вкрай рідко, а для неправильноїфункції градієнтний метод часто приводить до неоптимальної відповіді. Аналогічні проблемивиникають і з застосуванням інших математичних методів. У багатьох важливих завданняхпараметри можуть приймати лише певні значення, причому у всіх інших точкахцільова функція не визначена. Звичайно, в цьому випадку не може бути й мови про їїгладкості, і потрібні принципово інші підходи. Таким чином, виникає необхідністьв якомусь новому методі оптимізації, придатному для практики. Тут і з'являєтьсянеобхідність в якихось нових методах рішення, наприклад таких, як генетичнийалгоритм.
2. Генетичний алгоритм
2.1 Історія розвитку ГА
Те, що називається стандартним генетичнималгоритмом, було вперше детально описано й досліджено в роботі де Джонг. Він проаналізувавпросту схему кодування генів бітовими рядками фіксованої довжини і відповіднихгенетичних операторів, виконав значну кількість чисельних експериментів,порівнюючи результати з оцінками, пророкує теоремою Холланда. Важливість цієїроботи визначається насамперед її строгим і системним характером, ясністю викладуі представлення результатів, обраним рівнем абстракції і спрощення, що дозволяєуникнути непотрібної деталізації. Крім того, в цій роботі підкреслювалася необхідністьпроведення подальших досліджень більш складних схем представлення генотипу і операційнад ним. Наступні роботи де Джонг продемонстрували його інтерес до проблем,які вимагали менш структурованих схем представлення гена.
Інший відправною точкою розвитку дослідженьпо генетичним алгоритмам була публікація в 1975 році книги Холланда "Adaptation in Natural and Artificial Systems". Ця книга заклала теоретичний фундамент дляроботи де Джонг і всіх наступних робіт, математично обгрунтувавши ідею близькихпідмножин всередині генотипу, процесів загибелі і селективного відтворення. Ціліцієї книги були досить широкими. Хоча докази основних тверджень булипредставлені для генів фіксованої довжини і відповідних простих операторів,це не обмежувало розвиток представленого підходу на випадки більш багаті посвоїми можливостями. Наприклад, Холланд обговорював можливість застосування операторіввнутріхромосомной дуплікації, видалення та сегрегації ділянок хромосоми.
Тим не менше, більшість подальшихдослідників сприйняло теоретичні результати, що містяться в цих роботахзанадто буквально, і розробляли різні модифікації стандартного генетичногоалгоритму, дослідженого де Джонг.
Тільки невелика частина дослідниківзробила зусилля по розробці альтернативних схем. Серед них виділяються детекторпатернів Кавіча, робота Франца по інверсії, гравець в покер Сміта.
Дослідження Кавіча, націлене на розробкудетектора розпізнавання образів було одним з перших, що використовують гени змінноїдовжини. Розташовані на площині двійкові пікселі, здатні розрізняти світло і темряву,нумерувалися і об'єднувалися в підмножини, що утворюють різні детектори, якіпотім використовувалися деякими апріорно заданим алгоритмом для розпізнавання образів.При цьому не виникало використання одного і того ж пікселя двічі або не використанняпікселя.
Сміт використовував правила, які оперуютьрядками змінної довжини, створюючи модель машинного гравця в покер. Його LS-1 система використовувала модифікованийкросинговер, який розташовував точки кросинговеру як на границях рядків, що кодуютьправила, так і всередині них. Він також включив в алгоритм оператор інверсії, сподіваючись,що це допоможе більш ефективно розподіляти правила всередині рядка.
Дещо раніше Сміта, Франц розглянувможливість зміщення окремих підмножин бітів всередині рядки в своїй роботі понелінійної оптимізації. На жаль, через невдалого вибору виду функції оптимізації(Яка легко оптимізувалася і простим генетичним алгоритмом без використанняінверсії) не було показано реальних переваг нового алгоритму в порівнянні ззагальноприйнятим. Тим не менш, цю роботу можна вважати однією з перших, що почали застосуваннябільш гнучких схем генетичних алгоритмів.
Інші дослідники запропонували різнімодифікації схем генетичного переупорядочивания усередині рядка, коли використовуєтьсякросинговер. Одночасно було проведено ряд досліджень, що розвивали теорію Холланда,і продемонстровані нові генетичні оператори. Однак питання про їх перевагиі ретельному порівнянні зі стандартним генетичним алгоритмом продовжує залишатисявідкритим.
2.2 Загальний вигляд генетичного алгоритму
Спочатку ГА-функція генерує певнийкількість можливих рішень. Задається функція оптимальності, що визначає ефективністькожного знайденого рішення, для відстеження виходу рішення з допустимої областів функцію можна включити штрафний компонент. Кожне рішення кодується як векторx, званий хромосомою. Його елементи- Гени, що змінюються в певних позиціях, званих алелями. Геном - сукупністьвсіх хромосом. Генотип - значення геному.
Рис. 2. Структура хромосоми
Зазвичай хромосоми представляються в двійковому целочисленномвигляді або довічним з плаваючою комою. У деяких випадках більш ефективно будевикористання коду Грея (табл. 1), в якому зміна одного біта в будь-якій позиціїпризводить до зміни значення на одиницю. Для деяких завдань двійкове поданняприродно, для інших завдань може виявитися корисним відмовитися від двійкового представлення.У загальному випадку вибір способу представлення параметрів задачі у вигляді хромосоми впливаєна ефективність рішення.
Таблиця 1. Код Грея
|
 Український реферат переглянуто разів: |  Коментарів до українського реферату: 0 |
|
