Генетичні алгоритми в задачі оптимізації дійсних параметрів

Зміст

Введення

1. Еволюція в природі

1.1 Природний відбір

1.2 Завдання оптимізації

2. Генетичний алгоритм

2.1 Історія розвитку ГА

2.2 Загальний вигляд генетичного алгоритму

2.3 Генетичні оператори

2.4 Переваги і недоліки стандартнихі генетичних методів

3. Вплив параметрів генетичного алгоритмуна

ефективність пошуку

3.1 Оператори кросовера і мутації

3.2 Вибір батьківської пари

3.3 Механізм відбору

4. Найбільш актуальні проблеми ГА і цікавімодифікації ГА

5. Приклад ГА: Рішення діофантових рівнянь

5.1. Тема класу

5.2 Функція Fitness

5.3 Функція Likelihood

5.4 Функції Breeding

5.5 Функція Solve

5.6 Функція Main

Висновок

Список використаної літератури

Додаток В«Текст main.cpp

Додаток Б В«Текст Diophantine.h

Введення

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

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

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

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

еволюціягенетичний хромосома

1. Еволюція в природі

1.1 Природний відбір

Можна сказати, що еволюція- Це процес оптимізації всіх живих організмів. Ключову роль в еволюційній теоріїграє природний відбір. Його суть полягає в тому, що найбільш пристосованіособини краще виживають і приносять більше потомства, ніж менш пристосовані. Зауважимо,що сам по собі природний відбір ще не забезпечує розвитку біологічного виду.Дійсно, якщо припустити, що всі нащадки народжуються приблизно однаковими,то різні покоління будуть відрізнятися лише за чисельністю, але не по пристосованості.Тому дуже важливо вивчити, яким чином відбувається спадкування, тобто як властивостінащадка залежать від властивостей батьків. Основний закон спадкування інтуїтивно зрозумілийкожному - він полягає в тому, що нащадки схожі на батьків. Зокрема, нащадкибільш пристосованих батьків будуть, швидше за все, одними з найбільш пристосованиху своєму поколінні. Щоб зрозуміти, на чому заснована ця схожість, нам буде потрібнотрохи заглибитися в будову тваринної клітини - у світ генів і хромосом. Майже вкожній клітині будь-якої тварини є набір хромосом, що несуть інформацію про цетваринному. Основна частина хромосоми - нитка ДНК (молекула дезоксирибонуклеїнової кислоти),яка складається з чотирьох видів спеціальних сполук - нуклеотидів, що йдуть впевній послідовності. Нуклеотиди позначаються літерами A, T, C і G, ісаме порядок їх проходження кодує всі генетичні властивості даного організму.Говорячи більш точно, ДНК визначає, які хімічні реакції будуть відбуватися вданій клітині, як вона буде розвиватися і які функції виконувати. Ген - це відрізокланцюга ДНК, що відповідає за певну властивість особини, наприклад за колір очей, типволосся, колір шкіри і т. д. Вся сукупність генетичних ознак людини кодуєтьсядопомогою приблизно 60 тис. генів, сумарна довжина яких становить більше 90млн. нуклеотидів. Розрізняють два види клітин: статеві (такі, як сперматозоїд іяйцеклітина) і соматичні. У кожній соматичній клітині людини міститься 46хромосом. Ці 46 хромосом - насправді 23 пари, причому в кожній парі одна зхромосом отримана від батька, а друга - від матері. Парні хромосоми відповідають за одніі ті ж ознаки - наприклад, батьківська хромосома може містити ген чорного кольоруочей, а парна їй материнська - ген блакитноокого. Існують певні закони,керуючі участю тих чи інших генів у розвитку особини. Зокрема, у нашому прикладінащадок буде чорнооким, так як ген блакитних очей є "слабким" (рецесивним)і пригнічується геном будь-якого іншого кольору.

