main.js 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306
  1. import {render} from "./render.js";
  2. function rand_range(a, b) {
  3. return Math.random() * (b - a) + a;
  4. }
  5. function rand_normalish() {
  6. const r = Math.random() + Math.random() + Math.random() + Math.random();
  7. return (r / 4.0) * 2.0 - 1;
  8. }
  9. function lerp(x, a, b) {
  10. return x * (b - a) + a;
  11. }
  12. function clamp(x, a, b) {
  13. return Math.min(Math.max(x, a), b);
  14. }
  15. function sat(x) {
  16. return Math.min(Math.max(x, 0.0), 1.0);
  17. }
  18. class Population {
  19. constructor(params) {
  20. this._params = params;
  21. this._population = [...Array(this._params.population_size)].map(
  22. _ => ({fitness: 1, genotype: this._CreateRandomgenotype()}));
  23. this._lastGeneration = null;
  24. this._generations = 0;
  25. this._callback = null;
  26. }
  27. _CreateRandomGene() {
  28. return this._params.gene.ranges.map(r => rand_range(r[0], r[1]));
  29. }
  30. _CreateRandomgenotype() {
  31. return [...Array(this._params.genotype.size)].map(
  32. _ => this._CreateRandomGene());
  33. }
  34. Fittest() {
  35. return this._lastGeneration.parents[0];
  36. }
  37. async Run(srcData) {
  38. await render.setup(srcData);
  39. while (true) {
  40. await this._Step(srcData);
  41. }
  42. }
  43. async _Step(tgtImgData) {
  44. await this._StepPopulation(tgtImgData);
  45. const parents = this._population.sort((a, b) => (b.fitness - a.fitness));
  46. this._lastGeneration = {parents: parents};
  47. this._generations += 1;
  48. // Draw the main canvas on the worker while breeding next population.
  49. const cbPromise = this._callback(this, this._lastGeneration.parents[0]);
  50. this._population = this._BreedNewPopulation(parents);
  51. if (this._params.genotype.growth_per_increase > 0 ||
  52. this._params.genotype.size < this._params.genotype.max_size) {
  53. const increase = (
  54. (this._generations + 1) % this._params.genotype.generations_per_increase) == 0;
  55. if (increase) {
  56. const geneIncrease = this._params.genotype.growth_per_increase;
  57. this._params.genotype.size += geneIncrease;
  58. for (let i = 0; i < geneIncrease; i++) {
  59. for (let p of this._population) {
  60. p.genotype.push([...this._CreateRandomGene()]);
  61. }
  62. }
  63. }
  64. }
  65. await cbPromise;
  66. }
  67. async _StepPopulation(tgtImgData) {
  68. // Wait for them all to be done
  69. const promises = render.calculateFitnesses(
  70. this._params.gene.type, this._population.map(p => p.genotype));
  71. const responses = await Promise.all(promises);
  72. for (const r of responses) {
  73. for (const f of r.result) {
  74. this._population[f.index].fitness = f.fitness;
  75. }
  76. }
  77. }
  78. _BreedNewPopulation(parents) {
  79. function _RouletteSelection(sortedParents, totalFitness) {
  80. const roll = Math.random() * totalFitness;
  81. let sum = 0;
  82. for (let p of sortedParents) {
  83. sum += p.fitness;
  84. if (roll < sum) {
  85. return p;
  86. }
  87. }
  88. return sortedParents[sortedParents.length - 1];
  89. }
  90. function _RandomParent(sortedParents, otherParent, totalFitness) {
  91. const p = _RouletteSelection(sortedParents, totalFitness);
  92. return p;
  93. }
  94. function _CopyGenotype(g) {
  95. return ({
  96. fitness: g.fitness,
  97. genotype: [...g.genotype].map(gene => [...gene])
  98. });
  99. }
  100. const newPopulation = [];
  101. const totalFitness = parents.reduce((t, p) => t + p.fitness, 0);
  102. const numChildren = Math.ceil(parents.length * 0.8);
  103. const top = [...parents.slice(0, Math.ceil(parents.length * 0.25))];
  104. for (let j = 0; j < numChildren; j++) {
  105. const i = j % top.length;
  106. const p1 = top[i];
  107. const p2 = _RandomParent(parents, p1, totalFitness);
  108. const g = [];
  109. for (let r = 0; r < p1.genotype.length; r++ ) {
  110. const roll = Math.random();
  111. g.push(roll < 0.5 ? p1.genotype[r] : p2.genotype[r]);
  112. }
  113. newPopulation.push(_CopyGenotype({fitness: 1, genotype: g}));
  114. }
  115. // Let's say keep top X% go through, but with mutations
  116. const top5 = [...parents.slice(0, Math.ceil(parents.length * 0.05))];
  117. newPopulation.push(...top5.map(x => _CopyGenotype(x)));
  118. // Mutations!
  119. for (let p of newPopulation) {
  120. const genotypeLength = p.genotype.length;
  121. const mutationOdds = this._params.mutation.odds;
  122. const mutationMagnitude = this._params.mutation.magnitude;
  123. const mutationDecay = this._params.mutation.decay;
  124. function _Mutate(x, i) {
  125. const roll = Math.random();
  126. if (roll < mutationOdds) {
  127. const xi = genotypeLength - i;
  128. const mutationMod = Math.E ** (-1 * xi * mutationDecay);
  129. if (mutationMod <= 0.0001) {
  130. return x;
  131. }
  132. const magnitude = mutationMagnitude * mutationMod * rand_normalish();
  133. return sat(x + magnitude);
  134. }
  135. return x;
  136. }
  137. p.genotype = p.genotype.map(
  138. (g, i) => g.map(
  139. (x, xi) => _Mutate(x, i)));
  140. }
  141. // Immortality granted to the winners from the last life. May the odds be
  142. // forever in your favour.
  143. newPopulation.push(...top5.map(x => _CopyGenotype(x)));
  144. // Create a bunch of random crap to fill out the rest.
  145. while (newPopulation.length < parents.length) {
  146. newPopulation.push(
  147. {fitness: 1, genotype: this._CreateRandomgenotype()});
  148. }
  149. return newPopulation;
  150. }
  151. }
  152. class GeneticAlgorithmDemo {
  153. constructor() {
  154. this._Init();
  155. }
  156. _Init(scene) {
  157. this._statsText1 = document.getElementById('statsText');
  158. this._statsText2 = document.getElementById('numbersText');
  159. this._sourceImg = document.getElementById('sourceImg');
  160. this._sourceImg.src = 'assets/square.jpg';
  161. this._sourceImg.onload = () => {
  162. const ctx = this._sourceCanvas.getContext('2d');
  163. this._sourceCanvas.width = 128;
  164. this._sourceCanvas.height = this._sourceCanvas.width * (
  165. this._sourceImg.height / this._sourceImg.width);
  166. ctx.drawImage(
  167. this._sourceImg,
  168. 0, 0, this._sourceImg.width, this._sourceImg.height,
  169. 0, 0, this._sourceCanvas.width, this._sourceCanvas.height);
  170. this._sourceLODData = ctx.getImageData(
  171. 0, 0, this._sourceCanvas.width, this._sourceCanvas.height);
  172. this._sourceCanvas.width = 800;
  173. this._sourceCanvas.height = this._sourceCanvas.width * (
  174. this._sourceImg.height / this._sourceImg.width);
  175. this._targetCanvas.width = this._sourceCanvas.width;
  176. this._targetCanvas.height = this._sourceCanvas.height;
  177. ctx.drawImage(
  178. this._sourceImg,
  179. 0, 0, this._sourceImg.width, this._sourceImg.height,
  180. 0, 0, this._sourceCanvas.width, this._sourceCanvas.height);
  181. this._InitPopulation();
  182. };
  183. this._sourceCanvas = document.getElementById('source');
  184. this._targetCanvas = document.getElementById('target');
  185. }
  186. _InitPopulation() {
  187. const GENE_ELLIPSE = {
  188. type: 'ellipse',
  189. ranges: [
  190. [0, 1],
  191. [0, 1],
  192. [0, 1],
  193. [0.01, 0.1],
  194. [0, 1],
  195. [0, 1],
  196. [0.05, 0.5],
  197. [0, 1],
  198. ]
  199. };
  200. const GENE_LINE = {
  201. type: 'line',
  202. ranges: [
  203. [0, 1],
  204. [0, 1],
  205. [0, 1],
  206. [0.05, 0.2],
  207. [0, 1],
  208. [0, 1],
  209. [0, 1],
  210. [0, 1],
  211. [0, 1],
  212. ]
  213. };
  214. const params = {
  215. population_size: 512,
  216. genotype: {
  217. size: 64,
  218. max_size: 1000,
  219. generations_per_increase: 50,
  220. growth_per_increase: 1
  221. },
  222. gene: GENE_LINE,
  223. mutation: {
  224. magnitude: 0.25,
  225. odds: 0.1,
  226. decay: 0,
  227. }
  228. };
  229. this._population = new Population(params);
  230. this._population._callback = async (population, fittest) => {
  231. const p1 = render.draw(
  232. population._params.gene.type, fittest.genotype,
  233. this._targetCanvas.width, this._targetCanvas.height);
  234. const hd = await p1;
  235. const ctx = this._targetCanvas.getContext('2d');
  236. ctx.putImageData(hd.result.imageData, 0, 0);
  237. this._statsText2.innerText =
  238. this._population._generations + '\n' +
  239. this._population.Fittest().fitness.toFixed(3) + '\n' +
  240. this._population._population.length + '\n' +
  241. this._population._params.genotype.size;
  242. };
  243. this._population.Run(this._sourceLODData);
  244. this._statsText1.innerText =
  245. 'Generation:\n' +
  246. 'Fitness:\n' +
  247. 'Population:\n' +
  248. 'Genes:';
  249. }
  250. }
  251. const _DEMO = new GeneticAlgorithmDemo();