Vast quantities of filthy, filthy evolution code.

Also, bugs and crashes.


git-svn-id: http://svn.drobilla.net/lad/machina@961 a436a847-0d15-0410-975c-d299462d15a1

9 files changed, 423 insertions, 57 deletions

diff --git a/src/engine/Evolver.cpp b/src/engine/Evolver.cpp
index e509d97..507b4b8 100644
--- a/src/engine/Evolver.cpp
+++ b/src/engine/Evolver.cpp
@@ -32,28 +32,31 @@ namespace Machina {
 
 Evolver::Evolver(const string& target_midi, SharedPtr<Machine> seed)
 	: _problem(new Problem(target_midi, seed))
-	, _active_fitness(-FLT_MAX)
+	, _seed_fitness(-FLT_MAX)
 {	
 	SharedPtr<Eugene::HybridMutation<Machine> > m(new HybridMutation<Machine>());
 	
-	m->append_mutation(1/7.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
+	m->append_mutation(1/6.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
 			new Mutation::Compress()));
-	m->append_mutation(1/7.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
+	m->append_mutation(1/6.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
 			new Mutation::AddNode()));
-	m->append_mutation(1/7.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
-			new Mutation::RemoveNode()));
-	m->append_mutation(1/7.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
-			new Mutation::AdjustNode()));
-	m->append_mutation(1/7.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
+	//m->append_mutation(1/6.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
+	//		new Mutation::RemoveNode()));
+	//m->append_mutation(1/6.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
+	//		new Mutation::AdjustNode()));
+	m->append_mutation(1/6.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
+			new Mutation::SwapNodes()));
+	m->append_mutation(1/6.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
 			new Mutation::AddEdge()));
-	m->append_mutation(1/7.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
+	m->append_mutation(1/6.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
 			new Mutation::RemoveEdge()));
-	m->append_mutation(1/7.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
+	m->append_mutation(1/6.0f, boost::shared_ptr< Eugene::Mutation<Machine> >(
 			new Mutation::AdjustEdge()));
 
 	boost::shared_ptr< Selection<Machine> > s(new TournamentSelection<Machine>(_problem, 3, 0.8));
 	boost::shared_ptr< Crossover<Machine> > crossover;
-	_ga = SharedPtr<MachinaGA>(new MachinaGA(_problem, s, crossover, m, 10, 10, 2, 1.0, 0.0));
+	_ga = SharedPtr<MachinaGA>(new MachinaGA(_problem, s, crossover, m,
+				20, 20, 2, 1.0, 0.0));
 }
 	
 
@@ -63,7 +66,7 @@ Evolver::seed(SharedPtr<Machine> parent)
 	/*_best = SharedPtr<Machine>(new Machine(*parent.get()));
 	_best_fitness = _problem->fitness(*_best.get());*/
 	_problem->seed(parent);
-	_active_fitness = _problem->fitness(*parent.get());
+	_seed_fitness = _problem->fitness(*parent.get());
 }
 	
 
