Тау-Дарвинизм: Реализация Ruby

Предисловие

Слушай, ворона, а может быть, собака, А может и корова, но это тоже хорошо! У тебя такие перья, у тебя такие рога, Очень стройные копыта и добрая душа.

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

Программа написана на языке Ruby версии 1.9.2 (гемы: NArray, GNUPlot).

Заглянув под кат, вы найдете пример реального кодирования генетической информации и подходящий алгоритм скрещивания («плоский кроссовер»).

Введение

Предположим, у нас есть некий объект, передаточную функцию которого мы хотели бы узнать (упрощенную, близкую или эквивалентную реальной).

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

Как мы можем увидеть, что находится внутри коробки? Другими словами: как определить приближенную математическую модель исследуемого объекта? В теории автоматического управления (ACT) эта задача называется идентификацией.

Существуют разные методы идентификации, основанные на серьезной математике и сложные в реализации.

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

Подробности вы можете прочитать в первой статье по этому вопросу: ТАУ-дарвинизм , и здесь я остановлюсь на программной реализации.

Выполнение

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

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

У меня получилось вот так:

   

 class TFIndivid
     attr_reader :filter, :fitness, :dna, :num_len, :denom_len
     def initialize(num,denom,k=1.0,ts=@@ts)
       @num_len,@denom_len,@filter = num.length,denom.length,SSF::tf2ssd(num, denom, k, ts)
       @fitness = 1/(step_response_deviation(@filter)+@@eps)
       @fitness = 0.0 if @fitness.infinite?
       @dna = num + denom + [k] + [ts]
       self
     end
     def integrity_ok?(dna)
       return dna.length == @num_len + @denom_len + 2
     end
     def TFIndivid.flat_crossover(par1, par2)
       r = Random.new
       child = []
       par1.size.times { |i|
         if par1[i]>par2[i]
           child << r.rand(par2[i].

par1[i])
         else
           child << r.rand(par1[i].

par2[i])
         end
       }
       child
     end
     def recombine(other)
       child = TFIndivid::flat_crossover(self.dna, other.dna)
       res = self.integrity_ok?(child) ? TFIndivid.new(child[0.@num_len-1], child[@num_len.-3], child[-2], child[-1]) : []
       [res]
     end
     def mutate
       rnd = Random.new
       mutate_point = rnd.rand(@dna.size-1)
       @dna[mutate_point] *= rnd.rand(1.0)
     end
 end

   

Это сделано для удобства и использования конструктора, в котором создан цифровой фильтр для данных усиления, числителя и знаменателя передаточной функции (в непрерывном времени), а также периода квантования по времени.

Также в конструкторе передаваемые параметры объединяются в один одномерный массив для работы с ними с помощью генетических алгоритмов.

Приспособленность особи рассчитывается сразу в конструкторе и сохраняется в соответствующем свойстве.

Функция Flat_crossover реализует настоящее пересечение, упомянутое в самом начале статьи.

Вероятно, это самая простая реализация.

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

В этом случае сгенерированный ребенок формируется путем выбора случайного числа для каждого гена в интервале между значениями генов родителей.

Оператор мутации реализован как умножение значения гена на случайное число в диапазоне [0.0.1.0].

Таким образом, часть генов «притягивается» к нулю.

Выбранный оператор скрещивания производит преимущественно особей со значениями генов в средней части допустимого диапазона значений.

Выбранный метод мутации играет роль противовеса.

Сама оболочка эволюционного алгоритма работает так, как описано в предыдущей статье.

ТАУ-дарвинизм : формируется популяция, осуществляется отбор, рекомбинация (скрещивание), мутация.

Внутреннее устройство вы можете увидеть в исходном коде программы (ссылка в конце статьи).

Его пришлось немного переписать, как написано выше, чтобы можно было использовать его с Ruby 1.9. Но на самом деле у меня библиотека отказалась работать даже с версией 1.8 на кубунту 10.10 (почему так и не выяснил).

Как бы то ни было, сравнить его с оригинальным «гга4р» можно — изменений немного.

Некоторые вещи все еще необходимо изменить.

Фитнес-функция реализована как стандартное отклонение между выходным сигналом тестового фильтра и сигналом, генерируемым генами особи:

def step_response_deviation(filter) x, test_y,y = step_response(filter) av_err = 0.0 100.times {|i| err = test_y[i] - y[i] av_err += err*err } Math.sqrt(av_err / 99) end def step_response(filter) @@test_filter.reset filter.reset x = []; 100.times { |i| x << i*@@ts } test_y,y = [],[] 100.times { test_y << @@test_filter.step(@@test_input) y << filter.step(@@test_input) } return x,test_y,y end

