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

 

Согласованность и эффективность работы элементов биологических организмов наводит на мысль — можно ли использовать принципы биологической эволюции для оптимизации практически важных для человека систем?

В нескольких модификациях подобные идеи возникали у ряда авторов. В 1966 г. Л. Фогель, А. Оуэне, М. Уолш написали книгу «Искусственный интеллект и эволюционное моделирование», в которой предложили схему эволюции логических автоматов, решающих задачи прогноза. В 1975 г. вышла основополагающая книга Дж. Холланда «Адаптация в естественных и искусственных системах», в которой был предложен генетический алгоритм, исследованный в дальнейшем учениками и коллегами Холланда в Мичиганском университете. Примерно в это же время группа немецких ученых (И. Рехенберг, Г.-П. Швефель и др.) начала разработку так называемой эволюционной стратегии. Эти работы заложили основы прикладного эволюционного моделирования или эволюционных алгоритмов.

В нашей стране исследования по прикладному эволюционному моделированию, идейно близкие к работам Л. Фогеля с сотрудниками, были разносторонне развиты в работах И. Л. Букатовой.

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

Основные эволюционные алгоритмы:

· генетический алгоритм, предназначенный для оптимизации функций дискретных переменных и акцентирующий внимание на рекомбинациях геномов;

· эволюционное программирование, ориентированное на оптимизацию непрерывных функций без использования рекомбинаций;

· эволюционная стратегия, ориентированная на оптимизацию

· непрерывных функций с использованием рекомбинаций;

· генетическое программирование, использующее эволюцион

· ный метод для оптимизации компьютерных программ [6].

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

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

Для иллюстрации принципов работы эволюционных алгоритмов рассмотрим подробнее генетический алгоритм.

 

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

 

Генетический алгоритм (ГА) — это компьютерная модель эволюции популяции искусственных «особей». Каждая особь характеризуется своей хромосомой S_k, хромосома есть «геном» особи. Хромосома определяет приспособленность особи f(S_k); k=1,..., n; n — численность популяции. Хромосома есть цепочка символов S_k = (S_k1, S_k2, …, S_kN), N — длина цепочки. Символы интерпретируются как «гены» особи, расположенные в хромосоме S_k. Задача алгоритма состоит в максимизации функции приспособленности f(S_k).

Эволюция состоит из последовательности поколений. В каждом поколении отбираются особи с высокими значениями приспособленностями. Хромосомы отобранных особей рекомбинируются и подвергаются малым мутациям. Формально, схема ГА может быть представлена следующим образом (популяция t-ro поколения обозначается как {S_k(t)}):

Шаг 0. Создать случайную начальную популяцию {S_k(0)}.

Шаг 1. Вычислить приспособленность f(S_k) каждой особи S_k популяции {S_k(t)}.

Шаг 2. Производя отбор особей S_k в соответствии с их приспо-собленностями f(S_k) и применяя генетические операторы (рекомбинации и точечные мутации) к отобранным особям, сформировать популяцию следующего поколения {S_k(t+1)}.

Шаг 3. Повторить шаги 1, 2 для f = 0, 1, 2,..., до тех пор, пока не выполнится некоторое условие окончания эволюционного поиска (прекращается рост максимальной приспособленности в популяции, число поколений t достигает заданного предела и т. п.).

Имеется ряд конкретных вариантов генетического алгоритма, которые отличаются по схемам отбора, рекомбинаций, по форме представления хромосом и т. д.

Наиболее традиционный вариант генетического алгоритма базируется на следующей конкретной схеме: 1) цепочки символов в хромосомах бинарны (символы S_ki принимают значения 0 либо 1), длина цепочек постоянна (N= const), 2) метод отбора пропорционально-вероятностный (см. ниже), 3) рекомбинации производятся по схеме одноточечного кроссинговера.

Кроссинго́вер — явление обмена участками гомологичных хромосом во время конъюгации при мейозе. Помимо мейотического описан также митотический кроссинговер. Конъюгация — (от лат. conjugatio соединение) биологический термин, которым обозначается ряд процессов.

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

Поскольку кроссигновер вносит возмущения в картину сцепленного наследования, его удалось использовать для картирования «групп сцепления» (хромосом). Возможность картирования была основана на предположении о том, что, чем чаще наблюдается кроссинговер между двумя генами, тем дальше друг от друга расположены эти гены в группе сцепления и тем чаще будут наблюдаться отклонения от сцепленного наследования. Первые карты хромосом были построены в 1913 г. для классического экспериментального объекта плодовой мушки Drosophila melanogaster Альфредом Стёртевантом, учеником и сотрудником Томаса Ханта Моргана).

Пропорционально-вероятностный отбор означает, что на шаге 2 отбор производится с вероятностями, пропорциональными приспособленностям f_k особей (f_k = f(S_k)). Схему можно представить, как выбор особи с помощью рулетки, относительные площади секторов которой равны q_k =f_k[ f_i]^-1 (см. рис. и пояснение к нему).

 

Рис. Схема отбора, при которой особи выбираются в популяцию нового поколения с вероятностями q_k, пропорциональными их приспособленностям f_k. Показан пример, для которого n=4, f₁=2, f₂=4, f₃=1, f₄=1.

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

Одноточечный кроссинговер организуется по аналогии с биологической рекомбинацией. А именно, если есть два родителя S₁ = (S₁₁, S₁₂, …, S_1N) и S₂ = (S₂₁, S₂₂, …, S_2N), тo их потомки есть (S₁₁, …, S_1m, S_2,m+1,..., S_2N) и (S₂₁, …, S_2m, S_1,m+1,..., S_1N); т.е. «голова» и «хвост» хромосомы потомка берутся от разных родителей. Точка кроссинговера выбирается случайным образом, в приведенном примере она располагается между m-м и m+1-м «генами». Аналогичным образом может быть организован двухточечный и «несколько-точечный» кроссинговер. Тип рекомбинации по схеме кроссинговера часто дополняется инверсиями, т. е. изменением порядка следования символов в участках хромосом; это аргументируется, как необходимость подобрать существенные для приспособленности комбинации символов в хромосоме.

Некоторые схемы ГА используют равномерные рекомбинации. Это означает, что два родителя имеют двух потомков, символы хромосомы одного из потомков выбираются случайно от любого из двух родителей (но с сохранением порядка следования символов), а второму потомку достаются оставшиеся символы. Например, два потомка родителей S₁ = (S₁₁, S₁₂, …, S_1N) и S₂ = (S₂₁, S₂₂, …, S_2N) могут иметь следующие хромосомы (S₁₁, S₂₂, S₁₃, S₁₄, …, S_2N) и (S₂₁, S₁₂, S₂₃, S₂₄, …, S_1N).

Как метод оптимизации, ГА обладает внутренним параллелизмом (implicit parallelism): разные частные существенные комбинации генов — их часто называют «схематами» («schemata») — отыскиваются параллельным образом, одновременно для всех комбинаций. Отметим, что чем меньше комбинация, тем легче она может быть найдена.

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