Эволюционные методы

Методы, принадлежащие к этому классу, широко используются при решении ин­женерных задач, так как они хорошо подходят для решения задач с большим количе­ством независимых параметров. Кроме того, они имеют преимущества при работе с плохо определенными функциями качества, обладающими нежелательными свой­ствами, такие как нестабильности, различные помехи или даже неопределенные зна­чения.

Эволюционные методы — это методы оптимизации, при которых процесс поиска оптимума происходит по аналогии с процессом биологической эволюции. В этом случае биологические принципы переносятся на технические процессы (рис. 4.33). Эволюционные методы можно разделить на две группы. С одной стороны — это эволю­ционная стратегия, которая впервые была применена Рехенбергом [74] для решения задач оптимизации течений. С другой стороны — генетические алгоритмы, введен­ные Холландом [66] и Голденбергом [60]. Существует множество разновидностей этих стратегий оптимизации, но здесь будут рассмотрены только основные идеи, на которых они базируются. К другим методам, сравнимым с эволюционными алгорит­мами, относятся математический анализ и эволюционное программирование, однако эти методы здесь не рассматриваются. Обзорную информацию обо всех методах, упомянутых здесь, можно найти в работах [53,78,84].

Принцип

Биология

Техника

Репликация

(дублирование,

воспроизводство)

Идентичное дублирование генетического материала

Копирование существующего набора параметров

Мутация

Случайная, ненаправленная модификация генотипа

Случайная, ненаправленная модификация набора параметров

Рождение

Формирование фенотипа (индивидуума)

Выбор нового набора параметров

Жизнь

Существование форм жизни в условиях окружающей среды

Оценка качества сделанного выбора

Селекция

(естественный отбор)

Выживание наиболее приспо­собленных к окружающей среде особей и исчезновение менее приспособленных

Сравнение качества наборов параметров и отбрасывание наборов параметров с худшими качествами

Рис. 4.33. Перенос принципов биологии на оптимизацию технического процесса

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

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

1. В качестве отправной точки выбрать один или несколько наборов параметров.

2. Изменить случайным образом все существующие наборы параметров или один из них (мутация) и образовать определенное количество «потомков».

3. Из полученного множества наборов параметров выбрать тс, которые будут ис­пользованы в качестве «родителей» для получения следующего поколения «потомков». Остальные наборы параме тров отбрасываются.

4. Если цель оптимизации не достигнута, продолжить процесс с этапа 2.

Генетические алгоритмы

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

Кодирование:

Примерный вид таких двоичных последовательностей показан на рис. 4.34. В при­мере, приведенном на этой иллюстрации, три различных параметра закодированы с помощью последовательности двоичных чисел различной длины. Длины этих по­следовательностей, а также метод преобразования системных параметров в двоич­ные коды зависят от конкретной задачи. Когда найдена полезная схема кодирования вещественных чисел последовательностями двоичных чисел, отдельные параметры изменяются случайным образом в целях оптимизации. При использовании генетиче­ских алгоритмов эти случайные изменения осуществляются путем так называемых точечных мутаций и скрещиваний. Мутация изменяет одну цифру в последователь­ности двоичных чисел. Цифра, подлежащая изменению, определяется случайным

1

0

1

0

1

1

0

1

1

1

0

1

1

0

0

0

~Y V V

1-й закодиро - 2-й закодиро - 3-й закодиро­ванный ванный ванный

параметр параметр параметр

Мутация:

0

0 I 1 10 1 0

И GE

0

1

1 0

1

Скрещивание:

Рис. 4.34. Кодирование, мутация, и скрещивание

0

0

1

0

0

0

0

1

1

1

0

1|

о

О

1

0

0

1

0

1

1

1

0

0

образом. В частности, на рис. 4.34 показана такая мутация для параметра, кодируемого 6-битным двоичным числом. Кроме того, получаемые наборы параметров изменяют­ся за счет скрещиваний. За счет скрещивания на основе двух существующих наборов параметров создаются два новых. Новые наборы параметров, получаемые путем скре­щивания, создаются в результате обмена двоичными кодами, начинающимися с не­которой случайным образом определяемой цифры (рис. 4.34). После внесения изме­нений в наборы параметров, они еще раз проходят стадию отбора. Таким образом, процедура оптимизации на основе генетических алгоритмов может быть разделена на следующие стадии:

1. Из исходной «популяции» выбираются несколько наборов параметров.

2. Существующие наборы параметров случайным образом изменяются (проис­ходят мутации).

3. Путем скрещивания образуются новые наборы параметров.

4. Из числа полученных «потомков» отбираются наборы параметров, которые станут «родителями» для следующего поколения. Наборы параметров, не про­шедшие отбора, отбрасываются.

5. Если цель оптимизации не достигнута, процесс продолжается, начиная с шага 2.

Как для эволюционных, так и для генетических алгоритмов существует множе­ство способов образования мутаций и путей отбора потомков. Более подробные све­дения по этому вопросу приведены в работах [77,78].

Комментарии закрыты.