Это немного отличается от постановки задачи («дана запись о выходе и входе черного ящика; требуется…»), но удобнее, а суть та же.

Результаты

Подходящее решение находится достаточно быстро, если в популяции имеется достаточное количество особей.

Я поставил задачу так:

• Имеется эталонная (тестовая) передаточная функция — числитель: [1,5, 1,0], знаменатель: [0,75, 0,35, 1,1]
• Коэффициент усиления тестового фильтра был выбран равным единице (коэффициент передаточной функции при построении для него дискретного фильтра задан в функции SSF::tf2ssd - модуль «ssf.rb» в исходном коде)
• Период квантования 0,1 сек, для выбранного тестового фильтра период достаточно короткий.

• Численность населения - 350 в начале и 500 максимум.

• Количество итераций - 50

После запуска получил следующий результат:

$ ruby1.9.1 main.rb Iteration: 1 Population size: 387 best Individ: [ 1.552605923140199 1.8418549861379885 4.4154048910142265 5.556332886121151 5.320061971918478 1.6334223860651258 0.1 ] best fitness: 2.6508867715774027 mean fitness: 1.1722382322077871 mean fitness recalc 1.1722382322077871 ****************************** Iteration: 2 Population size: 421 best Individ: [ 0.37594352736713244 0.41988779230454 6.092873656120998 3.575618643442387 8.786369744495486 1.3186424599689655 0.1 ] best fitness: 2.9780762386062767 mean fitness: 1.381001802845182 mean fitness recalc 1.381001802845182 ****************************** Iteration: 3 Population size: 456 best Individ: [ 5.355702236617921 2.9021864520499134 3.979973441887163 1.1587534831116912 5.818934614234973 0.6934218845420625 0.1 ] best fitness: 4.008150118088937 mean fitness: 1.6192001539010286 mean fitness recalc 1.6192001539010286 ****************************** Iteration: 4 Population size: 501 best Individ: [ 6.981596537433821 7.0034200556235495 6.592795290155172 3.1179936580946577 7.236199584387684 1.4664747534746492 0.1 ] best fitness: 4.629268673426835 mean fitness: 1.8244067682429481 mean fitness recalc 1.8244067682429481 ****************************** Iteration: 5 Population size: 537 best Individ: [ 5.917012124258587 6.182284010197045 5.214809836688884 3.9333556599339055 8.349166334410114 1.544147649767568 0.1 ] best fitness: 4.900537478511452 mean fitness: 2.024810983956715 mean fitness recalc 2.024810983956715 ****************************** Iteration: 6 Population size: 551 best Individ: [ 5.917012124258587 6.182284010197045 5.214809836688884 3.9333556599339055 8.349166334410114 1.544147649767568 0.1 ] best fitness: 4.900537478511452 mean fitness: 2.3489882909253152 mean fitness recalc 2.3489882909253152 ****************************** Iteration: 7 Population size: 540 best Individ: [ 7.667944581517669 7.685145812466274 3.6039889820553768 2.4390348703480536 5.087422184655714 1.4689450977845646 0.1 ] best fitness: 8.166839319133336 mean fitness: 2.652950357867813 mean fitness recalc 2.652950357867813 ****************************** Iteration: 8 Population size: 552 best Individ: [ 7.667944581517669 7.685145812466274 3.6039889820553768 2.4390348703480536 5.087422184655714 1.4689450977845646 0.1 ] best fitness: 8.166839319133336 mean fitness: 2.9467084852969725 mean fitness recalc 2.9467084852969725 ****************************** Iteration: 9 Population size: 553 best Individ: [ 5.7806312313223485 4.681216450534634 5.384196754050039 3.0234885021495357 7.238140602489246 1.1815749271908358 0.1 ] best fitness: 9.966075154360498 mean fitness: 3.335389533280396 mean fitness recalc 3.335389533280396 ****************************** Iteration: 10 Population size: 543 best Individ: [ 5.7806312313223485 4.681216450534634 5.384196754050039 3.0234885021495357 7.238140602489246 1.1815749271908358 0.1 ] best fitness: 9.966075154360498 mean fitness: 3.818330258524996 mean fitness recalc 3.818330258524996 ****************************** Iteration: 11 Population size: 555 best Individ: [ 5.7806312313223485 4.681216450534634 5.384196754050039 3.0234885021495357 7.238140602489246 1.1815749271908358 0.1 ] best fitness: 9.966075154360498 mean fitness: 4.241020711174743 mean fitness recalc 4.241020711174743 ****************************** Iteration: 12 Population size: 563 best Individ: [ 7.114438733870453 5.7051128886012386 3.8495059720675098 1.8164317233081309 5.543227442940334 1.1352374472380862 0.1 ] best fitness: 11.644557896655645 mean fitness: 4.980294253355436 mean fitness recalc 4.980294253355436 ****************************** .

