Что такое эволюция.
Когда мы слышим слово эволюция, что первое приходит нам на ум?
Альбом группы Anacondaz, теория эволюции Дарвина, и тд.
В википедии термин звучит следующим образом:
Биологи́ческая эволю́ция (от лат. evolutio — «развёртывание») —
это изменение наследуемых характеристик биологических популяций на
протяжении последующих поколений.
Но как протекает эволюция в природе, понятно, вот была лошадка и через пару тысяч лет это уже жираф, но как отнести эволюцию к компьютерным программам...
Эволюция в программирование? Иди поспи!
А как же отнести эволюцию к программам? Да очень просто, всё так же как и в природе!
Эволюционные вычисления основаны на принципе дарвиновской эволюции. Её принцеп - улучшение качества плохого решения случайными мутациями, пока задача не будет решена с необходимой точностью.
Многие слышали о естественном отборе, этот механизм так же действует в компьютерных программах. Если у нас есть приблизительное решение задачи, то мы можем случайным образом изменять его и проверять, улучшило ли это его результаты. Если мы продолжим повторять этот процесс, то в результате всегда будем получать лучшее (или такое же) решение.
Итоговый термин эволюционные вычисления звучит так, термин взял из википедии
Эволюционные вычисления — направление в искусственном интеллекте,
которое использует и моделирует процессы естественного отбора.
Ладно, а как же работает эволюция в программах?
Работа Эволюционных вычислений довольно таки проста, она заключается в несложном механизме естественного отбора.
- Initialisation (инициализация). Эволюция должна стартовать с начального решения. Выбор хорошей стартовой точки важен, потому что он может привести к совершенно различным результатам.
- Duplication (дубликация). Создаётся множество копий текущего решения.
- Mutation (мутация). Каждая копия случайным образом мутирует. Величина мутации критична, потому что она управляет скоростью выполнения эволюционного процесса.
- Evaluation (оценка). Изменяется оценка гена, зависящая от показателей, продемонстрированных сгенерированным существом. Во многих случаях для него требуется этап интенсивной симуляции.
- Selection (отбор). После оценки существ лучшим из них разрешается репликация, позволяющая стать основой следующего поколения.
- Output (вывод). Эволюция — итеративный процесс, на любом этапе её можно остановить, чтобы получить улучшенную (или ту же самую) версию предыдущего поколения.
Почему?
Большинство интересных задач ― очень трудные. На столько, что оптимальное решение в общем случае невозможно найти за разумное время никакими методами. Эволюционные алгоритмы позволяют приблизиться к оптимальному решению. Причем, как правило, чем больше времени дать алгоритму ― тем ближе получится подобраться. На практике обычно формулируются конкретные требования: например, приспособленность полученного решения должна быть не ниже такой-то величины. Можно посчитать приспособленность, и если результат не устраивает, запустить алгоритм на более длительное время, возможно, предварительно внеся в него какие-нибудь полезные изменения.
А где они используются?
Сфера применения эволюционных вычислений очень обширна ― они полезны везде, где нужно что-нибудь оптимизировать, и используются как в индустрии, например, в промышленном дизайне, логистике и управлении, так и в других областях науки: в биоинформатике, медицине, робототехнике, машинном обучении (например, для генерации структуры нейронных сетей). Активным направлением в рамках эволюционных вычислений является так называемая поисковая инженерия программного обеспечения, в которой решаются вопросы автоматической генерации, изменения и тестирования программного кода. Также эволюционные вычисления могут применяться для создания объектов искусства и генерации уровней или персонажей в компьютерных играх.
Пример задачи.
Известным примером является космическая антенна NASA, полученная с помощью эволюционного алгоритма. Стояла задача подобрать форму антенны таким образом, чтобы она как можно лучше передавала сигнал. Сначала эту задачу пытались решить точными методами, но только эволюционный алгоритм смог найти оптимальную форму ― внешне довольно причудливую, инженерная мысль не могла дойти до такого решения.