mdd/lib/src/OptimizerEvolutionary.cpp

#include "OptimizerEvolutionary.h"

namespace mdd {
	void OptimizerEvolutionary::evaluate(size_t ignore_len)
	{
		_mutex.lock();
		//clear duplicates
		//std::sort(_children.begin(), _children.end(), Permutation::smaller);
		//_children.erase(std::unique(_children.begin(), _children.end(), Permutation::same), _children.end());
		std::vector<Permutation> save = _children;
		_children.clear();
		for (size_t i = 0; i < save.size(); i++)
		{
			bool found = false;
			for (size_t j = 0; j < _children.size(); j++)
			{
				if (save[i] == _children[j])
				{
					found = true;
					break;
				}
			}
			if (!found)
			{
				_children.push_back(save[i]);
			}
		}

		//print Modules which are not evaluated again
		opt_state def_state;
		def_state.module_state = state::UNCHANGED;
		for (int i = 0; i < ignore_len; ++i)
		{
			callback_evaluate_opt(_children[i]);
		}

		//calculate fitness
		for (auto it = _children.begin() + ignore_len; it != _children.end(); ++it)
		{
			auto per = findPermutation(it->dna);
			if (per == nullptr)
			{
				for (size_t j = 0; j < _inputs.size(); j++)
				{
					//std::cout << "set: " << j << ": " << it->dna[j] << std::endl;
					_inputs[j]->setValue() = it->dna[j];
				}
				// Start timer
				auto start = std::chrono::steady_clock::now();
				// Update Module
				opt_state opt = updateOutputs();
				// Stop timer
				auto end = std::chrono::steady_clock::now();
				std::chrono::duration<double> elapsed_seconds = end - start;
				it->time = elapsed_seconds.count();
				it->status = opt.module_state;
				it->fitness = opt.opt_value;
				callback_evaluate_opt(*it);

				if (opt.module_state == state::STATE_ERROR) {
					_children.erase(it);
				}
			}
			else{
				callback_evaluate_opt(*per);
			}
		}
		//find fitest
		double min = _children[0].fitness;
		_bests.clear();
		_bests.push_back(_children[0]);
		for (size_t i = 1; i < _children.size(); i++)
		{
			if (round(min/_precision)*_precision > round(_children[i].fitness / _precision) * _precision) {
				min = _children[i].fitness;
				_bests.clear();
				_bests.push_back(_children[i]);
			}
			else if(round(min / _precision) * _precision == round(_children[i].fitness / _precision) * _precision)
			{
				bool found = false;
				for (size_t j = 0; j < _bests.size(); j++)
				{
					if (_children[i] == _bests[j])
					{
						found = true;
						break;
					}
				}
				if (!found)
				{
					_bests.push_back(_children[i]);
				}
			}
		}
		_mutex.unlock();
		callback_autosave();
	}

	OptimizerEvolutionary::OptimizerEvolutionary()
		:OptimizerBase(R"JSON(
        {
            "converges":
			{
				"value": 0
			},
            "grow generation":
			{
            "value": 20
			},
            "max fitness":
			{
				"value": 0.0
			},
            "min generations": 
			{
				"value": -1
			},
            "precission":
			{
				"value": 0.001
			}
        })JSON")
	{
		key = "OptimizerEvolutionary";
		_converges = 0;
		_grow_generation = 20;
		_max_fitness = 0.0;
		_min_generations = -1;
		_precision = 0.001;
	}

	bool OptimizerEvolutionary::configureChild(const json& config) {
		bool found = false;
		auto jit = config.find("converges");
		if (jit != config.end())
		{
			json jval = jit.value()["value"];
			if (jval.is_string())
			{
				jval = json::parse(jval.get<std::string>());
			}
			_converges = jval.get<int>();
			_base_config["configure"]["converges"]["value"] = _converges;
			found = true;
		}
		jit = config.find("grow generation");
		if (jit != config.end())
		{
			json jval = jit.value()["value"];
			if (jval.is_string())
			{
				jval = json::parse(jval.get<std::string>());
			}
			_grow_generation = jval.get<int>();
			_base_config["configure"]["grow generation"]["value"] = _grow_generation;
			found = true;
		}
		jit = config.find("max fitness");
		if (jit != config.end())
		{
			json jval = jit.value()["value"];
			if (jval.is_string())
			{
				jval = json::parse(jval.get<std::string>());
			}
			_max_fitness = jval.get<double>();
			_base_config["configure"]["max fitness"]["value"] = _max_fitness;
			found = true;
		}
		jit = config.find("min generations");
		if (jit != config.end())
		{
			json jval = jit.value()["value"];
			if (jval.is_string())
			{
				jval = json::parse(jval.get<std::string>());
			}
			_min_generations = jval.get<int>();
			_base_config["configure"]["min generations"]["value"] = _min_generations;
			found = true;
		}
		jit = config.find("precision");
		if (jit != config.end())
		{
			json jval = jit.value()["value"];
			if (jval.is_string())
			{
				jval = json::parse(jval.get<std::string>());
			}
			_precision = jval.get<double>();
			_base_config["configure"]["precision"]["value"] = _precision;
			found = true;
		}
		return found;
	}

