15 июня

Два года тому назад я продолжил dz online после существенного перерыва выпуском о дарвинистских методах в программировании. Для тех, кто его не читал и не хочет, напомню кратко, о чём шла речь.

По Дарвину происхождение всего живого на земле - результат эволюции. Эволюция же суть три элемента. Мутации, которые привносят изменчивость в вид, отбор, который уничтожает непригодные особи и плодит пригодные и кроссинговер, который комбинирует варианты сочетаний свойств.

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

Впрочем, не всякая задача по зубам естественному отбору. Нужно выполнить два условия. Первое: нужно, чтобы решение задачи описывалось вектором, чем длинее, тем лучше. Второе - должна быть определена функция от этого вектора, значение которой есть качество особи, то есть степень пригодности особи для решения данной задачи. Точность, с которой функция отзывается на изменение качества особи довольно важна - например, если функция возвращает единицу или ноль (хорошая особь или плохая), то дело не пойдёт.

До сих пор я касался этой темы лишь теоретически. А не так давно упёрся в задачу, которая, как раз, аналитически не решается. (Кстати, именно из-за неё dz online и не выходил так долго. Плюс я до сих пор не нашёл прграммиста и посему вынужден, в кои то веки, программлять сам. Беда просто.)И подумал - а отчего бы не попробовать. Если господа из сассекса нашли решение для задачи распознавания речи, почему мою задачу так же не решить?

Для проверки гипотезы была выбрана тест-задача, заведомо более простая, чем та, которую, собственно, нужно решить. Причина - время счёта. На тест-задаче тысяча поколений при полутысяче особей просчитывается за секунду. Кстати, оказалось, что и этого многовато и нужна задача ещё проще, но не буду забегать вперёд.

Само программирование генетического аглоритма - дело тривиальное, полчаса включая отладку. Сложность не в нём. Сложность - в параметрах алгоритма. Ключевых параметров - пять. Число особей, число мутаций на поколение, число ротаций (о них ниже) на поколение, число смертей/рождений на поколение и число кроссинговеров. На поколение же.

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

У этой задачи есть одно неприятное свойство. Эволюция легко выводит особи, содержащие довольно длинные цепочки нужного вида, но цепочки постоянно "упираются" в край вектора - слева расти нельзя, так как ниже нуля алгоритм не заходит, а справа - некуда. Что делать? Вариантов - три. Разрешить алгоритму заходить "в минус" или за предел длины вектора, плюнуть (будет дольше решать) или сделать то, что сделал я.

Добавить вариант мутации по имени ротация. Обычный циклический сдвиг компонент вектора в случайном направлении. Отметим, в случайном! То есть знание структуры задачи использовано по минимуму. Я мог бы проверять, с какой стороны последовательности не хватает места и делать ротацию в нужном направлении, но счёл это неспортивным - в реальной задаче такой радости не будет. Но там не будет и нехватки "жилплощади" в решении.

Короче, итог первый. Оно работает!

Точнее говоря, на Xeon 500, FreeBSD, gcc -O3 вектор из 20 компонент доводится до решения из 18 последовательных числел за (в среднем) 1500-3000 поколений и 4-8 секунд счёта. К сожалению, мне нужно улучшить и этот результат на порядок... :-(

Но надо сказать, что и этого я достиг вовсе не сразу. Более того, чудо, что вообще достиг - мог бы и бросить на полпути. Потому как первые попытки дали результат вовсе не такой хороший. Точнее - просто никакой. С первого запуска система не работала вообще. Причина была в том, что я выбрал неприемлемо маленький размер популяции - всего 40 особей. Как показали первые эксперименты, на таких популяциях алгоритм не живёт - особи бурно деградируют, и никакие "достижения" не держатся сколь нибудь существенное время. Вот пример работы алгоритма на популяции в 45 особей. Здесь каждая цифра или точка - очередная секунда работы алгоритма. Цифра показывает качество лучшей особи в текущем поколении.

|4|5|4.....|6|4|5|4|6|4|5|6|8|5.|4..|9|11|5|4.|6|5

Вышеприведённая последовательность заняла 100 000 поколений и, как видим, ничего не смогла сделать - качество "4" хоть и выше случайного (обычно случайные особи обладают качеством от 0 до 3), но понятно, что за разумное время мы целевого качества (18) не получим. Кстати сказать, 18 (а не максимальное 20) выбрано не потому, что 20 недостижимо, а просто потому, что мне не хотелось вымерять до единицы все параметры и, более того, хотелось оставить себе запас для их варьирования.

Что интересно в случае с малой популяцией, это то, что она, паче чаяния, таки умеет достигать цели, хотя популяция и деградирует то и дело. Видимо, компоненты выигрышной цепочки генов сохраняются по частям в разных особях и время от времени воссоединяются. По крайней мере, когда я позволил этому варианту алогритма поработать подольше, он с задачей справился. (Естественно, я предположил, что это случайность и повторил ещё пяток раз - решает.) Путь к победе при этом крайне интересен:

|4|5|11.|6|4|6|5.|7|5...|4|7|5|4|5|4|7|12|5|4|3|5|6.|4|5|6|5..|4|5.|6|5..|4|3|11    |18

Но ещё интереснее то, что полное отключение кроссинговера резко, в разы ускоряет работу. Но, увы, результат весьма нестабилен - от двух до двадцати секунд. Но уже увеличение популяции до 100 особей весьма стабилизирует процесс. Всего 2-5 секунд, 10-20 тысяч поколений (при малом размере популяции это не страшно) - и задача решена.

Но есть ощущение, что программа поддаётся и дальнейшей оптимизации. Во-первых, алоритмической. Например, существенно повлияло изменение целевой функции - изначально она отражала лишь абсолютное качество особи, но со временем я добавил в неё некоторую эвристическую оценку приближения особи к идеалу - теперь особь, в которой значения элементов растут (не на единицу, а хоть как) слева направо лучше особи, у которой всё наоборот. Это дало отбору новый импульс, позволив оценивать (а значит - поощрять!) не только реальное, но и потенциальное качество особи.

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

Я рассудил, что подобрать параметры генетического алгоритма - это хорошая задача для генетического же алгоритма. Сказано - сделано. Результат - ноль. Сутки работы обернулись тем же, что и было в начале. Проблема в том, что параметры "объемлющего" генетического алгоритма тоже нужно найти. А это сложно, так как производительность его - примерно сотня поколений в минуту, то есть за рабочий день можно сделать лишь пяток экспериментов. Максимум.