Created
February 22, 2016 19:43
-
-
Save ken210/d0def07d8b44e0efbcc4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Using genetic algorithim | |
| Given an array of integers, say [-2, 9, 2, -5, 1, -3, -10, 6] | |
| Find a sum of elements that is closest to 0 | |
| This solution finds the best solution on 100 rounds. | |
| The best solution is the Gene with it's defect closest to 0, | |
| with the maximum number of elements included, | |
| found on the earliest round possible | |
| */ | |
| function rand (num) { | |
| if (!num) { | |
| num = 1; | |
| } | |
| return Math.floor(Math.random() * num); | |
| } | |
| var NUMBERS_ARRAY_SIZE = 10; | |
| var NUMBERS = (function () { | |
| var arr = []; | |
| for (var i = 0; i < NUMBERS_ARRAY_SIZE; i++) { | |
| arr.push(rand(10) * [1, -1][rand(2)]); | |
| } | |
| return arr; | |
| }()); | |
| var GENE_LENGTH = NUMBERS.length; | |
| var POPULATION_LENGTH = 20; | |
| var SELECT_CUT = 1 / 2; | |
| var ROUNDS = 100; | |
| function Gene (seq, currentRound) { | |
| this.seq = seq; | |
| if (this.seq == null) { | |
| this.seq = []; | |
| for (var i = 0; i < GENE_LENGTH; i++) { | |
| this.seq.push([1, 0][rand(2)]); | |
| } | |
| } | |
| if (currentRound == null) { | |
| currentRound = 0; | |
| } | |
| var sum = 0; | |
| var totalIns = 0; | |
| for (var i = 0; i < GENE_LENGTH; i++) { | |
| if (this.seq[i]) { | |
| sum += NUMBERS[i]; | |
| totalIns += 1; | |
| } | |
| } | |
| this.defect = sum; | |
| this.totalIns = totalIns; | |
| this.round = currentRound; | |
| } | |
| Gene.prototype.compareTo = function (otherGene) { | |
| if (Math.abs(this.defect) < Math.abs(otherGene.defect)) { | |
| return -1; | |
| } | |
| if (Math.abs(this.defect) > Math.abs(otherGene.defect)) { | |
| return 1; | |
| } | |
| if (Math.abs(this.defect) === Math.abs(otherGene.defect)) { | |
| if (this.totalIns > otherGene.totalIns) { | |
| return -1; | |
| } | |
| if (this.totalIns < otherGene.totalIns) { | |
| return 1; | |
| } | |
| } | |
| return 0; | |
| }; | |
| Gene.prototype.reproduceWith = function (otherGene) { | |
| var halfLength = Math.floor(this.seq.length / 2); | |
| var firstHalf = this.seq.slice(0, halfLength); | |
| var lastHalf = otherGene.seq.slice(halfLength); | |
| return new Gene(firstHalf.concat(lastHalf), this.round + 1); | |
| }; | |
| function Population () { | |
| this.members = []; | |
| this.bestGene = null; | |
| } | |
| Population.prototype.generate = function () { | |
| // random initial population | |
| for (var i = 0; i < POPULATION_LENGTH; i++) { | |
| var gene = new Gene(); | |
| this.members.push(gene); | |
| } | |
| }; | |
| Population.prototype.sort = function () { | |
| this.members.sort(function (a, b) { | |
| return a.compareTo(b); | |
| }); | |
| if (this.bestGene == null) { | |
| this.bestGene = this.members[0]; | |
| return; | |
| } | |
| if (this.members[0].compareTo(this.bestGene)) { | |
| this.bestGene = this.members[0]; | |
| } | |
| }; | |
| Population.prototype.select = function () { | |
| // select best genes | |
| var selected = []; | |
| for (var i = 0; i < POPULATION_LENGTH * SELECT_CUT; i++) { | |
| selected.push(this.members[i]); | |
| } | |
| this.members = selected; | |
| }; | |
| Population.prototype.reproduce = function () { | |
| // get the best individual, reproduce it with the second best, third and so on | |
| // if it doesn't fill the initial population, do the same with the second, and so on | |
| var firstParentIdx = 0; | |
| var secondParentIdx = 1; | |
| var newMembers = []; | |
| for (var i = 0; i < POPULATION_LENGTH; i++) { | |
| newMembers.push(this.members[firstParentIdx].reproduceWith( | |
| this.members[secondParentIdx]) | |
| ); | |
| secondParentIdx++; | |
| if (secondParentIdx >= this.members.length) { | |
| firstParentIdx++; | |
| secondParentIdx = firstParentIdx + 1; | |
| } | |
| } | |
| this.members = newMembers; | |
| }; | |
| Population.prototype.live = function () { | |
| for (var i = 0; i < ROUNDS; i++) { | |
| pop.sort(); | |
| pop.select(); | |
| pop.reproduce(); | |
| } | |
| console.log(this.bestGene); | |
| }; | |
| console.log(NUMBERS); | |
| var pop = new Population(); | |
| pop.generate(); | |
| pop.live(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment