Зміст
Введення
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 Завдання оптимізації
Як вже було зазначено вище,еволюція - це процес постійної оптимізації біологічних видів. ...
