Эволюционные вычисления: методы и история развития

Введение

Решатели задач методом проб и ошибок с метаэвристическим или стохастическим характером оптимизации.

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

История

Концепция имитации эволюционных процессов для решения задач возникла задолго до появления компьютеров, например, когда Алан Тьюринг предложил метод генетического поиска в 1948 году. Машины типа B u Тьюринга напоминают примитивные нейронные сети, а связи между нейронами изучались посредством своеобразного генетического алгоритма. Его машины типа P u напоминают метод обучения с подкреплением, где сигналы удовольствия и боли направляют машину к освоению определенных моделей поведения. Однако статья Тьюринга была опубликована лишь в 1968 году, а он умер в 1954 году, поэтому эта ранняя работа оказала незначительное или вообще никакого влияния на область эволюционных вычислений, которая впоследствии получила развитие. Эволюционные вычисления как самостоятельная область начали активно развиваться в 1950-х и 1960-х годах. В 1962 году Лоуренс Дж. Фогель начал исследования в области эволюционного программирования в Соединенных Штатах, которые рассматривались как попытка создания искусственного интеллекта. В этой системе конечные автоматы используются для решения задач прогнозирования: эти автоматы подвергаются мутациям (добавление или удаление состояний, либо изменение правил перехода между состояниями), а лучшие из мутировавших автоматов подвергаются дальнейшей эволюции в последующих поколениях. Полученный конечный автомат может использоваться для генерации прогнозов по мере необходимости. Метод эволюционного программирования успешно применялся к задачам прогнозирования, идентификации систем и автоматического управления. Впоследствии он был расширен для обработки данных временных рядов и моделирования эволюции игровых стратегий. Изначально эта техника оптимизации выполнялась без использования компьютеров, вместо этого для определения случайных мутаций использовались игральные кости. К 1965 году вычисления полностью перешли к машинному выполнению. В то время как другие подходы были сосредоточены на решении конкретных задач, Голланд в первую очередь стремился использовать генетические алгоритмы для изучения адаптации и определения способов ее моделирования. Популяции хромосом, представленных в виде битовых строк, преобразовывались посредством процесса искусственного отбора, отбирая определенные биты "аллели" в битовой строке. Среди других методов мутации использовались взаимодействия между хромосомами для моделирования рекомбинации ДНК между различными организмами. В отличие от предыдущих методов, отслеживавших только один оптимальный организм за раз (где потомки конкурировали с родителями), генетические алгоритмы Голланда отслеживали большие популяции (где множество организмов конкурировало в каждом поколении). К 1990-м годам появился новый подход к эволюционным вычислениям, получивший название генетического программирования, одним из сторонников которого был Джон Коза. Еще одним пионером в 1950-х годах был Алекс Фрейзер, опубликовавший серию статей о моделировании искусственного отбора. С ростом академического интереса, значительное увеличение вычислительной мощности компьютеров позволило реализовать практические приложения, включая автоматическую эволюцию компьютерных программ. Эволюционные алгоритмы теперь используются для решения многомерных задач более эффективно, чем программное обеспечение, разработанное людьми, а также для оптимизации проектирования систем.

The concept of mimicking evolutionary processes to solve problems originates before the advent of computers, such as when Alan Turing proposed a method of genetic search in 1948 Turing's B type u machines resemble primitive neural networks, and connections between neurons were learnt via a sort of genetic algorithm. His P type u machines resemble a method for reinforcement learning, where pleasure and pain signals direct the machine to learn certain behaviors. However, Turing's paper went unpublished until 1968, and he died in 1954, so this early work had little to no effect on the field of evolutionary computation that was to develop. Evolutionary computing as a field began in earnest in the 1950s and 1960s. In 1962, Lawrence J. Fogel initiated the research of Evolutionary Programming in the United States, which was considered an artificial intelligence endeavor. In this system, finite state machines are used to solve a prediction problem: these machines would be mutated (adding or deleting states, or changing the state transition rules), and the best of these mutated machines would be evolved further in future generations. The final finite state machine may be used to generate predictions when needed. The evolutionary programming method was successfully applied to prediction problems, system identification, and automatic control. It was eventually extended to handle time series data and to model the evolution of gaming strategies. Initially, this optimization technique was performed without computers, instead relying on dice to determine random mutations. By 1965, the calculations were performed wholly by machine. While the other approaches were focused on solving problems, Holland primarily aimed to use genetic algorithms to study adaptation and determine how it may be simulated. Populations of chromosomes, represented as bit strings, were transformed by an artificial selection process, selecting for specific 'allele' bits in the bit string. Among other mutation methods, interactions between chromosomes were used to simulate the recombination of DNA between different organisms. While previous methods only tracked a single optimal organism at a time (having children compete with parents), Holland's genetic algorithms tracked large populations (having many organisms compete each generation). By the 1990s, a new approach to evolutionary computation that came to be called genetic programming emerged, advocated for by John Koza among others. Another pioneer in the 1950s was Alex Fraser, who published a series of papers on simulation of artificial selection. As academic interest grew, dramatic increases in the power of computers allowed practical applications, including the automatic evolution of computer programs. Evolutionary algorithms are now used to solve multi dimensional problems more efficiently than software produced by human designers, and also to optimize the design of systems.

