Преимущества генетических алгоритмов

 

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

Недостаток генетических алгоритмов именно в этом же. Проигрыш от их применений состоит в возрастании ресурса, необходимого для получения решения.

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

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

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

Таким образом, мы видим, что критерий оптимальности важнее метода. Генетический алгоритм именно потому имеет право на существование, поскольку так или иначе использует критерий и так или иначе организует движение к экстремуму этого критерия. Не столь важно, как мы будем формировать новые решения, сколь важно, как мы будем выбраковывать плохие решения из получаемой совокупности. Если при формировании новых решений свойства родительских параметров будут сохраняться и приумножаться – этого достаточно для эффективного движения к цели, если это будет не всегда, то с учетом вводимых мутаций количество охватываемых вариантов решений все же растет, и генетический алгоритм может привести к успеху. Если же при объединении родительских генов их полезные свойства попросту разрушаются, то генетический алгоритм не приведет ни к чему хорошему.

Существенно, чтобы вычислительный и временной ресурс был более чем достаточен.

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

Пример с транспьютерными технологиями

 

Транспьютерами называют микропроцессоры, позволяющие строить ЭВМ не по принципу «один ведущий, остальные ведомые», а по принципу «все и ведомые и ведущие». Любой транспьютер должен обладать возможностью контролировать свою исправность и занятость (валентность), а также воспринимать сообщения об исправности и занятости сопряженных с ним транспьютеров. В случае готовности он воспринимает задачу от занятых сопряженных транспьютеров, в случае наличия более одного валентного «соседа» он дробит задачу на более простые и передает эти подзадачи «соседям». В случае отсутствия двух или более валентных соседей транспьютер решает задачу сам и возвращает ее туда, откуда она пришла. Роль транспьютера могут выполнять отдельно стоящие ЭВМ, а роль связующих с ними каналов – компьютерные сети. Таким образом, мы приходим к сетевым технологиям.

Транспьютерные алгоритмы хорошо иллюстрируются в задаче отыскания экстремумов или максимумов по множествам.

Скажем, пусть имеется 64 случайных векторов, и требуется найти самый длинный вектор.

Первый транспьютер в первом цикле разобьет задачу на две подзадачи по 32 вектора и передаст двум соседям. Соседи во втором цикле передадут еще двум парам соседей задачи по 16 векторов. Количество задействованных транспьютеров будет расти по степенному закону, а количество векторов в подзадачах по степенному закону падать. На шестом цикле транспьютер, получивший задачу из двух векторов, решит ее сам, поскольку она далее уже не упрощается, т.е. он даст значение и номер самого длинного вектора из двух. Таким образом, динамика задачи может быть описана таблицей 1.

 

Таблица 1. Динамика решения задачи поиска экстремума 1→2.

Номер цикла	Сложность задачи	Количество решающих транспьютеров	Количество ожидающих транспьютеров

 

При решении задачи на разных этапах в ней будет задействовано от 1 до 127 транспьютеров, вся задача будет решена за 13 циклов. В среднем при решении задачи занято 28,23 транспьютеров, даже если учитывать ожидающие. Традиционный компьютер для решения этой задачи должен осуществить перебор всех 128 векторов, для чего потребуется 128 циклов. При некоторых технологиях во время ожидания ответа транспьютер может быть занят решением других задач. Поэтому, вообще говоря, среднее количество задействованных транспьютеров именно в данной задаче еще почти вдвое меньше – т.е. около 15. При этом для успешного решения по этому алгоритму все же требуется наличие всех 127 транспьютеров на 7-м цикле. Т.е. в среднем задействовано значительно меньше вычислителей (менее четверти), чем необходимо для работоспособности алгоритма, и вместе с тем, если система решает несколько задач, поступающих не синхронно, то пики потребности аппаратного ресурса не должны совпадать (а если они совпадут, то возникнет очередь, что не помешает решить все поставленные задачи). Поэтому в среднем система из 128 транспьютеров может решать одновременно около четырех таких задач, экономя время почти в 10 раз по сравнению с традиционным компьютером.

Членение задачи вовсе не обязательно должно происходить в соотношении 1:2. Скажем, если один транспьютер загружает четыре соседних, то динамика решения той же задачи будет такой, как показано на таблице 2.

 

Таблица 2. Динамика решения задачи поиска экстремума 1→4.

Номер цикла	Сложность задачи	Количество решающих транспьютеров	Количество ожидающих транспьютеров

 

В этом случае задача решается всего за 7 циклов, максимальное значение задействованных транспьютеров 85, среднее количество занятых транспьютеров 19,9, т.е. занятым в среднем оказывается менее четверти ресурса. Рассмотрим ситуацию для членения задачи в соотношении 1:8 (см. таблицу 3).

 

Таблица 3. Динамика решения задачи поиска экстремума 1→8.

Номер цикла	Сложность задачи	Количество решающих транспьютеров	Количество ожидающих транспьютеров

 

В этом случае задача решается всего за 5 циклов, максимальное значение задействованных транспьютеров 73, среднее количество занятых транспьютеров 18,6, т.е. занято опять менее четверти ресурса.

Итак, мы видим, что в последнем случае ресурс по сравнению с простым компьютером возрастает в 73 раза, но в среднем лишь в 19 раз, скорость же вычислений возрастает в 25,6 раза. То есть среднее возрастание ресурса меньше, чем среднее возрастание скорости решения задачи.

Сетевая технология в соединении с принципом динамического программирования теоретически может позволить не только решать шахматную задачу, но в принципе и «закрыть» эту «проблему» раз и навсегда.

Действительно, теоретически количество шахматных позиций большое, но ограниченное. Каждый шахматный этюд – это решение задачи о том, как одному из игроков двигаться к выигрышу или ничьей. Все остальные ходы игрока будут неоптимальными, а все возможные ходы противника не улучшают исхода. Следовательно, всякий решенный этюд – это в каком-то смысле «точка с известным исходом», если считать, что оба игрока знают решение, или, как минимум, точка с гарантированным исходом, если хотя бы один игрок знает решение. Всякая позиция, приводящая к одной из точек с известным исходом, также становится новой точкой с известным исходом. Чем больше будет позиций, выходы из которых будут полностью просчитаны, тем больше шанс, что неизвестные позиции будут с ведены к одной из таких позиций. Движение от простых эндшпилей и этюдов к миттельшпилям, может достичь дебютов, и в идеале останется хотя бы один дебют, гарантированно приводящий к выигрышу. Если так, то шахматы теоретически перестанут быть спортом.

Пока это не достигнуто. Но не так давно считалось, что компьютер в принципе не может выиграть у чемпиона мира, однако сейчас это мнение уже опровергнуто на практике: чемпион мира проигрывал компьютеру.

Из этого видно преимущество сетевых, транспьютерных и нейронных вычислительных систем и наиболее приспособленных к ним алгоритмов программирования – генетических алгоритмов.