1 /** Neuroevolution.
2 
3    See_Also: https://en.wikipedia.org/wiki/Neuroevolution
4 
5    TODO Profile use of cellops and logops in a specific domain or pattern och
6    and use roulette wheel sampling based on these in future patterns.
7 
8    TODO reuse bit_traits.packedBitSizeOf
9 
10    TODO reuse `IndexedBy` `Cells` and `CellIx`
11 */
12 module nxt.nevo;
13 
14 @safe pure:
15 
16 /** Low-Level (Genetic Programming) Operation Network Node Types often implemented
17     in a modern hardware (CPU/GPU).
18 
19     See_Also: http://llvm.org/docs/LangRef.html#typesystem
20     See_Also: http://llvm.org/docs/LangRef.html#instref
21 */
22 enum Lop
23 {
24     summ,                       /// Sum.
25     prod,                       /// Product.
26     emin,                       /// Mininum.
27     emax                        /// Maximum.
28 }
29 
30 /** Obselete.
31 */
32 enum LOPobseleted
33 {
34     id, /**< Identity. */
35 
36     /* \name arithmetical: additive */
37     /* @{ */
38     add,                      /**< add (mi1o) */
39     sub,                      /**< subtract (mi1o) */
40     neg,                      /**< negation (1i1o) */
41     /* @} */
42 
43     /* \name arithmetical: multiplicative */
44     /* @{ */
45     mul,                      /**< multiply (mimo) */
46     div,                      /**< divide (mi1o) */
47     pow,                      /**< power (2i1o) */
48     inv,                      /**< inverse (1i1o) */
49     /* @} */
50 
51     /* \name Harmonic */
52     /* @{ */
53     sin,                      /**< sine (1i1o) */
54     cos,                      /**< cosine (1i1o) */
55     tan,                      /**< tangens (1i1o) */
56 
57     /* \name Inverse Harmonic */
58     csc,                      /**< 1/sin(a) */
59     cot,                      /**< cotangens (1i1o) */
60     sec,                      /**< 1/cos(a) */
61 
62     // Arcus
63     acos,                     /**< arcus cosine (1i1o) */
64     asin,                     /**< arcus sine (1i1o) */
65     atan,                     /**< arcus tanges (1t2i1o) */
66     acot,                     /**< arcus cotangens (1i1o) */
67     acsc,                     /**< arcus css (1i1o) */
68     /* @} */
69 
70     /* \name hyperbolic */
71     /* @{ */
72     cosh, sinh, tanh, coth, csch,
73     acosh, asinh, atanh, acoth, acsch,
74     /* @} */
75 
76     // /* \name imaginary numbers */
77     // /* @{ */
78     // real, imag, conj,
79     // /* @} */
80 
81     /* \name reorganizer/permutators/permutations */
82     /* @{ */
83     identity,                 /**< identity (copy) (1imo) */
84     interleave,               /**< interleave (1imo) */
85     flip,                     /**< flip (1i1o) */
86     mirror,                   /**< mirror (1i1o) */
87     shuffle,                  /**< shuffle (1i1o) */
88     /* @} */
89 
90     /* \name generators */
91     /* @{ */
92     ramp,                     /**< linear ramp (2imo) */
93     zeros,                    /**< zeros (0imo) */
94     ones,                     /**< ones (0imo) */
95     rand,                     /**< ranodm (0imo) */
96     /* @} */
97 
98     /* \name comparison */
99     /* @{ */
100     eq,                       /**< equality (mi1o) */
101     neq,                      /**< non-equality (mi1o) */
102     lt,                       /**< less-than (2i1o) */
103     lte,                      /**< less-than or equal (2i1o) */
104     gt,                       /**< greater-than (2i1o) */
105     gte,                      /**< greater-than or equal (2i1o) */
106     /* @} */
107 
108     /* \name logical */
109     /* @{ */
110     all,                      /**< all (non-zero) (mi1o) */
111     any,                      /**< any (non-zero) (mi1o) */
112     none,                     /**< none (zero) (mi1o) */
113     /* @} */
114 }
115 
116 version(none)
117 {
118 /** Return non-zero if \p lop is an \em Arithmetical \em Additive Operation. */
119 bool isAdd(Lop lop)
120 {
121     return (lop == Lop.add ||
122             lop == Lop.sub ||
123             lop == Lop.neg);
124 }
125 
126 /** Return non-zero if \p lop is an \em Arithmetical \em Additive Operation. */
127 bool isMul(Lop lop)
128 {
129     return (lop == Lop.mul ||
130             lop == Lop.div ||
131             lop == Lop.pow ||
132             lop == Lop.inv);
133 }
134 
135 bool isArithmetic(Lop lop)
136 {
137     return isAdd(lop) && isArithmetic(lop);
138 }
139 
140 /** Return non-zero if \p lop is an \em Trigonometric Operation. */
141 bool isTrigonometric(Lop lop)
142 {
143     return (lop == Lop.cos ||
144             lop == Lop.sin ||
145             lop == Lop.tan ||
146             lop == Lop.cot ||
147             lop == Lop.csc ||
148             lop == Lop.acos ||
149             lop == Lop.asin ||
150             lop == Lop.atan ||
151             lop == Lop.acot ||
152             lop == Lop.acsc
153         );
154 }
155 
156 /** Return non-zero if \p lop is an \em Hyperbolic Operation. */
157 bool isHyperbolic(Lop lop)
158 {
159     return (lop == Lop.cosh ||
160             lop == Lop.sinh ||
161             lop == Lop.tanh ||
162             lop == Lop.coth ||
163             lop == Lop.csch ||
164             lop == Lop.acosh ||
165             lop == Lop.asinh ||
166             lop == Lop.atanh ||
167             lop == Lop.acoth ||
168             lop == Lop.acsch);
169 }
170 
171 /** Return non-zero if \p lop is a \em Generator Operation. */
172 bool isGen(Lop lop)
173 {
174     return (lop == Lop.ramp ||
175             lop == Lop.zeros ||
176             lop == Lop.ones ||
177             lop == Lop.rand);
178 }
179 
180 /** Return non-zero if \p lop is a \em Comparison Operation. */
181 bool isCmp(Lop lop)
182 {
183     return (lop == Lop.eq ||
184             lop == Lop.neq ||
185             lop == Lop.lt ||
186             lop == Lop.lte ||
187             lop == Lop.gt ||
188             lop == Lop.gte);
189 }
190 
191 /** Return non-zero if \p lop is a \em Permutation/Reordering Operation. */
192 bool isPermutation(Lop lop)
193 {
194     return (lop == Lop.identity ||
195             lop == Lop.interleave ||
196             lop == Lop.flip ||
197             lop == Lop.mirror ||
198             lop == Lop.shuffle);
199 }
200 }
201 
202 /// Cell Operation.
203 enum CellOp
204 {
205     seqClone,                   /// sequential clone
206     parClone,                   /// parallel clone
207 }
208 alias CellOps = Owned!(DynamicArray!CellOp); // TODO bit-pack
209 
210 /**m Network (Transformation) Operation Type Code.
211  *
212  * Instructions for a Program that builds \em Computing Networks (for
213  * example Artificial Nerual Networks ANN).
214  *
215  * TODO What does \em nature cell this information bearer: Closest I
216  * have found is http://en.wikipedia.org/wiki/Allele.
217  */
218 enum Gop
219 {
220     /* \name Structural: Inter-Node */
221     /* @{ */
222     seq,                    /**< Sequential Growth. Inherit Initial Value. Set weight to +1. State is \em ON. */
223     par,                    /**< Parallel Growth */
224 
225     clone,                  /**< Clone. Like \c PAR but  */
226     /* @} */
227 
228     /* \name Local: Intra-Node */
229     /* @{ */
230     setLOp,                /**< Set Node Logic Operation (see \c Lop). */
231 
232     setOType, /**< Set Out-Type. Either \c int, \c float or \c double for now. */
233 
234     incBias,               /**< Increase Threshold */
235     decBias,               /**< Decrease Threshold */
236 
237     /* There is \em no need for "in-precision", since these are the same
238        as in-precision the "previous" nodes in the network. */
239     incOpRec,              /**< Increase Out-Precision */
240     decOpRec,              /**< Decrease Out-Precision */
241 
242     incLinkreg,            /**< Increase In-Link-Register */
243     decLinkreg,            /**< Decrease In-Link-Register */
244 
245     on,                     /**< \em Activate Current In-Link. */
246     off,                    /**< \em Deactivate Current In-Link. */
247 
248     /* @} */
249 
250     wait,                   /**< Wait (Delay) one clock-cycle? */
251     rec,                    /**< \em Recurse up to top (decreasing life with one). */
252 
253     jmp,                    /**< \em Jump to sub-Network/Procedure/Function. */
254     def,                    /**< \em Define sub-Network/Procedure/Function. */
255 
256     end,                    /**< \em Recursion Terminator in serialized code (stream of t's). */
257     null_,                   /**< \em Network Terminator in serialized code (stream of t's). */
258 }
259 
260 // wchar
261 // wchar_from_LOP(Lop lop)
262 // {
263 //     wchar_t wc = UNICODE_UNKNOWN;
264 //     switch (lop) {
265 //     case Lop.add: wc = UNICODE_CIRCLED_PLUS; break;
266 //     case Lop.sub: wc = UNICODE_CIRCLED_MINUS; break;
267 //     case Lop.neg: wc = UNICODE_SQUARED_MINUS; break;
268 //     case Lop.mul: wc = UNICODE_CIRCLED_TIMES; break;
269 //     case Lop.div: wc = UNICODE_CIRCLED_DIVISION_SLASH; break;
270 //     case Lop.pow: wc = UNICODE_UNKNOWN; break;
271 //     case Lop.inv: wc = UNICODE_CIRCLED_DIVISION_SLASH; break;
272 //     default: break;
273 //     }
274 //     return wc;
275 // }
276 
277 import std.bitmanip : BitArray;
278 import std.random : Random, uniform;
279 
280 import nxt.dynamic_array : DynamicArray;
281 import nxt.dynamic_array : DynamicArray;
282 
283 import nxt.typecons_ex : IndexedBy;
284 import nxt.owned : Owned;
285 
286 import nxt.variant : FastAlgebraic;
287 
288 alias Data = FastAlgebraic!(long, double);
289 alias Datas = Owned!(DynamicArray!Data);
290 
291 /// Scalar Operation Count.
292 alias OpCount = size_t;
293 
294 /// Relative Cell index.
295 alias CellRIx = ptrdiff_t;
296 
297 /// Relative Cell indexs.
298 alias CellRIxs = Owned!(DynamicArray!CellRIx);
299 
300 /// Calculating Cell.
301 struct Cell
302 {
303     import std.algorithm.iteration : map, filter, fold;
304 
305     @safe pure:
306 
307     this(Lop lop, size_t inputRIxsLength, size_t cellCount)
308     {
309     }
310 
311     /// Randomize a cell.
312     void randomize(Lop lop, size_t inputRIxsLength, size_t cellCount) @trusted
313     {
314         auto gen = Random();
315         this.lop = lop;
316 
317         // TODO use std.algorithm to fill in `inputCellRIxs`
318         inputCellRIxs.length = inputRIxsLength;
319         foreach (ref rix; inputCellRIxs[])
320         {
321             rix = uniform(cast(CellRIx)0, cast(CellRIx)cellCount/10, gen);
322         }
323     }
324 
325     nothrow:
326 
327     OpCount execute(const ref Datas ins, ref Datas outs) const
328     {
329         if (ins.empty) { return typeof(return).init; }
330         final switch (lop)
331         {
332         case Lop.summ: return summ(ins, outs);
333         case Lop.prod: return prod(ins, outs);
334         case Lop.emin: return emin(ins, outs);
335         case Lop.emax: return emax(ins, outs);
336         }
337     }
338 
339     /// Sum of `ins`.
340     OpCount summ(const ref Datas ins, ref Datas outs) const @trusted
341     {
342         import std.algorithm.iteration : sum;
343         outs.length = 1;
344         outs[0] = ins[].filter!(_ => _.hasValue)
345                        .map!(_ => _.commonValue)
346                        .sum();
347         return ins.length - 1;
348     }
349 
350     /// Product of `ins`.
351     OpCount prod(const ref Datas ins, ref Datas outs) const @trusted
352     {
353         outs.length = 1;
354         outs[0] = ins[].filter!(_ => _.hasValue)
355                        .map!(_ => _.commonValue)
356                        .fold!((a, b) => a * b)(cast(Data.CommonType)1.0);
357         return ins.length - 1;
358     }
359 
360     /// Minimum of `ins`.
361     OpCount emin(const ref Datas ins, ref Datas outs) const @trusted
362     {
363         import std.algorithm : minElement;
364         outs.length = 1;
365         outs[0] = ins[].filter!(_ => _.hasValue)
366                        .map!(_ => _.commonValue)
367                        .minElement(+Data.CommonType.max);
368         return ins.length - 1;
369     }
370 
371     /// Maximum of `ins`.
372     OpCount emax(const ref Datas ins, ref Datas outs) const @trusted
373     {
374         import std.algorithm : maxElement;
375         outs.length = 1;
376         outs[0] = ins[].filter!(_ => _.hasValue)
377                        .map!(_ => _.commonValue)
378                        .maxElement(-Data.CommonType.max);
379         return ins.length - 1;
380     }
381 
382     Lop lop;                  /// operation
383     CellRIxs inputCellRIxs;   /// relative indexes to (neighbouring) input cells
384 }
385 alias Cells = IndexedBy!(Owned!(DynamicArray!Cell), `Ix`);
386 
387 /// Network/Graph of `Cells`.
388 struct Network
389 {
390     @safe pure /*TODO nothrow @nogc*/:
391 
392     this(size_t cellCount)
393     {
394         auto gen = Random();
395 
396         cells.reserve(cellCount);
397         temps.reserve(cellCount);
398 
399         foreach (immutable i; 0 .. cellCount)
400         {
401             cells ~= Cell(gen.uniform!Lop, 10, cellCount);
402             temps ~= Data(gen.uniform!long);
403         }
404     }
405 
406     /// One step forward.
407     OpCount step() @trusted
408     {
409         typeof(return) opCount = 0;
410 
411         foreach (immutable i, ref cell; cells)
412         {
413             Datas ins;
414             ins.reserve(cell.inputCellRIxs.length);
415             foreach (immutable rix; cell.inputCellRIxs)
416             {
417                 ins ~= temps[(i + rix) % cells.length]; // relative index
418             }
419 
420             Datas tempOuts;         // data to be filled
421             if (immutable opCount_ = cell.execute(ins, tempOuts))
422             {
423                 opCount += opCount_;
424                 temps[i] = tempOuts[0];
425             }
426         }
427         return opCount;
428     }
429 
430     BitArray pack() nothrow @nogc
431     {
432         typeof(return) bits;
433         return bits;
434     }
435 
436     static typeof(this) unpack(in BitArray bits) nothrow @nogc
437     {
438         typeof(this) that;
439         return that;
440     }
441 
442     Cells cells;                /// operation/function cells
443     Datas temps;                /// temporary outputs from cells
444 }
445 
446 /// Generative Code.
447 struct Code
448 {
449     @safe pure nothrow:
450 
451     CellOps cellOps; // cell operations, an indirect generative network encoding
452     alias cellOps this;
453 
454     Cells.Ix writerIxs;         /// index to writers
455 
456     Network generate() const
457     {
458         typeof(return) network;
459         foreach (immutable cellOp; cellOps[])
460         {
461         }
462         return network;
463     }
464 }
465 
466 unittest
467 {
468     immutable cellCount = 1_000;
469     auto task = Network(cellCount);
470 
471     immutable stepCount = 1_0;
472     foreach (immutable i; 0 .. stepCount)
473     {
474         task.step();
475     }
476 
477     // dbg("DONE");
478 }