Программа поиска алгоритма по тестам

* 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 [аргументы]

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

L — полный перебор до длины L включительно
T — перебор в течении не более T секунд
Q — перебор вероятностный в течении T секунд (должны быть заданы параметры L и Freq)
M — перебор марковский в течении T секунд (должны быть заданы параметры L и Freq)
P — перебор полный до длины L +вероятностный до длины L1 в течении не более T секунд
A — поиск допустимых слов
G — поиск генетический (L,L1,T)

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

Примеры.

Полный перебор всех программ до длины 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.

аргумент, пример	Описание
`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

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

adm0.txt - начальный список допустимых слов.
Freq.csv - таблица попарных частот слов среди частичных программ.
В нулевой строке (после слова NULL) — частота появления слова в начале программы.
В нулевом столбце (перед GOTO) — общая частота появления слова.
result.txt - список частичных программ.
Включает в себя список (Best) наилучшых найденных программ каждой длины и
список (Freq) наиболее частых подстрок каждой длины.

Файл 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  ;
...