Прошли новогодние праздники и я вспомнил про 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
