Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

5.7. РЕАЛЬНЫЕ ПРИЛОЖЕНИЯ
Несмотря.на.негативное.мнение.Скиена,.генетические.алгоритмы.часто.и.эф-
фективно.применяются.в.многочисленных.пространствах.задач..Их.нередко.
используют.для.сложных.задач,.которые.не.требуют.абсолютно.оптимальных.
решений,.таких.как.задачи.с.ограничениями,.если.они.слишком.велики,.чтобы.
их.можно.было.решить.с.помощью.традиционных.методов..Один.из.примеров.
таких.задач.—.сложные.проблемы.планирования.
Генетические.алгоритмы.нашли.широкое.применение.в.вычислительной.биологии..
Они.были.успешно.использованы.для.соединения.белка-лиганда,.при.котором.
требовался.поиск.конфигурации.маленькой.молекулы,.связанной.с.реципиентом..
Эти.алгоритмы.используются.в.фармацевтических.исследованиях.и.для.того,.
чтобы.лучше.понять.механизмы.природных.явлений.
1
.
Eiben A. E., Smith J. E. 
Introduction.to.Evolutionary.Computation..—.2nd.ed..—.Springer,.
2015.

---

158
Глава 5.
Генетические алгоритмы
Одна.из.самых.известных.задач.в.области.компьютерных.наук.—.это.задача.
коммивояжера,.к.которой.мы.еще.вернемся.в.главе.9..Коммивояжер.желает.
найти.по.карте.кратчайший.маршрут,.чтобы.посетить.каждый.город.ровно.один.
раз.и.вернуться.в.исходную.точку..Эта.формулировка.может.напомнить.о.ми-
нимальных.связующих.деревьях.из.главы.4,.но.в.действительности.это.не.так..
Решение.задачи.коммивояжера.представляет.собой.гигантский.цикл,.который.
сводит.к.минимуму.затраты.на.его.прохождение,.тогда.как.минимальное.связу-
ющее.дерево.минимизирует.затраты.на.подключение.каждого.города..Человеку,.
путешествующему.через.минимальное.связующее.дерево.городов,.возможно,.
придется.дважды.посетить.один.и.тот.же.город,.чтобы.добраться.до.каждого.
города..Несмотря.на.то.что.задачи.выглядят.похожими,.не.существует.разумно.
рассчитанного.алгоритма.для.поиска.решения.задачи.коммивояжера.для.про-
извольного.числа.городов..Как.было.показано,.генетические.алгоритмы.находят.
неоптимальные,.но.довольно.хорошие.решения.за.короткий.промежуток.време-
ни..Эта.задача.широко.применяется.для.эффективного.распределения.товаров..
Например,.диспетчеры.грузовых.автомобилей.служб.FedEx.и.UPS.используют.
программное.обеспечение.для.решения.задачи.коммивояжера.в.повседневной.
деятельности..Алгоритмы,.помогающие.решить.эту.задачу,.позволяют.сократить.
расходы.в.самых.разных.отраслях.
В.компьютерном.искусстве.генетические.алгоритмы.иногда.применяются.для.
имитации.фотографий.с.помощью.стохастических.методов..Представьте.себе.
50.многоугольников,.случайным.образом.размещенных.на.экране.и.постепенно.
скручиваемых,.поворачиваемых,.перемещаемых,.изменяющих.размеры.и.цвет.до.
тех.пор,.пока.они.не.будут.как.можно.точнее.соответствовать.фотографии..Ре-
зультат.выглядит.как.работа.художника-абстракциониста.или,.если.задействовать.
более.угловатые.формы,.как.витраж.
Генетические.алгоритмы.—.это.часть.более.широкой.области,.называемой.эво-
люционными.вычислениями..Одной.из.областей.эволюционных.вычислений,.
тесно.связанной.с.генетическими.алгоритмами,.является.
генетическое
.
про-
граммирование
,.при.котором.программы.задействуют.операции.отбора,.крос-
синговера.и.мутации,.чтобы,.изменяя.себя,.найти.неочевидные.решения.задач.
программирования..Генетическое.программирование.—.не.слишком.широко.
используемая.технология,.но.представьте.себе.будущее,.в.котором.программы.
пишут.себя.сами.
Преимущество.генетических.алгоритмов.состоит.в.том,.что.они.легко.поддаются.
распараллеливанию..В.наиболее.очевидной.форме.каждая.популяция.может.быть.
смоделирована.на.отдельном.процессоре..В.более.детализированном.варианте.
для.каждого.индивида.выделяется.особый.поток,.в.котором.он.может.мутировать.
и.участвовать.в.кроссинговере.и.где.вычисляется.его.жизнеспособность..Суще-
ствует.также.множество.промежуточных.возможностей.

---

5.8. Упражнения