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

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

Таблица 5.1. Ранжированный список решений и их стоимостей

Решение

Стоимость

[7, 5, 2, 3, 1, 6, 1, 6, 7, 1, 0, 3]

4394

[7, 2, 2, 2, 3, 3, 2, 3, 5, 2, 0, 8]

4661

[0, 4, 0, 3, 8, 8, 4, 4, 8, 5, 6, 1]

7845

[5, 8, 0, 2, 8, 8, 8, 2, 1, 6, 6, 8]

8088

Проранжировав решения, мы создаем новую популяцию, которая называется следующим поколением. Сначала в новую популяцию включаются самые лучшие решения из текущей. Этот процесс называется элитизмом. Кроме них, в следующую популяцию входят совершенно новые решения, получающиеся путем модификации наилучших. Модифицировать решения можно двумя способами. Более простой называется мутацией; обычно это небольшое, простое, случайное изменение существующего решения. В нашем случае для мутации достаточно выбрать одну из переменных решения и уменьшить либо увеличить ее. На рис. 5.3 приведено два примера.

Рис. 5.3. Примеры мутации решения

Другой способ называется скрещиванием (или кроссовером). Состоит он в том, что мы берем какие-нибудь два из лучших решений и как-то комбинируем их. В нашем примере достаточно взять случайное число элементов из одного решения, а остальные – из другого, как показано на рис. 5.4.

Размер новой популяции обычно совпадает с размером предыдущей, а создается она путем случайных мутаций и скрещиваний лучших

Рис. 5.4. Пример скрещивания

решений. Затем этот процесс повторяется – новая популяция ранжируется и создается очередное поколение. Так продолжается заданное число раз или до тех пор, пока на протяжении нескольких поколений не наблюдается никаких улучшений. Добавьте функцию geneticoptimize в файл optimization.py: def geneticoptimize(domain,costf,popsize=50,step=1, mutprod=0.2,elite=0.2,maxiter=100):

#       Операция мутации def mutate(vec):

i=random.randint(0,len(domain)-1) if random.random( )<0.5 and vec[i]>domain[i][0]:

return vec[0:i]+[vec[i]-step]+vec[i+1:] elif vec[i]<domain[i][1]:

return vec[0:i]+[vec[i]+step]+vec[i+1:]

#       Операция скрещивания def crossover(r1,r2):

i=random.randint(1,len(domain)-2) return r1[0:i] + r2[i:]

#       Строим начальную популяцию pop=[]

for i in range(popsize): vec=[random.randint(domain[i][0],domain[i][1])

for i in range(len(domain))] pop.append(vec)

#       Сколько брать победителей из каждой популяции? topelite=int(elite*popsize)

#       Главный цикл

for i in range(maxiter): scores=[(costf(v),v) for v in pop] scores.sort( )

ranked=[v for (s,v) in scores]

# Сначала включаем только победителей pop=ranked[0:topelite]

#       Добавляем особей, полученных мутацией и скрещиванием победивших

#       родителей

while len(pop)<popsize:

if random.random( )<mutprob:

#   Мутация

c=random.randint(0,topelite) pop.append(mutate(ranked)) else:

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

c1=random.randint(0,topelite) c2=random.randint(0,topelite) pop.append(crossover(ranked[c1],ranked[c2]))

#       Печатаем полученные к текущему моменту наилучшие результаты print scores[0][0]

return scores[0][1] Эта функция принимает несколько необязательных параметров:

popsize

Размер популяции.

mutprob

Вероятность того, что новая особь будет результатом мутации, а не скрещивания.

elite

Доля особей в популяции, считающихся хорошими решениями и переходящих в следующее поколение. maxiter

Количество поколений. Попробуем оптимизировать план путешествия с помощью генетического алгоритма:

>>> s=optimization.geneticoptimize(domain,optimization.schedulecost)

3532 3503

2591 2591 2591

>>> optimization.printschedule(s)

Seymour

BOS

12

34

15

02

$109

10

33

12

03

$

74

Franny

DAL

10

30

14

57

$290

10

51

14

16

$2

56

Zooey

CAK

10

53

13

36

$189

10

32

13

16

$1

39

Walt

MIA

11

28

14

40

$248

12

37

15

05

$1

70

Buddy

ORD

12

44

14

17

$134

10

33

13

11

$1

32

Les

OMA

11

08

13

07

$175

11

07

13

24

$1

71

Отцом генетических алгоритмов принято считать ученого-теоретика Джона Холланда (John Holland), который в 1975 году написал книгу «Adaptation in Natural and Artificial Systems» (издательство Мичиганского университета). Но корни этих работ восходят к биологам 1950-х годов, которые пытались моделировать эволюцию на компьютерах. С тех пор генетические алгоритмы и другие методы оптимизации использовались для решения широчайшего круга задач, в том числе:

•        Нахождения формы концертного зала с оптимальными акустическими характеристиками.

•        Проектирования оптимальной формы крыла сверхзвукового самолета.

•        Составления оптимальной библиотеки химических веществ для синтеза потенциальных лекарств.

•        Автоматического проектирования микросхем для распознавания речи.

Решения этих задач можно представить в виде списков чисел. Это упрощает применение к ним генетических алгоритмов или метода имитации отжига.

Будет ли работать конкретный метод оптимизации, в значительной мере зависит от задачи. Метод имитации отжига, генетические алгоритмы и прочие методы оптимизации основаны на том факте, что в большинстве задач оптимальное решение близко к другим хорошим решениям. А на рис. 5.5 представлен случай, когда оптимизация может и не сработать.

Рис. 5.5. Задача, плохо поддающаяся оптимизации

Оптимальная стоимость соответствует низшей точке очень крутого участка кривой в правой части рисунка. Любое достаточно близкое решение, скорее всего, будет отвергнуто из-за его высокой стоимости, поэтому мы никогда не сможем добраться до глобального минимума. Большинство алгоритмов остановятся в каком-то локальном минимуме в левой части рисунка.

Пример с составлением расписания полетов работает, потому что выбор второго рейса вместо третьего, скорее всего, изменит стоимость менее значительно, чем выбор восьмого рейса. Если бы рейсы были упорядочены случайным образом, то методы оптимизации работали бы не лучше случайного поиска; на самом деле не существует ни одного метода оптимизации, который в этом случае работал бы устойчиво лучше, чем случайный поиск.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100