mdd/lib/src/OptimizerEvolutionary.cpp

#include <iostream>
#include "OptimizerBase.h"

namespace mdd {
	class OptimizerEvolutionary : public OptimizerBase {
	public:
		struct Individual {
		public:
			std::vector<std::vector<double>> dna;
			double fitness = 0;
			bool operator== (const Individual& ind) {
				return (dna == ind.dna) && (fitness == ind.fitness);
			};
		};
	protected:
		static int random_num(double min, double max, double inc = 1.0)
		{
			int range = (max - min) / inc + 1;
			return min + inc * (std::rand() % range);
		}

		Individual generateIndividual();
		Individual combine(Individual par1, Individual par2);

		std::vector<Individual> _children;
		Individual _best;
		int _min_generations;
		double _max_fitness;
		size_t _grow_generation;
		size_t _converges;

		void evolve(std::vector<Individual> parents);
		void evaluate(size_t ignore_len = 0);
		std::vector<double> mutateGene(std::shared_ptr<IInput> input, std::vector<double> seed = std::vector<double>());


	public:
		OptimizerEvolutionary();
		/*
		std::shared_ptr<IModule> module,
			size_t converges = 0,
			size_t grow_generation = 20,
			double max_fitness = 0.0,
			int min_generations = -1
		*/
		std::vector<std::vector<double>> update() override;
		Individual getBest();
		double evaluateFitness(const Individual& ind);
	};

	void OptimizerEvolutionary::evaluate(size_t ignore_len)
	{
		//calculate fitness
		for (auto it = _children.begin() + ignore_len; it != _children.end(); ++it)
		{
			for (size_t j = 0; j < _inputs.size(); j++)
			{
				//std::cout << "set: " << j << ": " << it->dna[j] << std::endl;
				_inputs[j]->setValue() = it->dna[j];
			}
			auto opt = updateOutputs();
			if (opt.module_state == state::STATE_ERROR) {
				_children.erase(it);
			}
			else {
				it->fitness = opt.opt_value;
			}
		}
		//find fitest
		double min = _children[0].fitness;
		for (size_t i = 1; i < _children.size(); i++)
		{
			if (min > _children[i].fitness) {
				min = _children[i].fitness;
				_best = _children[i];
			}
		}
	}
	OptimizerEvolutionary::OptimizerEvolutionary()
		:OptimizerBase(R"JSON(
        [{
            "name":"converges",
            "value": 0
        },{
            "name":"grow_generation",
            "value": 20
        },{
            "name":"max_fitness",
            "value": 0.0
        },{
            "name":"min_generations",
            "value": -1
        }])JSON")
	{
		//_module = module;
		_grow_generation = 0;
		_min_generations = 20;
		_max_fitness = 0.0;
		_converges = -1;
	}
	std::vector<std::vector<double>> OptimizerEvolutionary::update()
	{
		int gen = -1;
		bool check;
		Individual old_best;
		size_t same_counter = 0;
		if (_inputs.size() == 0)
		{
			std::cout << "ERROR: No optimizable inputs detected!" << std::endl;
			return std::vector<std::vector<double>>();
		}
		do
		{
			std::cout << _children.size() << " | " << gen << std::endl;
			if (_children.empty())
			{
				for (size_t i = 0; i < _grow_generation*2; i++)
				{
					_children.push_back(generateIndividual());
				}
				evaluate();
			}
			else {
				if (gen != -1)
				{
					evolve(_children);
				}
				else {
					evaluate();
				}
			}
			
			++gen;
			check = gen < _min_generations || _best.fitness > _max_fitness;
			if (!check && _converges > 0)
			{
				if (_best == old_best)
				{
					++same_counter;
				}
				else
				{
					old_best = _best;
					same_counter = 0;
				}
				if (same_counter < _converges)
				{
					check = true;
				}
			}
		} while (check);
		
		return _best.dna;
	}
	std::vector<double> OptimizerEvolutionary::mutateGene(std::shared_ptr<IInput> input, std::vector<double> seed)
	{
	
		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);
					check = (bool)func_expr.value();
				}
			} while (!check);
			return ret; 
			
		}
		std::cout << "ERROR in GENE elements! (END)" << std::endl;
		return input->getValue();//ERROR
	}

	void OptimizerEvolutionary::evolve(std::vector<Individual> parents)
	{
		////fittest should breed more
		//detect lower border
		double max = parents[0].fitness;
		for (size_t i = 1; i < parents.size(); i++)
		{
			if (max < parents[i].fitness) {
				max = parents[i].fitness;
			}
		}
		//detect lower border
		double sum = 0;
		for (size_t i = 0; i < parents.size(); i++)
		{
			sum += max - parents[i].fitness;
		}
		if (sum == 0)
		{
			sum = 1.0;
		}
		//multiply fitter parents
		std::vector<Individual> gen_pool = parents;
		for (size_t i = 0; i < parents.size(); i++)
		{
			int additional = std::round((max - parents[i].fitness) / sum * 20);
			//std::cout << additional << std::endl;
			for (size_t j = 1; j < additional; j++)
			{
				gen_pool.push_back(parents[i]);
			}
		}
		//fittest parents will also be new childrens
		_children.clear();
		double min = parents[0].fitness;
		for (size_t i = 1; i < parents.size(); i++)
		{
			if (max > parents[i].fitness) {
				min = parents[i].fitness;
			}
		}
		for (size_t i = 0; i < parents.size(); i++)
		{
			if (max == parents[i].fitness) {
				bool exist = false;
				for (size_t j = 0; j < _children.size(); j++)
				{
					if (_children[j].dna == parents[i].dna) {
						exist = true;
						break;
					}
				}
				if (!exist) {
					_children.push_back(parents[i]);
				}
			}
		}
		//breed
		size_t init_len = _children.size();
		for (size_t i = 0; i < _grow_generation; i++)
		{
			int p1 = (int)random_num(0, gen_pool.size() - 1);
			int p2 = (int)random_num(0, gen_pool.size() - 1);
			_children.push_back(combine(gen_pool[p1], gen_pool[p2]));
		}
		evaluate(init_len);
	}
	OptimizerEvolutionary::Individual OptimizerEvolutionary::combine(Individual par1, Individual par2)
	{
		size_t len = par1.dna.size();
		Individual child;
		for (size_t i = 0; i < len; i++)
		{
			double p = random_num(0.0, 100.0, 1.0);
			if (p<45.0)
			{
				child.dna.push_back(par1.dna[i]);
			}
			else if(p<90.0){
				child.dna.push_back(par2.dna[i]);
			}
			else
			{
				child.dna.push_back(mutateGene(_inputs[i]));
			}
		}
		return child;
	}
	OptimizerEvolutionary::Individual OptimizerEvolutionary::generateIndividual()
	{
		Individual ret;
		for (size_t i = 0; i < _inputs.size(); i++)
		{
			ret.dna.push_back(mutateGene(_inputs[i]));
		}
		return ret;
	}
	OptimizerEvolutionary::Individual OptimizerEvolutionary::getBest() {
		return _best;
	}
	double OptimizerEvolutionary::evaluateFitness(const Individual& ind) {
		for (size_t j = 0; j < _inputs.size(); j++)
		{
			_inputs[j]->setValue() = ind.dna[j];
		}
		auto opt = updateOutputs();
		return opt.opt_value;
	}
}