@@ -72,18 +75,31 @@ Evolver::_run()
 {
 	float old_best = _ga->best_fitness();
 
+	//cout << "ORIGINAL BEST: " << _ga->best_fitness() << endl;
+
+	_improvement = true;
+
 	while (!_exit_flag) {
-		cout << "{";
+		//cout << "{" << endl;
+		_problem->clear_fitness_cache();
 		_ga->iteration();
 
 		float new_best = _ga->best_fitness();
-		if (new_best > old_best) {
+	
+		/*cout << _problem->fitness_less(old_best, *_ga->best().get()) << endl;
+		cout << "best: " << _ga->best().get() << endl;
+		cout << "best fitness: " << _problem->fitness(*_ga->best().get()) << endl;
+		cout << "old best: " << old_best << endl;
+		cout << "new best: " << new_best << endl;*/
+		cout << "generation best: " << new_best << endl;
+
+		if (_problem->fitness_less_than(old_best, new_best)) {
 			_improvement = true;
 			old_best = new_best;
-			cout << "NEW BEST: " << new_best << endl;
+			cout << "*** NEW BEST: " << new_best << endl;
 		}
 		
-		cout << "}" << endl;
+		//cout << "}" << endl;
 	}
 }
 
diff --git a/src/engine/JackDriver.cpp b/src/engine/JackDriver.cpp
index 93145b0..752b372 100644
--- a/src/engine/JackDriver.cpp
+++ b/src/engine/JackDriver.cpp
@@ -100,6 +100,9 @@ JackDriver::detach()
 void
 JackDriver::set_machine(SharedPtr<Machine> machine)
 {
+	if (machine == _machine)
+		return;
+
 	cout << "DRIVER MACHINE: " << machine.get() << endl;
 	SharedPtr<Machine> last_machine = _last_machine; // Keep a reference 
 	_machine_changed.reset(0);
@@ -238,10 +241,10 @@ JackDriver::on_process(jack_nframes_t nframes)
 	/* Take a reference to machine here and use only it during the process
 	 * cycle so _machine can be switched with set_machine during a cycle. */
 	SharedPtr<Machine> machine = _machine;
-	machine->set_sink(shared_from_this());
 
 	// Machine was switched since last cycle, finalize old machine.
 	if (machine != _last_machine) {
+		cout << "MACHINE CHANGED!" << endl;
 		if (_last_machine) {
 			assert(!_last_machine.unique()); // Realtime, can't delete
 			_last_machine->set_sink(shared_from_this());
@@ -251,12 +254,16 @@ JackDriver::on_process(jack_nframes_t nframes)
 		_cycle_time.set_start(0);
 		_machine_changed.post(); // Signal we're done with it
 	}
-
-	if (_recording.get())
-		_record_time += nframes;
 	
-	if (!machine)
+	if (!machine) {
+		_last_machine = machine;
 		return;
+	}
+	
+	machine->set_sink(shared_from_this());
+	
+	if (_recording.get())
+		_record_time += nframes;
 
 	if (_stop.pending())
 		machine->reset(_cycle_time.start_beats());
@@ -302,11 +309,12 @@ JackDriver::on_process(jack_nframes_t nframes)
 		}
 	}
 
+end:
+
 	/* Remember the last machine run, in case a switch happens and
 	 * we need to finalize it next cycle. */
 	_last_machine = machine;
 	
-end:
 	if (_stop.pending()) {
 		_cycle_time.set_start(0);
 		_stop.finish();
diff --git a/src/engine/Mutation.cpp b/src/engine/Mutation.cpp
index 95e31a3..d60ef34 100644
--- a/src/engine/Mutation.cpp
+++ b/src/engine/Mutation.cpp
@@ -53,15 +53,24 @@ AddNode::mutate(Machine& machine)
 
 	// Create random node
 	SharedPtr<Node> node(new Node(1.0));
-	uint8_t note = rand() % 128;
+	node->set_selector(true);
+	
+	SharedPtr<Node> note_node = machine.random_node();
+	uint8_t note = PtrCast<MidiAction>(note_node->enter_action())->event()[1];
+
 	node->set_enter_action(ActionFactory::note_on(note));
 	node->set_exit_action(ActionFactory::note_off(note));
 	machine.add_node(node);
 	
-	// Add as a successor to some other random node
+	// Insert after some node
 	SharedPtr<Node> tail = machine.random_node();
-	if (tail && tail != node)
+	if (tail && tail != node/* && !node->connected_to(tail)*/)
 		tail->add_edge(boost::shared_ptr<Edge>(new Edge(tail, node)));
+	
+	// Insert before some other node
+	SharedPtr<Node> head = machine.random_node();
+	if (head && head != node/* && !head->connected_to(node)*/)
+		node->add_edge(boost::shared_ptr<Edge>(new Edge(node, head)));
 }
 
 
@@ -71,7 +80,8 @@ RemoveNode::mutate(Machine& machine)
 	//cout << "REMOVE NODE" << endl;
 
 	SharedPtr<Node> node = machine.random_node();
-	machine.remove_node(node);
+	if (node && !node->is_initial())
+		machine.remove_node(node);
 }
 
 	
@@ -93,6 +103,34 @@ AdjustNode::mutate(Machine& machine)
 	}
 }
 
