Физика процессов эволюции - Эбилинг В.
Скачать (прямая ссылка):
Приведенные примеры показывают, что знание процессов самоорганизации играет важную роль при разработке автоматизированных производственных установок, ибо позволяет исключить возможность возникновения нежелательной самоорганизации и, если обстоятельства позволяют, использовать самоорганизацию для оптимизации технических, экономических, экологических и др. процессов. Для этого чрезвычайно важны дальнейшие исследования. Одно из интересных направлений таких исследований — самоорганизация моделей прогнозирования (Ivachnenko, Miiller, 1984).
Обширной областью приложений принципов эволюции является актуальная проблема автоматизации процессов проектирования и оптимизации проектов (Re-chenberg, 1973; Schwefel, 1977). Оптимизация несомненно принадлежит к числу основных проблем современной экономики и технологии. Современному обществу требуются простые, надежные и недорогие решения. Примерами использования принципов самоорганизации и эволюции для решения задач оптимизации мы особенно обязаны работам Холланда, Рехенберга и Швефеля, успешно решивших большое число интересных технических проблем. Мы рассмотрим в этой главе лишь один специальный класс трудных задач на оптимизацию, частные случаи которых встречаются в самых различных областях экономики и техники.
Пример 1. В микроэлектронике стоит задача соединить проводящими путями по заданной схеме относительно большое количество заданных переключательных схем (» = 102-107). Как наилучшим образом расположить элементы на чипе, чтобы суммарная длина проводящих путей была возможно меньше? Разумеется, на практике приходится соблюдать множество дополнительных условий, например, следить за тем, чтобы проводящие пути не пересекались и т.д. (Iwainsky, 1984, 1985; Voigt, 1985).
Пример 2. Основная проблема современного двигателестроения состоит в том, чтобы построить оптимальный профиль дюз для многофазных и реактивных течений. Полный теоретический расчет протекающих при этом сложных процессов пока невозможен. Рехенберг (Rechenberg, 1973) и Швефель (Schwefel, 1977) показали, каким образом эволюционные стратегии позволяют найти оптимальные решения. Задача состояла в том, чтобы с помощью горячей смеси из паров и капель калия создать сопло с максимальной тягой. Для экспериментальной адаптивной оптимизации было подготовлено 330 конических сопел различного продольного сечения. Оптимальная форма сопла (рис. 12.6) была найдена методом проб и ошибок.
Пример 3. Торговые и транспортные проблемы нередко требуют расположить потребителей в такой последовательности, чтобы их можно было объехать по крат-
Рис. 12.6. Задача Рехенберга и Швефеля состоит в том, чтобы найти оптимальный профиль дюзы, обеспечивающий максимальную тягу двухфазного течения: (а) до; (б) после применения эволюционной стратегии
чайшему пути или снизить дорожные расходы до минимума. Эту проблему, известную под названием «задачи коммивояжера», пытались решить многие исследователи (Kirkpatrick et al., 1983, 1985).
Пример 4. Важной проблемой для эффективности производства является рациональное использование станочного парка. Речь идет о таком использовании имеющихся станков, при котором сводятся до минимума простои или расходы на переналадку. Аблай (АЫау, 1987) показал, что и такого рода задачи могут решаться с помощью эволюционных стратегий.
Трудность решения задач бегло очерченного выше класса связана с тем, что число производимых операций растет экспоненциально с увеличением числа элементов (неполиномиальная, или НП-, полнота). Это приводит к чудовищным временам счета и обусловливает непригодность классических стандартных методов оптимизации. Эффективность новых методов поиска решений мы продемонстрируем иа примере задачи об обходе всех ребер графа (рис. 12.7). Требуется найти маршрут обхода всех ребер, при котором длина пути была бы минимальной в заданной метрике. Метод решения состоит в том, чтобы, исходя из произвольно выбранного Pi,c-12.7. Задача коммиво-начального маршрута, с помощью стохастического пе- яж?ра состоит 8 5°“. чтобы
ребора ребер приблизиться, насколько это возможно, « гпИ^о
г ’ проходящии через п городов
к неизвестному оптимуму. Существует огромное число
математических работ, в которых наряду с классической градиентной стратегией предлагается ряд более практичных способов решения. Совершенно новый физически мотивированный подход был предложен в работе (Kirkpatrick, Gelatt, Vecchi, 1983). Авторы назвали свой метод стратегией моделируемого отжига. Идея метода состоит в следующем. Мы моделируем процесс стохастического перебора ребер замкнутого маршрута с вероятностями перехода, удовлетворяющими распределению Больцмана с псевдотемпературой Т (метод Монте—Карло, алгоритм Метрополиса). Начальную температуру мы выбираем высокой, а затем постепенно ее понижаем. В качестве функции Гамильтона служит суммарная длина пути
Я=Х=1>г
Иначе говоря, мы подходим к решению задачи так же, как доменщик, стремящийся выплавить высококачественный металл. Метод моделируемого охлаждения, известный также под названием больцмановской стратегии, применялся во многих научных исследованиях и неоднократно усовершенствовался и видоизменялся. Один из частных вариантов этого метода был предложен и авторами настоящей книги (Ebeling, Engel, 1986; Boseniuk, Ebeling, Engel, 1987). Основная идея состоит в сочетании больцмановской стратегии с дарвиновской стратегией. Мы исходили из следующего простого соображения: пример эволюции учит нас, что для возникновения качественно новой и обладающей какими-то преимуществами структуры из ансамбля
