зв'язку шляхом вибору оптимальної частоти, на якої буде вестися розмова. В основі цього програмного продукту і використовуються генетичні алгоритми. p> Основні принципи генетичних алгоритмів були сформульовані Голландії (Holland, 1975), і добре описані в багатьох роботах. У відміну від еволюції, яка відбувається у природі, генетичний алгоритм тільки моделюють ті процеси в популяціях, які є суттєвими для розвитку. Точну відповідь на запитання: які біологічні процеси істотні для розвитку, і які ні? - Все ще відкритий для дослідників. br/>
Реалізація генетичних алгоритмів
У природі особини в популяції конкурують один з одним за різні ресурси, такі, наприклад, як їжа або вода. Крім того, члени популяції одного виду часто конкурують за залучення шлюбного партнера. Ті особини, які найбільш пристосовані до навколишніх умов, матимуть відносно більше шансів відтворити нащадків. Незадовільно пристосовані особини або зовсім не справлять потомства, або їх потомство буде дуже нечисленним. Це означає, що гени від високо адаптованих або пристосованих особин будуть поширяться в зростаючому кількості нащадків на кожному наступному поколінні. Комбінація гарних характеристик від різних батьків іноді може призводити до появи "суперпріспособленного" нащадка, чия пристосованість більше, ніж пристосованість будь-якого з його батька. Таким чином, вид розвивається, краще і краще пристосовуючись до середовищі існування. p> Генетичні алгоритми використовують пряму аналогію з таким механізмом. Вони працюють з сукупністю "особин" - популяцією, кожна з яких представляє можливе рішення даної проблеми. Кожна особина оцінюється мірою її "пристосованості" згідно з тим, наскільки "добре" відповідне їй рішення задачі. Наприклад, мірою пристосованості могло б бути ставлення сили/ваги для даного проекту моста. (У природі це еквівалентно оцінці того, наскільки ефективний організм при конкуренції за ресурси.) Найбільш пристосовані особини отримують можливість "відтворює" потомство за допомогою "перехресного схрещування" з іншими особинами популяції. Це призводить до появи нових особин, які поєднують у собі деякі характеристики, успадковані ними від батьків. Найменш пристосовані особини з меншою ймовірністю зможуть відтворити нащадків, так що ті властивості, якими вони володіли, будуть поступово зникати з популяції в процесі еволюції. p> Так і відтворюється вся нова популяція допустимих рішень, вибираючи кращих представників попереднього покоління, схрещуючи їх і отримуючи безліч нових особин. Це нове покоління містить більш високе співвідношення характеристик, якими володіють хороші члени попереднього покоління. Таким чином, з покоління в покоління, хороші характеристики поширюються по всій популяції. Схрещування найбільш пристосованих особин призводить до того, що досліджуються найбільш перспективні ділянки простору пошуку. Зрештою, популяція буде сходитися до оптимальному вирішенню завдання. p> Є багато способів реалізації ідеї біологічної еволюції в рамках генетичного алгоритму. Традиційним вважається генетичний алгоритм, представлений на схемі 1:
ПОЧАТОК/генетичний алгоритм/
Створити початкову популяцію
Оцінити пристосованість кожної особини
останов: = FALSE
ПОКИ НЕ останов ВИКОНУВАТИ
ПОЧАТОК/створити популяцію нового покоління/
ПОВТОРИТИ (Размер_популяціі/2) РАЗ
ПОЧАТОК/* цикл відтворення */
Вибрати дві особини з високою пристосованістю з попереднього покоління для схрещування. p> Схрестити вибрані особини і отримати двухпотомков
Оцінити пристосованості нащадків
Помістити нащадків в нове покоління
КІНЕЦЬ
ЯКЩО популяція зійшлася ТО зупинення: = TRUE
КІНЕЦЬ
КІНЕЦЬ
Схема 1. Реалізація генетичного алгоритму
В останні роки, реалізовано багато генетичних алгоритмів і в більшості випадків вони мало схожі на цей генетичний алгоритм. З цієї причини в даний час під терміном "генетичні алгоритми "ховається не одна модель, а досить широкий клас алгоритмів, часом мало схожих один від одного. Дослідники експериментували з різними типами уявлень, операторів кросовера і мутації, спеціальних операторів, і різних підходів до відтворення та відбору. p> Хоча модель еволюційного розвитку, застосовувана в генетичному алгоритмі, сильно спрощена в порівнянні зі своїм природним аналогом, проте генетичний алгоритм є досить потужним засобом і може з успіхом застосовуватися для широкого класу прикладних завдань, включаючи ті, які важко, а іноді і зовсім неможливо, вирішити іншими методам. Однак, генетичні алгоритми, як і інші методи еволюційних обчислень, не гарантує виявлення глобального рішення за поліноміальний час. Генетичні алгоритми не гарантують і того, що глобальне рішення буде знайдено, але вони гарні для пошуку "досить хорошого" рішення завдання "досить швидко". Там, де завдання може бути вирішена спеціальними методам, майже завжди т...
