mutator

mutator - это моя реализация решения задачи генерации программы на основе генетического алгоритма.

StackLang

Для реализации простой логики, разработан маленький язык StackLang, который состоит из небольшого набора команд:

• push - положить число 0 в стек
• pop - вытолкнуть число из стека
• neg - вытолкнуть число из стека, умножить его на -1 и положить результат в стек
• xor - сложить два числа на вершине стека по модулю 2, и положить результат в стек
• add - сложить два числа на вершине стека, и положить результат в стек
• xorp - xor, но выталкиваем аргументы из стека
• addp - add, но выталкиваем аргументы из стека
• shlp - логический сдвиг влево числа на вершине стека
• shrp - логический сдвиг вправо числа на вершине стека
• inc - увеличить число на вершине стека на 1
• dec - уменьшить число на вершине стека на 1
• swap - обменять местами два числа на вершине стека
• copy - скопировать число на вершине стека и положить его в стек

Интерпретатор языка StackLang получает на вход начальное состояние стека и набор команд (программу), а при выполнении возвращает финальное состояние стека.

Генетический алгоритм

Генетический алгоритм используется для оценки наиболее точно выполняющих задачу программ на языке StackLang. Отбираются наиболее точные программы, которые в дальнейшем мутируются одним из следуюших способов:

1. Добавление новой команды в программу
2. Удаление команды из программы
3. Замена команды на другую
4. Смена порядка команд в программе

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

Оценка программы

Оценка работы программы оценивается по нескольким критериям

1. Наиболее важным критерием является наличие ошибок при выполнении программы. Если программа не выполняется, то она считается неудачной и не участвует в дальнейшем процессе генерации.
2. Расхождение между требуемым конечным состоянием стека и полученным. Чем меньше расхождение, тем лучше.
3. Количество команд в программе. Чем меньше команд, тем лучше.
4. Разность между размером стека в начале и в конце программы. Чем меньше разность, тем лучше. Используется в ходе отбора программ для приближения программы к требуемому конечному состоянию стека.

Запуск

Для запуска программы необходимо выполнить команду python3 main.py в корневой директории проекта и указать через запятую искомое финальное состояние стека, например python3 main.py 1,2,3 Помимо этого, можно указать следующие параметры:

• --start - начальное состояние стека, по умолчанию пустой стек
• --iter - максимальное количество итераций генетического алгоритма, по умолчанию 1000
• --take - количество программ, которые будут отобраны для мутации, по умолчанию 10
• --step - количество шагов, после которых будет происходить вывод промежуточных результатов, по умолчанию 100
• -e или --exec - выполнить программу, полученную в результате работы генетического алгоритма
• -v или --verbose - выводить промежуточные результаты во время работы генетического алгоритма

Проблемы

Из-за малой изменчивости при каждой мутации, генетическому алгоритму трудно находить решения, использующие последовательность из нескольких команд для достижения результата. Это приводит к тому, что часто возникают решения из, например, повторяющихся команд inc для получения нужного числа. Однако введение команды сдвига влево позволило улучшить ситуацию, позволив создавать более короткие и более изменчивые программы. Тем не менее, так как основной штраф приходится на сумму квадратов ошибок, то для относительно больших (>5) чисел в стеке, полученная в ходе отбора команда будет вычислять требуемый стек неточно, оставляя небольшую разницу в 1-2 единицы. Данная проблема частично решается за счёт усиления ошибки, даже если отклонение незначительно. Например, если программа вычисляет [..., 5, ...], а требуется [..., 6, ...], то ошибка будет составлять не 1, а 5 (в целом, ошибка равна max(err, 5)), что позволяет сильнее наказывать программу за неверный результат.

Примеры

Команда: python3 .\main.py 10,20,30 --start=40 -e

Результат:

Running genetic algorithm with parameters:
Start stack: [40]
Target stack: [10, 20, 30]
Number of iterations: 1000
Number of programs to take: 10
Number of iterations between output: 100
Best program: ['shrp', 'copy', 'shrp', 'swap', 'xor']
Best result: [10, 20, 30]
When expected: [10, 20, 30]
Error: 0
Distance: 0
Length: 5
Diff: 0
Total score: 40
Executing best program:
Start stack: [40]
shrp: [20]
copy: [20, 20]
shrp: [20, 10]
swap: [10, 20]
xor: [10, 20, 30]

Команда: python3 .\main.py 100 --start=20,13 -e

Результат:

Running genetic algorithm with parameters:
Start stack: [20, 13]
Target stack: [100]
Length: 3
Diff: 0
Total score: 24
Executing best program:
Start stack: [20, 13]
xorp: [25]
shlp: [50]
shlp: [100]

Команда: python3 .\main.py 0,1,1,2,3,5,8,13,21 --iter=1000 --step=100 -v -e

Результат:

Running genetic algorithm with parameters:
Start stack: [0]
Target stack: [0, 1, 1, 2, 3, 5, 8, 13, 21]
Number of iterations: 1000
Number of programs to take: 10
Number of iterations between output: 100
Iteration 0, best score: 10000000000000000
Iteration 100, best score: 11432
Iteration 200, best score: 11432
Iteration 300, best score: 11432
Iteration 400, best score: 11432
Iteration 500, best score: 26
Iteration 600, best score: 22
Iteration 700, best score: 22
Iteration 800, best score: 22
Iteration 900, best score: 22
Best program: ['copy', 'inc', 'push', 'inc', 'copy', 'shlp', 'xor', 'add', 'add', 'add', 'add']
Best result: [0, 1, 1, 2, 3, 5, 8, 13, 21]
When expected: [0, 1, 1, 2, 3, 5, 8, 13, 21]
Error: 0
Distance: 0
Length: 11
Diff: 0
Total score: 22
Executing best program:
Start stack: [0]
copy: [0, 0]
inc: [0, 1]
push: [0, 1, 0]
inc: [0, 1, 1]
copy: [0, 1, 1, 1]
shlp: [0, 1, 1, 2]
xor: [0, 1, 1, 2, 3]
add: [0, 1, 1, 2, 3, 5]
add: [0, 1, 1, 2, 3, 5, 8]
add: [0, 1, 1, 2, 3, 5, 8, 13]
add: [0, 1, 1, 2, 3, 5, 8, 13, 21]

Команда: python3 .\main.py 4 --start=17

Результат:

Running genetic algorithm with parameters:
Start stack: [17]
Target stack: [4]
Number of iterations: 1000
Number of programs to take: 10
Number of iterations between output: 100
Best program: ['shrp', 'shrp']
Best result: [4]
When expected: [4]
Error: 0
Distance: 0
Length: 2
Diff: 0
Total score: 4

Идеи для улучшения

• Добавить многопоточную обработку для ускорения работы при большом количестве программ в поколении
• Добавить возможность условного выполнения/повторения, что позволит писать программы, работающие по разному, в зависимости от входных данных
• Добавить более глубокие мутации с внесением нескольких изменений за раз