+	
+void
+SwapNodes::mutate(Machine& machine)
+{
+	//cout << "SWAP NODE" << endl;
+	
+	if (machine.nodes().size() <= 1)
+		return;
+
+	SharedPtr<Node> a = machine.random_node();
+	SharedPtr<Node> b = machine.random_node();
+	while (b == a)
+		b = machine.random_node();
+
+	SharedPtr<MidiAction> a_enter = PtrCast<MidiAction>(a->enter_action());
+	SharedPtr<MidiAction> a_exit  = PtrCast<MidiAction>(a->exit_action());
+	SharedPtr<MidiAction> b_enter = PtrCast<MidiAction>(b->enter_action());
+	SharedPtr<MidiAction> b_exit  = PtrCast<MidiAction>(b->exit_action());
+
+	uint8_t note_a = a_enter->event()[1];
+	uint8_t note_b = b_enter->event()[1];
+
+	a_enter->event()[1] = note_b;
+	a_exit->event()[1] = note_b;
+	b_enter->event()[1] = note_a;
+	b_exit->event()[1] = note_a;
+}
+
 
 void
 AddEdge::mutate(Machine& machine)
@@ -102,8 +140,11 @@ AddEdge::mutate(Machine& machine)
 	SharedPtr<Node> tail = machine.random_node();
 	SharedPtr<Node> head = machine.random_node();
 
-	if (tail && head && tail != head && !tail->connected_to(head))
+	if (tail && head && tail != head/* && !tail->connected_to(head) && !head->connected_to(tail)*/) {
+		SharedPtr<Edge> edge(new Edge(tail, head));
+		edge->set_probability(rand() / (float)RAND_MAX);
 		tail->add_edge(boost::shared_ptr<Edge>(new Edge(tail, head)));
+	}
 }
 
 
@@ -124,8 +165,10 @@ AdjustEdge::mutate(Machine& machine)
 	//cout << "ADJUST EDGE" << endl;
 
 	SharedPtr<Edge> edge = machine.random_edge();
-	if (edge)
+	if (edge) {
 		edge->set_probability(rand() / (float)RAND_MAX);
+		edge->tail().lock()->edges_changed();
+	}
 }
 
 
diff --git a/src/engine/Node.cpp b/src/engine/Node.cpp
index f965aff..486bc95 100644
--- a/src/engine/Node.cpp
+++ b/src/engine/Node.cpp
@@ -76,18 +76,32 @@ Node::random_edge()
 
 
 void
+Node::edges_changed()
+{
+	if ( ! _is_selector)
+		return;
+
+	// Normalize edge probabilities if we're a selector
+	double prob_sum = 0;
+	
+	for (Edges::iterator i = _edges.begin(); i != _edges.end(); ++i)
+		prob_sum += (*i)->probability();
+
+	for (Edges::iterator i = _edges.begin(); i != _edges.end(); ++i)
+		(*i)->set_probability((*i)->probability() / prob_sum);
+	
+	_changed = true;
+}
+
+
+void
 Node::set_selector(bool yn)
 {
 	_is_selector = yn;
 
-	if (yn) {
-		double prob_sum = 0;
-		for (Edges::iterator i = _edges.begin(); i != _edges.end(); ++i)
-			prob_sum += (*i)->probability();
+	if (yn)
+		edges_changed();
 	
-		for (Edges::iterator i = _edges.begin(); i != _edges.end(); ++i)
-			(*i)->set_probability((*i)->probability() / prob_sum);
-	}
 	_changed = true;
 }
 
@@ -140,8 +154,12 @@ void
 Node::add_edge(SharedPtr<Edge> edge)
 {
 	assert(edge->tail().lock().get() == this);
+	for (Edges::const_iterator i = _edges.begin(); i != _edges.end(); ++i)
+		if ((*i)->head() == edge->head())
+			return;
 	
 	_edges.push_back(edge);
+	edges_changed();
 }
 
 
@@ -149,6 +167,7 @@ void
 Node::remove_edge(SharedPtr<Edge> edge)
 {
 	_edges.erase(_edges.find(edge));
+	edges_changed();
 }
 
 	
@@ -175,6 +194,8 @@ Node::remove_edges_to(SharedPtr<Node> node)
 
 		i = next;
 	}
+	
+	edges_changed();
 }
 
 
diff --git a/src/engine/Problem.cpp b/src/engine/Problem.cpp
index 1d11870..3fa793f 100644
--- a/src/engine/Problem.cpp
+++ b/src/engine/Problem.cpp
@@ -15,9 +15,16 @@
  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  */
 
+#define __STDC_LIMIT_MACROS 1
+
+#include <stdint.h>
+#include <set>
+#include <vector>
 #include <iostream>
 #include <machina/Problem.hpp>
 #include <machina/Machine.hpp>
