This release is 133 versions behind 0.167.6 — the latest version of @stsoftware/neat-ai. Jump to latest
@stsoftware/neat-ai@0.121.0Built and signed on GitHub ActionsBuilt and signed on GitHub Actions
Built and signed on GitHub Actions
NEAT Neural Network. This project is a unique implementation of a neural network based on the NEAT (NeuroEvolution of Augmenting Topologies) algorithm, written in DenoJS using TypeScript.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545import { assert } from "jsr:/@std/assert@^1.0.8/assert"; import { yellow } from "jsr:/@std/fmt@^1.0.3/colors"; import { format } from "jsr:/@std/fmt@^1.0.3/duration"; import { emptyDirSync } from "jsr:@std/fs@^1.0.6"; import { addTag, getTag, removeTag, type TagInterface } from "jsr:@stsoftware/tags@^1.0.5"; import { CreatureUtil, Mutation } from "../mod.ts"; import type { CreatureExport, CreatureInternal, CreatureTrace, } from "./architecture/CreatureInterfaces.ts"; import { CreatureState, type NeuronStateInterface, } from "./architecture/CreatureState.ts"; import { creatureValidate } from "./architecture/CreatureValidate.ts"; import { type DataRecordInterface, makeDataDir, } from "./architecture/DataSet.ts"; import { Neuron } from "./architecture/Neuron.ts"; import type { NeuronExport, NeuronInternal, NeuronTrace, } from "./architecture/NeuronInterfaces.ts"; import { Synapse } from "./architecture/Synapse.ts"; import type { SynapseExport, SynapseInternal, SynapseTrace, } from "./architecture/SynapseInterfaces.ts"; import { dataFiles } from "./architecture/Training.ts"; import type { MemeticInterface } from "./blackbox/MemeticInterface.ts"; import { removeHiddenNeuron } from "./compact/CompactUtils.ts"; import { createNeatConfig } from "./config/NeatConfig.ts"; import type { NeatOptions } from "./config/NeatOptions.ts"; import type { CostInterface } from "./Costs.ts"; import { Activations } from "./methods/activations/Activations.ts"; import { IDENTITY } from "./methods/activations/types/IDENTITY.ts"; import { LOGISTIC } from "./methods/activations/types/LOGISTIC.ts"; import { WorkerHandler } from "./multithreading/workers/WorkerHandler.ts"; import { AddBackCon } from "./mutate/AddBackCon.ts"; import { AddConnection } from "./mutate/AddConnection.ts"; import { AddNeuron } from "./mutate/AddNeuron.ts"; import { AddSelfCon } from "./mutate/AddSelfCon.ts"; import { ModActivation } from "./mutate/ModActivation.ts"; import { ModBias } from "./mutate/ModBias.ts"; import { ModWeight } from "./mutate/ModWeight.ts"; import type { RadioactiveInterface } from "./mutate/RadioactiveInterface.ts"; import { SubBackCon } from "./mutate/SubBackCon.ts"; import { SubConnection } from "./mutate/SubConnection.ts"; import { SubNeuron } from "./mutate/SubNeuron.ts"; import { SubSelfCon } from "./mutate/SubSelfCon.ts"; import { SwapNeurons } from "./mutate/SwapNeurons.ts"; import type { Approach } from "./NEAT/LogApproach.ts"; import { Neat } from "./NEAT/Neat.ts"; import type { BackPropagationConfig } from "./propagate/BackPropagation.ts"; import type { SparseConfig } from "./propagate/sparse/SparseConfig.ts"; /** * Creature Class * * The Creature class represents an AI entity within the NEAT (NeuroEvolution of Augmenting Topologies) framework. * It encapsulates the neural network structure and its associated behaviors, including activation, mutation, * propagation, and evolution processes. This class is integral to the simulation and evolution of neural networks. */ export class Creature implements CreatureInternal { /** * The unique identifier of this creature. * @type {string | undefined} */ uuid?: string; /** * The number of input neurons. * @type {number} */ input: number; /** * The number of output neurons. * @type {number} */ output: number; /** * The array of neurons within this creature. * @type {Neuron[]} */ neurons: Neuron[]; /** * Optional tags associated with the creature. * @type {TagInterface[] | undefined} */ tags?: TagInterface[]; /** * The score of the creature, used for evaluating fitness. * @type {number | undefined} */ score?: number; /** * The array of synapses (connections) between neurons. * @type {Synapse[]} */ synapses: Synapse[]; /** Records the origins of this creature. */ memetic?: MemeticInterface; /** * The state of the creature, managing the internal state and activations. * @type {CreatureState} */ readonly state: CreatureState = new CreatureState(this); private cacheTo = new Map<number, Synapse[]>(); private cacheFrom = new Map<number, Synapse[]>(); private cacheSelf = new Map<number, Synapse[]>(); private cacheFocus: Map<number, boolean> = new Map(); /** * Debug mode flag. * @type {boolean} */ DEBUG: boolean = ((globalThis as unknown) as { DEBUG: boolean }).DEBUG; /** * Constructs a new Creature instance. * * @param {number} input - The number of input neurons. * @param {number} output - The number of output neurons. * @param {Object} [options] - Configuration options for initializing the creature. * @param {boolean} [options.lazyInitialization=false] - If true, the creature will not be initialized immediately. * @param {Object[]} [options.layers] - Optional layers configuration. */ constructor( input: number, output: number, options: { lazyInitialization?: boolean; layers?: { squash?: string; count: number }[]; } = {}, ) { this.input = input; this.output = output; this.neurons = []; this.synapses = []; this.tags = undefined; this.score = undefined; if (!options.lazyInitialization) { this.initialize(options); if (this.DEBUG) { creatureValidate(this); } } } /** * Dispose of the creature and all held memory. */ public dispose() { this.clearState(); this.clearCache(); this.synapses.length = 0; this.neurons.length = 0; } /** * Clear the cache of connections. * * @param {number} [from=-1] - The starting index of the cache to clear. * @param {number} [to=-1] - The ending index of the cache to clear. */ public clearCache(from: number = -1, to: number = -1) { if (from == -1 || to == -1) { this.cacheTo.clear(); this.cacheFrom.clear(); this.cacheSelf.clear(); } else { this.cacheTo.delete(to); this.cacheFrom.delete(from); this.cacheSelf.delete(from); } this.cacheFocus.clear(); } private initialize(options: { layers?: { squash?: string; count: number }[]; }) { let fixNeeded = false; // Create input neurons for (let i = this.input; i--;) { const type = "input"; const neuron = new Neuron(`input-${this.input - i - 1}`, type, 0, this); neuron.index = this.neurons.length; this.neurons.push(neuron); } if (options.layers) { let lastStartIndx = 0; let lastEndIndx = this.neurons.length - 1; for (let i = 0; i < options.layers.length; i++) { const layer = options.layers[i]; for (let j = 0; j < layer.count; j++) { let tmpSquash = layer.squash ? layer.squash : LOGISTIC.NAME; if (tmpSquash == "*") { tmpSquash = Activations .NAMES[Math.floor(Activations.NAMES.length * Math.random())]; fixNeeded = true; } const neuron = new Neuron( crypto.randomUUID(), "hidden", undefined, this, tmpSquash, ); neuron.index = this.neurons.length; this.neurons.push(neuron); } const tmpOutput = this.output; this.output = 0; for (let k = lastStartIndx; k <= lastEndIndx; k++) { for (let l = lastEndIndx + 1; l < this.neurons.length; l++) { this.connect(k, l, Synapse.randomWeight()); } } this.output = tmpOutput; lastStartIndx = lastEndIndx + 1; lastEndIndx = this.neurons.length - 1; } // Create output neurons for (let indx = 0; indx < this.output; indx++) { const type = "output"; const neuron = new Neuron( `output-${indx}`, type, undefined, this, LOGISTIC.NAME, ); neuron.index = this.neurons.length; this.neurons.push(neuron); } for (let k = lastStartIndx; k <= lastEndIndx; k++) { for (let l = lastEndIndx + 1; l < this.neurons.length; l++) { this.connect(k, l, Synapse.randomWeight()); } } } else { // Create output neurons for (let indx = 0; indx < this.output; indx++) { const type = "output"; const neuron = new Neuron( `output-${indx}`, type, undefined, this, LOGISTIC.NAME, ); neuron.index = this.neurons.length; this.neurons.push(neuron); } // Connect input neurons with output neurons directly for (let i = 0; i < this.input; i++) { for (let j = this.input; j < this.output + this.input; j++) { /** https://stats.stackexchange.com/a/248040/147931 */ const weight = Math.random() * this.input * Math.sqrt(2 / this.input); this.connect(i, j, weight); } } } if (fixNeeded) { this.fix(); } } /** * Clear the context of the creature. */ clearState() { this.score = undefined; this.state.clear(); } /** * Activates the creature and traces the activity. * * @param {Float32Array} input - The input values for the creature. * @param {boolean} feedbackLoop - Whether to use a feedback loop during activation. * @returns {number[]} The output values after activation. */ activateAndTrace( input: Float32Array, feedbackLoop: boolean, sparseConfig: SparseConfig, ): number[] { const output: number[] = new Array(this.output); this.state.makeActivation(input, feedbackLoop); const lastHiddenNode = this.neurons.length - this.output; // Activate hidden neurons for (let i = this.input; i < lastHiddenNode; i++) { const n = this.neurons[i]; if (sparseConfig.traceNeeded(n.uuid)) { n.activateAndTrace(); } else { n.activate(); } } // Activate output neurons and store their values in the output array for (let outIndx = 0; outIndx < this.output; outIndx++) { const n = this.neurons[lastHiddenNode + outIndx]; if (sparseConfig.traceNeeded(n.uuid)) { output[outIndx] = n.activateAndTrace(); } else { output[outIndx] = n.activate(); } } return output; } /** * Activates the creature without calculating traces. * * @param {number[]} input - The input values for the creature. * @param {boolean} [feedbackLoop=false] - Whether to use a feedback loop during activation. * @returns {number[]} The output values after activation. */ activate(input: Float32Array, feedbackLoop: boolean = false): Float32Array { const output: Float32Array = new Float32Array(this.output); this.state.makeActivation(input, feedbackLoop); const lastHiddenNode = this.neurons.length - this.output; // Activate hidden neurons for (let i = this.input; i < lastHiddenNode; i++) { this.neurons[i].activate(); } // Activate output neurons and store their values in the output array for (let outIndx = 0; outIndx < this.output; outIndx++) { output[outIndx] = this.neurons[lastHiddenNode + outIndx].activate(); } return output; } /** * Compact the creature by removing redundant neurons and connections. * * @returns {Creature | undefined} A new compacted creature or undefined if no compaction occurred. */ compact(): Creature | undefined { const holdDebug = this.DEBUG; this.DEBUG = false; const json = this.exportJSON(); this.DEBUG = holdDebug; const compactCreature = Creature.fromJSON(json); compactCreature.fix(); let complete = false; for (let changes = 0; complete == false; changes++) { complete = true; for ( let pos = compactCreature.input; pos < compactCreature.neurons.length - compactCreature.output; pos++ ) { const fromList = compactCreature.outwardConnections(pos).filter( (c: SynapseInternal) => { return c.from !== c.to; }, ); if (fromList.length == 0) { removeHiddenNeuron(compactCreature, pos); complete = false; } else { const toList = compactCreature.inwardConnections(pos).filter( (c: SynapseInternal) => { return c.from !== c.to; }, ); if (toList.length == 1) { const fromList = compactCreature.outwardConnections(pos).filter( (c: SynapseInternal) => { return c.from !== c.to; }, ); if (fromList.length == 1) { const to = fromList[0].to; const from = toList[0].from; const fromSquash = compactCreature.neurons[from].squash; if ( from > this.input && fromSquash == compactCreature.neurons[pos].squash && (fromSquash == IDENTITY.NAME || fromSquash == LOGISTIC.NAME) ) { if (compactCreature.getSynapse(from, to) == null) { const weightA = fromList[0].weight * toList[0].weight; assert(Number.isFinite(weightA), "weightA is not finite"); const tmpFromBias = compactCreature.neurons[from].bias; const tmpToBias = compactCreature.neurons[pos].bias; const biasA = tmpFromBias * toList[0].weight + tmpToBias; assert(Number.isFinite(biasA), "biasA is not finite"); compactCreature.neurons[from].bias = biasA; removeHiddenNeuron(compactCreature, pos); let adjustedTo = to; if (adjustedTo > pos) { adjustedTo--; } compactCreature.connect( from, adjustedTo, weightA, fromList[0].type, ); if (changes < 12) { complete = false; } break; } } } } } } } const json2 = compactCreature.exportJSON(); if (JSON.stringify(json) != JSON.stringify(json2)) { addTag(compactCreature, "approach", "compact" as Approach); delete compactCreature.memetic; removeTag(compactCreature, "approach-logged"); addTag(compactCreature, "old-neurons", this.neurons.length.toString()); addTag( compactCreature, "old-synapses", this.synapses.length.toString(), ); return compactCreature; } else { return undefined; } } /** * Validate the creature structure. */ validate() { creatureValidate(this); } /** * Get a self-connection for the neuron at the given index. * * @param {number} indx - The index of the neuron. * @returns {SynapseInternal | null} The self-connection or null if not found. */ selfConnection(indx: number): SynapseInternal | null { let results = this.cacheSelf.get(indx); if (results === undefined) { results = []; const tmpList = this.synapses; for (let i = tmpList.length; i--;) { const c = tmpList[i]; if (c.to === indx && c.from == indx) { results.push(c); } } this.cacheSelf.set(indx, results); } if (results.length > 0) { return results[0]; } else { return null; } } /** * Get the inward connections (afferent) for the neuron at the given index. * * @param {number} toIndx - The index of the target neuron. * @returns {Synapse[]} The list of inward connections. */ inwardConnections(toIndx: number): Synapse[] { let results = this.cacheTo.get(toIndx); if (results === undefined) { results = []; for (let i = this.synapses.length; i--;) { const c = this.synapses[i]; if (c.to === toIndx) results.push(c); } this.cacheTo.set(toIndx, results); } return results; } /** * Get the outward connections (efferent) for the neuron at the given index. * * @param {number} fromIndx - The index of the source neuron. * @returns {Synapse[]} The list of outward connections. */ outwardConnections(fromIndx: number): Synapse[] { let results = this.cacheFrom.get(fromIndx); if (results === undefined) { const startIndex = this.binarySearchForStartIndex(fromIndx); if (startIndex !== -1) { results = []; for (let i = startIndex; i < this.synapses.length; i++) { const tmp = this.synapses[i]; if (tmp.from === fromIndx) { results.push(tmp); } else { break; // Since it's sorted, no need to continue once 'from' changes } } } else { results = []; // No connections found } this.cacheFrom.set(fromIndx, results); } return results; } private binarySearchForStartIndex(fromIndx: number): number { let low = 0; let high = this.synapses.length - 1; let result = -1; // Default to -1 if not found while (low <= high) { const mid = Math.floor((low + high) / 2); const midValue = this.synapses[mid]; if (midValue.from < fromIndx) { low = mid + 1; } else if (midValue.from > fromIndx) { high = mid - 1; } else { result = mid; // Found a matching 'from', but need the first occurrence high = mid - 1; // Look left to find the first match } } return result; } /** * Get a specific synapse between two neurons. * * @param {number} from - The index of the source neuron. * @param {number} to - The index of the target neuron. * @returns {Synapse | null} The synapse or null if not found. */ getSynapse(from: number, to: number): Synapse | null { const outwardConnections = this.outwardConnections(from); for (let indx = outwardConnections.length; indx--;) { const c = outwardConnections[indx]; if (c.to == to) { return c; } else if (c.to < to) { break; } } return null; } /** * Connect two neurons with a synapse. * * @param {number} from - The index of the source neuron. * @param {number} to - The index of the target neuron. * @param {number} weight - The weight of the synapse. * @param {string} [type] - The type of the synapse. * @returns {Synapse} The created synapse. */ connect( from: number, to: number, weight: number, type?: "positive" | "negative" | "condition", ): Synapse { const connection = new Synapse( from, to, weight, type, ); let location = -1; for (let indx = this.synapses.length; indx--;) { const c = this.synapses[indx]; if (c.from < from) { location = indx + 1; break; } else if (c.from === from) { assert(c.to !== to, "Connection already exists"); /* assert(c.to !== to, `Connection already exists from ${this.neurons[from].ID()} to ${this.neurons[to].ID()}`); */ if (c.to < to) { location = indx + 1; break; } else { location = indx; } } else { location = indx; } } if (location !== -1 && location < this.synapses.length) { const left = this.synapses.slice(0, location); const right = this.synapses.slice(location); this.synapses = [...left, connection, ...right]; } else { this.synapses.push(connection); } this.clearCache(from, to); return connection; } /** * Disconnect two neurons by removing the synapse between them. * * @param {number} from - The index of the source neuron. * @param {number} to - The index of the target neuron. */ disconnect(from: number, to: number) { const connections = this.synapses; for (let i = 0; i < connections.length; i++) { const connection = connections[i]; if (connection.from === from && connection.to === to) { connections.splice(i, 1); this.clearCache(from, to); break; } } } /** * Apply learnings to the creature using back propagation. * * @param {BackPropagationConfig} config - The back propagation configuration. * @returns {boolean} True if the creature was changed, false otherwise. */ applyLearnings( config: BackPropagationConfig, sparseConfig: SparseConfig, ): boolean { this.propagateUpdate(config, sparseConfig); let changed = false; for (let indx = this.neurons.length - 1; indx >= this.input; indx--) { if (config.trainingMutationRate > Math.random()) { const n = this.neurons[indx]; if (sparseConfig.updateNeeded(n.uuid)) { changed ||= n.applyLearnings(); } } } if (changed) { delete this.uuid; delete this.memetic; this.fix(); } return changed; } /** * Propagate the expected values through the creature's network. * * @param {Float32Array} expected - The expected output values. * @param {BackPropagationConfig} config - The back propagation configuration. */ propagate( expected: Float32Array, config: BackPropagationConfig, sparseConfig: SparseConfig, ) { this.state.cacheAdjustedActivation.clear(); const indices = Int32Array.from({ length: this.output }, (_, i) => i); // Create an array of indices if (!config.disableRandomSamples) { CreatureUtil.shuffle(indices); } const lastOutputIndx = this.neurons.length - this.output; for (let i = this.output; i--;) { const expectedIndex = indices[i]; const nodeIndex = lastOutputIndx + expectedIndex; const n = this.neurons[nodeIndex]; if (sparseConfig.propagateNeeded(n.uuid)) { n.propagate( expected[expectedIndex], config, sparseConfig, ); } } } /** * Update the propagated values in the creature's network. * * @param {BackPropagationConfig} config - The back propagation configuration. */ propagateUpdate(config: BackPropagationConfig, sparseConfig: SparseConfig) { // @TODO randomize the order of the neurons for (let indx = this.neurons.length - 1; indx >= this.input; indx--) { const n = this.neurons[indx]; if (sparseConfig.updateNeeded(n.uuid)) { n.propagateUpdate(config); } } } /** * Evolve the creature to achieve a lower error on a dataset. * * @param {string} dataSetDir - The directory containing the dataset. * @param {NeatOptions} options - The NEAT configuration options. * @returns {Promise<{ error: number; score: number; time: number }>} The evolution result. */ async evolveDir( dataSetDir: string, options: NeatOptions, ): Promise< { error: number; score: number; time: number; generation: number } > { const start = Date.now(); const config = createNeatConfig(options); const endTimeMS = config.timeoutMinutes ? start + Math.max(1, config.timeoutMinutes) * 60000 : 0; const workers: WorkerHandler[] = []; const threads = config.threads; for (let i = threads; i--;) { workers.push( new WorkerHandler(dataSetDir, config.costName, threads == 1), ); } // Initialize the NEAT instance const neat = new Neat( this.input, this.output, config, workers, ); neat.populatePopulation(this); let error = Infinity; let bestScore = -Infinity; let bestCreature: Creature | undefined; let iterationStartMS = Date.now(); let generation = 0; const targetError = config.targetError; const iterations = config.iterations; while (true) { const result = await neat.evolve( bestCreature, ); const fittest: Creature = result.fittest; const fittestScore = fittest.score!; assert(fittestScore >= bestScore, "Score is less than best score"); if (fittestScore > bestScore) { const errorTmp = getTag(fittest, "error"); assert(errorTmp, "No error tag found"); error = Number.parseFloat(errorTmp); assert(Number.isFinite(error), "Error is not finite"); assert(error >= 0, "Error is negative"); assert(fittestScore <= error * -1, "Score (absolute) less than error"); bestScore = fittestScore; bestCreature = Creature.fromJSON(fittest.exportJSON()); bestCreature.uuid = fittest.uuid; bestCreature.score = bestScore; } const now = Date.now(); const timedOut = endTimeMS ? now > endTimeMS : false; generation++; const completed = timedOut || error <= targetError || generation >= iterations; if ( config.log && (generation % config.log === 0 || completed) ) { let avgTxt = ""; if (Number.isFinite(result.averageScore)) { avgTxt = `(avg: ${yellow(result.averageScore.toFixed(4))})`; } console.log( "Generation", generation, "score", fittest.score, avgTxt, "error", error, (config.log > 1 ? "avg " : "") + "time", yellow( format(Math.round((now - iterationStartMS) / config.log), { ignoreZero: true, }), ), ); iterationStartMS = now; } if (completed) { if (neat.finishUp()) { break; } } } for (let i = workers.length; i--;) { const w = workers[i]; w.terminate(); } workers.length = 0; // Release the memory. if (bestCreature) { this.loadFrom(bestCreature, config.debug ?? false); } if (config.creatureStore) { this.writeCreatures(neat, config.creatureStore); } return { error: error, score: bestScore, generation: generation, time: Date.now() - start, }; } /** * Evolve the creature to achieve a lower error on a dataset. * * @param {DataRecordInterface[]} dataSet - The dataset for evolution. * @param {NeatOptions} options - The NEAT configuration options. * @returns {Promise<{ error: number; score: number; time: number }>} The evolution result. */ async evolveDataSet( dataSet: DataRecordInterface[], options: NeatOptions, ): Promise<{ error: number; score: number; time: number }> { const config = createNeatConfig(options); const dataSetDir = makeDataDir(dataSet, config.dataSetPartitionBreak); const result = await this.evolveDir(dataSetDir, config); Deno.removeSync(dataSetDir, { recursive: true }); return result; } /** * Evaluate a dataset and return the error. * * @param {string} dataDir - The directory containing the dataset. * @param {CostInterface} cost - The cost function to evaluate the error. * @param {boolean} feedbackLoop - Whether to use a feedback loop during evaluation. * @returns {{ error: number }} The evaluation result. */ evaluateDir( dataDir: string, cost: CostInterface, feedbackLoop: boolean, ): { error: number } { const dataResult = dataFiles(dataDir); assert(dataResult.files.length > 0, "No data files found"); let error = 0; let count = 0; const valuesCount = this.input + this.output; const BYTES_PER_RECORD = valuesCount * 4; // Each float is 4 bytes const SSD_OPTIMAL_READ_SIZE = 128 * 1024; // 128 KB const BATCH_SIZE = Math.max( 1, Math.floor(SSD_OPTIMAL_READ_SIZE / BYTES_PER_RECORD), ); const BYTES_PER_BATCH = BYTES_PER_RECORD * BATCH_SIZE; // Shared buffers for batch processing const batchBuffer = new Uint8Array(BYTES_PER_BATCH); const batchArray = new Float32Array(batchBuffer.buffer); for (let fileIndx = dataResult.files.length; fileIndx--;) { const filePath = dataResult.files[fileIndx]; const file = Deno.openSync(filePath, { read: true }); try { while (true) { // Read a batch of records const bytesRead = file.readSync(batchBuffer); if (bytesRead === null || bytesRead === 0) { break; } const recordsRead = Math.floor(bytesRead / BYTES_PER_RECORD); assert( bytesRead % BYTES_PER_RECORD === 0, "Invalid number of bytes read", ); // Process each record in the batch for (let recordIndex = 0; recordIndex < recordsRead; recordIndex++) { const offset = recordIndex * valuesCount; const inputEnd = offset + this.input; const observations = batchArray.subarray( offset, inputEnd, ); const actual = this.activate(observations, feedbackLoop); const target = batchArray.subarray( inputEnd, offset + valuesCount, ); error += cost.calculate(target, actual); count++; } } } finally { file.close(); } } return { error: error / count }; } private writeCreatures(neat: Neat, dir: string) { let counter = 1; emptyDirSync(dir); neat.population.forEach((creature) => { const json = creature.exportJSON(); const txt = JSON.stringify(json, null, 1); const filePath = dir + "/" + counter + ".json"; Deno.writeTextFileSync(filePath, txt); counter++; }); } /** * Check if a neuron is in focus. * * @param {number} index - The index of the neuron. * @param {number[]} [focusList] - The list of focus indices. * @param {Set<number>} [checked] - The set of checked indices. * @returns {boolean} True if the neuron is in focus, false otherwise. */ public inFocus( index: number, focusList?: number[], checked: Set<number> = new Set(), ): boolean { if (!focusList || focusList.length == 0) { return true; } // Check the cache first if there is a focus list if (this.cacheFocus.has(index)) { return this.cacheFocus.get(index) as boolean; } if (checked.has(index)) { this.cacheFocus.set(index, false); return false; } checked.add(index); for (let pos = 0; pos < focusList.length; pos++) { const focusIndex = focusList[pos]; if (index == focusIndex) { this.cacheFocus.set(index, true); return true; } const toList = this.inwardConnections(index); for (let i = toList.length; i--;) { const checkIndx: number = toList[i].from; if (checkIndx === index) { this.cacheFocus.set(index, true); return true; } if (this.inFocus(checkIndx, focusList, checked)) { this.cacheFocus.set(index, true); return true; } } } this.cacheFocus.set(index, false); return false; } /** * Create a random connection for the neuron at the given index. * * @param {number} indx - The index of the target neuron. * @returns {Synapse | null} The created synapse or null if no connection was made. */ public makeRandomConnection(indx: number): Synapse | null { const toType = this.neurons[indx].type; assert(toType !== "input", "Can't connect to input"); assert(toType !== "constant", "Can't connect to constant"); for (let attempts = 0; attempts < 12; attempts++) { const from = Math.min( this.neurons.length - this.output - 1, Math.floor(Math.random() * indx + 1), ); const c = this.getSynapse(from, indx); if (c === null) { return this.connect( from, indx, Synapse.randomWeight(), ); } } const firstOutputIndex = this.neurons.length - this.output; for (let from = 0; from <= indx; from++) { if (from >= firstOutputIndex && from !== indx) continue; const c = this.getSynapse(from, indx); if (c === null) { return this.connect( from, indx, Synapse.randomWeight(), ); } } return null; } /** * Mutate the creature using a specific method. * * @param {Object} method - The mutation method. * @param {string} method.name - The name of the mutation method. * @param {number[]} [focusList] - The list of focus indices. */ mutate(method: { name: string }, focusList?: number[]): boolean { assert(method.name, "Mutate name is required"); let mutator: RadioactiveInterface | undefined; switch (method.name) { case Mutation.ADD_NODE.name: mutator = new AddNeuron(this); break; case Mutation.SUB_NODE.name: mutator = new SubNeuron(this); break; case Mutation.ADD_CONN.name: mutator = new AddConnection(this); break; case Mutation.SUB_CONN.name: mutator = new SubConnection(this); break; case Mutation.MOD_WEIGHT.name: mutator = new ModWeight(this); break; case Mutation.MOD_BIAS.name: mutator = new ModBias(this); break; case Mutation.MOD_ACTIVATION.name: mutator = new ModActivation(this); break; case Mutation.ADD_SELF_CONN.name: mutator = new AddSelfCon(this); break; case Mutation.SUB_SELF_CONN.name: mutator = new SubSelfCon(this); break; case Mutation.ADD_BACK_CONN.name: mutator = new AddBackCon(this); break; case Mutation.SUB_BACK_CONN.name: mutator = new SubBackCon(this); break; case Mutation.SWAP_NODES.name: mutator = new SwapNeurons(this); break; default: { throw new Error("unknown: " + method); } } let changed = false; changed = mutator.mutate(focusList); if (!changed && (!focusList || focusList.length == 0)) { console.info( `${method.name} didn't mutate the creature. ${this.input} observations, ${ this.neurons.length - this.input - this.output } neurons, ${this.output} outputs, ${this.synapses.length} synapses`, ); } delete this.uuid; this.fix(); if (this.DEBUG) { creatureValidate(this); } return changed; } /** * Fix the structure of the creature. */ fix() { const holdDebug = this.DEBUG; this.DEBUG = false; const startTxt = JSON.stringify(this.internalJSON()); this.DEBUG = holdDebug; const maxTo = this.neurons.length - 1; const minTo = this.input; const tmpSynapses: Synapse[] = []; this.synapses.forEach((synapse) => { if (synapse.to > maxTo) { console.debug("Ignoring connection to above max", maxTo, synapse); } else if (synapse.to < minTo) { console.debug("Ignoring connection to below min", minTo, synapse); } else if (synapse.weight && Number.isFinite(synapse.weight)) { /** Zero weight may as well be removed */ tmpSynapses.push(synapse as Synapse); } else { if (this.neurons[synapse.to].type == "output") { /** Don't remove the last one for an output neuron */ if (this.inwardConnections(synapse.to).length == 1) { tmpSynapses.push(synapse as Synapse); } } } }); this.synapses = tmpSynapses; /* Make sure the synapses are sorted */ this.synapses.sort((a, b) => { if (a.from === b.from) { return a.to - b.to; } else { return a.from - b.from; } }); this.clearCache(); let neuronRemoved = true; while (neuronRemoved) { neuronRemoved = false; for ( let pos = this.input; pos < this.neurons.length - this.output; pos++ ) { if (this.neurons[pos].type == "output") continue; if ( this.outwardConnections(pos).filter((c) => { return c.from !== c.to; }).length == 0 ) { removeHiddenNeuron(this, pos); neuronRemoved = true; break; } } } this.neurons.forEach((node) => { node.fix(); }); const tmpDebug = this.DEBUG; this.DEBUG = false; const endTxt = JSON.stringify(this.internalJSON()); this.DEBUG = tmpDebug; if (startTxt != endTxt) { delete this.memetic; delete this.uuid; } } /** * Get the output count of the creature. * * @returns {number} The number of output neurons. */ outputCount(): number { return this.output; } /** * Get the node count of the creature. * * @returns {number} The number of neurons. */ nodeCount(): number { return this.neurons.length; } /** * Convert the creature to a JSON object. * * @returns {CreatureExport} The JSON representation of the creature. */ exportJSON(): CreatureExport { if (this.DEBUG) { creatureValidate(this); } const json: CreatureExport = { neurons: new Array<NeuronExport>( this.neurons.length - this.input, ), synapses: new Array<SynapseExport>(this.synapses.length), input: this.input, output: this.output, tags: this.tags ? this.tags.slice() : undefined, }; const uuidMap = new Map<number, string>(); for (let i = this.neurons.length; i--;) { const neuron = this.neurons[i]; uuidMap.set(i, neuron.uuid ?? `unknown-${i}`); if (neuron.type == "input") continue; const tojson = neuron.exportJSON(); json.neurons[i - this.input] = tojson; } for (let i = this.synapses.length; i--;) { const exportJSON = this.synapses[i].exportJSON( uuidMap, ); json.synapses[i] = exportJSON; } if (this.memetic) { json.memetic = JSON.parse(JSON.stringify(this.memetic)); } return json; } /** * Convert the creature to a trace JSON object. * * @returns {CreatureTrace} The trace JSON representation of the creature. */ traceJSON(): CreatureTrace { const json = this.exportJSON(); const traceNeurons = Array<NeuronTrace>(json.neurons.length); let exportIndex = 0; this.neurons.forEach((n) => { if (n.type !== "input") { const indx = n.index; const traceNeuron: NeuronExport = json .neurons[exportIndex] as NeuronTrace; if (n.type !== "constant") { const ns = this.state.node(indx); if (ns.count) { (traceNeuron as NeuronTrace).trace = ns; } } traceNeurons[exportIndex] = traceNeuron as NeuronTrace; exportIndex++; } }); json.neurons = traceNeurons; const traceConnections = Array<SynapseTrace>(json.synapses.length); this.synapses.forEach((c, indx) => { const exportConnection = json.synapses[indx] as SynapseTrace; const cs = this.state.connection(c.from, c.to); if (cs.count) { exportConnection.trace = cs; } traceConnections[indx] = exportConnection; }); json.synapses = traceConnections; if (this.memetic) { json.memetic = JSON.parse(JSON.stringify(this.memetic)); } return json as CreatureTrace; } /** * Convert the creature to an internal JSON object. * * @returns {CreatureInternal} The internal JSON representation of the creature. */ internalJSON(): CreatureInternal { if (this.DEBUG) { creatureValidate(this); } const json: CreatureInternal = { uuid: this.uuid, neurons: new Array<NeuronInternal>( this.neurons.length - this.input, ), synapses: new Array<SynapseInternal>(this.synapses.length), input: this.input, output: this.output, tags: this.tags ? this.tags.slice() : undefined, }; for (let i = this.neurons.length; i--;) { const neuron = this.neurons[i]; if (neuron.type == "input") continue; const tojson = neuron.internalJSON(i); json.neurons[i - this.input] = tojson; } for (let i = this.synapses.length; i--;) { const internalJSON = this.synapses[i].internalJSON(); json.synapses[i] = internalJSON; } if (this.memetic) { json.memetic = JSON.parse(JSON.stringify(this.memetic)); } return json; } /** * Load the creature from a JSON object. * * @param {CreatureInternal | CreatureExport} json - The JSON object representing the creature. * @param {boolean} validate - Whether to validate the creature after loading. */ loadFrom(json: CreatureInternal | CreatureExport, validate: boolean) { this.uuid = (json as CreatureInternal).uuid; this.neurons.length = json.neurons.length; if (json.tags) { this.tags = [...json.tags]; } this.clearState(); const uuidMap = new Map<string, number>(); this.neurons = new Array(this.neurons.length); for (let i = json.input; i--;) { const key = `input-${i}`; uuidMap.set(key, i); const n = new Neuron(key, "input", undefined, this); n.index = i; this.neurons[i] = n; } let pos = json.input; let outputIndx = 0; const neurons = json.neurons; for (let i = 0; i < neurons.length; i++) { const jn = neurons[i]; if (jn.type === "input") continue; if (jn.type == "output") { jn.uuid = `output-${outputIndx}`; outputIndx++; } const n = Neuron.fromJSON(jn, this); n.index = pos; if ((jn as NeuronTrace).trace) { const trace: NeuronStateInterface = (jn as NeuronTrace).trace; const ns = this.state.node(n.index); Object.assign(ns, trace); } uuidMap.set(n.uuid, pos); this.neurons[pos] = n; pos++; } this.synapses.length = 0; const cLen = json.synapses.length; const synapses = json.synapses; for (let i = 0; i < cLen; i++) { const synapse = synapses[i]; const se = synapse as SynapseExport; const from = se.fromUUID ? uuidMap.get(se.fromUUID) : (synapse as SynapseInternal).from; assert(from !== undefined, "FROM is undefined"); const to = se.toUUID ? uuidMap.get(se.toUUID) : (synapse as SynapseInternal).to; assert(to !== undefined, "TO is undefined"); const connection = this.connect( from, to, synapse.weight, synapse.type, ); if (synapse.tags) { connection.tags = synapse.tags.slice(); } if ((synapse as SynapseTrace).trace) { const cs = this.state.connection(connection.from, connection.to); const trace = (synapse as SynapseTrace).trace; Object.assign(cs, trace); } } this.memetic = json.memetic; this.clearCache(); if (validate) { creatureValidate(this); } } /** * Convert a json object to a creature */ static fromJSON( json: CreatureInternal | CreatureExport, validate = false, ): Creature { const creature = new Creature(json.input, json.output, { lazyInitialization: true, }); const legacy = (json as unknown) as { nodes?: []; neurons?: []; connections?: []; synapses?: []; }; if (legacy.nodes) { legacy.neurons = legacy.nodes; delete legacy.nodes; } if (legacy.connections) { legacy.synapses = legacy.connections; delete legacy.connections; } creature.loadFrom(json, validate); return creature; } }