У статевих клітинах хромосомтільки 23, і вони непарні. При заплідненні відбувається злиття чоловічої і жіночоїстатевих клітин і утворюється клітина зародка, що містить як раз 46 хромосом. Яківластивості нащадок одержить від батька, а які - від матері? Це залежить від того, якісаме статеві клітини брали участь у заплідненні. Справа в тому, що процес виробленнястатевих клітин (так званий мейоз) в організмі піддається випадкам, завдякияким нащадки все ж багато в чому відрізняються від своїх батьків. При мейозі, зокрема,відбувається наступне: парні хромосоми соматичної клітини зближаються впритул,потім їх нитки ДНК розриваються в декількох випадкових місцях і хромосоми обмінюютьсясвоїми частинами.

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

1.2 Завдання оптимізації

Як вже було зазначено вище,еволюція - це процес постійної оптимізації біологічних видів. ...Тепер ми в станізрозуміти, як відбувається цей процес. Природний відбір гарантує, що найбільшпристосовані особини дадуть досить велике потомство, а завдяки генетичномуспадкуванню ми можемо бути впевнені, що частина цього потомства не тільки збережевисоку пристосованість батьків, але буде мати і деякими новими властивостями.Якщо ці нові властивості виявляться корисними, то з великою ймовірністю вони перейдутьі в наступне покоління. Таким чином, відбувається накопичення корисних якостей іпоступове підвищення пристосовності біологічного виду в цілому. Знаючи, як вирішуєтьсязадача оптимізації видів у природі, ми тепер застосуємо схожий метод для вирішеннярізних реальних задач. Задачі оптимізації - найбільш розповсюджений і важливийдля практики клас задач. Їх доводиться вирішувати кожному з нас або в побуті, розподіляючисвій час між різними справами, або на роботі, домагаючись максимальної швидкостіроботи програми чи максимальної прибутковості компанії - у залежності від посади.Серед цих завдань є розв'язувані простим шляхом, але є і такі, точне рішення якихзнайти практично неможливо. Введемо позначення і приведемо кілька класичнихприкладів. Як правило, у задачі оптимізації ми можемо керувати декількома параметрами(Позначимо їх значення через 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 0000 0000 1 0001 0001 2 0010 0011 3 0011 0010 4 0100 0110 5 0101 0111 6 0110 0101 7 0111 0100 8 1000 1100 9 1001 1101 10 1010 1111 11 1011 1110 12 1100 1010 13 1101 1011 14 1110 1001 15 1111 1000

Популяція - сукупність рішень на конкретній ітерації,кількість хромосом у популяції задається спочатку і в процесі зазвичайне змінюється. Для ГА поки не існує таких же чітких математичних основ, якдля НС, тому при реалізації ГА можливі різні варіації.

1. Початкова популяція - кінцевий набір допустимихрішень задачі.

2.

3.елементи.

4.

.

Таблиця

таким чином.

Рис. 3.Таким чином,

Рис. 4.

Рис. 5.

координатами.

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

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

Рис

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

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

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

3. Вплив параметрів генетичного алгоритму на ефективністьпошуку

3.1 Оператори кросовера і мутації

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

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

Підвищення ефективності пошуку при використаннівипадкового вибору операторів кроссовера вплинуло на те, щоб застосувати аналогічнийпідхід при реалізації процесу мутагенезу нових особин, проте в цьому випадку перевагаперед детермінованим підходом не так очевидно в силу традиційно малу ймовірністьмутації. В основному ймовірність мутації становить 0.001 - 0.01.

3.2 Вибір батьківської пари

Перший підхід найпростіший- Це випадковий вибір батьківської пари ("панмиксия"), коли обидві особини,які складуть батьківську пару, випадковим чином вибираються з

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

3.3 Механізм відбору

Обговорення питання про вплив методу створеннябатьківських пар на поведінку генетичного алгоритму неможливо вести у відривівід реалізованого механізму відбору при формуванні нового покоління. Найбільш ефективнідва механізми відбору елітний і відбір з витісненням.

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

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