+#include <machina/ActionFactory.hpp>
+#include <machina/Edge.hpp>
 #include <raul/SMFReader.hpp>
 #include <raul/midi_events.h>
 #include <eugene/core/Problem.hpp>
@@ -41,16 +48,21 @@ Problem::Problem(const std::string& target_midi, SharedPtr<Machine> seed)
 	uint32_t ev_size;
 	uint32_t delta_time;
 	while (smf.read_event(4, buf, &ev_size, &delta_time) >= 0) {
-		_target._length += delta_time / (double)smf.ppqn();
+		// time ignored
+		_target.write_event(0, ev_size, buf);
+#if 0
+		//_target._length += delta_time / (double)smf.ppqn();
 		if ((buf[0] & 0xF0) == MIDI_CMD_NOTE_ON) {
 			const uint8_t note = buf[1];
-			++_target._note_frequency[note];
-			++_target._n_notes;
+			/*++_target._note_frequency[note];
+			++_target.n_notes();*/
+			++_target._counts[note];
+			_target._notes.push_back(note);
 		}
+#endif
 	}
 
-	cout << "Target notes: " << _target._n_notes << endl;
-	cout << "Target duration: " << _target._length << endl;
+	cout << "Target notes: " << _target.n_notes() << endl;
 
 	_target.compute();
 }
