Cтраница 3
Второе различие между эволюционными стратегиями и генетическими алгоритмами кроется в организации процесса селекции. При реализации эволюционной стратегии формируется промежуточная популяция, состоящая из всех родителей и некоторого количества потомков, созданных в результате применения генетических операторов. С помощью селекции размер этой промежуточной популяции уменьшается до величины родительской популяции за счет исключения наименее приспособленных особей. Сформированная таким образом популяция образует очередное поколение. Напротив, в генетических алгоритмах предполагается, что в результате селекции из популяции родителей выбирается количество особей, равное размерности исходной популяции, при этом некоторые ( наиболее приспособленные) особи могут выбираться многократно. В то же время, менее приспособленные особи также имеют возможность оказаться в новой популяции. Однако шансы их выбора пропорциональны величине приспособленности особей. Независимо от применяемого в генетическом алгоритме метода селекции ( например, рулетки или рангового) более приспособленные особи могут выбираться многократно. При реализации эволюционных стратегий особи выбираются без повторений. В эволюционных стратегиях применяется детерминированная процедура селекции, тогда как в генетических алгоритмах она имеет случайный характер. [31]
Еще одно различие между эволюционными стратегиями и генетическими алгоритмами касается трактовки ограничений, налагаемых на решаемые оптимизационные задачи. Если при реализации эволюционных стратегий на некоторой итерации потомок не удовлетворяет всем ограничениям, то он отвергается и включается в новую популяцию. Если таких потомков оказывается много, то эволюционная стратегия запускает процесс адаптации параметров, например, путем увеличения вероятности скрещивания. В генетических алгоритмах такие параметры не изменяются. В них может применяться штрафная функция для тех особей, которые не удовлетворяют наложенным ограничениям, однако эта технология обладает многими недостатками. [32]
Моделирование развития и совершенствования природы позволяет найти новые пути построения интеллектуальных искусственных систем. Основными направлениями здесь могут выступить эволюционные стратегии, генетические алгоритмы, а также генетическое программирование. [33]
Параметры ( Np L r) эволюционных стратегий обеспечивают свободное согласование числа родителей в популяции. Параметр г определяет число хромосом и оператор рекомбинации применяется для любого данного множества г родителей. Дискретная версия выбирает случайно одну родительскую хромосому. Средняя версия дает усреднение всех родительских хромосом как хромосому потомка. Число г является независимым параметром рекомбинации. Для выполнения теоретического анализа необходимо, чтобы все родители являлись различными случайно выбранными из популяции размерности Np. Новый оператор применяется после селекции г родителей из популяции. Выбор двух хромосом для каждого i - ro случая выполняется только из г индивидов. В этом случае оригинальный механизм сохраняется неизменным, насколько это возможно, хотя вариации между двумя экстремумами г 2 и г Np возможны. [34]
Эволюционное моделирование - направление в математическом моделировании, объединяющее компьютерные методы моделирования эволюции, а также близкородственные по источнику заимствования идей ( теоретическая биология, если таковая существует) другие направления в эвристическом программировании. Включает в себя как разделы генетические алгоритмы, эволюционные стратегии, эволюционное программирование, искусственные нейронные сети, нечеткую логику. [35]
В основе алгоритма лежит разбиение общей задачи синтеза на ряд подзадач с определенным температурным интервалом каждая. В пределах каждой подзадачи синтез может проводиться с использованием эвристических правил или эволюционной стратегии. [36]
Рассмотренный алгоритм достаточно просто реализуется на начальном этапе синтеза теплообменных систем на основе критерия максимума рекуперации тепла. Однако как при получении базового варианта схемы, так и при его усовершенствовании используются определенные эвристические правила и эволюционные стратегии, связанные с опытом и эрудицией проектировщика и трудно поддающиеся формализации. Наиболее удобным режимом проектирования поэтому является режим непосредственного взаимодействия пользователя с ЭВМ. В этом случае, любая стратегия получения оптимального ( квазиоптимального) варианта схемы может быть легко реализована. Одной из важных задач для получения оптимального варианта теплообменной системы в соответствии с температурно-интервальным алгоритмом является объединение ( расщепление) потоков и теплообменников, перемещение подогревателей и холодильников вдоль температурных градиентов потоков таким образом, чтобы обеспечивалась необходимая. [37]
В июле 1996 г. состоялась первая Всепольская конференция по эволюционным алгоритмам, организованная Институтом основ электроники Варшавского политехнического университета и Клубом эволюционных алгоритмов. Это свидетельствует о появлении множества новых методов, основанных на эволюционном моделировании, но использующих базовые технологии - главным образом классический генетический алгоритм, эволюционные стратегии и эволюционное программирование. [38]
При реализации эволюционных стратегий вначале производится рекомбинация, а потом селекция. В случае выполнения генетических алгоритмов эта последовательность инвертируется. При осуществлении применении эволюционных стратегий потомок образуется в результате скрещивания двух родителей и мутации. Формируемая таким образом промежуточная популяция, состоящая из всех родителей и полученных от них потомков, в дальнейшем подвергается селекции, которая уменьшает размер этой популяции до размера исходной популяции. [39]
Еще одно различие между эволюционными стратегиями и генетическими алгоритмами касается трактовки ограничений, налагаемых на решаемые оптимизационные задачи. Если при реализации эволюционных стратегий на некоторой итерации потомок не удовлетворяет всем ограничениям, то он отвергается и включается в новую популяцию. Если таких потомков оказывается много, то эволюционная стратегия запускает процесс адаптации параметров, например, путем увеличения вероятности скрещивания. В генетических алгоритмах такие параметры не изменяются. В них может применяться штрафная функция для тех особей, которые не удовлетворяют наложенным ограничениям, однако эта технология обладает многими недостатками. [40]
Очевидно, что главное сходство заключается в том, что оба метода используют популяции потенциальных решений и реализуют принцип селекции и преобразования наиболее приспособленных особей. Однако обсуждаемые подходы сильно отличаются друг от друга. Первое различие заключается в способе представления особей. Эволюционные стратегии оперируют векторами действительных чисел, тогда как генетические алгоритмы - двоичными векторами. [41]
Классический генетический алгоритм выполняется при фиксированной длине двоичных последовательностей и в нем применяются операторы скрещивания и мутации. Эволюционные программы обрабатывают более сложные структуры ( не только двоичные коды) и могут выполнять иные генетические операции. Например, эволюционные стратегии могут трактоваться в качестве эволюционных программ, в которых хромосомы представляются вещественными ( не двоичными) числами, а мутация используется как единственная генетическая операция. [42]
Они заключаются в применении ряда правил, выработанных заранее, к исходной схеме с целью ее усовершенствования. Этот процесс логически содержит последовательное чередование этапов синтеза, анализа, оценки проектного решения и оптимизации. Общая методология эволюционного синтеза технологической схемы обычно включает три подзадачи: синтез исходного варианта технологической схемы, выработку правил модификации схемы, выработку эволюционной стратегии. [43]
Каждый объект в популяции характеризуется двумя векторами - вектором решения и случайным вектором, модифицирующим это решение. Случайный вектор характеризуется вектором дисперсии, который хранится в процессе поиска, и может быть дополнен корректирующим вектором, ускоряющим сходимость алгоритма. Значение моделирует величину шага изменения параметров, выбираемую случайным образом. В общем случае может принимать любые значения, однако в схеме моделирования эволюционных механизмов величина отражает интенсивность мутаций родителя и поэтому не слишком велика. В результате отбора одни особи гибнут, а другие живут и размножаются. Эту простую схему легко усовершенствовать, вводя по аналогии с естественными закономерностями зависимость числа порождаемых потомков от значений функций ценности родителей. Соответствующие эволюционные стратегии поиска известны и широко используются на практике. [44]
Второе различие между эволюционными стратегиями и генетическими алгоритмами кроется в организации процесса селекции. При реализации эволюционной стратегии формируется промежуточная популяция, состоящая из всех родителей и некоторого количества потомков, созданных в результате применения генетических операторов. С помощью селекции размер этой промежуточной популяции уменьшается до величины родительской популяции за счет исключения наименее приспособленных особей. Сформированная таким образом популяция образует очередное поколение. Напротив, в генетических алгоритмах предполагается, что в результате селекции из популяции родителей выбирается количество особей, равное размерности исходной популяции, при этом некоторые ( наиболее приспособленные) особи могут выбираться многократно. В то же время, менее приспособленные особи также имеют возможность оказаться в новой популяции. Однако шансы их выбора пропорциональны величине приспособленности особей. Независимо от применяемого в генетическом алгоритме метода селекции ( например, рулетки или рангового) более приспособленные особи могут выбираться многократно. При реализации эволюционных стратегий особи выбираются без повторений. В эволюционных стратегиях применяется детерминированная процедура селекции, тогда как в генетических алгоритмах она имеет случайный характер. [45]