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

1 files changed, 235 insertions, 18 deletions

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