TAU-Darwinism: Implementation in Ruby

Foreword

Listen, a crow, and maybe a dog, Maybe a cow, but also good! You have such feathers, you have horns such The hooves are very slender and kind soul.

Cartoon "Plasticine Crow".

In this article I present to your attention the implementation of an evolutionary approach to the identification of a dynamic system. The program is written in Ruby version 1.9.2 (gems: NArray, GNUPlot). Looking under the cat you will find an example of real coding of gene information and a suitable cross-crossing algorithm ("flat crossover").

Introduction

I’ll start by describing the black box task. Suppose we have some object whose transfer function we would like to know (simplified, close or equivalent to real). All we can do is to apply some impact to the input of the object and measure some output parameter (for example, the output voltage). How do we see what is inside the box? In other words: how to determine the approximate mathematical model of the object under study?
In automatic control theory (TAU), this task is called identification. There are various methods of identification, based on serious mathematics and difficult to implement. However, it is possible to obtain an approximate mathematical model in a relatively simple way, namely using a stochastic approach using evolutionary algorithms.
Details you can read in the first article devoted to this issue: TAU-Darwinism , and here I will focus on the software implementation.

Implementation

When writing algorithms, the gga4r library (rubygems.org) is used. This library was rewritten to be operational for compatibility with ruby ​​1.9. The author of this library (thanks to him very much!) Implemented an evolutionary wrapper approach over entities that implement representations of evolving individuals of different content but identical in form. It is proposed to implement your own class implementing genetic operators. I did it like this:

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 

In the example on the site “gga4r” the class of the individual is inherited from Array. I decided to change a little logic and started the additional property "@dna". This was done for the convenience and use of the constructor, in which a digital filter is created for the gain data, the numerator and denominator of the transfer function (in continuous time), as well as the time period of quantization. Also in the constructor, the passed parameters are merged into one one-dimensional array for working with them by means of genetic algorithms. Individual fitness is calculated immediately in the constructor and stored in the corresponding property.
The “flat_crossover” function is implemented by the real crossing mentioned at the very beginning of the article. This is probably the easiest to implement. There are a few more in which several children are implemented (one descendant is generated here) and which I probably have to realize. In this case, the generated child is formed by choosing for each gene a random number in the interval between the values ​​of the genes of the parents.
The mutation operator is implemented as a multiplication of the gene value by a random number in the range [0.0..1.0]. Thus, some of the genes "are attracted" to zero. The selected crossing operator forms mainly individuals with gene values ​​in the middle part of the allowable range of values. The chosen method of mutation plays the role of a counterweight.
The evolutionary algorithm wrapper itself works as described in the previous article TAU-Darwinism : a population is formed, selection is carried out, recombination (crossing), mutation takes place. You can see the insides in the source code of the program (link at the end of the article). It had to be slightly rewritten, as written above, to be used with ruby ​​1.9. But in fact, the library refused to work with me and with version 1.8 on kubuntu 10.10 (I did not figure out why). Anyway, you can compare with the original "gga4r" - a little change. Something has yet to change.
The fitness function is implemented as the standard deviation between the output signal of the test filter and the individual generated by the genes:

 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 

This is slightly different from the problem statement ("a record of the output and entrance of the black box is given; required ..."), but it is more convenient, but the essence is the same.
')

results

Playing with a new pendant In the course of preliminary studies, it was found out that it is most advantageous to set a large population size with a smaller number of iterations. A suitable solution is found rather quickly with a sufficient number of individuals in the population. The task set as follows:

• There is a reference (test) transfer function - numerator: [1.5, 1.0], denominator: [0.75, 0.35, 1.1]
• The gain of the test filter is chosen equal to one (the coefficient of the transfer function when building a discrete filter to it is given in the function SSF :: tf2ssd - the “ssf.rb” module in the source)
• The quantization period is 0.1 sec., For a selected test filter, a quite sufficiently small period
• Population size - 350 at the beginning and 500 maximum
• Number of iterations - 50

It turned out that despite the specified maximum population size exceeded the specified value. After launching, I got the following result:
$ 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
******************************
The first two numbers in the “best Individ” are the numerator of the transfer function, the next three are the denominator, then the scale factor and the quantization period. The best fitness, equal to 32 "parrots" - a fairly good result. In confirmation of the following figure:

It depicts graphs of transient processes of the test and obtained during the evolution of filters when a single step action is applied to the input. “Who” from the “Who” graphs for the time being I can’t say - the functionality for working with gnuplot was not finished, but it doesn’t matter in this case, because to the naked eye, you can see that the results are very close.

Conclusion

The program was implemented in the course of research work on the “U.M.NI.K” program. The code is raw but working (at least for me). Plans to equip the program with some simple GUI for convenience. Below is a link to the code.
UPD1: source is hosted on GitHub.
GitHub Repository