Преглед на кода на Еволюционен алгоритъм

'''Еволюционните алгоритми''' ('''ЕА''') (на [[английски език|английски]]: Evolutionary Algorithms (EA)) '''използват и моделират [[биологичната еволюция]]'''. 

==Същност на еволюционните алгоритми==
Еволюционните алгоритми поддържат популация от индивиди  ([[хромозоми]]), които еволюират чрез използване на [[селекция]] и други операции като кръстосване и мутация. Всеки индивид в популацията получава оценка за приспособимостта си (fitness function) към средата. В термините на [[оптимизация]]та това означава, че за всеки набор от променливи се изчислява [[стойност]]та на [[функция]]та, която се минимизира или максимизира. [[Селекция]]та служи за избор на най-добрите комбинации, които чрез кръстосване и [[мутация]] трябва да доведат до по-добри решения в следващото поколение.

Идеята за еволюционни изчисления е била представена през 1960 г. от I. Rechenberg в неговия труд "Еволюционни стратегии”.

Връзката между природата и еволюционните алгоритми е интуитивна:

* [[Индивид]]ите в природата - възможни решения на задачата.
* [[Природа]] – функция, чиито [[оптимум]] търсим ([[целева функция]]).
* [[Естествен подбор]], [[размножаване]] и мутация – основни еволюционни операции (аналог на действителните процеси).

В [[еволщционен алгоритъм|еволюционните алгоритми]] се използват трите основни принципа на естествената [[еволюция]], описани от Дарвин: репродукция, естествен подбор и разнообразие на индивидите, поддържано чрез разликите на всяко поколение с предишното. Теорията за еволюцията на видовете е довела до идеята за копиране на приспособимостта на видовете в природата и използването й за решаване на различни инженерни задачи. Ако всеки индивид се разглежда като възможно решение, а природата като функция, определяща кои решения са добри и кои не, лесно може да се направи аналогия с оптимизационните задачи. По този начин се е появила идеята за еволюционни алгоритми за оптимизация. [[Оптимизация]]та, както и еволюцията, е процес на търсене на по-добро решение сред множество от възможни решения. В този смисъл еволюцията се явява оптимизационна задача, търсеща най-добре приспособеният индивид.

==Схема на еволюционните алгоритми==

Една от най-често използваните схеми на еволюционните алгоритми включва следните стъпки:

[[Image:Genetic_Algorithms-Image1.png|right]]

1. Създаване на начално поколение
При повечето алгоритми първото поколение се генерира на случаен принцип – [[ген]]ите на отделните [[хромозома|хромозоми]] се избират случайно измежду азбуката на допустимите гени. Заради по-лесната изчислителна [[процедура]] се приема, че всички поколения се състоят от еднакъв брой индивиди (''N ''на брой).

2. Изчисляване на стойността на функцията, която минимизираме или максимизираме

3. Проверка за край на алгоритъма
Както при всички алгоритми за оптимизация и тук е възможно алгоритъмът да бъде прекратен по:

* Стойност на функцията – стойността на функцията на най-добрия индивид става достатъчно близка до зададена стойност. Обикновено не се препоръчва използването само на този критерий, защото поради [[стохастичния характер]] на търсенето не може да се гарантира достигане до желания екстремум в разумно време;
* Максимален брой [[итерации]] – това е най-често използвания критерий за спиране. Той гарантира, че независимо дали алгоритъмът е достигнал до екстремум или не ще спре след определено време;
* Достигане на установена стойност – ако в продължение на  предварително зададен брой итерации (поколения) не е настъпило подобрение на стойността на функцията, алгоритъмът спира.

4. Селекция
Измежду всички индивиди в текущото поколение се избират тези, които да продължат развитието си в [[кръстосване]]то и  [[мутация]]та. На този етап може да се използва [[елитарен подход]]. Това означава част от най-добрите индивиди (''n ''на брой) да се прехвърлят без промяна в следващото поколение. По този начин се гарантира, че достигнатата стойност на функцията не може да се влоши (веднъж достигнат екстремумът няма да бъде изпуснат).

5. Кръстосване

Избраните чрез селекция индивиди се [[кръстосват]]. По този начин се получават нови индивиди, като стремежът е тези индивиди да наследят възможно най-добрата комбинация от характеристики на родителите си.

6. Мутация

Чрез случайна промяна на някои от [[ген]]ите се гарантира, че дори нито един от индивидите в текущото поколението да не съдържа необходимият ген, пак е възможно да се достигне до екстремум.

7. Ново поколение

Избраните от селекцията индивиди се обединяват с получените чрез селекция и мутация и образува следващото поколение.

==Видове ==

Основните видове еволюционни алгоритми са:

* [[еволюционно програмиране]] (на английски: Evolutionary Programming);
* [[еволюционни стратегии]] (на английски: Evolutionary Strategies) и
* [[генетични алгоритми]] (на английски: Genetic Algorithms).

==Вижте също==

* [[Гаусова селекция]]
* [[Експертни системи]]
* [[Комбинаторика]]
* [[Принцип на Парето]]
* [[Програми за оптимизация]]
* [[Теория на информацията]]

==Източници==

* [http://www.geatbx.com/docu/algindex.html   Материали за еволюционни алгоритми (07.01.2011)]
* [http://www.znannya.org/?view=ga_general  Генетични алгоритми: ключови понятия и методи за реализация (07.01.2011)]
* Spears, W.  M., Evolutionary algorithms: the role of mutation and recombination. Springer, 2000 – Книга, посветена на еволюционните алгоритми
* Жуков В.Г., Золотарев В.В., Заблоцкая Н.С., Паротькин Н.Ю., Ширкова Е.А. - Системы управления и информационные технологии, 2009 – Разработен е подход за управление на информационните рискове с помощта на факторния анализ и еволюционен алгоритъм

==Външни препратки==

* [http://algolist.manual.ru/ai/ga/ga1.php  Историята на развитието на еволюционните алгоритми](ru) 

* [http://eprints.ecs.soton.ac.uk/6641/  Материали за еволюционни алгоритми](en)

[[category:Моделиране и прогнозиране в управлението]]