4. Найбільш актуальні проблеми ГА і цікаві модифікаціїГА

Невдалий вибір упорядкування та кодування бітів в хромосоміможе спричинити передчасне сходження до локального оптимуму, ведучи алгоритм похибному шляху. Для подолання цього недоліку можна вибирати спосіб кодуваннягрунтуючись на додатковій інформації про завдання. Існують так само мобільні ГА,із змінною довжиною хромосом. Для деяких завдань таке подання природно,для інших треба вводити спеціальні правила читання хромосом. Замість оператора кросинговерувикористовуються оператори розрізання рядків (CUT), ймовірністьякого підвищується із збільшенням довжини рядка, і оператор зчеплення рядків (SPLICE),який вибирає з популяції два шматки і зчіплює їх в один шматок. Популяція представляєсобою сукупність пере-і недовизначених рядків. Правила читання таких рядків можутьбути, наприклад такими: в перевизначення рядку при читанні зліва направо не враховуютьсявже використані гени, а в недовизначених рядках відсутні місця запозичуютьсяу кращого елемента.

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

Цікаві результати може дати поєднання ГА з іншимиметодами. І на закінчення зупинимося на те, коли ж слід використовувати генетичніалгоритми. В одних обставин вони гарні, в інших - не дуже. У загальному випадкугенетичні алгоритми не знаходять оптимального рішення дуже важких завдань. Якщооптимальне рішення задачі (наприклад, ЗКВ з дуже великим числом міст) не можебути знайдено традиційними способами - наприклад, методом зчеплення гілок (branchand bound method), - то і генетичний алгоритм навряд чи знайде оптимум. З іншогобоку, цілком можливо, що генетичний алгоритм знайде достатньо хороше рішення.Зрештою, комівояжеру в будь-якому випадку треба їхати продавати свої товари, навітьякщо ми не впевнені в абсолютній оптимальності маршруту! Але є приклади, коли вдуже важких завданнях, в тому числі і в ЗКВ, за допомогою генетичних алгоритмів булиотримані дуже гарні рішення.

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

Незважаючи на те, що конструювання хромосом і фітнес-функційможе вимагати значних зусиль, генетичні алгоритми легко реалізуютьсянавіть з нуля і здатні вирішувати широке коло завдань. Використовуючи аналогію з розвиткомживих організмів від простих форм до більш складних, генетичні алгоритми наблизилисядо того, щоб стати загальним методом вирішення завдань. Інші "пріродоподобние"парадигми, такі як моделювання відпалу (simulated annealing) і табу-пошук (taboosearch), теж дозволяють вирішувати аналогічні завдання.

5. Приклад ГА: Рішення діофантових рівнянь

Розглянемо диофантово (тільки цілі рішення)рівняння: 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 =

Таблиця 2: 1-е покоління хромосомі їх вміст

