аленьких островах? .. "
Автор: РОСС Клемент
Опубліковано в журналі "Компьютерра" № 11 від 16 березня 1999
Ключову роль у еволюційної теорії грає природний відбір. Його суть полягає в тому, що найбільш пристосовані особини краще виживають і приносять більше нащадків, ніж менш пристосовані. Зауважимо, що сам по собі природний відбір ще забезпечує розвиток біологічного виду. Тому дуже важливо зрозуміти, яким чином відбувається спадкування, тобто як властивості нащадка залежать від властивостей батьків. p> Основний закон спадкування інтуїтивно зрозумілий кожному - він полягає в тому, що нащадки схожі на батьків. Зокрема, нащадки більш пристосованих батьків будуть, швидше за все, одними з найбільш пристосованих у своєму поколінні. Щоб зрозуміти, на чому грунтується це схожість, потрібно трохи заглибитися в побудову природної клітини - у світ генів і хромосом [4]. p> Майже в кожній клітці будь особини є набір хромосом, що несуть інформацію про цю особини. Основна частина хромосоми - нитка ДНК, що визначає, які хімічні реакції будуть відбуватися в даній клітині, як вона буде розвиватися і які функції виконувати. Ген - це відрізок ланцюга ДНК, відповідальний за певну властивість особини, наприклад за колір очей, тип волосся, колір шкіри і т.д. При розмноженні тварин відбувається злиття двох батьківських статевих клітин та їх ДНК взаємодіють, створюючи ДНК нащадка. Основний спосіб взаємодії - кросовер (cross-over, схрещування). При кросовері ДНК предків діляться на дві частини, а потім обмінюються своїми половинками. p> При спадкуванні можливі мутації через радіоактивності або інших впливів, в результаті яких можуть змінитися деякі гени в статевих клітинах одного з батьків. Змінені гени передаються нащадку і надають йому нові властивості. Якщо ці нові властивості корисні, вони, швидше за все, збережуться в даному виді - при цьому відбудеться стрибкоподібне підвищення пристосованості виду. Вперше подібний алгоритм був запропонований в 1975 році Джоном Холландом (John Holland) в Мічиганському університеті. Він отримав назву В«репродуктивний план ХолландаВ» і ліг в основу практично всіх варіантів генетичних алгоритмів [8]. Однак, перед тим як ми його розглянемо докладніше, необхідно зупиниться на тому, яким чином єкти реального світу можуть бути закодовані для використання в генетичних алгоритмах.
1.2. Подання об'єктів. Кодування ознак
З біології ми знаємо, що будь-який організм може бути представлений своїм фенотипом, який фактично визначає, чим є об'єкт в реальному світі, і генотипом, який містить всю інформацію про об'єкт на рівні хромосомного набору. При цьому кожен ген, тобто елемент інформації генотипу, має своє відображення в фенотипі [9]. Таким чином, для вирішення завдань нам необхідно представити кожна ознака об'єкта у формі, придатної для використання в генетичному алгоритмі. Все подальше функціонування механізмів генетичного алгоритму виробляється на рівні генотипу, дозволяючи обійтися без інформації про внутрішню структурі об'єкта, що й обумовлює його широке застосування в самих різних завданнях.
У найбільш часто зустрічається різновиди генетичного алгоритму для подання генотипу об'єкта застосовуються бітові рядки. При цьому кожному атрибуту об'єкта в фенотипі відповідає один ген в генотипі об'єкта. Ген являє собою бітову рядок, найчастіше фіксованої довжини, яка являє собою значення цієї ознаки.
Для кодування таких ознак можна використовувати найпростіший варіант - бітове значення цієї ознаки. Тоді нам буде вельми просто використовувати ген певної довжини, достатньої для подання всіх можливих значень такої ознаки. Таким кодом є код Грея, який доцільно використовувати в реалізації генетичного алгоритму [9]. Значення кодів Грея розглянуті в таблиці нижче:
Двійкове кодування
Кодування за кодом Грея
десяткове
двійкове
шестнадца-
терічное
десяткове
двійкове
шестнадца-
терічное
0
000
0h
0
0000
0h
1
0001
1h
1
