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

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

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

Същност на еволюционните алгоритми

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

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

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

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

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

1. Създаване на начално поколение.

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

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

3. Проверка за край на алгоритъма.

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

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

4. Селекция.

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

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

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

6. Мутация.

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

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

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

Видове еволюционни алгоритми.

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

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

Източници

• Материали за еволюционни алгоритми (07.01.2011)
• Генетични алгоритми: ключови понятия и методи за реализация (07.01.2011)
• Spears, W. M., Evolutionary algorithms: the role of mutation and recombination. Springer, 2000 – Книга, посветена на еволюционните алгоритми
• Жуков В.Г., Золотарев В.В., Заблоцкая Н.С., Паротькин Н.Ю., Ширкова Е.А. - Системы управления и информационные технологии, 2009 – Разработен е подход за управление на информационните рискове с помощта на факторния анализ и еволюционен алгоритъм

Вижте също

• Гаусова селекция
• експертни системи
• комбинаторика
• Методи на Парето
• програми за оптимизация
• теория на информацията

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

• Историята на развитието на еволюционните алгоритми(ru)

• Материали за еволюционни алгоритми(en)