****************************** Iteration: 23 Population size: 542 best Individ: [ 5.949029964618817 4.681516090696933 4.8007731550065325 2.562344672524173 6.969591955243219 1.1684490266387202 0.1 ] best fitness: 20.468430876331446 mean fitness: 11.25191007878279 mean fitness recalc 11.25191007878279 ****************************** .

****************************** Iteration: 36 Population size: 550 best Individ: [ 6.304563716617802 4.937028188768713 5.01636959411469 2.5019167234335344 7.143946485486306 1.1690443373254094 0.1 ] best fitness: 30.361894930102864 mean fitness: 22.65217005076974 mean fitness recalc 22.65217005076974 ****************************** .

****************************** Iteration: 46 Population size: 542 best Individ: [ 6.548169493382168 5.060607979367818 4.739775170940725 2.3444848651883947 6.741642980854007 1.1564890916088506 0.1 ] best fitness: 32.826565607333514 mean fitness: 25.606090666108418 mean fitness recalc 25.606090666108418 ****************************** Iteration: 47 Population size: 550 best Individ: [ 6.548169493382168 5.060607979367818 4.739775170940725 2.3444848651883947 6.741642980854007 1.1564890916088506 0.1 ] best fitness: 32.826565607333514 mean fitness: 25.489911664932283 mean fitness recalc 25.489911664932283 ****************************** Iteration: 48 Population size: 561 best Individ: [ 6.548169493382168 5.060607979367818 4.739775170940725 2.3444848651883947 6.741642980854007 1.1564890916088506 0.1 ] best fitness: 32.826565607333514 mean fitness: 25.44926190395142 mean fitness recalc 25.44926190395142 ****************************** Iteration: 49 Population size: 550 best Individ: [ 3.1439340250602816 5.060607979367818 4.739775170940725 2.3444848651883947 6.741642980854007 1.1564890916088506 0.1 ] best fitness: 32.826565607333514 mean fitness: 26.108921277427932 mean fitness recalc 26.108921277427932 ****************************** Iteration: 50 Population size: 559 best Individ: [ 3.1439340250602816 5.060607979367818 4.739775170940725 2.3444848651883947 6.741642980854007 1.1564890916088506 0.1 ] best fitness: 32.826565607333514 mean fitness: 26.23635084771665 mean fitness recalc 26.23635084771665 ******************************

Первые два числа в «лучшем индивидууме» — это числитель передаточной функции, следующие три — знаменатель, затем масштабный коэффициент и период квантования.

Лучший фитнес, равный 32 «попугаям», — это достаточно хороший результат. Следующий рисунок иллюстрирует это:



На нем показаны графики переходных процессов тестового фильтра и полученного в ходе эволюции фильтров при подаче на вход одноступенчатого воздействия.

"Кто" из графиков "Кто" пока сказать не могу - я не доработал функционал для работы с gnuplot, но в данном случае это не имеет значения, т.к.

невооруженным глазом видно, что результаты очень близки .

Заключение

М.

Н.

ИК.

Код сыроват, но работает (по крайней мере у меня).

Для удобства планируется оснастить программу простым графическим интерфейсом.

Ниже приведена ссылка на код. УПД1: исходники размещены на GitHub. Репозиторий на GitHub Теги: #генетические алгоритмы #скрещивание #реализация #ruby #narray #gnuplot #TAU #ruby

• Амстердам

  19 Oct, 24

• Как Verizon И Bgp Optimizer Добились Успеха В Автономном Режиме

  19 Oct, 24

• Вредный Совет: Как Написать В Техподдержку

  19 Oct, 24

• Мне Хотелось Красивое Железо. Случилось

  19 Oct, 24

• Нанимать Сотрудников Нехорошо. И Твой Тоже

  19 Oct, 24

• Достойный Конец: Разработчики Уничтожили Мир Игры Planetside Метеоритной Бомбардировкой

  19 Oct, 24

• Кто Такие Радиолюбители Коротковолнового Диапазона?

  19 Oct, 24

• Организация Платежей Через Интернет С Использованием Банковских Карт

  19 Oct, 24

• Вебинар Крикета Ли — (Со)Автора Книг О Dns И Bind. Безопасность Dns: Угрозы И Решения, Лучшие Практики

  19 Oct, 24

• Активные Кнопки На Сайте

  19 Oct, 24