	bool OptimizerEvolutionary::loadStepDB(const json& j) {
		bool ret = true;
		for (size_t i = 0; i < j.size(); i++)
		{
			json jstep = j.at(i);
			int counter = json::parse(jstep["step"].get<std::string>()).get<int>();
			json dna = json::parse(jstep["dna"].get<std::string>());
			ret = ret && addStep(counter, dna);
			if (this->step != counter)
			{
				++this->step;
				_children.clear();
			}
			std::shared_ptr<Permutation> per_ptr = getPermutation(counter, dna);
			_children.push_back(*per_ptr);
		}
		return ret;
	}

	bool OptimizerEvolutionary::loadDB(const json& j) {
		bool ret = OptimizerBase::loadDB(j);
		if (step == -1)
		{
			return ret;
		}

		_bests = findBest(step -1);

		return ret;
	}

	void OptimizerEvolutionary::reset() {
		OptimizerBase::reset();
		_children.clear();
		_bests.clear();
		_same_counter = 0;
		_old_best = Permutation();
	}

	bool OptimizerEvolutionary::reachAbort(const std::vector<Permutation>& pers) {
		bool check;
		check = step < _min_generations || pers[0].fitness > _max_fitness;
		if (!check && _converges > 0)
		{
			bool found = false;
			for (size_t i = 0; i < pers.size(); i++)
			{
				Permutation p_container = pers.at(i);
				if (p_container == _old_best)
				{
					found = true;
					break;
				}
			}
			if (found)
			{
				++_same_counter;
			}
			else
			{
				_old_best = pers[0];
				_same_counter = 0;
			}
			if (_same_counter < _converges)
			{
				check = true;
			}
		}
		return !check;
	}

	double OptimizerEvolutionary::update()
	{

		if (_inputs.size() == 0)
		{
			std::cout << "ERROR: No optimizable inputs detected!" << std::endl;
			return -1.0;
		}
		do
		{
			++step;
			std::cout << _children.size() << " | " << step << std::endl;
			evolve();
			
		} while (!reachAbort(_bests));
		
		return _bests[0].fitness;
	}

	std::vector<double> OptimizerEvolutionary::mutateGene(std::shared_ptr<IInput> input, std::vector<double> seed)
	{
	
		const limits limit = *(input->getLimits());
		auto ret = seed;
		
		if (!limit.elements.empty())
		{
			int i = (int)random_num(0, limit.elements.size() - 1);
			ret = limit.elements[i];
			return ret;
		}
		if (!limit.min.empty() && !limit.max.empty()) {

			bool check = true;
			do {
				if (!ret.empty())
				{
					int i = (int)random_num(0, limit.min.size() - 1);
					if (!limit.step.empty()) {
						//randomly generate step dx in [min, max]
						/*std::cout << limit["min"][i].get<double>() << " | ";
						std::cout << limit["max"][i].dump() << " | ";
						std::cout << limit["step"][i].dump() << " | ";*/
						ret[i] = random_num(limit.min[i], limit.max[i], limit.step[i]);
					}
					else {
						int m = (int)random_num(0, 1);
						if (m == 0)
						{
							ret[i] = limit.min[i];
						}
						else {
							ret[i] = limit.max[i];
						}
					}
				}
				else
				{
					for (size_t i = 0; i < limit.min.size(); i++)
					{
						if (!limit.step.empty()) {
							//randomly generate step dx in [min, max]
							ret.push_back(random_num(limit.min[i], limit.max[i], limit.step[i]));
						}
						else {
							int m = (int)random_num(0, 1);
							if (m == 0)
							{
								ret.push_back(limit.min[i]);
							}
							else {
								ret.push_back(limit.max[i]);
							}
						}
					}
				}
				
				if (!limit.rule.empty()) {
					//use rule to check
					exprtk::symbol_table<double> symbol_table;
					
					symbol_table.add_vector("val", ret);
					symbol_table.add_constants();
					exprtk::expression<double> func_expr;
					func_expr.register_symbol_table(symbol_table);

					exprtk::parser<double> parser;
					parser.compile(limit.rule, func_expr);
					double func_val = func_expr.value();
					if (func_val < 0.5)
					{
						check = false;
					}
					else {
						check = true;
					}
				}
			} while (!check);
			return ret; 
			
		}
		std::cout << "ERROR in GENE elements! (END)" << std::endl;
		return input->getValue();//ERROR
	}

