Прошли новогодние праздники и я вспомнил про BrainFuck. Писать свой морской бой желания не было, а хотелось как в сказке «Ну ка, проги, пишитесь сами!».Основой послужила статья «Hello world!» с помощью генетических алгоритмов. Поэтому я сразу перейду к решению следующей задачи: написать программу, которая будет писать программы с помощью генетического алгоритма на BrainFuck, выводящую заданную строку. Реализовать её на Java.
Для начала потребуется интерпретатор BF кода, не будем изобретать велосипед, воспользуемся библиотекой BFI * Copyright © 2003 Thomas Cort. Для экспериментов я добавил ей возможность выполняться отдельным потоком.
Класс для описания программы:
class Individ implements Comparable
{
//текст программы
String data;
//как близко программа приблизилась к цели
double fitness;
//критерий по которому будем сортировать.
//Программы с меньшим значением fitness "живучие"
public int compareTo(Object o)
}
Теперь возьмёмся за написание генетического алгоритма. Этапы алгоритма показаны на рисунке:
Первое это формирование популяции, её получим случайным расположением операндов из словаря языка BF.
За скрещивание отвечает функция reproduction, она берёт две случайные особи разбивает на две части и склеивает попарно получившиеся половинки и так для всей популяции.
Реализовано три вида мутаций:
1) замена одного операнда на другой;
2) добавление в случайную позицию операнда;
3) добавление цикла.
Третий пункт введён т.к. цикл состоит из "[" и "]" и если добавлять по одной, то программа будет не корректной.
Самой сложной функцией является подсчёт пригодности особи. Значение пригодности показывает на сколько результат работы программы отклонился от искомого значения.
Первое что пришло в голову это считать сумму разности символов в строке, например, abc — aaa = 3, но при таком подходе генетический алгоритм быстро находит точку локального экстремума и дальше зацикливается.
Посмотрим на примере. Мы хотим получить строку «abb» а программа:
+++++++[<++++++++++++++>-]<…
выводит «bbb» пригодность такой программы 1. Что бы получить на первой позиции получить «a» нам необходимо поставить "-" после цикла:
+++++++[<++++++++++++++>-]-<…
эта программа уже выводит «aaa», но пригодность её стала 2, что хуже и такая «особь погибает».
Поэтому пригодность будем считать в зависимости от положения символа, на примере abc — aaa = |a — a| * 100^3 + |b — a| * 100^2 + |c — a| * 100^1 = 100200. Благодаря такому подходу символ расположенный левее имеет больший приоритет.
В качестве селекции выступает простая сортировка по убыванию значения пригодности.
И пока не получим программу будем размножать и мутировать.
А вот и результат работы программы, для строки «Hello»:
449-ое поколение
Длина программы: 236 симв. Текст программы: ++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++-+++++++++++++++++++.++-++++++..+++.>
Исходный код на code.google.com
Зеркало на ifolder