Эволюционные вычисления

Эволюционные вычисления представляют класс вычислительных методов и алгоритмов поиска, оптимизации или обучения, основанных на некоторых формализованных принципах естественного эволюционного отбора[2]. Особенности идей эволюции и самоорганизации заключаются в том, что они находят подтверждение не только для биологических систем. Эти идеи в настоящее время с успехом используются при разработке многих технических и, в особенности, программных систем. Эволюционные вычисления используют различные модели эволюционного процесса.

Среди них можно выделить следующие основные парадигмы:

1. Генетические алгоритмы (ГА);

2. Эволюционные стратегии (ЭС);

3. Эволюционное программирование (ЭП);

4. Генетическое программирование (ГП).

Отличаются они, в основном, способом представления искомых решений и различным набором используемых в процессе моделирования эволюции операторов.

Отметим, что в настоящее время все парадигмы используются при решении прикладных технических задач, но наиболее широко применяются генетические алгоритмы.

ЭВ основаны на моделировании следующих механизмов естественной эволюции:

1) Первый принцип основан на концепции выживания сильнейших и естественного отбора по Дарвину, который был сформулирован им в 1859 году в книге «Происхождение видов путем естественного отбора». Согласно Дарвину особи, которые лучше способны решать задачи в своей среде, выживают и больше размножаются (репродуцируют). В генетических алгоритмах каждая особь представляет собой решение некоторой проблемы. По аналогии с этим принципом особи с лучшими значениями целевой (фитнесс) функции имеют большие шансы выжить и репродуцировать. Формализация этого принципа, как мы увидим далее, дает оператор репродукции.

2) Второй принцип обусловлен тем фактом, что хромосома потомка состоит из частей полученных из хромосом родителей. Этот принцип был открыт в 1865 году Менделем. Его формализация дает основу для оператора скрещивания (кроссинговера).

3) Третий принцип основан на концепции мутации, открытой в 1900 году де Вре. Первоначально этот термин использовался для описания существенных (резких) изменений свойств потомков и приобретение ими свойств, отсутствующих у родителей. По аналогии с этим принципом генетические алгоритмы используют подобный механизм для резкого изменения свойств потомков и тем самым, повышают разнообразие (изменчивость) особей в популяции (множестве решений).

Эти три принципа составляют ядро ЭВ. Используя их, популяция (множество решений данной проблемы) эволюционирует от поколения к поколению. Эволюцию искусственной популяции – поиска множества решений некоторой проблемы формально можно описать алгоритмом, который представлен на рис.3.

Дата добавления: 2014-01-05