	void OptimizerEvolutionary::evolve()
	{
		_mutex.lock();
		if (_children.empty())
		{
			for (size_t i = 0; i < _grow_generation * 2; i++)
			{
				bool not_found = true;
				Permutation per;
				while (not_found)
				{
					per = generatePermutation();
					not_found = false;
					for (size_t i = 0; i < _children.size(); i++)
					{
						if (_children[i].dna == per.dna)
						{
							not_found = true;
							break;
						}
					}
				}
				_children.push_back(per);
			}
		}
		else {
			////fittest should breed more
			//detect lower border
			double max = _children[0].fitness;
			for (size_t i = 1; i < _children.size(); i++)
			{
				if (max < _children[i].fitness) {
					max = _children[i].fitness;
				}
			}
			//detect lower border
			double sum = 0;
			for (size_t i = 0; i < _children.size(); i++)
			{
				sum += max - _children[i].fitness;
			}
			if (sum == 0)
			{
				sum = 1.0;
			}
			//multiply fitter parents
			std::vector<Permutation> gen_pool = _children;
			for (size_t i = 0; i < _children.size(); i++)
			{
				int additional = std::round((max - _children[i].fitness) / sum * 20);
				//std::cout << additional << std::endl;
				for (size_t j = 1; j < additional; j++)
				{
					gen_pool.push_back(_children[i]);
				}
			}
			//fittest parents will also be new childrens
			_children = _bests;

			//breed
			for (size_t i = 0; i < _grow_generation; i++)
			{
				bool not_found = true;
				Permutation per;
				int try_counter = 0;
				while (not_found && try_counter < 20)
				{
					int p1 = (int)random_num(0, gen_pool.size() - 1);
					int p2 = (int)random_num(0, gen_pool.size() - 1);
					per = combine(gen_pool[p1], gen_pool[p2]);
					++try_counter;
					not_found = false;
					for (size_t i = 0; i < _children.size(); i++)
					{
						if (_children[i].dna == per.dna)
						{
							not_found = true;
							break;
						}
					}
				}
				_children.push_back(per);
			}
		}
		_mutex.unlock();
		callback_add_step(_children);
		evaluate(_bests.size());
	}

	OptimizerEvolutionary::Permutation OptimizerEvolutionary::combine(Permutation par1, Permutation par2, int try_counter)
	{
		size_t len = par1.dna.size();
		Permutation child;
		for (size_t i = 0; i < len; i++)
		{
			double p = random_num(0.0, 100.0, 1.0);
			if (p<45.0 - try_counter)
			{
				child.dna.push_back(par1.dna[i]);
			}
			else if(p<90.0 - 2*try_counter){
				child.dna.push_back(par2.dna[i]);
			}
			else
			{
				child.dna.push_back(mutateGene(_inputs[i]));
			}
		}
		return child;
	}

	OptimizerEvolutionary::Permutation OptimizerEvolutionary::generatePermutation()
	{
		Permutation ret;
		for (size_t i = 0; i < _inputs.size(); i++)
		{
			ret.dna.push_back(mutateGene(_inputs[i]));
		}
		return ret;
	}

	std::vector<OptimizerEvolutionary::Permutation> OptimizerEvolutionary::getBests() {
		return _bests;
	}

	double OptimizerEvolutionary::evaluateFitness(const Permutation& ind) {
		for (size_t j = 0; j < _inputs.size(); j++)
		{
			_inputs[j]->setValue() = ind.dna[j];
		}
		auto opt = updateOutputs();
		return opt.opt_value;
	}
}