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

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

Одно из наиболее популярных направлений эволюционных вычислений – генетические алгоритмы, предложенные профессором Мичиганского университета Джоном Холландом в 1975 г. Отличительной особенностью генетических алгоритмов является представление любой альтернативы решения в виде кодовой строки фиксированной длины, большинство манипуляции с которой производится в отсутствие всякой связи с ее смысловой интерпретацией. В теории генетических алгоритмов применяется определенная терминология.

Ген (свойство) – атомарный элемент хромосомы. Ген может быть битом, числом или неким другим объектом.

Хромосома (цепочка) – упорядоченная последовательность генов.

Генотип (код) – упорядоченная последовательность хромосом.

Особь (индивидуум) – конкретный экземпляр генотипа.

Фенотип – аргумент (аргументы) целевой функции, соответствующий генотипу (т. е. интерпретация генотипа с точки зрения решаемой задачи).

В наиболее распространенном случае генотип состоит из одной хромосомы и представляется в виде битовой строки. Тогда ген – это бит; генотип (хромосома) – битовая строка, заданной размерности и с определенным положением битов; особь – конкретный набор битов (0 и 1).

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

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

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

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

Операторы скрещивания, мутации и редукции называют генетическими операторами. Скрещивание и мутация выполняются с использованием элементов случайности, а редукция – по строго определенным правилам.

Общая схема работы алгоритма представлена на рис. 40.

Рис. 40. Общая схема работы генетического алгоритма

Критерием остановки работы генетического алгоритма может быть одно из следующих событий:

· сформировано заданное число поколений;

· исчерпано время, отведенное на эволюцию;

· популяция достигла заданного качества (значение критерия одной (нескольких, всех) особей превысило заданный порог);

· достигнут некоторый уровень сходимости (особи в популяции стали настолько подобными, что дальнейшее их улучшение происходит чрезвычайно медленно);

· и т. д.