Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2016
215
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5. #include <unistd.h>
  6. #include <sys/select.h>
  7. #include <termios.h>
  8. #include <ctype.h>
  9. #include <math.h>
  10.  
  11. // adjustable parameters
  12. #define POPULATION_SIZE 50000 // total population size
  13. #define NUM_SURVIVORS 1 // number of survivors per generation (must be less than POPULATION_SIZE)
  14. #define GENOME_LEN 28 // number of loci in each genome (each locus is one character)
  15. #define MUTATION_RATE 0.01 // probability that a locus is mutated per generation
  16. #define SELECTION_COEFF 5.0 // selection coefficient
  17. #define DISPLAY_INTERVAL 10 // display results every n generations, where n == DISPLAY_INTERVAL
  18. #define PAUSE_TIME 50000 // pause time in microseconds
  19. #define GENOMES_TO_DISPLAY 1 // in STEP_MODE, number of genomes to display at each step
  20. #define STEP_MODE 1 // if set, program will pause every n generations and display the genomes
  21. #define ENABLE_LATCHING 0 // if set, enable latching
  22. #define ENABLE_SELECTION 1 // if set, enable selection; otherwise, select survivors with no bias
  23.  
  24. #define CHARSET_SIZE 27 // 26 uppercase letters plus the space character
  25. #define NUM_LINES 300 // number of lines in the program's display "window"
  26. #define CHARS_PER_LINE 120 // for each line in the "window"
  27.  
  28. long long generation; // generation count
  29. long long histogram[GENOME_LEN+1]; // histogram of Hamming distance from the target
  30. double mutation_rate;
  31. double selection_coefficient;
  32. char buffer[20];
  33.  
  34. // A genome consists of an array of loci, the associated fitness value, and a field indicating the number of matches
  35. // between the genome and the target phrase.
  36. typedef struct {
  37. char locus[GENOME_LEN];
  38. double fitness;
  39. int matches;
  40. } genome_t;
  41.  
  42. genome_t target; // target phrase
  43. genome_t genome_array[POPULATION_SIZE]; // genomes of all members of the population
  44.  
  45. char weasel_to_ascii(char c) {
  46. switch(c) {
  47. case 0: return ' ';
  48. case 1: return 'A';
  49. case 2: return 'B';
  50. case 3: return 'C';
  51. case 4: return 'D';
  52. case 5: return 'E';
  53. case 6: return 'F';
  54. case 7: return 'G';
  55. case 8: return 'H';
  56. case 9: return 'I';
  57. case 10: return 'J';
  58. case 11: return 'K';
  59. case 12: return 'L';
  60. case 13: return 'M';
  61. case 14: return 'N';
  62. case 15: return 'O';
  63. case 16: return 'P';
  64. case 17: return 'Q';
  65. case 18: return 'R';
  66. case 19: return 'S';
  67. case 20: return 'T';
  68. case 21: return 'U';
  69. case 22: return 'V';
  70. case 23: return 'W';
  71. case 24: return 'X';
  72. case 25: return 'Y';
  73. case 26: return 'Z';
  74. }
  75. }
  76.  
  77. char ascii_to_weasel(char c) {
  78. switch(c) {
  79. case ' ': return 0;
  80. case 'A': return 1;
  81. case 'B': return 2;
  82. case 'C': return 3;
  83. case 'D': return 4;
  84. case 'E': return 5;
  85. case 'F': return 6;
  86. case 'G': return 7;
  87. case 'H': return 8;
  88. case 'I': return 9;
  89. case 'J': return 10;
  90. case 'K': return 11;
  91. case 'L': return 12;
  92. case 'M': return 13;
  93. case 'N': return 14;
  94. case 'O': return 15;
  95. case 'P': return 16;
  96. case 'Q': return 17;
  97. case 'R': return 18;
  98. case 'S': return 19;
  99. case 'T': return 20;
  100. case 'U': return 21;
  101. case 'V': return 22;
  102. case 'W': return 23;
  103. case 'X': return 24;
  104. case 'Y': return 25;
  105. case 'Z': return 26;
  106. }
  107. }
  108.  
  109. // Swap two genomes given their indices.
  110. void swap_genomes(int g1, int g2) {
  111. genome_t temp_genome;
  112. if (g1 == g2) {
  113. return;
  114. } else {
  115. temp_genome = genome_array[g1];
  116. genome_array[g1] = genome_array[g2];
  117. genome_array[g2] = temp_genome;
  118. }
  119. }
  120.  
  121. // Thoroughly and randomly scramble the population within the genome array.
  122. void scramble_genomes() {
  123. for (int i=0; i<6; i++) {
  124. for (int j=0; j<POPULATION_SIZE; j++) {
  125. swap_genomes(j, rand()%POPULATION_SIZE);
  126. }
  127. }
  128. }
  129.  
  130. // Calculate a genome's fitness by determining the number of loci at which
  131. // it matches the target, then applying the formula (1+s)^m where s is the selection
  132. // coefficient and m is the number of matches.
  133. double fitness(genome_t *genome) {
  134. genome->matches = 0;
  135.  
  136. // scan the entire genome, counting the number of loci that match the target
  137. for (int i=0; i < GENOME_LEN; i++) {
  138. if (genome->locus[i] == target.locus[i]) ++genome->matches;
  139. }
  140.  
  141. return pow(1.0+selection_coefficient, genome->matches);
  142. }
  143.  
  144. // Display a genome as a character string.
  145. void display_genome(genome_t *genome) {
  146. for (int i=0; i < GENOME_LEN; i++) {
  147. putchar(weasel_to_ascii(genome->locus[i]));
  148. }
  149. }
  150.  
  151. // Convert an ascii string to a Weasel genome
  152. void weaselize (char *ascii_str, genome_t *genome) {
  153. for (int i=0; i<GENOME_LEN; i++) {
  154. genome->locus[i] = ascii_to_weasel(ascii_str[i]);
  155. }
  156. }
  157.  
  158. // Move cursor to the home position
  159. void cursor_home() {
  160. printf("\x1b[H");
  161. }
  162.  
  163. // Overwrite everything on the screen with spaces
  164. void clear_screen() {
  165. cursor_home();
  166. for (int i=0; i < NUM_LINES; i++) {
  167. for (int j=0; j < CHARS_PER_LINE; j++) {
  168. putchar(' ');
  169. }
  170. printf("\n\r");
  171. }
  172. }
  173.  
  174. // Mutate 'old' genome, placing results in 'new'
  175. void mutate(genome_t *old, genome_t *new) {
  176. for (int i=0; i < GENOME_LEN; i++) {
  177. if ((double)rand()/(double)RAND_MAX < mutation_rate * 27.0/26.0 && (!ENABLE_LATCHING || old->locus[i] != target.locus[i])) {
  178. new->locus[i] = (char)(rand()%CHARSET_SIZE); // mutate this locus
  179. } else {
  180. new->locus[i] = old->locus[i]; // don't mutate
  181. }
  182. }
  183. new->fitness = fitness(new);
  184. }
  185.  
  186. // Initialize a genome with a random string
  187. void init_genome_rand(genome_t *genome) {
  188. for (int i=0; i < GENOME_LEN; i++) {
  189. genome->locus[i] = (char)(rand()%CHARSET_SIZE);
  190. }
  191. genome->fitness = fitness(genome);
  192. }
  193.  
  194. // Comparison function for use by qsort() library routine
  195. int compare_fitness (const void * elem1, const void * elem2) {
  196. if (((genome_t *)elem2)->fitness > ((genome_t *)elem1)->fitness) return 1;
  197. if (((genome_t *)elem2)->fitness == ((genome_t *)elem1)->fitness) return 0;
  198. return -1;
  199. }
  200.  
  201. // Use weighted random selection to choose offspring for the survivor slots
  202. void pick_survivors() {
  203.  
  204. double total_fitness = 0.0;
  205. double cumulative_fitness;
  206. double rand_num;
  207. int j;
  208.  
  209. // add up all fitnesses
  210. for (int i=0; i<POPULATION_SIZE; i++) {
  211. total_fitness += genome_array[i].fitness;
  212. }
  213.  
  214. // for each survivor slot
  215. for (int i=0; i<NUM_SURVIVORS; i++) {
  216.  
  217. cumulative_fitness = 0.0;
  218.  
  219. // generate a random number in the range 0-total_fitness
  220. rand_num = (double)rand()/(double)RAND_MAX * total_fitness;
  221.  
  222. // from the remaining offspring, select the one whose range is hit by the random number
  223. for (j=i; j<POPULATION_SIZE; j++) {
  224. cumulative_fitness += genome_array[j].fitness;
  225. if (cumulative_fitness >= rand_num) {
  226. break;
  227. }
  228. }
  229.  
  230. // swap it with the one in the survivor slot
  231. swap_genomes(i,j);
  232.  
  233. // adjust the total fitness to reflect only the remaining offspring
  234. total_fitness -= genome_array[j].fitness;
  235. }
  236. }
  237.  
  238. void display_histogram() {
  239. long long max = 0;
  240. long long width;
  241.  
  242. printf("Histogram of Hamming distances:\n\n\r");
  243.  
  244. for (int i=0; i<=GENOME_LEN; i++) {
  245. if (histogram[i] > max) {
  246. max = histogram[i];
  247. }
  248. }
  249.  
  250. if (max > 0) {
  251. for (int i=0; i<=GENOME_LEN; i++) {
  252. printf("%2d: %8lld ", i, histogram[i]);
  253. width = 60 * histogram[i]/max;
  254. for (int j=0; j<width; j++) {
  255. printf("X");
  256. }
  257. printf("\n\r");
  258. }
  259. }
  260. printf("\n\r");
  261. }
  262.  
  263. //
  264. // From http://stackoverflow.com/questions/448944/c-non-blocking-keyboard-input
  265. //
  266.  
  267. struct termios orig_termios;
  268.  
  269. void reset_terminal_mode()
  270. {
  271. tcsetattr(0, TCSANOW, &orig_termios);
  272. }
  273.  
  274. void set_conio_terminal_mode()
  275. {
  276. struct termios new_termios;
  277.  
  278. /* take two copies - one for now, one for later */
  279. tcgetattr(0, &orig_termios);
  280. memcpy(&new_termios, &orig_termios, sizeof(new_termios));
  281.  
  282. /* register cleanup handler, and set the new terminal mode */
  283. atexit(reset_terminal_mode);
  284. cfmakeraw(&new_termios);
  285. tcsetattr(0, TCSANOW, &new_termios);
  286. }
  287.  
  288. int kbhit()
  289. {
  290. struct timeval tv = { 0L, 0L };
  291. fd_set fds;
  292. FD_ZERO(&fds);
  293. FD_SET(0, &fds);
  294. return select(1, &fds, NULL, NULL, &tv);
  295. }
  296.  
  297. int getch()
  298. {
  299. int r;
  300. unsigned char c;
  301. if ((r = read(0, &c, sizeof(c))) < 0) {
  302. return r;
  303. } else {
  304. return c;
  305. }
  306. }
  307.  
  308. // Read a double-precision floating point number from keyboard input.
  309. // Can't use scanf here because of the non-blocking I/O.
  310. void get_double(double *ptr) {
  311. int i = 0;
  312. char c;
  313. do {
  314. while (!kbhit()) { // wait for keystroke
  315. ;
  316. }
  317. c = getch();
  318. putchar(c);
  319. fflush(stdout);
  320. buffer[i++] = c;
  321. } while (buffer[i-1] != '\r'); // accumulate characters in buffer until CR
  322. buffer[i-1] = '\n';
  323. i=0;
  324. fflush(stdout);
  325. sscanf(buffer, "%lf", ptr);
  326. }
  327.  
  328. int main() {
  329.  
  330. int i;
  331. int selection_enabled = ENABLE_SELECTION;
  332. char ascii_target[GENOME_LEN+1];
  333. char c;
  334.  
  335. set_conio_terminal_mode();
  336.  
  337. printf("\n\n\n\n\r");
  338.  
  339. // set cursor to home position, clear screen, and rehome
  340. clear_screen();
  341. cursor_home();
  342.  
  343. // seed the random number generator with the current time
  344. srand(time(NULL));
  345.  
  346. // set up ascii version of initial fitness target
  347. ascii_target[0] = 'M';
  348. ascii_target[1] = 'E';
  349. ascii_target[2] = 'T';
  350. ascii_target[3] = 'H';
  351. ascii_target[4] = 'I';
  352. ascii_target[5] = 'N';
  353. ascii_target[6] = 'K';
  354. ascii_target[7] = 'S';
  355. ascii_target[8] = ' ';
  356. ascii_target[9] = 'I';
  357. ascii_target[10] = 'T';
  358. ascii_target[11] = ' ';
  359. ascii_target[12] = 'I';
  360. ascii_target[13] = 'S';
  361. ascii_target[14] = ' ';
  362. ascii_target[15] = 'L';
  363. ascii_target[16] = 'I';
  364. ascii_target[17] = 'K';
  365. ascii_target[18] = 'E';
  366. ascii_target[19] = ' ';
  367. ascii_target[20] = 'A';
  368. ascii_target[21] = ' ';
  369. ascii_target[22] = 'W';
  370. ascii_target[23] = 'E';
  371. ascii_target[24] = 'A';
  372. ascii_target[25] = 'S';
  373. ascii_target[26] = 'E';
  374. ascii_target[27] = 'L';
  375.  
  376. // set up weasel version of the fitness target
  377. weaselize(ascii_target, &target);
  378.  
  379. // randomly initialize the genomes of the entire population
  380. for (i=0; i < POPULATION_SIZE; i++) {
  381. init_genome_rand(&genome_array[i]);
  382. }
  383. printf("\n\n\rInitial Organism 0 Genome:\n\n\r");
  384. display_genome(&genome_array[0]);
  385. printf("\n\n\n\r");
  386.  
  387. generation = 0;
  388. mutation_rate = MUTATION_RATE;
  389. selection_coefficient = SELECTION_COEFF;
  390.  
  391. // initialize the histogram to zeroes
  392. for (int i=0; i<=GENOME_LEN; i++) {
  393. histogram[i] = 0;
  394. }
  395.  
  396. while (1) {
  397.  
  398. // preserve the survivors, but convert the rest into mutated copies of the survivors
  399. for (i=0; i < POPULATION_SIZE - NUM_SURVIVORS; i++) {
  400. mutate(&genome_array[i%NUM_SURVIVORS], &genome_array[i+NUM_SURVIVORS]);
  401. }
  402.  
  403. // now mutate the survivors themselves
  404. for (i=0; i<NUM_SURVIVORS; i++) {
  405. mutate(&genome_array[i], &genome_array[i]);
  406. }
  407.  
  408. if (selection_enabled) {
  409. // use weighted random selection to choose offspring for the survivor slots
  410. pick_survivors();
  411. } else {
  412. // randomly scramble the genome array
  413. scramble_genomes();
  414. }
  415.  
  416. ++histogram[GENOME_LEN-genome_array[0].matches];
  417.  
  418. ++generation;
  419.  
  420. // in step mode, pause and display all genomes periodically
  421. if (STEP_MODE && generation % DISPLAY_INTERVAL == 0) {
  422. clear_screen();
  423. cursor_home();
  424. printf("\n\rTarget Phrase: ");
  425. printf("%s", ascii_target);
  426. printf("\n\n\rGeneration: %lld\n\r", generation);
  427. printf("\n\rSelection: %s Coefficient: %1.2lf Mutation rate: %1.2lf\n\n\r", selection_enabled ? "ON" : "OFF", selection_coefficient, mutation_rate);
  428. for (i = 0; i < GENOMES_TO_DISPLAY; i++) {
  429. printf("Organism %d Fitness %1.2le Hamming distance %d\n\n\r", i, genome_array[i].fitness, GENOME_LEN-genome_array[0].matches);
  430. display_genome(&genome_array[i]);
  431. printf("\r\n\n");
  432. }
  433. display_histogram();
  434. usleep(PAUSE_TIME); // pause briefly before continuing
  435. }
  436.  
  437. if (!STEP_MODE && generation % DISPLAY_INTERVAL == 0) {
  438. printf("generation = %lld fitness = %1.2le Hamming distance = %d\n\r", generation, genome_array[0].fitness, GENOME_LEN-genome_array[0].matches);
  439. }
  440.  
  441. if (kbhit()) { // keystroke detected
  442. switch(getch()) {
  443.  
  444. case 'c': // clear the histogram
  445. for (int i=0; i<=GENOME_LEN; i++) {
  446. histogram[i] = 0;
  447. }
  448. break;
  449.  
  450. case 'f': // change the selection coefficient
  451. printf("Enter new selection coefficient: ");
  452. fflush(stdout);
  453. get_double(&selection_coefficient);
  454. break;
  455.  
  456. case 'h': // print help message
  457. printf("Commands:\r\n");
  458. printf(" c - clear the histogram data\r\n");
  459. printf(" f - change the selection coefficient\r\n");
  460. printf(" h - print this help message\r\n");
  461. printf(" m - change the mutation rate\r\n");
  462. printf(" p - pause until a key is pressed\r\n");
  463. printf(" q - quit the program\r\n");
  464. printf(" s - toggle selection on/off\r\n");
  465. printf(" t - change the target phrase\r\n");
  466. printf("\r\nHit any key to continue\r\n");
  467. while(!kbhit()){
  468. ;
  469. }
  470. (void)getch(); // consume character
  471. break;
  472.  
  473. case 'm': // change the mutation rate
  474. printf("Enter new mutation rate: ");
  475. fflush(stdout);
  476. get_double(&mutation_rate);
  477. break;
  478.  
  479. case 'p': // pause until next keystroke
  480. printf("Paused: Hit any key to continue\r\n");
  481. while(!kbhit()){
  482. ;
  483. }
  484. (void)getch(); // consume character
  485. break;
  486.  
  487. case 'q': // quit the program
  488. exit(0);
  489.  
  490. case 's': // toggle selection on and off
  491. selection_enabled = !selection_enabled;
  492. break;
  493.  
  494. case 't': // set new target phrase
  495. printf("Enter new target phrase (spaces and letters only): ");
  496. fflush(stdout);
  497. i = 0;
  498. do {
  499. while (!kbhit()) { // wait for keystroke
  500. ;
  501. }
  502. c = toupper(getch());
  503. if (c == '\r') break;
  504. if (isalpha(c) || c == ' ') {
  505. putchar(c);
  506. fflush(stdout);
  507. ascii_target[i++] = c; // add character to target phrase
  508. }
  509. } while (ascii_target[i-1] != '\r' && i-1 < GENOME_LEN);
  510. for(; i<GENOME_LEN; i++) {
  511. ascii_target[i] = ' '; // pad remainder of target with spaces
  512. }
  513. weaselize(ascii_target, &target);
  514. // need to recompute fitness values because the target has changed
  515. for (i=0; i<POPULATION_SIZE; i++) {
  516. genome_array[i].fitness = fitness(&genome_array[i]);
  517. }
  518. break;
  519. }
  520. }
  521. }
  522.  
  523. printf("\n\n\rFinal generation = %lld fitness = %1.2le Hamming distance = %d\n\r", generation, genome_array[0].fitness, GENOME_LEN-genome_array[0].fitness);
  524. printf("\n\rFinal genome:\n\n\r");
  525. display_genome(&genome_array[0]);
  526. printf("\n\n\r");
  527. tcsetattr(0, TCSANOW, &orig_termios);
  528. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement