* Exe for search Fort-programs by tests using genetic methods in russian (this file)
* Exe for search Fort-programs by tests using genetic methods in english
* List of available test files

Программа поиска Fort-программы по тестам

Программа gen_03.exe предназначена для поиска программы на языке Fort, реализующий алгоритм заданный с помощью тестового файла вида:
#T SHIFTR_0 x,y →  x*2^y  комментарий
<in> 9   3 </in><out>  1536 </out> 
<in> 4   3 </in><out>    48 </out> 
<in> 2   7 </in><out>    28 </out> 
<in> 3   3 </in><out>    24 </out> 
<in> 6   5 </in><out>   320 </out> 
<in> 2   5 </in><out>    20 </out> 
<in> 7   5 </in><out>   640 </out> 
...
Подробнее об используемом языке и применяемых методах можно прочитать в статье "Генетические алгоритмы" в arxiv.org.
 
gen_03.exe command [аргументы]

Возможные команды:

Аргументы могут идти в любом порядке.

Примеры.

Полный перебор всех программ до длины 8 включительно (если параметр test не указан, считается равным test.tst):

  gene_03 L test=poly1.tst L=8
Результаты остаются в файле result.txt, Freq.csv. Если решение надено, оно ДОПИСЫВАЕТСЯ в файл Ok.txt.

Полный перебор всех программ до длины 8 включительно со списком допустимых слов admit2.adm.:

  gene_03 L test=poly1.tst L=8 admit=admit2.adm

Полный перебор всех программ не дольше T секунд (если перебор программ длины n не укладывается в T секунд, то он и не начинается):
  gene_03 T test=poly1.tst T=100

Вероятностный перебор программ длины 12 с таблицей частот из файла Freq02.csv. Файлы такой структуры получаются после работы с командами L, T, P, A:
  gene_03 Q test=poly1.tst L=12 Freq=Freq02.csv

Марковский перебор программ длины 12 с таблицей частот из файла Freq02.csv. Файлы такой структуры получаются после работы с командами L, T, P, A:
  gene_03 M test=poly1.tst L=12 Freq=Freq02.csv

Полный перебор до длины L а затем вероятностный/Марковский до длины L1 в течении не более T секунд:
  gene_03 P test=poly1.tst L=8 L1=16 T=400
Результаты остаются в файлах result*.txt, Freq*.csv. Если решение надено, оно ДОПИСЫВАЕТСЯ в файл Ok.txt.

Поиск допустимых слов:

  gene_03 A test=poly1.tst
Найденные слова вместе с дополнительной информацией записываются в файл adm_find.adm. Для дальнейшей работы в этом файле надо оставить только последнюю строку.
поиск генетический (L,L1,T)
  gene_03 G test=poly1.tst L=8 L1=16 T=400 admit=am0.adm
Результаты остаются в файлах result*.txt, Freq*.csv. Если решение надено, оно ДОПИСЫВАЕТСЯ в файл Ok.txt.

Аргументы могут идти в любом порядке. Вот их список:
аргумент, пример Описание
test=test000.tst Указать тестовый файл. Если параметр test не указан, считается равным test.tst.
Len=12 или L=12Указать длину (нужна в командах SearchQ, SearchM)
L1=14Другая длина (команда searchP)
Freq=ProbB1.csw Указать файл с таблицей частот(нужна в командах SearchQ, SearchM).
Файлы требуемого вида (ProbA.csv, ProbB.csv) создаются после работы командами SearchL, SearchT, SearchP.
Обратить внимание на список слов. Список слов, с которыми построен файл должен совпадать с текущим списком слов.
admit=adm01.adm Список дополнительных и допустимых слов.
Если параметр admit не указан, считается что дополнительных слов нет и все имеющиеся слова допустимы. Пример:
: F01 DUP -- ;
IF CONST  DUP  DROP  SWAP OVER ROT -ROT + - * =0 -- F01
или
: F01 DUP -- ;
: F02 DUP -- * DUP  ;
IF CONST  DUP  DROP  SWAP OVER ROT -ROT  *  ++ -- F01 F02
При вероятностном поиске список допустимых слов не нужен, всё определяется таблицей частот. Но файл всё равно может потребоваться, если используются дополнительные слова.
stSize=8Размер Fort-стека для искомых программ. По умолчанию stSize=16.
maxTm=8Максимальное время выполнения искомой программы в командах. По умолчанию maxTm=80.
nPart=100Количество частичных программ. По умолчанию nPart=400.
Kind=1Использование условных переходов в программе:
  • Kind=1 - нет переходов,
  • Kind=2 - обязательно есть,
  • Kind=3 - обязательно есть переход назад,
  • Kind=0 - всё равно, могут быть, а могут и нет.
