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

156
Глава 5.
Генетические алгоритмы
Всего.лишь.6.байт.по.сравнению.с.первоначальным.порядком.—.экономия.состав-
ляет.примерно.4.%..Можно.сказать,.что.4.%.не.имеют.значения,.но.если.бы.это.был.
гораздо.больший.список,.который.многократно.передавался.бы.по.сети,.то.эконо-
мия.выросла.бы.многократно..Представьте,.что.получилось.бы,.если.бы.это.был.
список.размером.1.Мбайт,.который.передавался.бы.через.интернет.10.000.000.раз..
Если.бы.генетический.алгоритм.мог.оптимизировать.порядок.списка.для.сжатия,.
чтобы.сэкономить.4.%,.то.он.сэкономил.бы.примерно.40.Кбайт.на.каждую.передачу.
и.в.итоге.400.Гбайт.пропускной.способности.для.всех.передач..Это.не.очень.большая.
экономия,.но.она.может.оказаться.значительной.настолько,.что.будет.иметь.смысл.
один.раз.запустить.алгоритм.и.получить.почти.оптимальный.порядок.сжатия.
Однако.подумайте.вот.о.чем:.в.действительности.неизвестно,.нашли.ли.мы.оп-
тимальную.последовательность.для.12.имен,.не.говоря.уже.о.гипотетическом.
списке.размером.1.Мбайт..Как.об.этом.узнать?.Поскольку.мы.не.обладаем.глу-
боким.пониманием.алгоритма.сжатия,.следует.проверить.степень.сжатия.для.
всех.возможных.последовательностей.в.списке..Но.даже.для.списка.всего.лишь.
из.12.пунктов.это.трудновыполнимые.479.001.600.возможных.вариантов.(12!,.где.
знак.!.означает.факториал)..Использование.генетического.алгоритма,.который.
пытается.найти.оптимальный.вариант,.возможно,.будет.более.целесообразным,.
даже.если.мы.не.знаем,.действительно.ли.его.окончательное.решение.оптимально.
5.6. ПРОБЛЕМЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
Генетические.алгоритмы.—.это.не.панацея..В.сущности,.для.большинства.задач.
они.не.подходят..Для.любой.задачи,.для.которой.существует.быстрый.детерми-
нированный.алгоритм,.подход.с.использованием.генетического.алгоритма.не.
имеет.смысла..Стохастическая.природа.генетических.алгоритмов.не.позволяет.
предсказать.время.их.выполнения..Чтобы.решить.эту.проблему,.можно.прерывать.
работу.алгоритма.через.определенное.количество.поколений..Но.тогда.остается.
неясным,.было.ли.найдено.действительно.оптимальное.решение.
Стивен.Скиена,.автор.одного.из.самых.популярных.текстов.об.алгоритмах,.даже.
написал.следующее:.
«Я никогда не сталкивался с задачей, для которой генети-
ческие алгоритмы показались бы мне подходящим способом решения. Кроме того, 
мне никогда не встречались вычислительные результаты, полученные с использо-
ванием генетических алгоритмов, которые произвели бы на меня благоприятное 
впечатление»
1
.
Мнение.Скиены.несколько.радикально,.но.оно.свидетельствует.о.том,.что.к.гене-
тическим.алгоритмам.следует.прибегать,.только.когда.вы.совершенно.уверены:.
1
.
Skiena S. 
The.Algorithm.Design.Manual..—.2nd.ed..—.Springer,.2009.

---

5.7. Реальные приложения
157
лучшего.решения.не.существует.—.или.решаете.неизвестную.вам.задачу..Еще.одна.
проблема.генетических.алгоритмов.—.определить,.как.представить.потенциальное.
решение.задачи.в.виде.хромосомы..Традиционная.практика.заключается.в.пред-
ставлении.большинства.задач.в.виде.двоичных.строк.(последовательности.1.и.0,.
необработанные.биты)..Зачастую.это.оптимально.с.точки.зрения.использования.
пространства.и.позволяет.легко.выполнять.функции.кроссинговера..Но.боль-
шинство.сложных.задач.не.так.легко.представить.в.виде.кратных.битовых.строк.
Еще.одна,.более.специфичная.особенность,.на.которую.стоит.обратить.внима-
ние,.—.это.проблемы,.связанные.с.отбором.методом.рулетки,.описанным.ранее..
Отбор.методом.рулетки,.иногда.называемый.
пропорциональным отбором по 
жизнеспособности
,.может.привести.к.отсутствию.разнообразия.в.популяции.из-за.
преобладания.довольно.хорошо.подходящих.особей.при.каждом.отборе..В.то.же.
время,.если.значения.жизнеспособности.близки,.отбор.методом.рулетки.может.
привести.к.отсутствию.давления.отбора
1
..Кроме.того,.этот.метод.не.работает.в.за-
дачах,.в.которых.жизнеспособность.может.принимать.отрицательные.значения,.
как.в.простом.уравнении.в.разделе.5.3.
Короче.говоря,.для.большинства.задач,.достаточно.больших,.чтобы.для.них.стоило.
использовать.генетические.алгоритмы,.последние.не.могут.гарантировать.поиск.
оптимального.решения.за.предсказуемое.время..По.этой.причине.такие.алгорит-
мы.лучше.всего.применять.в.ситуациях,.которые.требуют.найти.не.оптимальное,.
а.лишь.приемлемое.решение..Эти.алгоритмы.довольно.легко.реализовать,.но.на-
стройка.их.параметров.может.потребовать.множества.проб.и.ошибок.