Эволюционные алгоритмы

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

Эволюционные алгоритмы и биология

Генетические алгоритмы предоставляют методы моделирования биологических систем и системной биологии, которые связаны с теорией динамических систем, поскольку они используются для предсказания будущих состояний системы. Это лишь яркий (но, возможно, вводящий в заблуждение) способ привлечь внимание к упорядоченному, хорошо контролируемому и высокоструктурированному характеру развития в биологии. Однако использование алгоритмов и информатики, в особенности вычислительной теории, помимо аналогии с динамическими системами, также важно для понимания самой эволюции. Преимущество этой точки зрения заключается в признании отсутствия центрального контроля над развитием: организмы развиваются в результате локальных взаимодействий внутри и между клетками. Наиболее перспективными нам кажутся идеи о параллелях в разработке программ, указывающие на явную аналогию между процессами внутри клеток и низкоуровневой работой современных компьютеров. Таким образом, биологические системы подобны вычислительным машинам, обрабатывающим входную информацию для вычисления следующих состояний, что делает биологические системы ближе к вычислению, чем классическая динамическая система. Более того, опираясь на концепции вычислительной теории, микропроцессы в биологических организмах фундаментально неполны и неразрешимы (полнота (в логике)), что подразумевает, что аналогия между клетками и компьютерами – это не просто грубая метафора. Аналогия с вычислениями распространяется и на взаимосвязь между системами наследственности и биологической структурой, которая часто считается ключом к решению одной из самых важных проблем в объяснении происхождения жизни. Эволюционные автоматы, являющиеся обобщением эволюционных машин Тьюринга, были введены для более точного изучения свойств биологических и эволюционных вычислений. В частности, они позволяют получить новые результаты об экспрессивности эволюционных вычислений. Это подтверждает первоначальный результат о неразрешимости естественной эволюции и эволюционных алгоритмов и процессов. Эволюционные конечные автоматы, самый простой подкласс эволюционных автоматов, работающих в терминальном режиме, способны принимать произвольные языки над заданным алфавитом, включая нерекурсивно перечислимые (например, диагональный язык) и рекурсивно перечислимые, но не рекурсивные языки (например, язык универсальной машины Тьюринга).

Genetic algorithms deliver methods to model biological systems and systems biology that are linked to the theory of dynamical systems, since they are used to predict the future states of the system. This is just a vivid (but perhaps misleading) way of drawing attention to the orderly, well controlled and highly structured character of development in biology. However, the use of algorithms and informatics, in particular of computational theory, beyond the analogy to dynamical systems, is also relevant to understand evolution itself. This view has the merit of recognizing that there is no central control of development; organisms develop as a result of local interactions within and between cells. The most promising ideas about program development parallels seem to us to be ones that point to an apparently close analogy between processes within cells, and the low level operation of modern computers. Thus, biological systems are like computational machines that process input information to compute next states, such that biological systems are closer to a computation than classical dynamical system. Furthermore, following concepts from computational theory, micro processes in biological organisms are fundamentally incomplete and undecidable (completeness (logic)), implying that “there is more than a crude metaphor behind the analogy between cells and computers. The analogy to computation extends also to the relationship between inheritance systems and biological structure, which is often thought to reveal one of the most pressing problems in explaining the origins of life. Evolutionary automata, a generalization of Evolutionary Turing machines, have been introduced in order to investigate more precisely properties of biological and evolutionary computation. In particular, they allow to obtain new results on expressiveness of evolutionary computation. This confirms the initial result about undecidability of natural evolution and evolutionary algorithms and processes. Evolutionary finite automata, the simplest subclass of Evolutionary automata working in terminal mode can accept arbitrary languages over a given alphabet, including non recursively enumerable (e. g., diagonalization language) and recursively enumerable but not recursive languages (e. g., language of the universal Turing machine).