// Author: John McCullock // Date: 04-17-06 // Description: Genetic Algorithm Example #include #include #include #include #include #include using namespace std; const int target = 100; // The number for the algorithm to find. const int maxInputs = 50; // Number of chomosomes in population. const int maxEpochs = 50; // Arbitrary number of cycles to stop after. /* 0000 0000 0000 0000 0000 0000 0000 0000 0000 Four bits are required to represent the range of characters used: Digits: 0: 0000 1: 0001 2: 0010 3: 0011 4: 0100 5: 0101 6: 0110 7: 0111 8: 1000 9: 1001 Operators: +: 1010 +: 1011 -: 1100 -: 1101 *: 1110 /: 1111 */ const int maxSize = 36; int digits[10][4] = {{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 1, 0}, {0, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 1}}; int operators[6][4] = {{1, 0, 1, 0}, {1, 0, 1, 1}, {1, 1, 0, 0}, {1, 1, 0, 1}, {1, 1, 1, 0}, {1, 1, 1, 1}}; int inputs[maxInputs][maxSize]; // Current population. int nextGen[maxInputs][maxSize]; // Next population. int totals[maxInputs]; // Decoded values. int fitness[maxInputs]; // Fitness as percentage. bool selected[maxInputs]; // Eligible parents. void geneticAlgorithm(); void prepNextEpoch(); void selection(); void mating(); int chooseParent(); int chooseParent(int parentA); void crossover(int chromA, int chromB, int newChrom[]); int decodeInput(int inputIndex); void getFitness(); int getRandomNumber(int low, int high); int minimum(int intArray[]); int maximum(int intArray[]); void initializeChromosomes(); int main() { srand((unsigned)time(0)); geneticAlgorithm(); return 0; } void geneticAlgorithm() { int epoch; bool done = false; initializeChromosomes(); epoch = 0; do { for(int i = 0; i <= maxInputs - 1; i++) { totals[i] = decodeInput(i); if(totals[i] == target || epoch == maxEpochs) { done = true; } } // i getFitness(); for(int i = 0; i <= maxInputs - 1; i++) { for(int j = 0; j <= maxSize - 1; j++) { cout << inputs[i][j]; } // j cout << " = " << totals[i]; cout << "\t" << fitness[i] << "%" << endl; } // i cout << "\n"; selection(); mating(); prepNextEpoch(); epoch += 1; //This is here simply to show the runtime status. cout << "Epoch: " << epoch << endl; }while(!done); cout << "Done." << endl; cout << "Completed " << epoch << " epochs." << endl; } void initializeChromosomes() { int getRand, l; /* j = 0 1 2 3 4 5 6 7 8 '0000 0000 0000 0000 0000 0000 0000 0000 0000 '0-3: operand '4-7: operator '8-11: operand '12-15: operator '16-19: operand '20-23: operator '24-27: operand '28-31: operator '32-35: operand */ for(int i = 0; i <= maxInputs - 1; i++) { l = 0; for(int j = 0; j <= 8; j++) { if((j % 2) == 0) { // j is even; this is an operand getRand = getRandomNumber(0, 9); for(int k = 0; k <= 3; k++) { inputs[i][l] = digits[getRand][k]; l += 1; } // k }else{ // j is odd; this is an operator getRand = getRandomNumber(0, 5); for(int k = 0; k <= 3; k++) { inputs[i][l] = operators[getRand][k]; l += 1; } // k } } // j } // i return; } // NOTE: The way I've designed the GetFitness function in this example, the computer will sometimes hang or // throw an "NaN" error message. // NaN means "not a number". This will often show up when a "divide-by-zero"-like error occurs while using // type Double variables (as opposed to integers). The way I've implemented this genetic algorithm, it will // sometimes weed out all but the one chromosome closest to the target, which leaves nothing but a whole // population of the exact same chromosome. And when there's no diversity, the algorithm will only be able // to generate "NaN" for fitness scores. void getFitness() { /* 'Renders errors into percentage of correctness. 'Lowest errors = 100% 'Less errors renders to higher percentage. 'More errors renders to lower percentage. 'Highest errors = 0% */ int bestScore, worstScore; // The worst score would be the one furthest from the Target. worstScore = abs(target - totals[maximum(totals)]); // The best would be the closest. bestScore = abs(target - totals[minimum(totals)]); // Convert to a weighted percentage. bestScore = worstScore - abs(target - totals[minimum(totals)]); for(int i = 0; i <= maxInputs - 1; i++) { fitness[i] = (worstScore - (abs(target - totals[i]))) * 100 / bestScore; } // i } void selection() { /* 'We start out with n individuals, and will stay with n. 'To do this, pick out the most fit, mate them, then replace the least fit 'with the new offspring. The parents will remain for the next 'population. Basically, the least fit are always being weeded out. */ int rouletteSpin; for(int i = 0; i <= maxInputs - 1; i++) { rouletteSpin = getRandomNumber(0, 100); if(fitness[i] >= rouletteSpin){ selected[i] = true; }else{ selected[i] = false; } } // i } void mating() { int pointer1, pointer2; int maxChild = 0; int canMate = 0; int cannotMate[maxInputs]; int parentA, parentB; int newChild[maxSize]; for(int i = 0; i <= maxInputs - 1; i++) { cannotMate[i] = -1; } //Determine total who can mate. pointer1 = 0; pointer2 = 0; for(int i = 0; i <= maxInputs - 1; i++) { if(selected[i] == true){ canMate += 1; // Copy selected individuals to next generation. for(int j = 0; j <= maxSize - 1; j++) { nextGen[pointer1][j] = inputs[i][j]; } // j pointer1 += 1; }else{ // Cannot mate. cannotMate[pointer2] = i; pointer2 += 1; } } // i maxChild = maxInputs - canMate; // Total number of offspring to be created. if(canMate > 1 && pointer2 > 0) { for(int i = 0; i <= maxChild - 1; i++) { parentA = chooseParent(); parentB = chooseParent(parentA); crossover(parentA, parentB, newChild); for(int j = 0; j <= maxSize - 1; j++) { nextGen[pointer1][j] = newChild[j]; } // j pointer1 += 1; } // i } } int chooseParent() { //Overloaded function, see also "ChooseParent(ByVal ParentA As Integer)". int parent; bool done = false; do { // Randomly choose an eligible parent. parent = getRandomNumber(0, maxInputs - 1); if(selected[parent] == true) { done = true; } }while(!done); return parent; } int chooseParent(int parentA) { //Overloaded function, see also "ChooseParent()". int parent; bool done = false; do { //Randomly choose an eligible parent. parent = getRandomNumber(0, maxInputs - 1); if(parent != parentA) { if(selected[parent] == true) { done = true; } } }while(!done); return parent; } void crossover(int chromA, int chromB, int newChrom[]) { // select a random gene along the length of the chromosomes and // swap all genes after that point. int randomPoint; // We want the point to be at a logical place, so that // valid operands and operators are kept intact. randomPoint = getRandomNumber(0, 8); randomPoint *= 4; for(int i = 0; i <= maxSize - 1; i++) { if(i < randomPoint){ newChrom[i] = inputs[chromA][i]; }else if(i >= randomPoint){ newChrom[i] = inputs[chromB][i]; } } // i } // Yeah, I know. Don't laugh at my extra large If...Else block. Some might think highly of the Switch command, but I'm really not a big fan of it. int decodeInput(int inputIndex) { /* Take a chromosome, decode it, evaluate it mathematically, and return the answer. Ignore the usual rules of algebraic evaluation, and simple go from left to right. */ int pointer; bool done = false; int operatr; int operand; double retMod; double total = 0.0; /* '0000 0000 0000 0000 0000 0000 0000 0000 0000 '0-3: operand '4-7: operator '8-11: operand '12-15: operator '16-19: operand '20-23: operator '24-27: operand '28-31: operator '32-35: operand */ pointer = 0; // Get first operand... for(int i = 3; i >= 0; i--) { //Convert from binary to decimal. total += inputs[inputIndex][pointer] * pow(2, i); pointer += 1; } // i done = false; do { //Get next operator... operatr = 0; for(int i = 3; i >= 0; i--) { // Convert from binary to decimal. operatr += inputs[inputIndex][pointer] * static_cast(pow(2, i)); pointer += 1; } // i // Get next operand... operand = 0; for(int i = 3; i >= 0; i--) { //Convert from binary to decimal. operand += inputs[inputIndex][pointer] * static_cast(pow(2, i)); pointer += 1; } // i if(operatr == 10 || operatr == 11){ // Addition total += operand; }else if(operatr == 12 || operatr == 13){ // Subtraction total -= operand; }else if(operatr == 14){ // Multiplication total *= operand; }else{ // Division if(operand != 0){ // Avoid divide-by-zero errors. total /= operand; } } if(pointer >= 35){ done = true; } }while(!done); // Round total to the nearest whole number. if(modf(total, &retMod) < 0.5){ total = floor(total); }else if(modf(total, &retMod) >= 0.5){ total = ceil(total); } return static_cast(total); } void prepNextEpoch() { //Copy next generation into current generation input. for(int i = 0; i <= maxInputs - 1; i++) { for(int j = 0; j <= maxSize - 1; j++) { inputs[i][j] = nextGen[i][j]; } // j } // i //Reset flags for selected individuals. for(int i = 0; i <= maxInputs - 1; i++) { selected[i] = false; } // i } int getRandomNumber(int low, int high) { //Generate random value between low and high (inclusive). return (rand() % ((high + 1) - low)) + low; } int minimum(int intArray[]) { // Returns an array index. int winner = 0; bool foundNewWinner; bool done = false; do { foundNewWinner = false; for(int i = 0; i <= maxInputs - 1; i++) { if(i != winner) // 'Avoid self-comparison. { // The minimum has to be in relation to the Target. if(abs(target - intArray[i]) < abs(target - intArray[winner])) { winner = i; foundNewWinner = true; } } } // i if(foundNewWinner == false) { done = true; } }while(!done); return winner; } int maximum(int intArray[]) { // Returns an array index. int winner = 0; bool foundNewWinner; bool done = false; do { foundNewWinner = false; for(int i = 0; i <= maxInputs - 1; i++) { if(i != winner) // 'Avoid self-comparison. { // The minimum has to be in relation to the Target. if(abs(target - intArray[i]) > abs(target - intArray[winner])) { winner = i; foundNewWinner = true; } } } // i if(foundNewWinner == false) { done = true; } }while(!done); return winner; }