Непрекъснати генетични алгоритми
Малко история
Генетичните алгоритми (GA) са мощен инструмент за решаване на сложни проблеми. Те са намерили приложения в оптимизацията, изкуствения интелект, инженерството и други области. GA се основава на принципи, заимствани от биологията и генетиката. Припомнете си: основната идея на GA е да се създаде популация от индивиди (индивиди), всяка от които е представена като хромозома. Всяка хромозома е възможно решение на разглеждания проблем с оптимизацията. За да се намерят най-добрите решения, е необходима само стойността на целевата функция или функцията за фитнес. Стойността на фитнес функцията на индивида показва доколко индивидът, описан от дадена хромозома, е подходящ за решаване на проблем. Хромозомата се състои от краен брой гени, представляващи генотипа на обект, т.е. съвкупността от неговите наследствени характеристики. Процесът на еволюционно търсене се извършва само на ниво генотип. Основните биологични оператори се прилагат към популацията: кръстосвания, мутации, инверсии и др. В процеса на еволюция е в сила добре познатият принцип „най-здравият оцелява“. Популацията непрекъснато се актуализира от генерирането на нови индивиди и унищожаването на стари, като всяка нова популация става по-добра и зависи само от предишната.
Първоначално непрекъснатите гени започнаха да се използват в специфични приложения (например, хемометрия, оптимален избор на параметри за стандартни оператори на GA и др.). По-късно те започват да се използват за решаване на други задачи за оптимизация в непрекъснати пространства (трудове на изследователи Райт, Дейвис, Михалевич, Ешелман, Херера през 1991-1995 г.). Тъй като не е имало теоретична основа за функционирането на непрекъснати GA преди 1991 г., използването на този нов подвид е противоречиво; Учените, запознати с фундаменталната теория на еволюционните изчисления, която доказа превъзходството на бинарната азбука над другите, бяха критични към успеха на реално кодираните алгоритми. След известно време се появи теоретична основа, непрекъснатите GA напълно изместиха бинарните хромозоми при търсене в непрекъснати пространства.
По-нататък в текста, по аналогия с терминологията на английски език, съкращението BGA (двоично кодирано) ще се използва за GA с двоично кодиране и RGA (Real coded) за GA с непрекъснати гени.
Предимства и недостатъци на двоичното кодиране
Преди да изложим характеристиките на математическия апарат на непрекъснато GA, нека се спрем на анализа на предимствата и недостатъците на двоичните схеми за кодиране.
Както знаете, високата ефективност за намиране на глобалния минимум или максимум чрез генетичен алгоритъм с двоично кодиране е теоретично обоснована в основната теорема за генетичните алгоритми ("теорема на модела"), доказана от Холанд. Подробното му покритие и доказателство могат да бъдат намерени в съответните източници. Същността му е, че двоичната азбука ви позволява да обработвате максимално количество информация в сравнение с други схеми за кодиране.
Бинарното представяне на хромозомите обаче води до определени трудности при търсене в непрекъснати пространства с големи размери и когато се изисква висока точност на намереното решение. В BGA се използва специална техника за преобразуване на генотип във фенотип, основана на факта, че целият диапазон от допустими стойности на атрибута на обекта $ [a_i, b_i] $ е разделен на секции с необходимата точност. Посочената точност $ p $ се определя от израза
където $ N $ е броят на битовете за кодиране на битовия низ.
Тази формула показва, че $ p $ силно зависи от $ N $, т.е. точността на представянето се определя от броя на битовете, използвани за кодиране на една хромозома. Следователно, с увеличаване на $ N $, пространството за търсене се разширява и става огромно. Добре известен пример за книга: нека за $ 100 $ променливи, вариращи в интервала $ [- 500; 500] $, трябва да намерите екстремума с точност до шест знака след десетичната запетая. В този случай, когато се използва GA с двоично кодиране, дължината на низа ще бъде $ 3000 $ елементи, а пространството за търсене ще бъде около $ 10 ^ 1000 $ хромозоми.
Ефективността на BGA в този случай ще бъде ниска. При първите итерации алгоритъмът ще похарчи много усилия, за да оцени най-малко значимите битове от броя, кодиран във фрагмента на бинарната хромозома. Но оптималната стойност при първите повторения ще зависи от най-значимите цифри на числото. Следователно, докато в процеса на еволюция алгоритъмът достигне стойността на най-значимия бит в близост до оптимума, операциите с най-малко значими цифри ще бъдат безполезни. От друга страна, когато това се случи, вече няма да са необходими операции с най-значимите битове - необходимо е да се подобри точността на решението чрез търсене в най-малко значимите битове. Това „идеално“ поведение не се осигурява от семейството алгоритми BGA; тези алгоритми работят върху целия битов низ и в първите епохи долните цифри на числата „замръзват“, приемайки случайна стойност. В класическата GA са разработени специални техники за излизане от тази ситуация. Например, последователно стартиране на ансамбъл от генетични алгоритми с постепенно стесняване на пространството за търсене.