In what will hopefully be an ongoing feature, I am posting a small exploration into an area of computer science. I’ve been interested in genetic algorithms for a while, and decided to try my hand at one. Read on to see what I learned.
Starting with the tutorial at AI Junkie, I began working on a simple genetic algorithm. I used the proposed exercise, to find an equation that results in a given number. I cleaned up the example spec a bit, and added support for a unary minus to allow negative numbers.
More importantly, I learned a few interesting things. For one, we’re really talking about a large population for this example, I ended up using 20,000 population members over 100,000 generations. Even so, because of the nature of this problem, there are large gaps in the solution space, so most solutions, if they are found, are discovered in less than 500 generations. I also found it better, when doing chromosome crossovers, to break on the edge of operators, rather than at any random point, and I also discovered that for this problem, a good mutation rate helps, but if it’s too high, solutions with a high fitness score may mutate into uselessness. Perhaps the digital equivalent of my population living near Chernobyl or Fukushima… I guess that rules out any chance of X-Men for now.
I think that the most important things to take away from this exercise are that in order to use a genetic algorithm, you need a deep understanding of the problem, and what constitutes a good solution. It would also help to have a better formula for determining fitness, in this case. For this problem, the weight of individual genes is not equal, and not even position dependent. This is due to the nature of arithmetic. Multiplication and division will have a larger impact on the result of an equation than addition or subtraction, given the same operands. Therefore a chromosome could be nearly a solution, but with a mutation in the wrong place, it becomes totally unfit, where a similar mutation in a different position would have made it a perfect match.
Following is the code:
|
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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 |
#include <iostream> #include <stdlib.h> #include <time.h> #include <stdint.h> #define STARTING_POPULATION 20000 #define MAX_GENERATIONS 100000 #define OUT_OF_RANGE 200000000.0 // 200000000 is larger than any number that can be expressed by a chromosome // making it a good return value for any invalid chromosome, as it's further // from the target than any valid chromosome can be, including +- difference. #define CROSSOVER_RATE 0.7 #define MUTATION_RATE 0.005 // Starting rate was 0.001 #define CHROMOSOME_TYPE uint32_t #define PLUS 10 #define MINUS 11 #define TIMES 12 #define DIVIDE 13 #define INVALID > 13 float eval(int operation, float total, float current, float mult) { switch(operation) { case PLUS: total += current * mult; break; case MINUS: total -= current * mult; break; case TIMES: total *= current * mult; break; case DIVIDE: total /= current * mult; break; } return total; } float parse(CHROMOSOME_TYPE chromosome) { int state = 0; float total = 0.0; // since the first code we'll accept is a number, we can add it to zero to get started float mult = 1.0; // Multiplier to handle unary - float current = 0.0; // Holds number we're working on as we build it from digits int operation = PLUS; // start with addition operation CHROMOSOME_TYPE mask = 0xf; CHROMOSOME_TYPE chunk; for(int i = 0; i < sizeof(CHROMOSOME_TYPE) * 2; i++) { chunk = (chromosome & mask) >> (4 * i); switch(state) { case 0: // Looking for the start of a valid number, 0-9 or unary - if(chunk < 10) { state = 2; current = (float)chunk; if(i == (sizeof(CHROMOSOME_TYPE) * 2) - 1) // We're at the end of the chromosome { total = eval(operation, total, current, mult); } } else if(chunk == MINUS) { state = 1; mult = -1.0; } else { return OUT_OF_RANGE; } break; case 1: // We had a unary -, the next digit must be a number if(chunk < 10) { state = 2; current = (float)chunk; } else { return OUT_OF_RANGE; } break; case 2: // We're building a number, stop when we encounter the end of the chromosome or an operator if(chunk < 10) { current = (current * 10.0) + (float)chunk; if(i == (sizeof(CHROMOSOME_TYPE) * 2) - 1) // We're at the end of the chromosome { total = eval(operation, total, current, mult); } } else if(chunk INVALID) // Consider chromosome ended if we encounter a bad gene { total = eval(operation, total, current, mult); return total; } else // Operator encountered { if(i == (sizeof(CHROMOSOME_TYPE) * 2) - 1) // We're at the end of the chromosome { return OUT_OF_RANGE; } else { state = 0; total = eval(operation, total, current, mult); operation = chunk; mult = 1.0; } } break; default: // Anything else would be invalid return OUT_OF_RANGE; break; } mask = mask << 4; } return total; } void printChromosome(CHROMOSOME_TYPE chromosome) { std::cout << "Solution found: "; CHROMOSOME_TYPE mask = 0xf; CHROMOSOME_TYPE chunk; for(int i = 0; i < sizeof(CHROMOSOME_TYPE) * 2; i++) { chunk = (chromosome & mask) >> (4 * i); if(chunk < 10) { std::cout << chunk << " "; } else if(chunk == 10) { std::cout << "+ "; } else if(chunk == 11) { std::cout << "- "; } else if(chunk == 12) { std::cout << "* "; } else if(chunk == 13) { std::cout << "/ "; } else { std::cout << std::endl; return; } mask = mask << 4; } std::cout << std::endl; } int main(int argc, char* argv[]) { int generations = 1; bool solutionFound = false; // Check to see if we have a target value if(argc != 2) { std::cerr << "Please provide the target value." << std::endl; return 1; } // Store the target float target = atof(argv[1]); std::cout << "Searching for a solution of " << target << " with a population of " << STARTING_POPULATION << " in at most " << MAX_GENERATIONS << " generations." << std::endl; // Generate the starting set of chromosomes CHROMOSOME_TYPE population[STARTING_POPULATION]; srand(time(0)); for(int i = 0; i < STARTING_POPULATION; i++) { population[i] = rand() + rand(); } // Check the fitness of our population members float fitness[STARTING_POPULATION]; float fit; for(int i = 0; i < STARTING_POPULATION; i++) { fit = parse(population[i]); if(fit == target) { std::cout << "In initial population:" << std::endl; printChromosome(population[i]); fitness[i] = 0.0; solutionFound = true; } else { fitness[i] = 1.0 / (target - fit); } } while(!solutionFound) { for(int j = 0; j < STARTING_POPULATION; j++) { if(fitness[j] != 0.0) { CHROMOSOME_TYPE mother, father; float select = ((float)(rand() / RAND_MAX) / 2.0) + 0.5; for(int k = rand() % STARTING_POPULATION; k < STARTING_POPULATION; k++) { // Find the first candidate that meets or exceeds our selection threshhold // Starting at a random point in the population // If no suitable mate found, select any random member if(fitness[k] >= select) { mother = population[k]; k = STARTING_POPULATION; } else if(k == STARTING_POPULATION - 1) { mother = population[rand() % STARTING_POPULATION]; } } for(int k = rand() % STARTING_POPULATION; k < STARTING_POPULATION; k++) { if(fitness[k] >= select) { father = population[k]; k = STARTING_POPULATION; } else if(k == STARTING_POPULATION - 1) { father = population[rand() % STARTING_POPULATION]; } } float crossover = rand() / RAND_MAX; if(crossover < CROSSOVER_RATE) { int slicePoint = (rand() % (sizeof(CHROMOSOME_TYPE) * 2)) * 4; CHROMOSOME_TYPE leftMask, rightMask; leftMask = 0xffffffff << slicePoint; rightMask = 0xffffffff >> slicePoint; population[j] = (mother & leftMask) | (father & rightMask); } float mutate = rand() / RAND_MAX; if(mutate < MUTATION_RATE) { int mutationPoint = rand() % (sizeof(CHROMOSOME_TYPE) * 8); population[j] ^= (1 << mutationPoint); } } } // Check the fitness of our population members for(int i = 0; i < STARTING_POPULATION; i++) { fit = parse(population[i]); if(fit == target) { std::cout << "In generation " << generations << ":" << std::endl; printChromosome(population[i]); fitness[i] = 0.0; solutionFound = true; } else { fitness[i] = 1.0 / (target - fit); } } generations++; if(generations > MAX_GENERATIONS) { std::cout << "No solution found within generation limit of " << MAX_GENERATIONS << "." << std::endl; solutionFound = true; } } return 0; } |