Solving C++ optimization problems are one of the areas of all quantitative disciplines from social science, economics to engineering fields such as computer science. Genetic Algorithm (GA) is a kind of machine learning process that is used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover, and selection. In this post, we explain how you can achieve optimization using artificial intelligence techniques.
The Genetic Algorithm that we use here below was first mentioned by Željko Kovačević (Embarcadero MVP). Željko has amazing VCL Examples and blog posts about C++ Builder. He gave me this example below as a console app about GA and allowed me to release it free, but credits of this code may require contact with him. Then I improve and simplify (I can’t ofc) it for the C++ Builder and C++ Builder CE. Here, the field and codes below may be harder for beginners but I am sure this post may help how you can develop your scientific applications with C++ Builder CE.
Table of Contents
What is a Genetic Algorithm?
In computer science and research, a Genetic Algorithm (GA) is an algorithm that is used to solve optimization problems by evolving towards better solutions, just as sentient beings do in nature. Genetic Algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms. Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover, and selection. In a Genetic Algorithm, first, we create an initial population, then we iterate in a loop by calculating the fitness value, selection, crossover, and mutation steps as below,
Genetic Algorithms are one of the older AI/ML methods developed to solve some problems such as solving sudoku puzzles. Genetic Algorithms and Fuzzy Logic were very popular in the 1990s. A typical genetic algorithm requires:
- A genetic representation of the solution domain,
- a fitness function to evaluate the solution domain.
How to develop a genetic algorithm with C++ Builder?
In our optimization example in C++, we develop an optimization algorithm such as Genetic Algorithm about our chosen field. Now let’s explain quickly what we mean by that. First, we have a global Input value that represents a value (number) for which Genetic Algorithm (GA) is trying to find its binary representation.
|
1 2 3 |
unsigned int inputValue = 1234567890; |
We have individuals to evaluate with genetic algorithms, so we can create this class below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Individual { public: std::vector<bool> gene = std::vector<bool>(32); // number of bits unsigned int fitness{ std::numeric_limits<int>::max() }; void evaluate() { unsigned int number = toNumber(); if (number < inputValue) fitness = inputValue - number; else fitness = number - inputValue; } unsigned int toNumber() const { unsigned int sum = 0; for (unsigned int i = 0; i < gene.size(); i++) sum += (gene[i]) * (int)std::pow(2, gene.size() - i - 1); return sum; } }; |
In this case, for input value 1234567890 GA is trying to find a correct solution which is 0100.1001.1001.0110.0000.0010.1101.0010. To do so, first, it will create a random (initial) population (Generation 1) and then will optimize the currently best solutions through generations using selection, crossover, and mutation operations. So, first, we need a Population class as shown below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
class Population { public: std::vector<Individual> individual; void generateRandom(int size) { for (int i = 0; i < size; i++) { Individual pom; for (unsigned int j = 0; j < pom.gene.size(); j++) pom.gene[j] = rand() % 2; individual.push_back(pom); } } // evaluating population void evaluate() { for (unsigned int i = 0; i < individual.size(); i++) individual[i].evaluate(); } // best fitness in the population void getBestFitness(unsigned int* bestFitness, unsigned int* closestValue) { *bestFitness = individual[0].fitness; *closestValue = individual[0].toNumber(); for (unsigned int i = 1; i < individual.size(); i++) { if (individual[i].fitness < *bestFitness) { *bestFitness = individual[i].fitness; *closestValue = individual[i].toNumber(); } } } // adding elite members of previous generation void addElite(Population* previousGen, int elitism) { // sort individuals in current population sort(individual.begin(), individual.end(), [](Individual I1, Individual I2) { return I1.fitness < I2.fitness; }); // sort individuals from the previous generation sort(previousGen->individual.begin(), previousGen->individual.end(), [](Individual I1, Individual I2) { return I1.fitness < I2.fitness; }); // replace the worst individuals in current population with elite individuals from the previous generation int eliteCount = (int)std::ceil((elitism * individual.size()) / 100.); for (int i = 0; i < eliteCount; i++) { individual[individual.size() - i - 1] = previousGen->individual[i]; } // sort individuals in current population sort(individual.begin(), individual.end(), [](Individual I1, Individual I2) { return I1.fitness < I2.fitness; }); } }; |
We need to display our value of generations in binary mode, so we need to convert our value (i.e. InputValue) to binary string as below,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
std::string numberToBin(int n, int minBits = 16) { std::vector<int> pom; while (n != 0) { pom.push_back(n % 2); n /= 2; } // fill zeros for (int i = pom.size(); i < minBits; i++) pom.push_back(0); // binary representation std::string res; int counter = 0; for (auto it = pom.rbegin(); it != pom.rend(); it++) { if (counter++ % 4 == 0) res += '.'; res += ('0' + *it); } std::string rets= res.substr(1); return rets; } |
How to iterate a genetic algorithm in C++?
In genetic iteration loop, we need a tournament selection method tournamentSelection() as shown below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// tournament selection Population tournamentSelection(const Population& P0, int tournamentSize) { Population P1; // repeat tournament until population is full for (unsigned int i = 0; i < P0.individual.size(); i++) { // choose N random contenders in the tournament std::vector<int> randomContender; for (int j = 0; j < tournamentSize; j++) randomContender.push_back(rand() % P0.individual.size()); // who is the winner? int winner = 0; for (unsigned int j = 1; j < randomContender.size(); j++) if (P0.individual[randomContender[j]].fitness < P0.individual[randomContender[winner]].fitness) // ! winner = j; // add winner in the next generation P1.individual.push_back(P0.individual[randomContender[winner]]); } return P1; } |
We need to crossover gene pairs with crossPair() method like so:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void crossoverPair(const Individual& parent1, const Individual& parent2, Individual* offspring1, Individual* offspring2) { Individual offspring[2]; for (int i_crossoverTimes = 0; i_crossoverTimes < 2; i_crossoverTimes++) { for (unsigned int i_gene = 0; i_gene < parent1.gene.size(); i_gene++) { int dice = rand() % 100 + 1; // child takes a gene from the 1st parent if (dice <= 50) // 50 - 50 probability offspring[i_crossoverTimes].gene[i_gene] = parent1.gene[i_gene]; else // child takes a gene from the 2st parent offspring[i_crossoverTimes].gene[i_gene] = parent2.gene[i_gene]; } } *offspring1 = offspring[0]; *offspring2 = offspring[1]; } |
and we can create a Crossover() class as below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
Population Crossover(const Population& P1, int crossoverProbability) { Population P2 = P1; // probability crossover table type class crossoverIndividualType { public: Individual individual; int indexInPopulation; int probability; crossoverIndividualType(Individual _individual, int _indexInPopulation, int _probability) : individual(_individual) { indexInPopulation = _indexInPopulation; probability = _probability; } }; // creating crossover probability table std::vector<crossoverIndividualType> crossoverProbabilityTable; // 1-100 % for (unsigned int i = 0; i < P2.individual.size(); i++) { int probability = rand() % 100 + 1; // probability of crossover for i-th individual if (probability <= crossoverProbability) crossoverProbabilityTable.push_back(crossoverIndividualType(P2.individual[i], i, probability)); } // if having odd number of parents, delete the last one if (crossoverProbabilityTable.size() % 2 != 0) crossoverProbabilityTable.pop_back(); // shuffle parents if (crossoverProbabilityTable.size() > 1) { for (unsigned int i = 0; i < crossoverProbabilityTable.size(); i++) { int j = rand() % crossoverProbabilityTable.size(); crossoverIndividualType temp = crossoverProbabilityTable[j]; crossoverProbabilityTable[j] = crossoverProbabilityTable[i]; crossoverProbabilityTable[i] = temp; } } // mate parents for (unsigned int i = 0; i < crossoverProbabilityTable.size(); i += 2) { Individual parent1 = crossoverProbabilityTable[i].individual; Individual parent2 = crossoverProbabilityTable[i + 1].individual; Individual offspring1, offspring2; crossoverPair(parent1, parent2, &offspring1, &offspring2); // replace parents with their children P2.individual[crossoverProbabilityTable[i].indexInPopulation] = offspring1; P2.individual[crossoverProbabilityTable[i + 1].indexInPopulation] = offspring2; } return P2; } |
We can do some mutations (random gene changes) with this Mutation() method like so:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// mutation - random gene changes void Mutation(Population* P2, int mutationProbability) { // for every individual in the population... for (unsigned int i_individual = 0; i_individual < P2->individual.size(); i_individual++) { // for every gene for (unsigned int i_gene = 0; i_gene < P2->individual[i_individual].gene.size(); i_gene++) { int dice = rand() % 100 + 1; // mutate? if (dice <= mutationProbability) P2->individual[i_individual].gene[i_gene] = rand() % 2; } } } |
How to run a genetic algorithm with one click in C++ Builder?
Now we can create our C++ Builder FMX app, with the following components:
- 2 Edit (TEdit),
- a Memo (TMemo),
- a TeeChart with y=f(x) Series (TChart)
- a Button (TButton)
Here, Edit1 is for Input value, Edit2 is to see Seed value, Memo1 is to display results, TChart1 is to display GA optimization in graphics and Button1 to run GA again and again. Double click to Button1. This Button will setup GA and run the GA Algorithm. It will create a random (initial) population (Generation 1), and then will optimize currently best solutions through generations using selection, crossover and mutation operations. Here we is how it will do,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
void __fastcall TForm1::Button1Click(TObject *Sender) { int seed = (unsigned)time(NULL); srand(seed); int popSize = 250; int ts = 2; int pc = 70; // % int pm = 10; // % int el = 10; // % //bool multithreaded = false; unsigned int maxGen = 2500; // maximum number of generations inputValue = Edit1->Text.ToInt(); auto start_t = std::chrono::high_resolution_clock::now(); std::vector<Population> generation; Population randomPopulation; randomPopulation.generateRandom(popSize); randomPopulation.evaluate(); unsigned int bestFitness, currentFitness, closestNumber; randomPopulation.getBestFitness(¤tFitness, &closestNumber); bestFitness = currentFitness; generation.push_back(randomPopulation); Memo1->Lines->Add( "Seed: "+ IntToStr(seed) ); Edit2->Text= IntToStr(seed); std::string sbin= numberToBin(inputValue, generation[0].individual[0].gene.size()); Memo1->Lines->Add( " Input value: " + UIntToStr(inputValue)+" bin: "+ sbin.c_str() ); sbin = numberToBin(closestNumber, generation[0].individual[0].gene.size()); UnicodeString ustr; ustr.printf( L"Generation:%4u fitness:%10u val:%10u", 1, currentFitness, closestNumber); Memo1->Lines->Add(ustr+" bin: "+sbin.c_str() ); Series1->Clear(); Series1->Add( currentFitness , 1 ,clTeeColor ); Application->ProcessMessages(); // genetic algorithm do { // selection Population P1 = tournamentSelection(generation[generation.size() - 1], ts); // crossover Population P2 = Crossover(P1, pc); // mutation Mutation(&P2, pm); // elitism P2.addElite(&generation[generation.size() - 1], el); generation.push_back(P2); generation[generation.size() - 1].evaluate(); generation[generation.size() - 1].getBestFitness(¤tFitness, &closestNumber); if (currentFitness < bestFitness) { bestFitness = currentFitness; //output after finding better fitness value sbin= numberToBin(closestNumber, generation[0].individual[0].gene.size()); ustr.printf( L"Generation:%4u fitness:%10u val:%10u", generation.size(), currentFitness, closestNumber ); Memo1->Lines->Add(ustr+" bin: "+sbin.c_str() ); Series1->Add( currentFitness , generation.size() ,clTeeColor ); } if (bestFitness == 0) { /*std::string sbin= numberToBin(inputValue, generation[0].individual[0].gene.size()); Memo1->Lines->Add( " Input value: " + UIntToStr(inputValue)+" bin: "+ sbin.c_str() ); */ Memo1->Lines->Add( "Solution is found in generation: " + UIntToStr(generation.size()) ); break; } } while (bestFitness != 0 && generation.size() <= maxGen); // termination condition auto end_t = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_t - start_t).count(); Memo1->Lines->Add( "Duration: " + IntToStr(duration)+ " ms"); } |
This will optimize currently best solutions through generations using selection, crossover and mutation operations. Here is an example runtime:
This application can be developed by the C++ Builder CE free version or by the professional versions of C++ Builder. Here is the full project that you can download from my personal web page : https://www.yyoru.com/dl/GeneticAlgorithmsFMX.rar
To know how close it is to a correct solution (global optima) fitness function (value) is used. In this case, it is a minimization problem where the GA values the solutions (binary representations) that are closer to the correct solution. So, the best fitness value, in this case, is 0 (the best solution in the current generation is no different than the correct solution). As it can be seen, first it starts with a large fitness value, and then it gets smaller and smaller because the individuals (solutions) get better and better through generations. Finally, it reaches 0 in the last generation number when it found a correct solution.
Note that, GAs are non-deterministic and solutions may vary each time you run the app. That is why the Seed value is used to be able to repeat the process under the same conditions.
What are you waiting for? Download the free version of C++ Builder 11 CE Community Edition here: https://www.embarcadero.com/products/cbuilder/starter and start to develop your scientific app!