Хромосома (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 і буде потрібним значенням.

Таблиця 3: Коефіцієнти виживаностіпершого покоління хромосом (набору рішень)

Хромосома Коефіцієнт виживаності 1 | 114-30 | = 84 2 | 54-30 | = 24 3 | 56-30 | = 26 4 | 163-30 | = 133 5 | 58-30 | = 28

Так як менші значення ближчедо 30, то вони більш бажані. У нашому випадку великі чисельні значення коефіцієнтіввиживаності підходять, на жаль, менше. Щоб створити систему, де хромосоми з більшпідходящими значе...ннями мають великі шанси виявитися батьками, ми повинні обчислити,з якою ймовірністю (в%) може бути обрана кожна. Одне рішення полягає втому, щоб взяти суму зворотних значень коефіцієнтів, і виходячи з цього обчислювативідсотки. (Зауважимо, що всі рішення були згенеровані генератором випадкових чисел- ГВЧ).

Таблиця 4: Імовірність виявитисябатьком

Хромосома Подходящесть 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. Щоб вибрати першу пару кидаємо кістка дварази і вибираємо випали хромосоми.

Таблиця 5: Симуляція вибору батьків

Хромосома батька Хромосома матері 3 1 5 2 3 5 2 5 5 3

Кожен нащадок містить інформаціюпро генах і батька і від матері. Взагалі кажучи, це можна забезпечити різними способами,однак у нашому випадку можна використовувати т.з. "Кроссовер" (cross-over).Нехай мати містить наступний набір рішень: a1, b1, c1, d1, а батько - a2, b2, c2, d2,тоді можливо 6 різних крос-овер (| = розділова лінія):

Таблиця 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

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

Таблиця 7: Симуляція кроссоверів хромосом батьків

Хромосома-батько Хромосома-матір Хромосома-нащадок (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) нащадків.

Таблиця 8: Коефіцієнти виживаності нащадків (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) більш швидко і стабільно.

5.1 Заголовок класу

# include

# include

# include

# define MAXPOP 25

struct gene

{

int alleles [4];

int fitness;

float likelihood;// Тест на рівність

operator == (gene gn)

for (int i = 0; i <4; i + +)

{

if (gn.alleles [i]! = alleles [i])return false;

}

return true;

class CDiophantine

public:

CDiophantine (int, int, int, int, int);//Конструктор з коефіцієнтами при а, b, c, d

int Solve ();// Обчислює рішеннярівняння

gene GetGene (int i)

{return population [i];}

protected:

int ca, cb, cc, cd;//Коефіцієнти при а, b, c, d

int result;

gene population [MAXPOP];//Масив з генів - популяція

int Fitness (gene &);//Функція пристосованості

float MultInv ();

int CreateFitnesses ();

void CreateNewPopulation ();

int GetIndex (float val);

gene Breed (int p1, int p2);

{

}

явл. вирішенням даногоур-я

int fitness = 0;

for (int i = 0; i

{

fitness = Fitness (population [i]);

if (fitness == 0)

{

return i;

}

}

}

Таблиця

1 2 3 4 5

Таблиця

1 2 3 4 5

float CDiophantine :: MultInv ()

{

float sum = 0;

for (int i = 0; i

{

sum + = 1/((float) population [i]. fitness);

}

}

{

float last = 0;

for (int i = 0; i

{

}

}

Зауважимо, що

int CDiophantine :: Solve ()

{

int fitness = -1;

// Створюємо початкову популяцію

srand ((unsigned) time (NULL));

for (int i = 0; i

for (int j = 0; j <4; j + +)

{

population [i]. alleles [j] = rand ()% (result+ 1);

}

}

if (fitness = CreateFitnesses ())

{

eturn fitness;

}

int iterations = 0;

while (fitness! = 0 | | iterations <50)

{//Рахуємо до тих пір поки рішення не буде знайденоабо к-сть ітерацій більше 50

GenerateLikelihoods ();

CreateNewPopulation ();

if (fitness = CreateFitnesses ())

{

printf ("iterations% d n", iterations);

return fitness;

}

iterations + ...+;

}

return -1;

}

5.6 Функція Main

Розглянемо код головної функції:

# include

# include

# include "diophantine.h"

void main () {

CDiophantine dp (1,2,3,4,30);

int ans;

ans = dp.Solve ();

if (ans == -1){

cout <<"Solutionnot found. "<

} else {

gene gn = dp.GetGene (ans);

cout <<"Thesolution set to a +2 b +3 c +4 d = 30 is: n ";

cout <<"a= "<

cout <<"b= "<

cout <<"c= "<

cout <<"d= "<

} getch ();

}

Висновок

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

Список використаної літератури

1.Кантор І.А. (переклад) Введення в ГАі Генетичне Програмування-http ://www. algolist.manual.ru

2.Скурихін А.Н. Генетичні алгоритми. Новини штучного інтелекту - 1995, № 4, с. 6-46.

3.Хезфілд Р., Кирби Л. Мистецтво програмуванняна C - До.: DIAsoft, 2001.

4.Поспєлов Д.А. Інформатика. Енциклопедичнийсловник для початківців - М: Педагогіка-Прес, 1994, - 350 с.

5.Курс лекцій з предмета "Основипроектування систем зі штучним інтелектом "/ Сост. Сотник С.Л. -URL: .neuropower.de

6.Кузнецов О.П. Про некомп'ютерних підходахдо моделювання інтелектуальних процесів мозку - Москва, Інститут проблем управлінняРАН

7.Самоорганізуються нейронні мережі таїх застосування - URL: .chat.ru/ ~ neurolab

8.Редько В.Г. Курс лекцій "Еволюційнакібернетика "- URL: inet.keldysh.ru/BioCyber/Lectures.html

9.Головко В.А. Нейроінтеллект: Теоріяі застосування Книга 1 Організація та навчання нейронних мереж з прямими і зворотнимизв'язками - Брест: БПІ, 1999, - 260 с.

10.Головко В.А. Нейроінтеллект: Теоріяі застосування Книга 2 Самоорганізація, відмовостійкість і застосування нейроннихмереж - Брест: БПІ, 1999, - 228 с.

11.А.Н. Генетичні алгоритми. Новиништучного інтелекту - 1995, № 4, с. 6-46.

12.С.А. Ісаєв Генетичні алгоритми -еволюційні методи пошуку-URL: rv.ryazan.ru/ ~ bug/library/ai/isaev/2/part1.html

13.Д.І. Батищев, С.А. Ісаєв Оптимізаціябагатоекстремального функцій за допомогою генетичних алгоритмів-URL: bspu.secna.ru/Docs/ ~ saisa/ga/summer97.html

14.Group Method of Data Handling- URL: .inf.kiev.ua/GMDH-home

15. Береснєв В. Л., Гімаді Е. Х., ДементьєвВ. Т. Екстремальні задачі стандартизації. - Новосибірськ: Наука, 1978.

16. Гері В., Джонсон Д. Обчислювальні машиниі труднорешаемие завдання. - М.: Мир, 1982.

17.Ліма-ле-Фаріа А. Еволюція без відбору:Автоеволюція форми і функції. - Москва, "Світ", 1991.

Додаток А

Текст main.cpp

# include

# include

# include "diophantine.h"

# define MAXPOP 25

void main () {

CDiophantine dp (1,2,3,4,30);

int ans;

ans = dp.Solve ();

if (ans == -1) {

cout <<"Solution not found."<

} else {

gene gn = dp.GetGene (ans);

cout <<"The solution set to a +2 b +3 c +4 d = 30is: n ";

cout <<"a =" <

cout <<"b =" <

cout <<"c =" <

cout <<"d =" <

} getch ();

}

Додаток Б

Текст Diophantine.h

# include

# include

# include

// # define MAXPOP 25

struct gene

{

int alleles [4];

int fitness;

float likelihood;

// Тест на рівність

operator == (gene gn)

{

for (int i = 0; i <4; i + +)

{

if (gn.alleles [i]! = alleles [i]) return false;

}

return true;

}

};

class CDiophantine

{

public:

CDiophantine (int, int, int, int, int);//Конструктор з коефіцієнтами при а, b, c, d

int Solve ();//Обчислює рішення рівняння

gene GetGene (int i)

{return population [i];}

protected:

int ca, cb, cc, cd;//Коефіцієнти при а, b, c, d

int result;

gene population [MAXPOP];//Масив з генів - популяція

int Fitness (gene &);//Функція пристосованості

void GenerateLikelihoods ();// Обчислює ймовірність відтворення

float MultInv ();

int CreateFitnesses ();

void CreateNewPopulation ();

int GetIndex (float val);

gene Breed (int p1, int p2);

};

CDiophantine :: CDiophantine (int a, int b, intc, int d, int res): ca (a), cb (b), cc (c), cd (d), result (res) {}

int CDiophantine :: Solve ()

{

int fitness = -1;

// Створюємо початкову популяцію

srand ((unsigned) time (NULL));

for (int i = 0; i

{//Аллели хромосом заповнюємо

// довільними числами від 0 до result

for (int j = 0; j <4; j + +)

{

population [i]. alleles [j] = rand ()% (result+ 1);

}

}

if (fitness = CreateFitnesses ())

{

return fitness;

}

int iterations = 0;

while (fitness! = 0 | | iterations <50)

{//Рахуємо до тих пір поки рішення

// не буде знайдено або к-сть ітерацій більше 50

GenerateLikelihoods ();

CreateNewPopulation ();

if (fitness = CreateFitnesses ())

{

printf ("iterations% d n", iterations);

return fitness;

}

iterations + +;

}

return -1;

}

int CDiophantine :: Fitness (gene & gn)// Обчислює коефіцієта

// пристосованості для даного гена

{

int total = ca * gn.alleles [0] + cb * gn.alleles [1]+ Cc * gn.alleles [2] + cd * gn.alleles [3];

return gn.fitness = abs (total - result);

}

int CDiophantine :: CreateFitnesses ()// Повертаєномер гена в популяції,

{//кіт. явл. вирішенням даногоур-я

float avgfit = 0;

int fitness = ...0;

for (int i = 0; i

{

fitness = Fitness (population [i]);

// avgfit + = fitness;

if (fitness == 0)

{

return i;

}

}

return 0;// Повертає0, якщо серед генів даної

// популяції не знайшлося рішення

}

float CDiophantine :: MultInv ()

{

float sum = 0;

for (int i = 0; i

{

sum + = 1/((float) population [i]. fitness);

}

return sum;// Сума зворотних коефіцієнтів

// пристосованості всіх генів в популяції

}

void CDiophantine :: GenerateLikelihoods ()// Генерує ймовірності відтворення

{

float multinv = MultInv ();

float last = 0;

for (int i = 0; i

{

population [i]. likelihood = last = last + ((1/((float) population [i]. fitness)/ Multinv) * 100);

}

}

int CDiophantine :: GetIndex (float val)// За даним числу від0 до 100 повертає

{//номер необхідного гена в популяції

float last = 0;

for (int i = 0; i

{

if (last <= val && val <= population [i]. likelihood)return i;

else last = population [i]. likelihood;

}

return 4;

}

gene CDiophantine :: Breed (int p1, int p2)

{

int crossover = rand ()% 3 +1;// Число від 1 до 3 - генеруємо точку кросовера.

int first = rand ()% 100;// Який батько буде першим?

gene child = population [p1];// Ініціалізувати дитини першимбатьком

int initial = 0, final = 4;

if (first <50) initial = crossover;//Якщо перший батько р1 (ймовірність цього 50%) -

// починаємо з точки кросовера

else final = crossover;// Інакше - закінчуємо на точці кросовера

for (int i = initial; i

{//Кроссовер

child.alleles [i] = population [p2]. alleles [i];

if (rand ()% 101 <5) child.alleles [i] =rand ()% (result + 1) ;//5% - мутація

}

return child;//Повертаємо дитини

}

void CDiophantine :: CreateNewPopulation () {

gene temppop [MAXPOP];

for (int i = 0; i

{

int parent1 = 0, parent2 = 0, iterations = 0;

while (parent1 == parent2 | | population [parent1]== Population [parent2])

{

parent1 = GetIndex ((float) (rand ()% 101));

parent2 = GetIndex ((float) (rand ()% 101));

if (+ + iterations> MAXPOP) break;// В цьому випадку

// батьків вибираємо випадково

}

temppop [i] = Breed (parent1, parent2);// Процес розмноження

}

for (i = 0; i

population [i] = temppop [i];

}