@@ -59,10 +71,14 @@ Problem::Problem(const std::string& target_midi, SharedPtr<Machine> seed)
 float
 Problem::fitness(const Machine& const_machine) const
 {
-	cout << "(";
+	//cout << "(";
 
 	// kluuudge
 	Machine& machine = const_cast<Machine&>(const_machine);
+
+	map<Machine*, float>::const_iterator cached = _fitness.find(&machine);
+	if (cached != _fitness.end())
+		return cached->second;
 	
 	SharedPtr<Evaluator> eval(new Evaluator(*this));
 
@@ -77,27 +93,65 @@ Problem::fitness(const Machine& const_machine) const
 	Raul::TimeSlice time(1.0/(double)ppqn, 120);
 	time.set_start(0);
 	time.set_length(2*ppqn);
+		
+	machine.run(time);
+	if (eval->n_notes() == 0)
+		return 0.0f; // bad dog
+	
+	time.set_start(time.start_ticks() + 2*ppqn);
 
-	while (eval->_n_notes < _target._n_notes) {
+	while (eval->n_notes() < _target.n_notes()) {
 		machine.run(time);
+		if (machine.is_finished())
+			machine.reset(time.start_ticks());
 		time.set_start(time.start_ticks() + 2*ppqn);
-		if (time.start_beats() >= _target._length)
-			break;
 	}
 
 	eval->compute();
-
+	
+	// count
+#if 0
 	float f = 0;
 
 	for (uint8_t i=0; i < 128; ++i) {
-		if (eval->_note_frequency[i] <= _target._note_frequency[i])
+		/*if (eval->_note_frequency[i] <= _target._note_frequency[i])
 			f += eval->_note_frequency[i];
 		else
-			f -= _target._note_frequency[i] - eval->_note_frequency[i];
+			f -= _target._note_frequency[i] - eval->_note_frequency[i];*/
+		//f -= fabs(eval->_note_frequency[i] - _target._note_frequency[i]);
+	}
+#endif
+	//cout << ")";
+	
+	// distance
+	//float f = distance(eval->_notes, _target._notes);
+	
+	float f = 0.0;
+	
+	for (Evaluator::Patterns::const_iterator i = eval->_patterns.begin(); i != eval->_patterns.end(); ++i) {
+		// Reward for matching patterns
+		if (_target._patterns.find(i->first) != _target._patterns.end()) {
+			Evaluator::Patterns::const_iterator c = _target._patterns.find(i->first);
+			const uint32_t cnt = (c == _target._patterns.end()) ? 1 : c->second;
+			f += min(i->second, cnt) * (i->first.length());
+
+		// Punish for bad patterns
+		} else {
+			const uint32_t invlen = (eval->_order - i->first.length() + 1);
+			f -= (i->second / (float)eval->_patterns.size() * (float)(invlen*invlen*invlen)) * 4;
+		}
 	}
 	
+	// Punish for missing patterns
+	for (Evaluator::Patterns::const_iterator i = _target._patterns.begin(); i != _target._patterns.end(); ++i) {
+		if (eval->_patterns.find(i->first) == _target._patterns.end()) {
+				f -= i->second / (float)_target.n_notes() * (float)(eval->_order - i->first.length() + 1);
+		}
+	}
+
+	//cout << "f = " << f << endl;
 
-	cout << ")";
+	_fitness[&machine] = f;
 
 	return f;
 }
@@ -109,9 +163,36 @@ Problem::Evaluator::write_event(Raul::BeatTime time,
                                 const uint8_t* ev) throw (std::logic_error)
 {
 	if ((ev[0] & 0xF0) == MIDI_CMD_NOTE_ON) {
+
 		const uint8_t note = ev[1];
-		++_note_frequency[note];
+		
+		if (_first_note == 0)
+			_first_note = note;
+		
+		/*++_note_frequency[note];
+		++n_notes();*/
+		//_notes.push_back(note);
+		if (_read.length() == 0) {
+			_read = note;
+			return;
+		}
+		if (_read.length() == _order)
+			_read = _read.substr(1);
+
+		_read = _read + (char)note;
+
+		for (size_t i = 0; i < _read.length(); ++i) {
+			const string pattern = _read.substr(i);
+			Patterns::iterator i = _patterns.find(pattern);
+			if (i != _patterns.end())
+				++(i->second);
+			else
+				_patterns[pattern] = 1;
+		}
+
+		++_counts[note];
 		++_n_notes;
+		
 	}
 }
 
@@ -119,9 +200,10 @@ Problem::Evaluator::write_event(Raul::BeatTime time,
 void
 Problem::Evaluator::compute()
 {
-	/*for (uint8_t i=0; i < 128; ++i) {
+	/*
+	for (uint8_t i=0; i < 128; ++i) {
 		if (_note_frequency[i] > 0) {
-			_note_frequency[i] /= (float)_n_notes;
+			_note_frequency[i] /= (float)n_notes();
 			//cout << (int)i << ":\t" << _note_frequency[i] << endl;
 		}
 	}*/
@@ -133,12 +215,147 @@ Problem::initial_population(size_t gene_size, size_t pop_size) const
 {
 	boost::shared_ptr<Population> ret(new std::vector<Machine>());
 
-	for (size_t i = 0; i < pop_size; ++i)
-		ret->push_back(Machine(*_seed.get()));
+	// FIXME: ignores _seed and builds based on MIDI
+	// evolution of the visible machine would be nice..
+	SharedPtr<Machine> base = SharedPtr<Machine>(new Machine());
+	for (uint8_t i=0; i < 128; ++i) {
+		if (_target._counts[i] > 0) {
+			//cout << "Initial note: " << (int)i << endl;
+			SharedPtr<Node> node(new Node(1.0));
+			node->set_enter_action(ActionFactory::note_on(i));
+			node->set_exit_action(ActionFactory::note_off(i));
+			node->set_selector(true);
+			base->add_node(node);
+		}
+	}
+
+	for (size_t i = 0; i < pop_size; ++i) {
+		// FIXME: double copy
+		Machine m(*base.get());
+
+		set< SharedPtr<Node> > unreachable;
+		SharedPtr<Node> initial;
+
+		for (Machine::Nodes::iterator i = m.nodes().begin(); i != m.nodes().end(); ++i) {
+			if (PtrCast<MidiAction>((*i)->enter_action())->event()[1] == _target.first_note()) {
+				(*i)->set_initial(true);
+				initial = *i;
+			} else {
+				unreachable.insert(*i);
+			}
+		}
+
+		SharedPtr<Node> cur = initial;
+		unreachable.erase(cur);
+		SharedPtr<Node> head;
+
+		while ( ! unreachable.empty()) {
+			if (rand() % 2)
+				head = m.random_node();
+			else
+				head = *unreachable.begin();
+
+			if ( ! head->connected_to(head) ) {
+				cur->add_edge(SharedPtr<Edge>(new Edge(cur, head)));
+				unreachable.erase(head);
+				cur = head;
+			}
+		}
+		
+		ret->push_back(m);
+
+		/*cout << "initial # nodes: " << m.nodes().size();
+		cout << "initial fitness: " << fitness(m) << endl;*/
+	}
 
 	return ret;
 }
 
 
+/** levenshtein distance (edit distance) */
+size_t
+Problem::distance(const std::vector<uint8_t>& source,
+                  const std::vector<uint8_t>& target) const
+{
+	// Derived from http://www.merriampark.com/ldcpp.htm
+	
+	assert(source.size() < UINT16_MAX);
+	assert(target.size() < UINT16_MAX);
+	
+	// Step 1
+
+	const uint16_t n = source.size();
+	const uint16_t m = target.size();
+	if (n == 0)
+		return m;
+	if (m == 0)
+		return n;
+
+	_matrix.resize(n + 1);
+	for (uint16_t i = 0; i <= n; i++)
+		_matrix[i].resize (m + 1);
+
+	// Step 2
+
+	for (uint16_t i = 0; i <= n; i++)
+		_matrix[i][0] = i;
+
+	for (uint16_t j = 0; j <= m; j++)
+		_matrix[0][j] = j;
+
+	// Step 3
+
+	for (uint16_t i = 1; i <= n; i++) {
+
+		const uint8_t s_i = source[i - 1];
+
+		// Step 4
+
+		for (uint16_t j = 1; j <= m; j++) {
+
+			const uint8_t t_j = target[j - 1];
+
+			// Step 5
+
+			uint16_t cost;
+			if (s_i == t_j) {
+				cost = 0;
+			} else {
+				cost = 1;
+			}
+
+			// Step 6
+
+			const uint16_t above = _matrix[i - 1][j];
+			const uint16_t left = _matrix[i][j - 1];
+			const uint16_t diag = _matrix[i - 1][j - 1];
+			uint16_t cell = min (above + 1, min (left + 1, diag + cost));
+
+			// Step 6A: Cover transposition, in addition to deletion,
+			// insertion and substitution. This step is taken from:
+			// Berghel, Hal ; Roach, David : "An Extension of Ukkonen's
+			// Enhanced Dynamic Programming ASM Algorithm"
+			// (http://www.acm.org/~hlb/publications/asm/asm.html)
+
+			if (i > 2 && j > 2) {
+				uint16_t trans = _matrix[i - 2][j - 2] + 1;
+				if (source[i - 2] != t_j)
+					trans++;
+				if (s_i != target[j - 2])
+					trans++;
+				if (cell > trans)
+					cell = trans;
+			}
+
+			_matrix[i][j] = cell;
+		}
+	}
+
+	// Step 7
+
+	return _matrix[n][m];
+}
+
+
 } // namespace Machina
 
diff --git a/src/engine/machina/Evolver.hpp b/src/engine/machina/Evolver.hpp
index 051513b..6025210 100644
--- a/src/engine/machina/Evolver.hpp
+++ b/src/engine/machina/Evolver.hpp
@@ -47,7 +47,7 @@ private:
 
 	SharedPtr<MachinaGA> _ga;
 	SharedPtr<Problem>   _problem;
-	float                _active_fitness;
+	float                _seed_fitness;
 	Schrodinbit          _improvement;
 };
 
diff --git a/src/engine/machina/Mutation.hpp b/src/engine/machina/Mutation.hpp
index 52c02bc..18bc621 100644
--- a/src/engine/machina/Mutation.hpp
+++ b/src/engine/machina/Mutation.hpp
@@ -39,6 +39,7 @@ struct Compress   SUPER { void mutate(Machine& machine); };
 struct AddNode    SUPER { void mutate(Machine& machine); };
 struct RemoveNode SUPER { void mutate(Machine& machine); };
 struct AdjustNode SUPER { void mutate(Machine& machine); };
+struct SwapNodes  SUPER { void mutate(Machine& machine); };
 struct AddEdge    SUPER { void mutate(Machine& machine); };
 struct RemoveEdge SUPER { void mutate(Machine& machine); };
 struct AdjustEdge SUPER { void mutate(Machine& machine); };
diff --git a/src/engine/machina/Node.hpp b/src/engine/machina/Node.hpp
index 1f0face..87e14af 100644
--- a/src/engine/machina/Node.hpp
+++ b/src/engine/machina/Node.hpp
@@ -44,7 +44,7 @@ class Node : public Raul::Stateful {
 public:
 	typedef std::string ID;
 
-	Node(BeatCount duration=0, bool initial=false);
+	Node(BeatCount duration=1.0, bool initial=false);
 	Node(const Node& copy);
 
 	void set_enter_action(SharedPtr<Action> action);
@@ -56,6 +56,8 @@ public:
 	void enter(SharedPtr<Raul::MIDISink> driver, BeatTime time);
 	void exit(SharedPtr<Raul::MIDISink> driver, BeatTime time);
 
+	void edges_changed();
+
 	void add_edge(SharedPtr<Edge> edge);
 	void remove_edge(SharedPtr<Edge> edge);
 	void remove_edges_to(SharedPtr<Node> node);
@@ -82,6 +84,8 @@ public:
 	SharedPtr<Edge> random_edge();
 	
 private:
+	Node& operator=(const Node& other); // undefined
+
 	Schrodinbit       _changed;
 	bool              _is_initial;
 	bool              _is_selector;
diff --git a/src/engine/machina/Problem.hpp b/src/engine/machina/Problem.hpp
index 96ecb39..7605e88 100644
--- a/src/engine/machina/Problem.hpp
+++ b/src/engine/machina/Problem.hpp
@@ -18,6 +18,7 @@
 #ifndef MACHINA_PROBLEM_HPP
 #define MACHINA_PROBLEM_HPP
 
+#include <map>
 #include <raul/MIDISink.hpp>
 #include <eugene/core/Problem.hpp>
 #include <machina/Machine.hpp>
@@ -34,13 +35,20 @@ public:
 	float fitness(const Machine& machine) const;
 	
 	bool fitness_less_than(float a, float b) const { return a < b; }
+
+	void clear_fitness_cache() { _fitness.clear(); }
 	
 	boost::shared_ptr<Population>
 	initial_population(size_t gene_size, size_t pop_size) const;
 
 private:
-	struct Evaluator : public Raul::MIDISink {
-		Evaluator(const Problem& problem) : _problem(problem), _n_notes(0), _length(0) {
+	size_t distance(const std::vector<uint8_t>& source,
+	                const std::vector<uint8_t>& target) const;
+
+	// count
+	/*struct FreqEvaluator : public Raul::MIDISink {
+		Evaluator(const Problem& problem)
+		: _problem(problem), _n_notes(0), _length(0) {
 			for (uint8_t i=0; i < 128; ++i)
 				_note_frequency[i] = 0;
 		}
@@ -49,14 +57,62 @@ private:
 		                 const uint8_t* ev) throw (std::logic_error);
 		void compute();
 		const Problem& _problem;
+		
+		size_t n_notes() const { return _n_notes; }
 	
 		float  _note_frequency[128];
 		size_t _n_notes;
 		double _length;
+	};*/
+
+	// distance
+	/*struct Evaluator : public Raul::MIDISink {
+		Evaluator(const Problem& problem) : _problem(problem) {}
+		void write_event(Raul::BeatTime time,
+		                 size_t         ev_size,
+		                 const uint8_t* ev) throw (std::logic_error);
+		void compute();
+		const Problem& _problem;
+
+		size_t n_notes() const { return _notes.size(); }
+	
+		std::vector<uint8_t> _notes;
+		float                _counts[128];
+	};*/
+	
+	struct Evaluator : public Raul::MIDISink {
+		Evaluator(const Problem& problem) : _problem(problem), _order(8), _n_notes(0), _first_note(0) {
+			for (uint8_t i=0; i < 128; ++i)
+				_counts[i] = 0;
+		}
+		void write_event(Raul::BeatTime time,
+		                 size_t         ev_size,
+		                 const uint8_t* ev) throw (std::logic_error);
+		void compute();
+		const Problem& _problem;
+
+		size_t n_notes() const { return _n_notes; }
+		uint8_t first_note() const { return _first_note; }
+	
+		const uint32_t _order;
+
+		std::string _read;
+
+		typedef std::map<std::string, uint32_t> Patterns;
+		Patterns _patterns;
+		uint32_t _counts[128];
+		size_t   _n_notes;
+		uint8_t  _first_note;
 	};
 
 	Evaluator          _target;
 	SharedPtr<Machine> _seed;
+	
+	/// for levenshtein distance
+	mutable std::vector< std::vector<uint16_t> > _matrix;
+
+	/// memoization
+	mutable std::map<Machine*, float> _fitness;
 };