По умолчанию Kind=0.

При выполнении команды SearchA (поиск допустимых слов) результаты поиска пишутся в файл prot.txt вида:

gen:admFind, ищем допустимые слова для теста SHIFTR_0
gen:admFind, Результат полного перебора до длины 8 в файлах result01.txt, Freq00.csv.
Далее - случайные поиск с длиной от 7 до 14
gen:admFind, Частоты слов получились такие:
GOTO IF CONST DUP DROP SWAP OVER ROT -ROT PICK 2PICK 3PICK 4PICK ROLL 3ROLL 4ROLL NEG + - * / % %/ AND OR XOR > < = 0= 0> 0< ++ -- 
  64 915 218 751  194  544  671  200 162  38  38 38  38 38 38 40 38 439 630 333  38  42 38 38 38 38 38 38 78 42 38 40 44 42 
Допустимые слова:
  1   2   3   4   5   6   7   8   9  18  19  20  29 
GOTO IF CONST DUP DROP SWAP OVER ROT -ROT + - * = 

Пример запуска:

gen_03.exe SearchP 800  admit=adm_ff.adm test=..\tests\FACTORIAL_0.tst  Kind=3

После работы программ оставляет в текущем каталоге файлы:

Файл result.txt содержит более подробную информацию:
max.tests: 3, mid per 1 mill.:  681.90
Histogramm:
  0: 1090240739
  1:     405654
  2:     169059
  3:         20

Executed tests:
  N  number of execut.
  0:          0
  1:          0
  2:     493800
  3:     223540
  4:      19963
  5:       5677
  6:        742
  7:         95
  8:         15
  9:          0
 10:          0

The best programs:
Length, number of tests, program
Best( 2,  2)  ++ --  ;
Best( 3,  2)  -- >0 ++  ;
Best( 4,  2)  ++ ++ -- --  ;
Best( 5,  2)  CONST -2 - -- --  ;
Best( 6,  3)  DUP -- * DUP =0 XOR  ;

Most frequent substrings:
Freq= 39,L= 2:  =0 OR  ;
Freq= 39,L= 2:  =0 XOR  ;
Freq= 36,L= 2:  <0 OR  ;
Freq= 37,L= 2:  <0 XOR  ;
Freq=  4,L= 3:  CONST 12 /%  ;
Freq=  4,L= 3:  CONST 12 =0  ;
Freq=  4,L= 3:  CONST 12 <0  ;
Freq=  4,L= 3:  DUP -- DUP  ;
Freq=  4,L= 3:  DUP -- *  ;
Freq=  5,L= 3:  OVER % ++  ;
Freq=  5,L= 3:  % ++ *  ;
Freq=  3,L= 4:  DUP -- DUP =0  ;
Freq=  3,L= 4:  DUP -- * DUP  ;
Freq=  5,L= 4:  OVER % ++ *  ;
Freq=  3,L= 4:  -- * DUP =0  ;
Freq=  3,L= 5:  DUP -- * DUP =0  ;

Words freq:
  1 GOTO             248
  2 IF               494
  3 CONST            314
  4 DUP              453
  5 DROP             125
  6 SWAP             168
  7 OVER             126
 ...

Partial programs and the number of tests for each of them:
   2:  ++ --  ;
   2:  -- ++  ;
   2:  DUP XOR  ;
   2:  DUP AND  ;
   2:  NEG NEG  ;
   2:  DUP DROP  ;
   2:  -- >0 ++  ;
   2:  DUP <0 XOR  ;
   2:  DUP =0 XOR  ;
...